Article

On the analysis of the (1+1) memetic algorithm

Author:

Dirk SudholtAuthors Info & Claims

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Pages 493 - 500

https://doi.org/10.1145/1143997.1144087

Published: 08 July 2006 Publication History

Get Access

Abstract

Memetic algorithms are evolutionary algorithms incorporating local search to increase exploitation. This hybridization has been fruitful in countless applications. However, theory on memetic algorithms is still in its infancy.Here, we introduce a simple memetic algorithm, the (1+1) Memetic Algorithm (1+1(MA)), working with a population size of 1 and no crossover. We compare it with the well-known (1+1) EA and randomized local search and show that these algorithms can outperform each other drastically.On problems like, e.g., long path problems it is essential to limit the duration of local search. We investigate the (1+1) MA with a fixed maximal local search duration and define a class of fitness functions where a small variation of the local search duration has a large impact on the performance of the (1+1) MA.All results are proved rigorously without assumptions.

References

[1]

C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268--308, 2003.

Digital Library

Google Scholar

[2]

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

Google Scholar

[3]

J. Horn, D. E. Goldberg, and K. Deb. Long path problems. In Y. Davidor, H.-P. Schwefel, and R. Männer, editors, Parallel Problem Solving from Nature (PPSN enskip III), volume 866, pages 149--158. Springer, 1994.

Digital Library

Google Scholar

[4]

T. Jansen and I. Wegener. Real royal road functions - where crossover provably is essential. Discrete Applied Mathematics, 149:111--125, 2005.

Digital Library

Google Scholar

[5]

P. Merz. Advanced fitness landscape analysis and the performance of memetic algorithms. Evolutionary Computation, 12(3):303--326, 2004.

Digital Library

Google Scholar

[6]

P. Moscato. Memetic algorithms: a short introduction. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 219--234. McGraw-Hill, 1999.

Digital Library

Google Scholar

[7]

G. Rudolph. How mutation and selection solve long-path problems in polynomial expected time. Evolutionary Computation, 4(2):195--205, 1997.

Digital Library

Google Scholar

[8]

C. Witt. An analysis of the (μ+1) EA on pseudo-boolean functions. In Genetic and Evolutionary Computation Conference (GECCO 2004), pages 761--773. Springer, 2004. LNCS 3102.

Crossref

Google Scholar

Cited By

View all

Lai XZhou Y(2023)Runtime analysis of some hybrid algorithmsNeural Computing and Applications10.1007/s00521-023-08388-135:19(14153-14167)Online publication date: 23-Mar-2023
https://dl.acm.org/doi/10.1007/s00521-023-08388-1
Nguyen PSudholt DTakadama K(2018)Memetic algorithms beat evolutionary algorithms on the class of hurdle problemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205456(1071-1078)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205456
Peng XXia XLiao WGuo Z(2018)Running time analysis of the Pareto archived evolution strategy on pseudo-Boolean functionsMultimedia Tools and Applications10.1007/s11042-017-5466-377:9(11203-11217)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-5466-3
Show More Cited By

Index Terms

On the analysis of the (1+1) memetic algorithm
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Memetic algorithms beat evolutionary algorithms on the class of hurdle problems
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Memetic algorithms are popular hybrid search heuristics that integrate local search into the search process of an evolutionary algorithm in order to combine the advantages of rapid exploitation and global optimisation. However, these algorithms are not ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
More effective crossover operators for the all-pairs shortest path problem

The all-pairs shortest path problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown ...

Comments

Information & Contributors

Information

Published In

GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

July 2006

2004 pages

ISBN:1595931864

DOI:10.1145/1143997

General Chair:
Mike Cattolico
Tiger Mountain Scientific, Inc., USA

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 ACM 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO06

Sponsor:

GECCO06: Genetic and Evolutionary Computation Conference

July 8 - 12, 2006

Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
20
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lai XZhou Y(2023)Runtime analysis of some hybrid algorithmsNeural Computing and Applications10.1007/s00521-023-08388-135:19(14153-14167)Online publication date: 23-Mar-2023
https://dl.acm.org/doi/10.1007/s00521-023-08388-1
Nguyen PSudholt DTakadama K(2018)Memetic algorithms beat evolutionary algorithms on the class of hurdle problemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205456(1071-1078)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205456
Peng XXia XLiao WGuo Z(2018)Running time analysis of the Pareto archived evolution strategy on pseudo-Boolean functionsMultimedia Tools and Applications10.1007/s11042-017-5466-377:9(11203-11217)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s11042-017-5466-3
Wei KDinneen MArnold D(2014)Runtime analysis to compare best-improvement and first-improvement in memetic algorithmsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598386(1439-1446)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598386
Wei KDinneen M(2014)Hybridizing the dynamic mutation approach with local searches to overcome local optima2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900360(74-81)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900360
Wei KDinneen M(2014)Runtime analysis comparison of two fitness functions on a memetic algorithm for the Clique Problem2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900359(133-140)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900359
Gießen CAlba E(2013)Hybridizing evolutionary algorithms with opportunistic local searchProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463475(797-804)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463475
Dinneen MWei K(2013)On the analysis of a (1+1) adaptive memetic algorithm2013 IEEE Workshop on Memetic Computing (MC)10.1109/MC.2013.6608203(24-31)Online publication date: Apr-2013
https://doi.org/10.1109/MC.2013.6608203
Lin JChen Y(2013)On the effect of population size and selection mechanism from the viewpoint of collaboration between exploration and exploitation2013 IEEE Workshop on Memetic Computing (MC)10.1109/MC.2013.6608202(16-23)Online publication date: Apr-2013
https://doi.org/10.1109/MC.2013.6608202
Dinneen MWei K(2013)A (1+1) Adaptive Memetic Algorithm for the Maximum Clique Problem2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557756(1626-1634)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557756
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Memetic algorithms beat evolutionary algorithms on the class of hurdle problems

The choice of the offspring population size in the (1,λ) evolutionary algorithm

More effective crossover operators for the all-pairs shortest path problem

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations