Back to search

University of Birmingham

Self-adaptive parameter control mechanisms in evolutionary computation

Abstract

dc:description.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.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qin, Xiaoyu
ORCID person:identifier.orcid

Subjects

dc:subject × 2

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Qin, Xiaoyu. Self-adaptive parameter control mechanisms in evolutionary computation. d_ph thesis, University of Birmingham, 2024.