A Rigorous Analysis of Self‐Adaptation in Discrete Evolutionary Algorithms

Date & BST or UK time:  Tuesday, June 30., 2020 –  3:00 p.m.

Speaker: Prof. Per Kristian Lehre. Senior Lecturer at the University of Birmingham, UK.

Issue:

A key challenge to making effective use of evolutionary algorithms (EAs) is to choose appropriate settings for their parameters. However, the appropriate parameter setting generally depends on the structure of the optimization problem, which is often unknown to the user. Non‐deterministic parameter control mechanisms adjust parameters using information obtained from the evolutionary process. Self-adaptation‐‐ where parameter settings are encoded in the chromosomes of individuals and evolve through mutation and crossover ‐‐ is a popular parameter control mechanism in evolutionary strategies. However, there is little theoretical evidence that self‐adaptation is effective, and self-adaptation has largely been ignored by the discrete evolutionary computation community. Here we show through a rigorous runtime analysis that a non‐elitist, discrete evolutionary algorithm which self-adapts its mutation rate not only outperforms EAs which use static mutation rates on the leading‐ones and substring problems but also improves asymptotically on an EA using a state‐of‐the‐art control mechanism. The structure of these two problems depends on a parameter k, which is a priori unknown to the algorithm, and which is needed to appropriately set a fixed mutation rate. The self‐adaptive EA achieves the same runtime as if this parameter was known to the algorithm beforehand, which is an asymptotic speedup for this problem compared to all other EAs previously studied. An experimental study of how the mutation‐rates evolve shows that they respond adequately to a diverse range of problem structures. These results suggest that self‐adaptation should be adopted more broadly as a parameter control mechanism in discrete, non‐elitist evolutionary algorithms.



Click to rate this post
[Total: 0 Average: 0]