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.