Journal of Experimental & Theoretical Artificial Intelligence · 1990 · 185 citations · 16 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningOptimizationCrossover OperatorsEvolutionary ComputationEvolutionary OptimizationGenetic AlgorithmsMetaheuristic OptimizationPopulation-based SearchAffine TransformationsEvolutionary AlgorithmsEvolutionary SearchFailure ModesGenetic Algorithm OptimizationPermutationsRepresentation In Evolutionary AlgorithmsTransformations
Abstract Functions are partially characterized as easy or hard for genetic algorithms to optimize. The failure modes of inappropriate embedding, crossover disruption, and deceptiveness are introduced, analyzed, and resolved in part. Virtually all optimizable (by any method) real valued functions defined on a finite domain are shown to be theoretically easy for genetic algorithms given appropriately chosen representations. Unfortunately, problems that are easy in theory can be difficult in practice because of sampling error. Also, the transformations required to induce favorable representations are generally arbitrary permutations, and the space of permutations is so large that search for good ones is intractable. The space of inversions is amenable to search, but inversions are insufficiently powerful to overcome deceptiveness. On the other hand, affine transformations (over the diadic group) are shown to be sufficiently powerful to transform at least selected deceptive problems into easy ones. These new results should be useful in guiding empirical studies and are expected to provide a foundation for further theoretical analysis.
16
Genetic algorithms in search, optimization, and machine learning
Choice Reviews Online · 1989 · 49.3K citations
From dissertation abstracts international
ACM SIGGRAPH Computer Graphics · 1974 · 12.2K citations
Messy genetic algorithms: motivation, analysis, and first results
David E. Goldberg, Bradley Korb, Kalyanmoy Deb · Complex Systems · 1989 · 1.1K citations
Computing, Genetics, Algorithms +11