Self-adaptive parameter control mechanisms in evolutionary computation

Qin, Xiaoyu ORCID: 0000-0002-9720-3220 (2024). Self-adaptive parameter control mechanisms in evolutionary computation. University of Birmingham. Ph.D.

Preview

Qin2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (4MB) | Preview

Abstract

Evolutionary algorithms (EAs) are effective solvers for a variety of discrete black-box optimisation problems. However, their performance heavily relies on the proper selection of algorithmic parameters, such as mutation rate, crossover rate, and selection pressure, which are often problem- and instance-specific. One promising approach is self-adaptive parameter control mechanisms, where the parameters are encoded in the individuals and evolved along with their solutions through variation operators. Although there have been some theoretical studies demonstrating the efficiency of self-adaptive EAs on certain functions with unknown structure, the potential benefits of this approach in other scenarios remain unknown. Moreover, there is a great opportunity for creativity in designing elegant self-adaptive EAs.

In this thesis, we first examine the benefits of self-adaptation in noisy optimisation, where the presence of noise can significantly affect the algorithm performance. We provide a mathematical analysis of the runtime of 2-tournament EAs with self-adapting mutation rates and two other parameter strategies on a theoretical benchmark optimisation problem with and without symmetric noise. Our results demonstrate that self-adaptation consistently achieves the lowest runtime compared to using fixed mutation rates. This is confirmed regardless of the presence of noise, through additional experiments with other noise types and self-adaptation mechanisms. Next, we investigate the performance of self-adaptive EAs on a natural tracking dynamic optima problem, known as the Dynamic Substring Matching (DSM) problem. This problem requires the algorithm to track a sequence of structure-changing optima, and our analysis reveals that mutation-based EAs with a fixed mutation rate have small chance of succeeding, while self-adaptive EAs can track the dynamic optima with high probability. Finally, we propose a novel self-adaptive EA for single-objective optimisation, which incorporates multi-objective optimisation principles to jointly optimise the fitness and mutation rates. We call this algorithm multi-objective self-adaptive EA (MOSA- EA). Our runtime analysis shows that the MOSA-EA can efficiently escape the local optima with unknown sparsity, where fixed mutation rate EAs may become trapped. In an empirical study on complex combinatorial problems, the MOSA-EA outperforms twelve other algorithms on NK-Landscape and Max-k-Sat problem instances. Overall, this thesis suggests that the self-adaptation has great potential for controlling parameters in EAs, especially in challenging optimisation scenarios, such as uncertain optimisation.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):