An initial analysis of data parallelism in the fast messy genetic algorithm
Larry D. Merkle, Gary B. Lamont · 1994
Genetic algorithms (GAs) are highly parallelizable algorithms, inspired by Darwiniaa theories of evolution and survival of the fittest, which are used most frequently as function optimizers.The messy GA [4, 5, 6] makes use of partially enumerative initialization (PEI) and tournament selection, with competitions restricted to similar individuals.Consequently, efficient parallelization of the messy GA demands consideration of data distribution [12].The fast messy GA replaces PEI with Probabilistically Complete Initialization (PCI) and building block filtering, and increases the threshold for similarity determinations [7].Two algorithmic design approaches to parallelization of the fast messy GA are presented.One uses independent subpopulations throughout the execution, while the other uses recombines subpopulations following the primordial phase.Execution times are examined theoretically and experimentally against a fully deceptive function.Experiments are performed on an Intel Paragon parallel supercomputer.