Real-Valued Evolutionary Multi-Modal Optimization driven by Hill-Valley Clustering
This work addresses the challenge of unknown multi-modality in black-box optimization for researchers and practitioners in evolutionary computation, representing an incremental improvement over existing niching methods.
The paper tackles the problem of multi-modal optimization in evolutionary algorithms by introducing Hill-Valley Clustering to adaptively cluster the search space into niches, each containing a single mode, and shows that the resulting HillVallEA is competitive with state-of-the-art methods on a standard benchmark, with superior performance in the long run.
Model-based evolutionary algorithms (EAs) adapt an underlying search model to features of the problem at hand, such as the linkage between problem variables. The performance of EAs often deteriorates as multiple modes in the fitness landscape are modelled with a unimodal search model. The number of modes is however often unknown a priori, especially in a black-box setting, which complicates adaptation of the search model. In this work, we focus on models that can adapt to the multi-modality of the fitness landscape. Specifically, we introduce Hill-Valley Clustering, a remarkably simple approach to adaptively cluster the search space in niches, such that a single mode resides in each niche. In each of the located niches, a core search algorithm is initialized to optimize that niche. Combined with an EA and a restart scheme, the resulting Hill-Valley EA (HillVallEA) is compared to current state-of-the-art niching methods on a standard benchmark suite for multi-modal optimization. Numerical results in terms of the detected number of global optima show that, in spite of its simplicity, HillVallEA is competitive within the limited budget of the benchmark suite, and shows superior performance in the long run.