More Efficient Real-Valued Gray-Box Optimization through Incremental Distribution Estimation in RV-GOMEA

Genetic and Evolutionary Computation Conference (GECCO), pp. 755–763

Abstract

The Gene-pool Optimal Mixing EA (GOMEA) family of EAs offers a specific means to exploit problem-specific knowledge through linkage learning, i.e., inter-variable dependency detection, expressed using subsets of variables, that should undergo joint variation. Such knowledge can be exploited if faster fitness evaluations are possible when only a few variables are changed in a solution, enabling large speed-ups. The recent-most version of Real-Valued GOMEA (RV-GOMEA) can learn a conditional linkage model during optimization using fitness-based linkage learning, enabling fine-grained dependency exploitation in learning and sampling a Gaussian distribution. However, while the most efficient Gaussian-based EAs, like NES and CMA-ES, employ incremental learning of the Gaussian distribution rather than performing full re-estimation every generation, the recent-most RV-GOMEA version does not employ such incremental learning. In this paper, we therefore study whether incremental distribution estimation can lead to efficiency enhancements of RV-GOMEA. We consider various benchmark problems with varying degrees of overlapping dependencies. We find that, compared to RV-GOMEA and VKD-CMA-ES, the required number of evaluations to reach high-quality solutions can be reduced by a factor of up to 1.5 if population sizes are tuned problem-specifically, while a reduction by a factor of 2–3 can be achieved with generic population-sizing guidelines.

Authors 3

1. Renzo J. Scholman

   Delft University of Technology · Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands

   Delft University of Technology, Delft, Netherlands

2. Tanja Alderliesten Aachen

   Leiden University · Leiden University Medical Center

   Affiliation as printed

   Leiden University Medical Centre, Leiden, Netherlands

3. Peter A. N. Bosman

   Delft University of Technology · Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands

   Delft University of Technology, Delft, Netherlands