More Web Proxy on the site http://driver.im/

research-article

Fast re-optimization via structural diversity

Authors:

Benjamin Doerr,

Frank NeumannAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 233 - 241

https://doi.org/10.1145/3321707.3321731

Published: 13 July 2019 Publication History

Abstract

When a problem instance is perturbed by a small modification, one would hope to find a good solution for the new instance by building on a known good solution for the previous one. Via a rigorous mathematical analysis, we show that evolutionary algorithms, despite usually being robust problem solvers, can have unexpected difficulties to solve such re-optimization problems. When started with a random Hamming neighbor of the optimum, the (1+1) evolutionary algorithm takes Ω(n²) time to optimize the LeadingOnes benchmark function, which is the same asymptotic optimization time when started in a randomly chosen solution. There is hence no significant advantage from re-optimizing a structurally good solution.

We then propose a way to overcome such difficulties. As our mathematical analysis reveals, the reason for this undesired behavior is that during the optimization structurally good solutions can easily be replaced by structurally worse solutions of equal or better fitness. We propose a simple diversity mechanism that prevents this behavior, thereby reducing the re-optimization time for LeadingOnes to O(γδn), where γ is the population size used by the diversity mechanism and δ ≤ γ the Hamming distance of the new optimum from the previous solution. We show similarly fast re-optimization times for the optimization of linear functions with changing constraints and for the minimum spanning tree problem.

References

[1]

Anne Auger and Benjamin Doerr. 2011. Theory of Randomized Search Heuristics: Foundations and Recent Developments. Vol. 1. World Scientific.

Digital Library

[2]

Süntje Böttcher, Benjamin Doerr, and Frank Neumann. 2010. Optimal Fixed and Adaptive Mutation Rates for the LeadingOnes Problem. In Proc. of Parallel Problem Solving from Nature (PPSN'10) (Lecture Notes in Computer Science), Vol. 6238. Springer, 1--10.

Digital Library

[3]

Raymond Chiong, Thomas Weise, and Zbigniew Michalewicz (Eds.). 2012. Variants of Evolutionary Algorithms for Real-World Applications. Springer.

Digital Library

[4]

Raphaël Dang-Nhu, Thibault Dardinier, Benjamin Doerr, Gautier Izacard, and Dorian Nogneng. 2018. A New Analysis Method for Evolutionary Optimization of Dynamic and Noisy Objective Functions. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'18). ACM, 1467--1474.

Digital Library

[5]

Kalyanmoy Deb. 2012. Optimization for Engineering Design - Algorithms and Examples, Second Edition. PHI Learning Private Limited. http://phindia.com/bookdetails/optimization_for_engineering_design_-algorithms_and_examples_by-deb_kalyanmoy_-isbn-978-81-203-4678-9

[6]

Benjamin Doerr. 2018. Better Runtime Guarantees Via Stochastic Domination. In Proc. of Evolutionary Computation in Combinatorial Optimization (EvoCOP'18). Springer, 1--17. Full version available at https://arxiv.org/abs/1801.04487.

[7]

Benjamin Doerr. 2018. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics. CoRR abs/1801.06733 (2018). arXiv:1801.06733 http://arxiv.org/abs/1801.06733

[8]

Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus, and Frank Neumann. 2007. A Rigorous View on Neutrality. In Proc. of IEEE Congress on Evolutionary Computation (CEC'07). IEEE, 2591--2597.

[9]

Benjamin Doerr, Edda Happ, and Christian Klein. 2011. Tight Analysis of the (1+1)-EA for the Single Source Shortest Path Problem. Evolutionary Computation 19 (2011), 673--691.

Digital Library

[10]

Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover Can Provably be Useful in Evolutionary Computation. Theoretical Computer Science 425 (2012), 17--33.

Digital Library

[11]

Benjamin Doerr, Dirk Sudholt, and Carsten Witt. 2013. When Do Evolutionary Algorithms Optimize Separable Functions in Parallel?. In Proc. of Foundations of Genetic Algorithms (FOGA'13). ACM, 48--59.

Digital Library

[12]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

Digital Library

[13]

Jörg Lässig and Dirk Sudholt. 2013. Design and Analysis of Migration in Parallel Evolutionary Algorithms. Soft Computing 17 (2013), 1121--1144.

Digital Library

[14]

Andrei Lissovoi and Carsten Witt. 2015. Runtime Analysis of Ant Colony Optimization on Dynamic Shortest Path Problems. Theoretical Computer Science 561 (2015), 73--85.

Digital Library

[15]

Frank Neumann and Ingo Wegener. 2006. Minimum Spanning Trees Made Easier via Multi-Objective Optimization. Natural Computing 5 (2006), 305--319.

Digital Library

[16]

Frank Neumann and Ingo Wegener. 2007. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science 378 (2007), 32--40.

Digital Library

[17]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity (1st ed.). Springer.

Digital Library

[18]

Frank Neumann and Carsten Witt. 2015. On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling. In Proc. of International Joint Conference on Artificial Intelligence (IJCAI'15). AAAI Press, 3742--3748.

Digital Library

[19]

T.T. Nguyen and X. Yao. 2012. Continuous Dynamic Constrained Optimization: The Challenges. IEEE Transactions on Evolutionary Computation 16, 6 (2012), 769--786.

Digital Library

[20]

Mojgan Pourhassan, Wanru Gao, and Frank Neumann. 2015. Maintaining 2-Approximations for the Dynamic Vertex Cover Problem Using Evolutionary Algorithms. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'15). ACM, 903--910.

Digital Library

[21]

Günther R. Raidl, Gabriele Koller, and Bryant A. Julstrom. 2006. Biased Mutation Operators for Subgraph-Selection Problems. IEEE Trans. Evolutionary Computation 10 (2006), 145--156.

Digital Library

[22]

Pratyusha Rakshit, Amit Konar, and Swagatam Das. 2017. Noisy evolutionary optimization algorithms - A comprehensive survey. Swarm and Evolutionary Computation 33 (2017), 18--45.

[23]

Joachim Reichel and Martin Skutella. 2009. On the size of weights in randomized search heuristics. In Proc. of Foundations of Genetic Algorithms (FOGA'09). ACM, 21--28.

Digital Library

[24]

Hendrik Richter and Shengxiang Yang. 2013. Dynamic Optimization Using Analytic and Evolutionary Approaches: A Comparative Review. In Handbook of Optimization - From Classical to Modern Approach, Ivan Zelinka, Václav Snásel, and Ajith Abraham (Eds.). Intelligent Systems Reference Library, Vol. 38. Springer, 1--28.

[25]

Vahid Roostapour, Aneta Neumann, and Frank Neumann. 2018. On the Performance of Baseline Evolutionary Algorithms on the Dynamic Knapsack Problem. In Proc. of Parallel Problem Solving from Nature (PPSN'18) (Lecture Notes in Computer Science), Vol. 11101. Springer, 158--169.

[26]

Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2018. Pareto Optimization for Subset Selection with Dynamic Cost Constraints. CoRR abs/1811.07806 (2018). arXiv:1811.07806 http://arxiv.org/abs/1811.07806 Conference version appears at AAAI 2019.

[27]

Vahid Roostapour, Mojgan Pourhassan, and Frank Neumann. 2018. Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments. CoRR abs/1806.08547 (2018). arXiv:1806.08547 http://arxiv.org/abs/1806.08547

[28]

Jonathan E. Rowe and Dirk Sudholt. 2014. The Choice of the Offspring Population Size in the (1, λ) Evolutionary Algorithm. Theoretical Computer Science 545 (2014), 20--38.

Digital Library

[29]

Baruch Schieber, Hadas Shachnai, Gal Tamir, and Tami Tamir. 2018. A Theory and Algorithms for Combinatorial Reoptimization. Algorithmica 80, 2 (2018), 576--607.

Digital Library

[30]

Feng Shi, Frank Neumann, and Jianxin Wang. 2018. Runtime Analysis of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO'18). ACM, 1515--1522.

Digital Library

[31]

Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, and Frank Neumann. 2017. Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO'17). ACM, 1407--1414.

Digital Library

[32]

Dirk Sudholt. 2018. On the Robustness of Evolutionary Algorithms to Noise: Refined Results and an Example where Noise Helps. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO'18). ACM, 1523--1530.

Digital Library

[33]

Ingo Wegener. 2001. Theoretical Aspects of Evolutionary Algorithms. In Proc. of Automata, Languages and Programming (ICALP'01) (Lecture Notes in Computer Science), Vol. 2076. Springer, 64--78.

Digital Library

[34]

Carsten Witt. 2014. Revised analysis of the (1+1) EA for the minimum spanning tree problem. In Proc. of Genetic and Evolutionary Computation Conference (GECCO'14). ACM, 509--516.

Digital Library

[35]

Anna Zych-Pawlewicz. 2018. Reoptimization of NP-Hard Problems. In Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday (Lecture Notes in Computer Science), Vol. 11011. Springer, 477--494.

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Er Raqabi EWu YEl Hallaoui ISoumis F(2024)Towards resilience: Primal large-scale re-optimizationTransportation Research Part E: Logistics and Transportation Review10.1016/j.tre.2024.103819192(103819)Online publication date: Dec-2024
https://doi.org/10.1016/j.tre.2024.103819
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5
Show More Cited By

Index Terms

Fast re-optimization via structural diversity
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random search heuristics

Recommendations

Artificial physics optimisation algorithm guided by diversity

In order to avoid the stagnation evolution of APO population, the thinking of dissipative structure theory and population diversity are combined in APO. Firstly, a chaos factor is introduced to judge whether the individuals doing dissipative movement or ...
Promoting diversity in particle swarm optimization to solve multimodal problems
ICONIP'11: Proceedings of the 18th international conference on Neural Information Processing - Volume Part II

Promoting diversity is an effective way to prevent premature converge in solving multimodal problems using Particle Swarm Optimization (PSO). Based on the idea of increasing possibility of particles “jump out” of local optima, while keeping the ability ...
Maintaining Diversity in EDAs for Real-Valued Optimisation Problems
FBIT '07: Proceedings of the 2007 Frontiers in the Convergence of Bioscience and Information Technologies

A recent extension applicable to a wide range of discrete EDA algorithms, called Sampling-Mutation, has shown promise on a non-stationary problem, as well as on a hierarchical deceptive problem. In this paper we further the empirical exploration on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

July 2019

1545 pages

ISBN:9781450361118

DOI:10.1145/3321707

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
96
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Er Raqabi EWu YEl Hallaoui ISoumis F(2024)Towards resilience: Primal large-scale re-optimizationTransportation Research Part E: Logistics and Transportation Review10.1016/j.tre.2024.103819192(103819)Online publication date: Dec-2024
https://doi.org/10.1016/j.tre.2024.103819
Doerr BKelley A(2024)Fourier Analysis Meets Runtime Analysis: Precise Runtimes on PlateausAlgorithmica10.1007/s00453-024-01232-586:8(2479-2518)Online publication date: 10-May-2024
https://doi.org/10.1007/s00453-024-01232-5
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Alza JBartlett MCeberio JMcCall J(2023)On the elusivity of dynamic optimisation problemsSwarm and Evolutionary Computation10.1016/j.swevo.2023.10128978(101289)Online publication date: Apr-2023
https://doi.org/10.1016/j.swevo.2023.101289
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Bulanova NBuzdalova ADoerr C(2022)Fast Re-Optimization of LeadingOnes with Frequent Changes2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870400(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870400
Doerr BKrawiec K(2021)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461406(369-398)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461406
Bossek JNeumann FPeng PSudholt D(2021)Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring ProblemAlgorithmica10.1007/s00453-021-00838-3Online publication date: 18-Jun-2021
https://doi.org/10.1007/s00453-021-00838-3
Doerr BCoello Coello C(2020)A gentle introduction to theory (for non-theoreticians)Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389889(373-403)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389889
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents