An Examination of Hypercube Implementations of Genetic Algorithms
AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING
Pagination or Media Count:
Genetic algorithms are stochastic search algorithms which model natural adaptive systems. In support of the development of a genetic search package for AFITs iPSC2 Hypercube, this study focused on two problem areas associated with hypercube implementations. Premature convergence occurs when the population becomes dominated by locally optimal, but globally inferior, solutions. Based on an examination of past hypercube implementations, the selection and communication strategies were hypothesized as causes of premature convergence. Experiments to test these hypotheses were conducted on Rosenbrocks saddle, a function often associated with premature convergence. Communication of best solutions led to premature convergence in small population sizes, but increased the likelihood of finding the global optimal in large population sizes. Genetic algorithms using global selection were more robust than those using local selection. GA-hard problems are intrinsically difficult for standard genetic algorithms. Messy genetic algorithms are effective against GA-hard problems. The second part of this study added a parallel version of a messy genetic algorithm to the genetic algorithm package. Against a sample GA-hard problem, the parallel implementation achieved a linear speedup of the sequential bottleneck while still finding the global optimal. The messy genetic algorithm should be applied to problems of practical importance. Genetic algorithms, Hypercube.
- Operations Research
- Computer Programming and Software