Linkage Tree Genetic Algorithms: Variants and Analysis


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.

Meeting Name

14th International Conference on Genetic and Evolutionary Computation, GECCO'12 (2012: Jul. 7-11, Philadelphia, PA)


Computer Science


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)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2012 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 Jan 2012