TY - GEN
T1 - Real-valued evolutionary multi-modal optimization driven by hill-valley clustering
AU - Maree, S. C.
AU - Thierens, D.
AU - Alderliesten, T.
AU - Bosman, P. A. N.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85050639989&origin=inward
U2 - https://doi.org/10.1145/3205455.3205477
DO - https://doi.org/10.1145/3205455.3205477
M3 - Conference contribution
T3 - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
SP - 857
EP - 864
BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
PB - Association for Computing Machinery, Inc
T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018
Y2 - 15 July 2018 through 19 July 2018
ER -