Distributed genetic algorithms

Abstract

The objective of this thesis is to study distributed genetic algorithms and to use a few experiments to see how distribution affects the performance of the algorithm. Genetic algorithms can be distributed by either doing the evaluations concurrently or by distributing the population into sub-populations, so that different genetic algorithm processes can handle different sub-populations concurrently. The sub-populations communicate with each other periodically to exchange information about their best solutions. In this thesis we adopt the latter method. In our implementation, the processes working on the sub-populations are connected in a ring. Each processor sends its best solution to the process on the right and gets a best solution from the process on the left. We use a transportation problem and a staff scheduling problem for our experiments. For the transportation problem, the results show that increasing the size of the population improves the performance of the genetic algorithm. But the time the algorithm takes to complete a run also increases. We found that distributing the population into sub-populations improves the performance of the genetic algorithm without making it slower. In fact, the algorithm with the more distributed populations arrive at a better solution than the less distributed ones. The next set of experiments are on the migration parameters: migration rate which determines the proportion of the solution exchanged between processes, and migration interval which determines the number of generations between every exchange. Our results show that the average solution fitness improves with increasing number of solutions exchanged. Also, a more frequent exchange improves the quality of the final solution arrived at. For the scheduling problem, distribution did not improve the performance of the genetic algorithm. We experimented with 2, 3, 4, and 5 sub-populations of size 20 each. In each of the cases, the performance of the distributed algorithm was similar to the performance of the undistributed algorithm with population size 20, and did not match the performance of the corresponding bigger populations.