Abstract
Non-elitist evolutionary algorithms (EAs) can be beneficial in optimisation of noisy and or rugged fitness landscapes. However, this benefit can only be realised if the parameters of the non-elitist EAs are carefully adjusted in accordance with the fitness function. Self-adaptation is a promising parameter adaptation method that encodes and evolves parameters in the chromosome. Existing self-adaptive EAs often sort the population by first preferring higher fitness and then the mutation rate. A previous study (Case and Lehre, 2020) proved that self-adaptation can be effective in certain discrete problems with unknown structure. However, the population can be trapped on local optima, because individuals in “dense” fitness valleys which survive high mutation rates and individuals on “sparse” local optima which only survive with lower mutation rates cannot be simultaneously preserved.
Recently, the Multi-Objective Self-Adaptive EA (MOSA-EA) (Lehre and Qin, 2022) was proposed to optimise single-objective functions, treating parameter control via multi-objectivisation. The algorithm maximises the fitness and the mutation rates simultaneously, allowing individuals in “dense” fitness valleys and on “sparse” local optima to co-exist on a non-dominated Pareto front. The previous study proved its efficiency in escaping local optima with unknown sparsity, where some fixed mutation rate EAs become trapped. However, the performance is unknown in other settings.
This paper continues the study of MOSA-EA through an empirical study. We find that the MOSA-EA has a comparable performance on unimodal functions, and outperforms eleven randomised search heuristics considered on a bi-modal function with “sparse” local optima. For NP-hard problems, the MOSA-EA increasingly outperforms other algorithms for harder NK-LANDSCAPE and k-SAT instances. Notably, the MOSA-EA outperforms a problem-specific MAXSAT solver on several hard k-SAT instances. Finally, we show that the MOSA-EA self-adapts the mutation rate to the noise level in noisy optimisation. The results suggest that self-adaptation via multi-objectivisation can be adopted to control parameters in non-elitist EAs.
Recently, the Multi-Objective Self-Adaptive EA (MOSA-EA) (Lehre and Qin, 2022) was proposed to optimise single-objective functions, treating parameter control via multi-objectivisation. The algorithm maximises the fitness and the mutation rates simultaneously, allowing individuals in “dense” fitness valleys and on “sparse” local optima to co-exist on a non-dominated Pareto front. The previous study proved its efficiency in escaping local optima with unknown sparsity, where some fixed mutation rate EAs become trapped. However, the performance is unknown in other settings.
This paper continues the study of MOSA-EA through an empirical study. We find that the MOSA-EA has a comparable performance on unimodal functions, and outperforms eleven randomised search heuristics considered on a bi-modal function with “sparse” local optima. For NP-hard problems, the MOSA-EA increasingly outperforms other algorithms for harder NK-LANDSCAPE and k-SAT instances. Notably, the MOSA-EA outperforms a problem-specific MAXSAT solver on several hard k-SAT instances. Finally, we show that the MOSA-EA self-adapts the mutation rate to the noise level in noisy optimisation. The results suggest that self-adaptation via multi-objectivisation can be adopted to control parameters in non-elitist EAs.
Original language | English |
---|---|
Title of host publication | Parallel Problem Solving from Nature – PPSN XVII |
Subtitle of host publication | 17th International Conference, PPSN 2022, Dortmund, Germany, September 10–14, 2022, Proceedings, Part I |
Editors | Günter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar |
Publisher | Springer |
Pages | 308–323 |
Number of pages | 16 |
Edition | 1 |
ISBN (Electronic) | 9783031147142 |
ISBN (Print) | 9783031147135 |
DOIs | |
Publication status | Published - 14 Aug 2022 |
Event | The seventeenth International Conference on Parallel Problem Solving from Nature - Dortmund, Germany Duration: 10 Sept 2022 → 14 Sept 2022 https://ppsn2022.cs.tu-dortmund.de |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13398 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | The seventeenth International Conference on Parallel Problem Solving from Nature |
---|---|
Country/Territory | Germany |
City | Dortmund |
Period | 10/09/22 → 14/09/22 |
Internet address |
Bibliographical note
Funding Information:Acknowledgements. This work was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025562/1) and BlueBEAR/Baskerville HPC service.
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Keywords
- Evolutionary algorithms
- Self-adaptation
- Local optima
- Combinatorial optimisation
- Noisy optimisation
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science