More Concise and Robust Linkage Learning by Filtering and Combining Linkage Hierarchies

Exploiting a problem’s structure to arrive at the most efficient optimization algorithm is key in many optimization disciplines. In evolutionary computation, especially for solving discrete optimization problems from a black-box optimization (BBO) perspective, linkage learning is an important research line because if important linkages are disrupted during variation, optimization will not proceed efficiently [4]. Estimation-of-distribution algorithms (EDAs) are well-k nown for building and using models to exploit problem structure [2, 3]. Models in EDAs represent probability distributions and linkage information is processed via probabilistic dependency relations within these distributions. Although EDAs can be very powerful, estimating complete distributions might be more than what is required to respect important linkage relations. Here, we therefore consider the class of Genepool Optimal Mixing Evolutionary Algorithms (GOMEAs) as they exploit linkage information by integrating greedy local search, genetic recombination and fitness-based selection [1] based on linkage models, which can typically be learned more efficiently. Recent results indicate that the use of hierarchical linkage models in GOMEAs leads to the best performance [1]. There are, arguably, however still potential ine fficiencies. In this paper, we consider ways to filter these out. We further consider a way to combine the strengths of different linkage models.