Generalization and Parallelization of Messy Genetic Algorithms and Communication in Parallel Genetic Algorithms.
Abstract
Genetic algorithms (GA) are highly parallelizable, robust semi- optimization algorithms of polynomial complexity. The most commonly implemented GAs are 'simple' GAs (SGAs). Reproduction, crossover, and mutation operate on solution populations. Deceptive and GA-hard problems are provably difficult for simple GAs. Messy GAs (MGA) are designed to overcome these limitations. The MGA is generalized to solve permutation type optimization problems. Its performance is compared to another MGA's, an SGA's, and a permutation SGA's. Against a fully deceptive problem the generalized MGA (GMGA) consistently performs better than the simple GA. Against an NP-complete permutation problem, the GMGA performs better than the other GAs. Against DeJong function f2, the GMGA performs better than the other MGA, but not as well as the SGA. Four parallel MGA data distribution strategies are compared and not found to significantly affect solution quality. The interleaved strategy obtains near linear speedup. The indexed, modified indexed, and block strategies obtain 'super-linear speedup,' indicating that the sequential algorithm can be improved. Population partitioning impacts implementation of selection and crossover. Experiments which compare the solution quality, execution time, and convergence characteristics of three selection algorithms and three solution sharing strategies are performed.... Parallel processing, Genetic algorithms, Optimization.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1992
- Accession Number
- ADA258994
Entities
People
- Laurence D. Merkle
Organizations
- Air Force Institute of Technology