Linkage Tree Genetic Algorithms: Variants and Analysis
Abstract
Discovering and exploiting the linkage between genes during evolutionary search allows the Linkage Tree Genetic Algorithm (LTGA) to maximize crossover effectiveness, greatly reducing both population size and total number of evaluations required to reach success on decomposable problems. This paper presents a comparative analysis of the most prominent LTGA variants and a newly introduced variant. While the deceptive trap problem (Trap-k) is one of the canonical benchmarks for testing LTGA, when LTGA is combined with applying steepest ascent hill climbing to the initial population, as is done in all significant LTGA variations, trap-k is trivially solved. This paper introduces the deceptive step trap problem (StepTrap-k,s), which shows the novel combination of smallest first subtree ordering with global mixing (LTS-GOMEA) is effective for black box optimization, while least linked first subtree ordering (LT-GOMEA) is effective on problems where partial reevaluation is possible. Finally, nearest neighbor NK landscapes show that global mixing is not effective on problems with complex overlapping linkage structure that cannot be modeled correctly by a linkage tree, emphasizing the need to extend how LTGA stores linkage to allow the power of global mixing to be applied to these types of problems.
Recommended Citation
B. W. Goldman and D. R. Tauritz, "Linkage Tree Genetic Algorithms: Variants and Analysis," Proceedings of the 2013 Genetic and Evolutionary Computation Conference Companion (GECCO 2012), pp. 625 - 632, Association for Computing Machinery (ACM), Jan 2012.
The definitive version is available at https://doi.org/10.1145/2330163.2330252
Meeting Name
14th International Conference on Genetic and Evolutionary Computation, GECCO'12 (2012: Jul. 7-11, Philadelphia, PA)
Department(s)
Computer Science
Sponsor(s)
Missouri University of Science and Technology. Natural Computation Laboratory
Keywords and Phrases
Deceptive Step Trap; Deceptive Trap; Linkage Learning; LTGA; Nearest Neighbor NK Landscapes; Optimal Mixing
International Standard Book Number (ISBN)
978-1450311779
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2012 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
01 Jan 2012
