Examination of Hypercube Implementations of Genetic Algorithms.

摘要

Genetic algorithms are stochastic search algorithms which model natural adaptive systems. In support of the development of a genetic search package for AFIT's iPSC/2 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 Rosenbrock's 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.