Solving multi-structured problems by introducing linkage kernels into GOMEA

Genetic and Evolutionary Computation Conference (GECCO), pp. 703–711

Abstract

Model-Based Evolutionary Algorithms (MBEAs) can be highly scalable by virtue of linkage (or variable interaction) learning. This requires, however, that the linkage model can capture the exploitable structure of a problem. Usually, a single type of linkage structure is attempted to be captured using models such as a linkage tree. However, in practice, problems may exhibit multiple linkage structures. This is for instance the case in multi-objective optimization when the objectives have different linkage structures. This cannot be modelled sufficiently well when using linkage models that aim at capturing a single type of linkage structure, deteriorating the advantages brought by MBEAs. Therefore, here, we introduce linkage kernels, whereby a linkage structure is learned for each solution over its local neighborhood. We implement linkage kernels into the MBEA known as GOMEA that was previously found to be highly scalable when solving various problems. We further introduce a novel benchmark function called Best-of-Traps (BoT) that has an adjustable degree of different linkage structures. On both BoT and a worst-case scenario-based variant of the well-known MaxCut problem, we experimentally find a vast performance improvement of linkage-kernel GOMEA over GOMEA with a single linkage tree as well as the MBEA known as DSMGA-II.

Authors 4

1. Arthur Guijt

   Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

2. Dirk Thierens

   Utrecht University

   Affiliation as printed

   Utrecht University, Utrecht, The Netherlands

3. Tanja Alderliesten Aachen

   Leiden University Medical Center

   Affiliation as printed

   Leiden University Medical Center, Leiden, The Netherlands

4. Peter A. N. Bosman

   Delft University of Technology

   Affiliation as printed

   Delft University of Technology, Delft, The Netherlands