Fitness-based Linkage Learning and Maximum-Clique Conditional Linkage Modelling for Gray-box Optimization with RV-GOMEA

Genetic and Evolutionary Computation Conference (GECCO), pp. 647–655

Abstract

For many real-world optimization problems it is possible to perform partial evaluations, meaning that the impact of changing a few variables on a solution's fitness can be computed very efficiently. It has been shown that such partial evaluations can be excellently leveraged by the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) that uses a linkage model to capture dependencies between problem variables. Recently, conditional linkage models were introduced for RV-GOMEA, expanding its state-of-the-art performance even to problems with overlapping dependencies. However, that work assumed that the dependency structure is known a priori. Fitness-based linkage learning techniques have previously been used to detect dependencies during optimization, but only for non-conditional linkage models. In this work, we combine fitness-based linkage learning and conditional linkage modelling in RV-GOMEA. In addition, we propose a new way to model overlapping dependencies in conditional linkage models to maximize the joint sampling of fully interdependent groups of variables. We compare the resulting novel variant of RV-GOMEA to other variants of RV-GOMEA and VkD-CMA on 12 problems with varying degree of overlapping dependencies. We find that the new RV-GOMEA not only performs best on most problems, also the overhead of learning the conditional linkage models during optimization is often negligible.

Authors 3

1. Georgios Andreadis Aachen Department of Radiation Oncology

   Leiden University Medical Center

   Affiliation as printed

   Department of Radiation Oncology, Leiden University Medical Center, Leiden, Zuid-Holland, Netherlands

2. Tanja Alderliesten Aachen Department of Radiation Oncology

   Leiden University Medical Center

   Affiliation as printed

   Department of Radiation Oncology, Leiden University Medical Center, Leiden, Zuid-Holland, Netherlands

3. Peter A. N. Bosman

   Delft University of Technology · Centrum Wiskunde & Informatica

   Affiliation as printed

   Algorithmics Section, Delft University of Technology, Delft, Zuid-Holland, Netherlands

   Evolutionary Intelligence Group, Centrum Wiskunde & Informatica (CWI), Amsterdam, Noord-Holland, Netherlands