Recreating the Dream Team using the Genetic Algorithm
Authors — Pratik P S , Nicolas Brown (AI Skunks)
Problem statement
The United States is home to the world’s premier men’s professional basketball league the National Basketball Association(NBA), one of North America’s major professional sports leagues. Of many, one of these popular teams is the Los Angeles Lakers. The Lakers are planning on creating a team to outperform the “1971–72 team” by buying some of the best players in the league this season to win the championship. They want to do so by getting the players they are eyeing based on player rating and budget. The Lakers analytics team is trying to find a way to get the best combination of player-to-budget ratio such that they get sign-and-trade deals to maximize the overall pick rating with the current budget of 105k.
We shall use The Genetic algorithm to solve this problem.
What if I told you, you could simulate evolution?
Yes, you heard it right. The Genetic Algorithm does exactly that. GA uses natural selection to approximate solutions to a given problem. It is part of the Family of Evolutionary Algorithms. GA generates solutions to problems there are no solutions. It works on the underlying principles of Genetic Mutation.
What is a Genetic Algorithm?
The genetic algorithm chooses members of the existing population to serve as parents and uses them to produce the offspring that will make up the following generation. The population “evolves” toward the best option over the course of subsequent generations.
There are 4 steps to the GA
- Initiation
- Fitness selection
- Crossover
- Mutation
This flow chart outlines the steps to the algorithm:
Algorithm
“x” is the fraction of the population to be replaced by a crossover in each iteration. “n” is the number of samples in the population and “e” is the number of evolutions.
Implementation
Major Functions used :
1. Team Generator: Generates teams with randomness from the given option of players
2. Team Combinations Generator: Creates a list of teams of a particular size, in this case, the number of teams generated per population batch is 10.
3. Fitness Function: A function to check the overall team pricing and value is calculated and the team is discarded if the value is above the weight limit ie. 105
4. Cross-Over Function: Cross combines a pair of parent teams to generate a pair of off-springs, based on a cross-over point.
5. Mutation Function: Inverts a single bit from 1->0 or 0->1 based on the probability value
Note — Players in the team list are represented by 1s and 0s. The inclusion of a particular player is indicated by 1 and 0 otherwise.
6. Run — Evolution Function — the master function that calls the rest of the function with a limit of 100 evolution and a Minimum rating of 29. if a team with a value below the fitness limit is found. the 2 fittest parents moved to the next generation rest of the fraction of the population is Mutated and crossed over to produce new offspring for the next generation. and the Cycle repeats till a winner is found or a limit is reached.
Results
The resultant team consists of Steph Curry, Kevin Durant, Anthony Davis, and Zach LaVine with an Overall pick rating of 29.
Time taken
the Genetic algorithm outperforms the brute-force approach by executing faster.
link to the code- https://github.com/Pratik-Prakash-Sannakki/NBA_LakersDramTeam_SuperPicks
Conclusion
The algorithm is not deterministic, it does not give the same result every time we run the algorithm. But with more generated solutions per generation, we will ultimately reach a result that is “close enough” if not the “best solution”
Larger selection
With larger values to select from, the brute force takes an exorbitant amount of time and GA will remain efficient with low time complexity as cited by — Svogor, Ivan & Crnkovic, Ivica & Vrcek, Neven. (2013). Multi-criteria software component allocation on a heterogeneous platform. Proceedings of the International Conference on Information Technology Interfaces, ITI. 341–346. 10.2498/iti.2013.0558.- https://www.researchgate.net/publication/261306247_Multi-criteria_software_component_allocation_on_a_heterogeneous_platform
Local Maxima Problem
As the Genetic algorithm explores various generations to find the best-fit solution/ Close to the best-fit solution and does not stop at its first over-the-fitness limit value it does not face the local maxima problem.
References
- Code references — https://github.com/kiecodes/genetic-algorithms
- Basics of Genetic Algorithm by MatLab-https://www.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
