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

research-article

Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints

Authors:

Tobias Friedrich,

Gregor Lagodzinski,

Martin SchirneckAuthors Info & Claims

FOGA '17: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Pages 45 - 54

https://doi.org/10.1145/3040718.3040728

Published: 12 January 2017 Publication History

Abstract

Linear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective and the constraint function is given by the OneMax function and present upper bounds as well as lower bounds for the general case. We also consider the LeadingOnes fitness function.

References

[1]

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

Digital Library

[2]

R. Beier. Probabilistic Analysis of Discrete Optimization Problems. PhD thesis, Universität des Saarlandes, 2005.

[3]

D. Dang and P. K. Lehre. Simplified Runtime Analysis of Estimation of Distribution Algorithms. In Proc. of GECCO'15, pages 513-518, 2015.

Digital Library

[4]

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

Digital Library

[5]

S. Droste. Analysis of the (1+1) EA for a Noisy OneMax. In Proc. of GECCO'04, pages 1088-1099, 2004.

[6]

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

[7]

J. S. Frame. Mean Deviation of the Binomial Distribution. The American Mathematical Monthly, 52:377-379, 1945.

[8]

C. Gießen and T. Kötzing. Robustness of Populations in Stochastic Environments. Algorithmica, 75:462-489, 2016.

Digital Library

[9]

M. Harman. Software Engineering Meets Evolutionary Computation. IEEE Computer, 44:31-39, 2011.

Digital Library

[10]

J. He, B. Mitavskiy, and Y. Zhou. A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, July 6-11, 2014, pages 141-148. IEEE, 2014.

[11]

J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3:21-35, 2004.

Digital Library

[12]

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

Digital Library

[13]

D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, 2010.

[14]

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

[15]

T. Kötzing. Concentration of First Hitting Times Under Additive Drift. Algorithmica, 75:490-506, 2016.

Digital Library

[16]

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

[17]

T. Kötzing, F. Neumann, D. Sudholt, and M. Wagner. Simple Max-Min Ant Systems and the Optimization of Linear Pseudo-Boolean Functions. In Proc. of FOGA'11, pages 209-218, 2011.

Digital Library

[18]

C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer. GenProg: A Generic Method for Automatic Software Repair. IEEE Transaction on Software Engineering, 38:54-72, 2012.

Digital Library

[19]

P. K. Lehre and C. Witt. Black-Box Search by Unbiased Variation. Algorithmica, 64:623-642, 2012.

Digital Library

[20]

X. Li, M. R. Bonyadi, Z. Michalewicz, and L. Barone. Solving a Real-world Wheat Blending Problem Using a Hybrid Evolutionary Algorithm. In Proc. of CEC'13, pages 2665-2671, 2013.

[21]

D. Lückehe, M. Wagner, and O. Kramer. On Evolutionary Approaches to Wind Turbine Placement with Geo-Constraints. In Proc. of GECCO'15, pages 1223-1230, 2015.

Digital Library

[22]

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

[23]

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

Digital Library

[24]

P. S. Oliveto and C. Witt. Improved Time Complexity Analysis of the Simple Genetic Algorithm. Theoretical Computer Science, 605:21-41, 2015.

Digital Library

[25]

J. E. Rowe and D. Sudholt. The Choice of the O_spring Population Size in the (1,¿) EA. In Proc. of GECCO'12, pages 1349-1356, 2012.

Digital Library

[26]

D. A. Spielman and S. Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Communications of the ACM, 52:76-84, 2009.

Digital Library

[27]

C. S. Stokes, A. R. Simpson, and H. R. Maier. A Computational Software Tool for the Minimization of Costs and Greenhouse Gas Emissions Associated with Water Distribution Systems. Environmental Modelling and Software, 69:452-467, 2015.

Digital Library

[28]

D. Sudholt and C. Witt. Runtime Analysis of a Binary Particle Swarm Optimizer. Theoretical Computer Science, 411:2084-2100, 2010.

Digital Library

[29]

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

[30]

F. Zheng, A. R. Simpson, and A. C. Zecchin. Improving the Efficiency of Multi-objective Evolutionary Algorithms Through Decomposition: An Application to Water Distribution Network Design. Environmental Modelling and Software, 69:240-252, 2015.

Digital Library

[31]

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

Neshat MNezhad MMirjalili SGarcia DDahlquist EGandomi A(2023)Short-term solar radiation forecasting using hybrid deep residual learning and gated LSTM recurrent network with differential covariance matrix adaptation evolution strategyEnergy10.1016/j.energy.2023.127701278(127701)Online publication date: Sep-2023
https://doi.org/10.1016/j.energy.2023.127701
Shi FSchirneck MFriedrich TKötzing TNeumann F(2020)Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica10.1007/s00453-020-00739-xOnline publication date: 20-Jul-2020
https://doi.org/10.1007/s00453-020-00739-x
Neumann FSutton AFriedrich TDoerr CArnold D(2019)Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340315(147-153)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340315
Show More Cited By

Index Terms

Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints

Recommendations

Analysis of (1+1) EA on LeadingOnes with Constraints
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first ...
Comparing evolutionary algorithms to the (1+1) -EA

In this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-EA compares favorably to other evolutionary algorithms (EAs) in terms of fitness function distribution at a given iteration and with respect to the average ...
Self-adjusting population sizes for the (1,λ)-EA on monotone functions
Abstract
We study the ( 1 , λ )-EA with mutation rate c / n for c ≤ 1, where the population size is adaptively controlled with the ( 1 : s + 1 )-success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA '17: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

January 2017

170 pages

ISBN:9781450346511

DOI:10.1145/3040718

Program Chairs:
Christian Igel
University of Copenhagen, Denmark
,
Dirk Sudholt
University of Sheffield, United Kingdom
,
Carsten Witt
Technical University of Denmark, Denmark

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: 12 January 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Union Seventh Framework Programme (FP7/2007-2013)
Australian Research Council

Conference

FOGA '17

Sponsor:

SIGEVO

FOGA '17: Foundations of Genetic Algorithms XIV

January 12 - 15, 2017

Copenhagen, Denmark

Acceptance Rates

FOGA '17 Paper Acceptance Rate 13 of 23 submissions, 57%;

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
101
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Neshat MNezhad MMirjalili SGarcia DDahlquist EGandomi A(2023)Short-term solar radiation forecasting using hybrid deep residual learning and gated LSTM recurrent network with differential covariance matrix adaptation evolution strategyEnergy10.1016/j.energy.2023.127701278(127701)Online publication date: Sep-2023
https://doi.org/10.1016/j.energy.2023.127701
Shi FSchirneck MFriedrich TKötzing TNeumann F(2020)Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica10.1007/s00453-020-00739-xOnline publication date: 20-Jul-2020
https://doi.org/10.1007/s00453-020-00739-x
Neumann FSutton AFriedrich TDoerr CArnold D(2019)Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340315(147-153)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340315
Roostapour VPourhassan MNeumann FFriedrich TDoerr CArnold D(2019)Analysis of baseline evolutionary algorithms for the packing while travelling problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340313(124-132)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340313
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 FSchirneck MFriedrich TKötzing TNeumann FBosman P(2017)Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraintsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071270(1407-1414)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071270

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