By Amirhossein Rajabi, Carsten Witt, in Proc. of GECCO 2020.
The Paper Story
Self-adjusting Mechanisms
Self-adjusting Evolutionary Algorithms can learn good or even near-optimal parameters settings.
- Examples of popular self-adjusting EAs:
GA with 1/5-rule: if then if then
EA with two rates Create offspring by flipping each bit with prob. Create offspring by flipping each bit with prob. With prob. , replace with the strength that the best offspring has been created with (but with probability do a random step).
These self-adjusting schemes work since they in some sense measure how successful different parameter choices are compared to each other. There is basically no signal for the self-adjusting scheme in a local optimum. Mostly, classical self-adjusting algorithms would take many unsuccessful steps in such situations and suggest to set the mutation rate to its minimum although that might not be the best choice to leave the local optimum. On multimodal problems, however, increasing the rate is often beneficial and existing self-adjusting EAs perform poorly in this situation.
Most self-adjusting EAs perform poorly in local optima.
We are going to address this shortcoming by proposing Stagnation Detection.
Stagnation Detection is an efficient solution.
Multimodal Functions
Definition of "gap": Given a fitness function
- Multimodal functions have at least one point such that .
Example: In multimodal function, for all points such that .
Stagnation Detection Idea
Assume the current search point is such that .
Improvement time of (1+1) EA with different mutation strengths (mutation probability ): → ⇒ → ⇒ (Optimum but requiring the gap size).
But in the real world, we don't know how large the gaps are. But hopefully we can find out how large the gaps are not. But How?
Assume that , and the algorithm doesn't make any improvement within steps, then with high probability the gap size is larger or much larger than .
We use this fact to develop the stagnation detection mechanism ⇒
Starting from strength , the strength is increased from to when the counter exceeds the threshold . . If , If , .
- Parameter
EA with Stagnation Detection (EA)
Let's use the Stagnation Detection module in classical (1+1) EA and call it SD-(1+1)EA.
Escaping from Local Optima
Theorem: SD-EA escapes from the local optimum in , where .
SD- EA on JUMP
Theorem: The expected runtime of the SD-EA on with satisfies
General Bound on Fitness Function
- = the number of points of visited.
- where
Theorem: The expected runtime of the SD-EA is at most , moreover, .
- Use this theorem to calculate the upper bound that the Stagnation Detection mechanism has on any fitness function.
SASD-EA
- EA with two-rate and Stagnation Detection (SASD-EA)
- This algorithm behaves like EA with two rates on unimodal points and like EA with stagnation detection on local optima.
- The threshold is since in each iteration the algorithm produces .
Two states:
S1 → EA with two rates.
S2 → EA with stagnation detection.
SASD-EA Idea - S1 at the beginning. - Shift to S2 where the counter exceeds the threshold. - Shift to S1 where a strict improvement is observed.
Experimental Results on
We carried out an experiment that compares different algorithms on jump function with gap size of 4 and different n. The Numbers are averaged over 1000 independent runs of the algorithms.
- This result is showing the performance of Stagnation Detection on Jump function as a benchmark in practice.
Where Self-adaptation Fails
- In the second part of the paper, we present a function where stagnation detection and other self-adjusting schemes cannot find its global optimum in polynomial time. Because measuring the number of successes does not hint on the location of the global optimum.
- Ratio of successfully achieved global optimum where over 1000 runs.
The optimization time of different algorithms on : - Theorem 4.1: EA with strength w.h.p. - Theorem 4.1: EA with strength for any constant w.h.p. - Theorem 4.2: SD-EA at least w.h.p. - Theorem 4.3: SASD-EA at least w.h.p.
- The proofs of all theorems are available in the arXiv version.
Summary
- We have designed and analyzed self-adjusting EAs for multimodal optimization with Stagnation Detection.
- Stagnation Detection can be added to existing EAs without essentially changing their behavior on unimodal (sub)problems.
- (1+1)EA with stagnation detection (SD-(1+1)EA) optimizes the Jump function with in asymptotically optimal time .
- We have proved a general upper bound for multimodal functions.
- We have presented a function, on which all of our investigated self-adjusting EAs provably fail to be efficient.
Thank you. if you have any question please don't hesitate to contact us.