Distributed genetic algorithms for function optimization.

The genetic algorithm is a general purpose, population-based search algorithm in which the individuals in the population represent samples from the set of all possibilities, whether they are solutions in a problem space, strategies for a game, rules in classifier systems, or arguments for problems in function optimization. The individuals evolve over time to form even better individuals by sharing and mixing their information about the space. This dissertation proposes a parallelized version of a genetic algorithm called the distributed genetic algorithm, which can achieve near-linear speedup over the traditional version of the algorithm. This algorithm divides the large population into many equal-sized small subpopulations and runs the genetic algorithm on each subpopulation independently. Each subpopulation periodically selects some individuals and exchanges them with other subpopulations; the process known as migration. The functions used to evaluate the performance of the distributed genetic algorithm and the traditional algorithm are called Walsh polynomials, which are based on Walsh functions. Walsh polynomials can be categorized into classes of functions with each class having a different degree of difficulty. By generating a large number of instances of the various classes, the performance difference between the distributed and traditional genetic algorithms can be analyzed statistically. The first part of this dissertation examines the partitioned genetic algorithm, a version of the distributed genetic algorithm with no migration. The experiments on four different classes of Walsh polynomials show that the partitioned algorithm consistently outperforms the traditional algorithm as a function optimizer. This is because the physical subdivision of the population will allow each subpopulation to explore the space independently. Also, good individuals are more likely to be recognized in a smaller subpopulation than they would be in a large, diverse population. The second part of this research examines the effects of migration on the performance of the distributed genetic algorithm. The experiments show that with a moderate migration rate the distributed genetic algorithm finds better individuals than the traditional algorithm while maintaining a high overall fitness of the population. Finally, this dissertation also discusses the issue of balancing exploration against exploitation in the distributed genetic algorithm, by allowing different subpopulations to run with different parameters, so that some subpopulations can emphasize exploration while others emphasize exploitation. The distributed algorithm is shown to be more robust than the traditional version: even when each subpopulation runs with different combinations of crossover and mutation rates, the distributed algorithm performs better than the traditional one.PhDComputer scienceUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/162372/1/9001722.pd