Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constra
- PDF / 985,846 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 148 Views
Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints Feng Shi1 · Martin Schirneck2 · Tobias Friedrich2 · Timo Kötzing2 · Frank Neumann3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Correction to: Algorithmica (2019) 81:828–857 https://doi.org/10.1007/s00453-018-0451-4 In the article Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints, we claimed a worst-case runtime of O(nD log D) and O(nD) for the Multi-Objective Evolutionary Algorithm and the Multi-Objective (𝜇+(𝜆, 𝜆)) Genetic Algorithm, respectively, on linear profit functions under dynamic uniform constraint, where D = |B − B∗ | denotes the difference between the original constraint bound B and the new one B∗ . The technique used to prove these results contained an error. We correct this mistake and show a weaker bound of O(nD2 ) for both algorithms instead. The Multi‑Objective Evolutionary Algorithm In Theorem 9 of the original article [4], we claimed a bound of O(nD log D) for the expected reoptimization time of the Multi-Objective Evolutionary Algorithm (MOEA), where D = |B − B∗ | denotes the difference between the original constraint bound B and the new one B∗ . Its proof was based on the notion of candidate solutions x for which there is an optimum x∗ (assuming B ≤ B∗ ) such that xi = 1 implies xi∗ = 1 . In other words, an optimum can be created from a candidate by only flipping 0-bits. We used drift analysis on the potential function The original article can be found online at https://doi.org/10.1007/s00453-018-0451-4. * Feng Shi [email protected] 1
School of Computer Science and Engineering, Central South University, Changsha, Hunan, People’s Republic of China
2
Hasso Plattner Institute, Potsdam, Germany
3
School of Computer Science, The University of Adelaide, Adelaide, Australia
13
Vol.:(0123456789)
Algorithmica
G = B∗ − h , where h is the largest Hamming weight among all candidates in S. The analysis relied on this potential to be non-increasing during the reoptimization. This is not the case as illustrated by the following counterexample. Suppose n = 5 , B = 2 , and B∗ = 4 ; the weights of the profit function P shall observe the inequalities w1 ≥ w2 ≥ w3 ≥ w4 > w5 and w2 + w5 > w3 + w4 , the population S may consist of the solutions y = 11000 and z = 10110 . The unique optimum of P under constraint B∗ is x∗ = 11110 , making both members of S candidates. Their largest Hamming weight h is 3. A mutation of z flipping 4 bits may result in the string z� = 11001 , which replaces z due to the higher profit. However, z′ is not a candidate anymore. The candidate of highest Hamming weight is now y and h decreases to 2. This increases the potential G in turn. We now prove a weaker runtime bound for the MOEA with an alternative technique. Theorem 9 The reoptimization time of the MOEA on linear functions under dynamic uniform constraint is
E[T] = O(nD2 ). Proof We first present th
Data Loading...
