Analyzing the Performance of the Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm on Tree Decomposition Mk Landscapes using Local Optima Networks

Abstract

Abstract This thesis analyses the performance of Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm (LT-GOMEA) on Tree Decomposition Mk Landscapes for problems generated by the benchmark function CliqueTreeMk introduced by Thierens et al. [16]. To understand the challenges faced by LT-GOMEA on these landscapes, the search process is visualized using Local Optima Networks (LONs) introduced by Ochoa et al. [13]. Problems are generated in both a random and deceptive-trap codomain, and the input parameters for CliqueTreeMk are varied to create problems with different characteristics. The main parameter being varied is the overlap between subfunctions, and the number of subfunctions increases as well to maintain a constant problem length. Two implementations of LT-GOMEA are tested: the standard population-based version and a non-population-based version in which the building blocks are learned from a hill-climbed population. For population-based LT-GOMEA, the performance for both codomains increased prior to decreasing with an increase in overlap, but the deceptive-trap codomain performed better at higher overlap. This is thought to be due to a lower number of local optima (than for the random codomain) and decreased deceptiveness with an increase in overlap. The non-population based LT-GOMEA had similar results for the deceptivetrap codomain, but performed poorly on the random codomain with overlap higher than 0, suggesting that an evolving population is necessary to utilize the linkage learning of LT-GOMEA. We also discovered that the intended deceptiveness of the deceptive-trap codomain decreases with overlap, and this could also contribute to the increase in global optima for the deceptive-trap neutral codomain. The findings about the challenges faced by LT-GOMEA are supported by analyzing the search process through the use of LONs. The LONs reveal that problems generated with the same input parameters can vary significantly in difficulty, and gaining a deeper understanding of the reasons behind this variance could improve the effectiveness of CliqueTreeMk as a benchmark function, by being able to more precisely estimate the difficulty of the generated problems.