research-article

Memetic algorithms with variable-depth search to overcome local optima

Author:

Dirk SudholtAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 787 - 794

https://doi.org/10.1145/1389095.1389251

Published: 12 July 2008 Publication History

Abstract

Variable-depth search (shortly VDS) is well-known as Lin-Kernighan strategy for the TSP and Kernighan-Lin for graph partitioning. The basic idea is to make a sequence of local moves and to freeze all moved combinatorial objects to prevent the search from looping. VDS stops when no further local move is possible and returns a best found solution.

We analyze memetic algorithms with VDS for three binary combinatorial problems: Mincut, Knapsack, and Maxsat. More precisely, we focus on simply structured problem instances containing local optima that are very hard to overcome. Many common trajectory-based algorithms fail to find a global optimum: the (1+1)EA, iterated local search, and simulated annealing need exponential time with high probability. However, memetic algorithms using VDS easily manage to find a global optimum in expected polynomial time. These results strengthen the usefulness of memetic algorithms with VDS from a theoretical perspective.

References

[1]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.

Digital Library

[2]

S. Droste, T. Jansen, and I. Wegener. A natural and simple function which is hard for all evolutionary algorithms. In Proc. of IECON '2000, pages 2704--2709. IEEE Press, 2000.

[3]

S. Fischer. A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model. In Proc. of GECCO '04, pages 1100--1112. Springer, 2004.

[4]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Theoretical analysis of diversity mechanisms for global exploration. In Proc. of GECCO '08, to appear.

Digital Library

[5]

O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of STACS '03, pages 415--426. Springer, 2003.

Digital Library

[6]

W. E. Hart, N. Krasnogor, and J. E. Smith, editors. Recent Advances in Memetic Algorithms. Springer, 2004.

[7]

H. Ishibuchi, T. Yoshida, and T. Murata. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation, 7(2):204--223, 2003.

Digital Library

[8]

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

Digital Library

[9]

T. Jansen and I. Wegener. A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation. Theor. Comput. Sci., 386(1-2):73--93, 2007.

Digital Library

[10]

M. Jerrum and G. B. Sorkin. The metropolis algorithm for graph bisection. Discrete Appl. Math., 82(1-3):155--175, 1998.

Digital Library

[11]

B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Tech J., 49(2):291--307, 1970.

[12]

S. Lin and B. W. Kernighan. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21:498--516, 1973.

Digital Library

[13]

H. R. Lourenço, O. Martin, and T. Stützle. Iterated local search. In Handbook of Metaheuristics, pages 321--353. Kluwer Academic Publishers, Norwell, MA, 2002.

[14]

N. Mladenović and P. Hansen. Variable neighborhood search. Computers & OR, 24(11):1097--1100, 1997.

Digital Library

[15]

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, 4(3):281--293, 2007.

[16]

C. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

[17]

M. Stoer and F. Wagner. A simple min cut algorithm. In Proc. of ESA '94, pages 141--147, 1994.

Digital Library

[18]

D. Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO '05, pages 1161--1167. ACM Press, 2005.

Digital Library

[19]

D. Sudholt. Local search in evolutionary algorithms: the impact of the local search frequency. In Proc. of ISAAC '06, pages 359--368. Springer, 2006.

Digital Library

[20]

D. Sudholt. On the analysis of the (1+1) memetic algorithm. In Proc. of GECCO '06, pages 493--500. ACM Press, 2006.

Digital Library

[21]

I. Wegener. Complexity Theory - Exploring the Limits of Efficient Algorithms. Springer, 2005.

Digital Library

[22]

I. Wegener. Simulated annealing beats metropolis in combinatorial optimization. In Proc. of ICALP '05, pages 589--601, 2005.

Digital Library

[23]

C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS '05, pages 44--56. Springer, 2005.

Digital Library

Cited By

Moscato PCotta C(2018)An Accelerated Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-3-319-91086-4_9(275-309)Online publication date: 21-Sep-2018
https://doi.org/10.1007/978-3-319-91086-4_9
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)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
Show More Cited By

Index Terms

Memetic algorithms with variable-depth search to overcome local optima
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Hybridizing evolutionary algorithms with opportunistic local search
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

There is empirical evidence that memetic algorithms (MAs) can outperform plain evolutionary algorithms (EAs). Recently the first runtime analyses have been presented proving the aforementioned conjecture rigorously by investigating Variable-Depth Search,...
Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima
Special Issue: Theory of Evolutionary Computation

Hybridizing evolutionary algorithms with local search has become a popular trend in recent years. There is empirical evidence for various combinatorial problems where hybrid evolutionary algorithms perform better than plain evolutionary algorithms. Due ...
Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima

Hybridizing evolutionary algorithms with local search has become a popular trend in recent years. There is empirical evidence for various combinatorial problems where hybrid evolutionary algorithms perform better than plain evolutionary algorithms. Due ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
250
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moscato PCotta C(2018)An Accelerated Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-3-319-91086-4_9(275-309)Online publication date: 21-Sep-2018
https://doi.org/10.1007/978-3-319-91086-4_9
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)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
Sudholt D(2011)Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local OptimaAlgorithmica10.5555/3118791.311928659:3(343-368)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.5555/3118791.3119286
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Sudholt D(2010)Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local OptimaAlgorithmica10.1007/s00453-009-9384-259:3(343-368)Online publication date: 9-Jan-2010
https://doi.org/10.1007/s00453-009-9384-2
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6
Friedrich TOliveto PSudholt DWitt C(2009)Analysis of diversity-preserving mechanisms for global exploration*Evolutionary Computation10.1162/evco.2009.17.4.1740117:4(455-476)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1162/evco.2009.17.4.17401
Sudholt D(2009)The impact of parametrization in memetic evolutionary algorithmsTheoretical Computer Science10.1016/j.tcs.2009.03.003410:26(2511-2528)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.03.003
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.

Figures

Tables

Media

View Table of Conten