Hybridizing Evolutionary Algorithms with Opportunistic Local Search

Christian Gießen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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, VDS for short (Sudholt, 2008). Sudholt raised the question if there are problems where VDS performs badly. We answer this question in the affirmative in the following way. We analyze MAs with VDS, which is also known as Kernighan-Lin for the TSP, on an artificial problem and show that MAs with a simple first-improvement local search outperform VDS. Moreover, we show that the performance gap is exponential. We analyze the features leading to a failure of VDS and derive a new local search operator, coined Opportunistic Local Search, that can easily overcome regions of the search space where local optima are clustered. The power of this new operator is demonstrated on the Rastrigin function encoded for binary hypercubes. Our results provide further insight into the problem of how to prevent local search algorithms to get stuck in local optima from a theoretical perspective. The methods stem from discrete probability theory and combinatorics.
Original languageEnglish
Title of host publicationProceedings of the 15th annual conference on Genetic and evolutionary computation (GECCO'13)
PublisherAssociation for Computing Machinery
Publication date2013
ISBN (Print)978-1-4503-1963-8
Publication statusPublished - 2013
Event2013 Genetic and Evolutionary Computation Conference - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013


Conference2013 Genetic and Evolutionary Computation Conference
Internet address


  • Memetic Algorithms
  • Local Search
  • Variable-Depth Search
  • Opportunistic Local Search
  • Kernighan-Lin
  • Runtime Analysis


Dive into the research topics of 'Hybridizing Evolutionary Algorithms with Opportunistic Local Search'. Together they form a unique fingerprint.

Cite this