A modified genetic algorithm for a special case of the generalized assignment problem

Authors : Murat Dörterler, Ömer Faruk Bay, Mehmet Ali Akcayol

Pages : 794-805

View : 21 | Download : 6

Publication Date : 9999-12-31

Article Type : Makaleler

Abstract :Many central examinations are performed nationwide in Turkey. These examinations are held simultaneously throughout Turkey. Examinees attempt to arrive at the examination centers at the same time and they encounter problems such as traffic congestion, especially in metropolises. The state of mind that this situation puts them into negatively affects the achievement and future goals of the test takers. Our solution to minimize the negative effects of this issue is to assign the test takers to closest examination centers taking into account the capacities of examination halls nearby. This solution is a special case of the generalized assignment problem (GAP). Since the scale of the problem is quite large, we have focused on heuristic methods. In this study, a modified genetic algorithm (GA) is used for the solution of the problem since the classical GA often generates infeasible solutions when it is applied to GAPs. A new method, named nucleotide exchange, is designed in place of the crossover method. The designed method is run between the genes of a single parent chromosome. In addition to the randomness, the consciousness factor is taken into consideration in the mutation process. With this new GA method, results are obtained successfully and quickly in large-sized data sets.
Keywords : Genetic algorithm, optimization, generalized assignment problem