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

## Abstract

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.

In **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.

On , we proved the optimization time , a speed-up by a factor of at least compared to the previous asymmetric from [1].

On general , where both contains zeroes and ones, we proved the same asymptotic bound.

## 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

We propose a rather conservative setting that flips -bits with probability for some value and -bits with probability .

- 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 .

Experimentally, was compared against the and [1] on in Figure 1, with parameters and . A clear difference between the performance of and the algorithms using asymmetric mutations. The outperforms although we used relatively small and large .

## 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 .

Experimentally, was compared against the and [1] on with in Table 2 with parameters: and . Similarity between data suggests that the asymmetric algorithms perform neither worse nor better compared to . More precisely, all p-values obtained from a Mann-Whitney U test between algorithms, with respect to the null hypothesis of identical behavior, are greater than 0.1.

### 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)

Thank you. if you have any question please don't hesitate to contact us.