Genetic Algorithm for Game Scheduling Problem of NBA
Date Issued
2016
Date
2016
Author(s)
Wei, Kang-Yi
Abstract
NBA Scheduling Problem is a particular game scheduling problem. The purpose of the problem is to generate a reasonable schedule by following basic information and restrictions from the league. The goal is to reduce Traveling Length Total by satisfying all hard constraints, and also decrease the statistic of soft constraints. This work construct NBA benchmarks from recent official information, then use genetic algorithm to solve it, finally, compare the results to official schedule. Encoding scheme uses game sequencing as format. Due to this format, this work develop a method to generate initial populations to avoid arranging same game on near position. The method reduce the number of infeasible solutions which have excessive season length after decoding scheme. Besides, to reduce traveling distance, the algorithm use distance between two games as game cost, and design a heuristic mutation method to improve the team schedule which has highest game cost. After define mathematical functions of the problem, we develop a genetic algorithm-based software to test three benchmarks: 2012-2013, 2013-2014, and 2014-2015. Moreover, this work compare the results with official schedule. The results show that this algorithm can not only reduce traveling distance effectively, but also decrease the statistic of two soft constraints: Back-to-back Games Count Total and Four-games-in-five Count Total.
Subjects
Sport Scheduling
Genetic Algorithm
National Basketball Association
Type
thesis