By Amirhossein Rajabi, Carsten Witt, in Proc. of PPSN 2020.

Evolutionary Algorithms (EAs) and other randomized search heuristics are often considered as unbiased algorithms that are invariant with respect to different transformations of the underlying search space. However, if a certain amount of domain knowledge is available the use of biased search operators in EAs becomes viable. We consider a simple (1+1) EA for binary search spaces and analyze an asymmetric mutation operator that can treat zero- and one-bits differently. This operator extends previous work by Jansen and Sudholt (ECJ 18(1), 2010) by allowing the operator asymmetry to vary according to the success rate of the algorithm. Using a self-adjusting scheme that learns an appropriate degree of asymmetry, we show improved runtime results on the class of functions describing the number of matching bits with a fixed target .

# The Paper Story

## Self-adjusting Asymmetric Mutation

- Evolutionary Algorithms (EAs) are often considered as
**unbiased algorithms**that are invariant with respect to different transformations of the underlying search space. However, if a certain amount of**domain knowledge**is available the use of biased search operators in EAs becomes viable. - On
**bit strings**, it might be known beforehand that zero-bits have a different interpretation than one-bits and that the total number of one-bits in high-quality solutions should lie within a certain interval. - In the
**minimum spanning tree (MST)**problem with vertices and edges, all valid solutions should have exactly one-bits.

**Self-adjusting Asymmetric Mutation**, the mutation operator flips - and -bits of the current search point with different probabilities that can be adjusted based on the

**number of successes**with a given probability profile.

## Standard and Asymmetric Mutations

**Standard bit mutation:**Flip each bit independently with probability . The Algorithm 1 with this mutation is called**.****Asymmetric mutation:**Flip each -bit with probability for , where is defined as the number of -bits. The Algorithm 1 with the latter mutation is called [1,2].

## Algorithm

- Initially, .
- In an observation phase of length the following pairs of - and -strengths are tried alternatingly:

,

- The pair that leads to relatively more successes is used as the ground pair for the next phase. In case of a tie a uniform random choice is made.
- The strengths are confined to .

## on

- Fitness function .
- outperforms the from [1] by a constant factor of roughly 2 on .

**Theorem:**The runtime of the on satisfies where , , for an arbitrarily small constant , and .

## on

- Fitness function for an unknown target , where denotes the Hamming distance.
- In other words, returns the number of matching bits in and .
- does not harm its optimization time on :

**Theorem:**The runtime of the on is where , , and .

### References:

**[1]** Jansen, T., Sudholt, D.: **Analysis of an asymmetric mutation operator**. Evolutionary Computation18(1), 1–26 (2010)

**[2]** Neumann, F., Wegener, I.: **Randomized local search, evolutionary algorithms, and the minimum spanning tree problem.** Theoretical Computer Science378(1), 32–40 (2007)