Performance and effectiveness of Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm on Tree Decomposition Mk Landscapes

Abstract

Whitley et al. recently introduced Mk Landscapes and Tree Decomposition (TD) Mk Landscapes, which are generalizations of NK Landscapes and Adjacent NK Landscapes, respectively. TD Mk Landscapes are convenient for benchmarking optimization algorithms, as the global optimum can be found in polynomial time using the problem structure, but could be difficult to find for a black-box optimization algorithm. Contrary to Whitley et al., who tested gray box algorithms (algorithms with problem structure knowledge), we test a black box linkage learning (LL) algorithm, namely Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm (LT-GOMEA), on TD Mk Landscapes. We test the performance and effectiveness of LT-GOMEA on various subclasses of TD Mk Landscapes with specific codomain and topological properties, and use the results to quantify the effects of certain subclasses and landscape features. In particular, we are interested in the effects of an increase of overlap between the cliques in the clique tree (= TD) and an increase in the branching factor of the clique tree, on TD Mk Landscapes with the deceptive trap codomain. To generate the TD Mk Landscapes for our experiments, we use the recently introduced CliqueTreeMk algorithm by Thierens et al. Interestingly, our results show that the performance and effectiveness of LT-GOMEA does not solely decrease with increasing overlap on the deceptive trap codomain. Instead, the performance and effectiveness decrease prior to increasing. Furthermore, our results indicate that both the overlap and branching increase the interference between the subfunctions, possibly leading to decreased deceptiveness and decreased importance of learning the (exact) linkage. Finally, the branching factor of the clique tree has a great effect on the number of global optima of the TD Mk Landscape and should therefore be further researched. In conclusion, our results suggest that the TD Mk Landscapes is a promising and convenient benchmark for black box genetic algorithms.