Avoiding Redundant Restarts in Multimodal Global Optimization

arXiv (Cornell University)

Abstract

Naïve restarts of global optimization solvers when operating on multimodal search landscapes may resemble the Coupon's Collector Problem, with a potential to waste significant function evaluations budget on revisiting the same basins of attractions. In this paper, we assess the degree to which such ``duplicate restarts'' occur on standard multimodal benchmark functions, which defines the \textit{redundancy potential} of each particular landscape. We then propose a repelling mechanism to avoid such wasted restarts with the CMA-ES and investigate its efficacy on test cases with high redundancy potential compared to the standard restart mechanism.

Authors 5

1. Jacob de Nobel Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

2. Diederick Vermetten Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

3. Anna V. Kononova Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

4. Ofer M. Shir

   Tel Hai Academic College

   Affiliation as printed

   Tel-Hai College and Migal Institute , Upper Galilee , Israel

5. Thomas Bäck