Niching an estimation-of-distribution algorithm by hierarchical Gaussian mixture learning
Estimation-of-Distribution Algorithms (EDAs) have been applied with quite some success when solving real-valued optimization problems, especially in the case of Black Box Optimization (BBO). Generally, the performance of an EDA depends on the match between its driving probability distribution and the landscape of the problem being solved. Because most well-known EDAs, including CMA-ES, NES, and AMaLGaM, use a uni-modal search distribution, they have a high risk of getting trapped in local optima when a problem is multi-modal with a (moderate) number of relatively comparable modes. This risk could potentially be mitigated using niching methods that define multiple regions of interest where separate search distributions govern sub-populations. However, a key question is how to determine a suitable number of niches, especially in BBO. In this paper, we present a novel, adaptive niching approach that determines the niches through hierarchical clustering based on the correlation between the probability densities and fitness values of solutions. We test the performance of a combination of this niching approach with AMaLGaM on both new and well-known niching benchmark problems and ind that the new approach properly identifies multiple landscape modes, leading to much beter performance on multi-modal problems than with a non-niched, uni-modal EDA.
|Keywords||Black box, Continuous optimization, Estimation of distribution algorithm, Gaussian mixture model, Hierarchical clustering|
|Project||ICT based Innovations in the Battle against Cancer – Next - Generation Patient -Tailored Brachytherapy Cancer Treatment Planning|
|Conference||Genetic and Evolutionary Computation Conference|
|Grant||This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/628.006.003 - ICT based Innovations in the Battle against Cancer – Next - Generation Patient -Tailored Brachytherapy Cancer Treatment Planning|
Maree, S.C, Alderliesten, T, Thierens, D, & Bosman, P.A.N. (2017). Niching an estimation-of-distribution algorithm by hierarchical Gaussian mixture learning. In GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference (pp. 713–720). doi:10.1145/3071178.3071283