TY - CHAP
T1 - Two-Phase Real-Valued Multimodal Optimization with the Hill-Valley Evolutionary Algorithm
AU - Maree, S. C.
AU - Thierens, D.
AU - Alderliesten, T.
AU - Bosman, P. A. N.
N1 - Funding Information: Acknowledgements This work is part of the research programme IPPSI-TA with project number 628.006.003, which is financed by the Netherlands Organization for Scientific Research (NWO) and Elekta. We also acknowledge financial support of the Nijbakker-Morra Foundation for a high-performance computing system. Publisher Copyright: © 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - The aim of multimodal optimization (MMO) is to obtain all global optima of an optimization problem. In this chapter, we introduce a general framework for two-phase MMO evolutionary algorithms (EAs), in which different high-fitness regions (niches) are located in the first phase via clustering, and each of the located niches is separately optimized with a core search algorithm in the second phase. One such two-phase MMO EA is the Hill-Valley Evolutionary Algorithm (HillVall-EA). In HillVallEA, the remarkably simple hill-valley clustering method is used. The idea behind hill-valley clustering is that two solutions belong to the same niche (valley) when there is no hill in between them, which can be easily tested by performing additional function evaluations. We compare hill-valley clustering to two other recently introduced fitness-informed clustering methods: nearest-better clustering and hierarchical Gaussian mixture learning. We show how these clustering methods, as well as different core search algorithms, influence the resulting optimization performance of the two-phase MMO framework on the commonly used CEC 2013 niching benchmark suite. Our results show that HillVallEA, equipped with the core search algorithm Adapted Maximum-Likelihood Gaussian Model Univariate (AMu) as core search algorithm, outperforms all other MMO EAs, both within the limited benchmark budget, and in the long run. HillVallEA-AMu was the winner of the GECCO niching competition in 2018 and 2019, and is currently, to the best of our knowledge, the best performing algorithm on this benchmark suite.
AB - The aim of multimodal optimization (MMO) is to obtain all global optima of an optimization problem. In this chapter, we introduce a general framework for two-phase MMO evolutionary algorithms (EAs), in which different high-fitness regions (niches) are located in the first phase via clustering, and each of the located niches is separately optimized with a core search algorithm in the second phase. One such two-phase MMO EA is the Hill-Valley Evolutionary Algorithm (HillVall-EA). In HillVallEA, the remarkably simple hill-valley clustering method is used. The idea behind hill-valley clustering is that two solutions belong to the same niche (valley) when there is no hill in between them, which can be easily tested by performing additional function evaluations. We compare hill-valley clustering to two other recently introduced fitness-informed clustering methods: nearest-better clustering and hierarchical Gaussian mixture learning. We show how these clustering methods, as well as different core search algorithms, influence the resulting optimization performance of the two-phase MMO framework on the commonly used CEC 2013 niching benchmark suite. Our results show that HillVallEA, equipped with the core search algorithm Adapted Maximum-Likelihood Gaussian Model Univariate (AMu) as core search algorithm, outperforms all other MMO EAs, both within the limited benchmark budget, and in the long run. HillVallEA-AMu was the winner of the GECCO niching competition in 2018 and 2019, and is currently, to the best of our knowledge, the best performing algorithm on this benchmark suite.
UR - http://www.scopus.com/inward/record.url?scp=85117919802&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/978-3-030-79553-5_8
DO - https://doi.org/10.1007/978-3-030-79553-5_8
M3 - Chapter
T3 - Natural Computing Series
SP - 165
EP - 189
BT - Natural Computing Series
PB - Springer Science and Business Media Deutschland GmbH
ER -