The Right Mutation Strength for Multi-Valued Decision Variables

Benjamin Doerr, Carola Doerr, Timo Kötzing

TL;DR

This paper investigates how to best mutate solutions in evolutionary algorithms when decision variables can take more than two values (e.g., 0, 1, 2, ..., r-1). The authors show that a "harmonic" mutation strategy, which favors smaller step sizes but allows for larger ones, significantly outperforms simpler mutation strategies, reducing the dependence on the number of possible values from linear to polylogarithmic.

What Problem Does This Paper Address?

Evolutionary algorithms (EAs) are powerful optimization tools, but they often rely on bit strings to represent solutions, which is ideal for binary decisions. However, many real-world problems involve variables with multiple discrete values (e.g., scheduling jobs on machines, where a job can be assigned to one of 'r' machines). Extending EAs to these "multi-valued" domains is challenging, and there's a lack of theoretical understanding about how to design effective mutation operators for them. This paper aims to fill that gap by analyzing the performance of simple EAs on multi-valued OneMax-like problems with different mutation strategies.

Methods

The authors analyze the runtime of the (1+1) EA and Randomized Local Search (RLS) algorithms on multi-valued OneMax functions. The core of their work lies in comparing different mutation operators:

  • Uniform Mutation: A selected component is changed to any other value in the alphabet uniformly at random.
  • ±1 Mutation: A selected component is changed by adding or subtracting 1 (with equal probability). This is referred to as "mutation strength one."
  • Harmonic Mutation: A step size j is chosen with probability inversely proportional to j (i.e., smaller steps are more likely). The selected component is then changed by +j or -j.

They employ drift analysis, a powerful mathematical tool for analyzing the expected progress of algorithms towards a target solution, to derive theoretical bounds on the expected optimization time. A key contribution is a new variant of the multiplicative drift theorem that handles processes that can occasionally move away from the target.

Datasets

Not discussed in the paper. The authors introduce and analyze theoretical "multi-valued OneMax functions" as benchmarks. These functions are defined as the sum of distances between the current solution's components and a target vector, using either an interval or a ring metric.

Key Insights and Ideas

  • The "Right" Mutation Matters: The choice of mutation operator significantly impacts performance in multi-valued domains. Simply extending bit-string mutation strategies doesn't always yield optimal results.
  • The Power of Harmonic Mutation: A mutation strategy that favors smaller, more "cautious" steps (harmonic distribution) but still allows for larger jumps proves to be remarkably effective. This strategy balances exploration and exploitation better than simpler methods.
  • Linear vs. Polylogarithmic Dependence on r: The number of possible values (r) can be a bottleneck. The harmonic mutation strategy dramatically reduces this bottleneck, changing the runtime dependence from linear in r to polylogarithmic in r.
  • Drift Analysis is Key: The paper heavily relies on sophisticated drift analysis techniques, including a novel multiplicative drift theorem, to rigorously prove performance bounds.

Key Results

The paper provides tight theoretical bounds on the expected optimization time for different mutation strategies on multi-valued OneMax functions:

  • Uniform Mutation: Expected runtime is $\Theta(nr \log n)$. The linear dependence on r is a significant drawback for large alphabets.
  • ±1 Mutation: Expected runtime is $\Theta(nr + n \log n)$. This is an improvement over uniform mutation, especially for smaller r, but still has a linear dependence on r.
  • Harmonic Mutation: Expected runtime is $\Theta(n \log r (\log n + \log r))$. This is the most significant result, showing a polylogarithmic dependence on r, making it much more scalable for problems with large alphabets.

Limitations and Future Work

  • Theoretical Focus: The results are theoretical bounds derived for simplified OneMax-like problems. Their direct applicability to more complex, real-world EAs with intricate fitness landscapes needs further empirical validation.
  • Simple Algorithms: The analysis is primarily for the (1+1) EA and RLS, which are among the simplest EAs. Extending these findings to more sophisticated EAs (e.g., with larger populations) is a natural next step.
  • Harmonic Distribution Optimality: While the paper suggests the harmonic distribution is likely optimal for variable step-size mutation, further work could explore other distributions or adaptive mechanisms.
  • Dynamic Problems: The current work focuses on static OneMax functions. Analyzing these mutation strategies on dynamic or changing fitness landscapes would be valuable.

Summary updated

Abstract

The most common representation in evolutionary computation are bit strings. This is ideal to model binary decision variables, but less useful for variables taking more values. With very little theoretical work existing on how to use evolutionary algorithms for such optimization problems, we study the run time of simple evolutionary algorithms on some OneMax-like functions defined over Ω = {0, 1, ..., r-1}n. More precisely, we regard a variety of problem classes requesting the component-wise minimization of the distance to an unknown target vector z ∈ Ω. For such problems we see a crucial difference in how we extend the standard-bit mutation operator to these multi-valued domains. While it is natural to select each position of the solution vector to be changed independently with probability 1/n, there are various ways to then change such a position. If we change each selected position to a random value different from the original one, we obtain an expected run time of Θ(nr log n). If we change each selected position by either +1 or -1 (random choice), the optimization time reduces to Θ(nr + n log n). If we use a random mutation strength i ∈ {0,1,...,r-1}n with probability inversely proportional to i and change the selected position by either +i or -i (random choice), then the optimization time becomes Θ(n log(r)(log(n)+log(r))), bringing down the dependence on $r$ from linear to polylogarithmic. One of our results depends on a new variant of the lower bounding multiplicative drift theorem.
BibTeX
@inproceedings{doerr2016right,
  author = {Benjamin Doerr and Carola Doerr and Timo Kötzing},
  title = {{The Right Mutation Strength for Multi-Valued Decision Variables}},
  booktitle = {GECCO},
  year = {2016},
  url = {https://openreview.net/forum?id=KXzPlJokD5_},
}
Figure