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

research-article

Runtime analysis to compare best-improvement and first-improvement in memetic algorithms

Authors:

Michael J. DinneenAuthors Info & Claims

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 1439 - 1446

https://doi.org/10.1145/2576768.2598386

Published: 12 July 2014 Publication History

Abstract

In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm (MA) to solve one problem (a single fitness function), has been verified in many successful experiments. These experiments also give the observation that the local search operator that gives the best results in an MA on the same fitness function for solving a NP-hard problem is instance specific. This paper will pro- vide a theoretical evidence for this observation. In this pa- per, we will formalize the (1+1) Restart Memetic Algorithms applying two different local searches, the first-improvement and the best-improvement, respectively. We will then run them on a single fitness function to solve the Clique Prob- lem. We then show that there are two families of graphs such that, for the first family of graphs, MAs with one local search drastically outperform MAs with the other local search, and vice versa for the second family of graphs. Our study explains why using multiple local searches can outperform using a single local search in Memetic Algorithms.

References

[1]

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

Digital Library

[2]

M. J. Dinneen, Z. Y. Lin, and K. Wei, "An intelligent self-adjusting memetic algorithm for solving course scheduling problems," in 3rd International Conference on Information Science and Engineering (ICISE), vol. 1, 2011, pp. 140--144.

[3]

M. J. Dinneen and K. Wei, "A (1+1) adaptive memetic algorithm for the maximum clique problem," in Proceedings of Congress on Evolutionary Computation, CEC'13, vol. 1. IEEE, June 2013, pp. 1626--1634.

[4]

M. J. Dinneen and K. Wei, "On the analysis of a (1+1) adaptive memetic algorithm," in Proceedings of Memetic Computing, MC2013. IEEE, 2013, pp. 24--31.

[5]

C. GieBen, "Hybridizing evolutionary algorithms with opportunistic local search," in Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference, GECCO'13. ACM, 2013, pp. 797--804.

Digital Library

[6]

E. Happ, D. Johannsen, C. Klein, and F. Neumann, "Rigorous analyses of fitness-proportional selection for optimizing linear functions," in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO'08. ACM, 2008, pp. 953--960.

Digital Library

[7]

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

Digital Library

[8]

N. Krasnogor and J. Smith, "Emergence of profitable search strategies based on a simple inheritance mechanism," in Proceedings of the 2001 Genetic and Evolutionary Computation, GECCO'01, N. Krasnogor, Ed. ACM, 2001, pp. 432--439.

[9]

N. Krasnogor and J. Smith, "A tutorial for competent memetic algorithms: model, taxonomy, and design issues," IEEE Transactions on Evolutionary Computation, vol. 9, no. 5, pp. 474--488, 2005.

Digital Library

[10]

F. Neri, J. Toivanen, G. L. Cascella, and Y.-S. Ong, "An adaptive multimeme algorithm for designing HIV multidrug therapies," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 4, no. 2, pp. 264--278, Apr. 2007.

Digital Library

[11]

F. Neumann and C. Witt, Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity, 1st ed. Springer-Verlag, 2010.

Digital Library

[12]

P. S. Oliveto, J. He, and X. Yao, "Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results," International Journal of Automation and Computing, vol. 4, no. 3, pp. 281--293, 2007.

[13]

Y.-S. Ong, M.-H. Lim, N. Zhu, and K.-W. Wong, "Classification of adaptive memetic algorithms: a comparative study," Trans. Sys. Man Cyber. Part B, vol. 36, no. 1, pp. 141--152, Feb. 2006.

Digital Library

[14]

J. E. Smith, "Coevolving memetic algorithms: A review and progress report," Trans. Sys. Man Cyber. Part B, vol. 37, no. 1, pp. 6--17, Feb. 2007.

Digital Library

[15]

D. Sudholt, "On the analysis of the (1+1) memetic algorithm," in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO'06. ACM, 2006, pp. 493--500.

Digital Library

[16]

D. Sudholt, "Memetic algorithms with variable-depth search to overcome local optima," in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO'08. ACM, 2008, pp. 787--794.

Digital Library

[17]

D. Sudholt, "The impact of parametrization in memetic evolutionary algorithms," Theoretical Computer Science, vol. 410, no. 26, pp. 2511--2528, 2009.

Digital Library

[18]

K. Wei and M. J. Dinneen, "Hybridizing the dynamic mutation approach with local searches to overcome local optima," in Proceedings of Congress on Evolutionary Computation, CEC'14. IEEE, July 2014, World Congress on Computaitonal Intelligence. To appear.

[19]

K. Wei and M. J. Dinneen, "Runtime analysis comparison of two fitness functions on a memetic algorithm for the clique problem," in Proceedings of Congress on Evolutionary Computation, CEC'14. IEEE, July 2014, World Congress on Computational Intelligence. To appear.

Cited By

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://doi.org/10.1007/s00521-023-08388-1
Pardo EBlanco-Linares JVelázquez DSerradilla F(2020)Optimization of a Steam Reforming Plant Modeled with Artificial Neural NetworksElectronics10.3390/electronics91119239:11(1923)Online publication date: 16-Nov-2020
https://doi.org/10.3390/electronics9111923
Nguyen PSudholt D(2020)Memetic algorithms outperform evolutionary algorithms in multimodal optimisationArtificial Intelligence10.1016/j.artint.2020.103345(103345)Online publication date: Jun-2020
https://doi.org/10.1016/j.artint.2020.103345
Show More Cited By

Index Terms

Runtime analysis to compare best-improvement and first-improvement in memetic algorithms
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Locally-adaptive and memetic evolutionary pattern search algorithms

Recent convergence analyses of evolutionary pattern search algorithms (EPSAs) have shown that these methods have a weak stationary point convergence theory for a broad class of unconstrained and linearly constrained problems. This paper describes how ...
Memetic cooperative coevolution of Elman recurrent neural networks

Cooperative coevolution decomposes an optimisation problem into subcomponents and collectively solves them using evolutionary algorithms. Memetic algorithms provides enhancement to evolutionary algorithms with local search. Recently, the incorporation ...
Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clustering
Special issue on magnetic algorithms

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1478 pages

ISBN:9781450326629

DOI:10.1145/2576768

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Copyright © 2014 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 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
89
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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://doi.org/10.1007/s00521-023-08388-1
Pardo EBlanco-Linares JVelázquez DSerradilla F(2020)Optimization of a Steam Reforming Plant Modeled with Artificial Neural NetworksElectronics10.3390/electronics91119239:11(1923)Online publication date: 16-Nov-2020
https://doi.org/10.3390/electronics9111923
Nguyen PSudholt D(2020)Memetic algorithms outperform evolutionary algorithms in multimodal optimisationArtificial Intelligence10.1016/j.artint.2020.103345(103345)Online publication date: Jun-2020
https://doi.org/10.1016/j.artint.2020.103345
Nallaperuma SOliveto PPérez Heredia JSudholt D(2019)On the Analysis of Trajectory-Based Search AlgorithmsAlgorithmica10.1007/s00453-018-0462-181:2(858-885)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00453-018-0462-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
Nallaperuma SOliveto PHeredia JSudholt DBosman P(2017)When is it beneficial to reject improvements?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071273(1391-1398)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071273

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