Linkage Neighbors, Optimal Mixing and Forced Improvements in Genetic Algorithms

Recently, the Linkage Tree Genetic Algorithm (LTGA) was introduced as one of the latest developments in a line of EA research that studies building models to capture and exploit linkage information between problem variables. LTGA was reported to exhibit excellent performance on several linkage benchmark problems, mainly attributed to use of the LT linkage model. In this paper we consider a technique called Forced Improvements (FI), that allows LTGA to converge to a single solution without requiring an explicit, diversity-reducing, selection step. We further consider a different linkage model, called Linkage Neighbors (LN), that is more flexible, yet can be learned equally efficiently from data. Even with the simplest learning approach for configuring the LN, better results are obtained on the linkage benchmark problems than when the LT model is used However, on weighted MAXCUT (a combinatorial optimization problem), very poor results are obtained and a more involved multiscale LN variant is required to obtain a performance near that of LTGA. Our results underline the advantage of processing linkage in a single model on multiple scales as well as the importance of also considering problems other problems than common linkage benchmark problems when judging the merits of linkage learning techniques.