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

research-article

Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints

Authors:

Martin Schirneck,

Tobias Friedrich,

Frank NeumannAuthors Info & Claims

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

Pages 1407 - 1414

https://doi.org/10.1145/3071178.3071270

Published: 01 July 2017 Publication History

Abstract

The investigations of linear pseudo-Boolean functions play a central role in the area of runtime analysis of evolutionary computing techniques. Having an additional linear constraint on a linear function is equivalent to the NP-hard knapsack problem and special problem classes thereof have been investigated in recent works. In this paper, we extend these studies to problems with dynamic constraints and investigate the runtime of different evolutionary algorithms to recompute an optimal solution when the constraint bound changes by a certain amount. We study the classical (1+1) EA and population-based algorithms and show that they recompute an optimal solution very efficiently. Furthermore, we show that a variant of the (1+(λ, λ)) GA can recompute the optimal solution more efficiently in some cases.

References

[1]

A. Auger and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments, volume 1. World Scientific, 2011.

Digital Library

[2]

B. Doerr and C. Doerr. Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings. In Proc. of GECCO'15, pages 1335--1342, 2015.

Digital Library

[3]

B. Doerr, C. Doerr, and F. Ebel. From Black-box Complexity to Designing New Genetic Algorithms. Theoretical Computer Science, 567:87--104, 2015.

Digital Library

[4]

B. Doerr, D. Johannsen, and C. Winzen. Multiplicative Drift Analysis. Algorithmica, 64:673--697, 2012.

Digital Library

[5]

S. Droste, T. Jansen, and I. Wegener. On the Analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[6]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation, 18(4):617--633, 2010.

Digital Library

[7]

T. Friedrich, T. Kötzing, J. A. G. Lagodzinski, F. Neumann, and M. Schirneck. Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints. In Proc. of FOGA'17, pages 45--54, 2017.

Digital Library

[8]

T. Jansen. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer, 2013.

Digital Library

[9]

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.

[10]

T. Kötzing, A. Lissovoi, and C. Witt. (1+1) EA on Generalized Dynamic OneMax. In Proc. of FOGA'15, pages 40--51, 2015.

Digital Library

[11]

S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754--771, 2013.

Digital Library

[12]

E. Mezura-Montes and C. A. C. Coello. Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation, 1(4):173--194, 2011.

[13]

H. Mühlenbein. How Genetic Algorithms Really Work: Mutation and Hillclimbing. In Proc. of PPSN'92, volume 92, pages 15--25, 1992.

[14]

F. Neumann and I. Wegener. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5(3):305--319, 2006.

Digital Library

[15]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[16]

C. Witt. Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions. Combinatorics, Probability and Computing, 22:294--318, 2013.

[17]

Y. Zhou and J. He. A runtime analysis of evolutionary algorithms for constrained optimization problems. IEEE Transactions on Evolutionary Computation, 11:608--619, 2007.

Digital Library

Cited By

Xie YNeumann ANeumann FCoello Coello C(2020)Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problemProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390162(271-279)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390162
Xie YHarper OAssimi HNeumann ANeumann FAuger AStützle T(2019)Evolutionary algorithms for the chance-constrained knapsack problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321869(338-346)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321869
Bossek JNeumann FPeng PSudholt DAuger AStützle T(2019)Runtime analysis of randomized search heuristics for dynamic graph coloringProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321792(1443-1451)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321792
Show More Cited By

Index Terms

Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints

Recommendations

Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints

Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-...
Self-adjusting Evolutionary Algorithms are Slow on a Class of Multimodal Landscapes
Parallel Problem Solving from Nature – PPSN XVIII
Abstract
The one-fifth rule and its generalizations are a classical parameter control mechanism in discrete domains. They have also been transferred to control the offspring population size of the $(1, λ)$ -EA. This has been shown to work very well for hill-...
Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 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: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
108
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xie YNeumann ANeumann FCoello Coello C(2020)Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problemProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390162(271-279)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390162
Xie YHarper OAssimi HNeumann ANeumann FAuger AStützle T(2019)Evolutionary algorithms for the chance-constrained knapsack problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321869(338-346)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321869
Bossek JNeumann FPeng PSudholt DAuger AStützle T(2019)Runtime analysis of randomized search heuristics for dynamic graph coloringProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321792(1443-1451)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321792
Doerr BDoerr CNeumann FAuger AStützle T(2019)Fast re-optimization via structural diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321731(233-241)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321731
Pourhassan MRoostapour VNeumann F(2019)Runtime analysis of RLS and (1 + 1) EA for the dynamic weighted vertex cover problemTheoretical Computer Science10.1016/j.tcs.2019.03.003Online publication date: Mar-2019
https://doi.org/10.1016/j.tcs.2019.03.003
Shi FSchirneck MFriedrich TKötzing TNeumann F(2019)Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica10.1007/s00453-018-0451-481:2(828-857)Online publication date: 15-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0451-4
Shi FNeumann FWang JTakadama K(2018)Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205580(1515-1522)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205580
Dang-Nhu RDardinier TDoerr BIzacard GNogneng DTakadama K(2018)A new analysis method for evolutionary optimization of dynamic and noisy objective functionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205563(1467-1474)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205563
Roostapour VNeumann ANeumann F(2018)On the Performance of Baseline Evolutionary Algorithms on the Dynamic Knapsack ProblemParallel Problem Solving from Nature – PPSN XV10.1007/978-3-319-99253-2_13(158-169)Online publication date: 22-Aug-2018
https://doi.org/10.1007/978-3-319-99253-2_13
Neumann F(2017)Parameterized analysis of bio-inspired computing2017 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2017.8285451(1-3)Online publication date: Nov-2017
https://doi.org/10.1109/SSCI.2017.8285451
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