Hybridizing Evolutionary Algorithms with Opportunistic Local Search

Christian Gießen

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

Abstract

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
Pages797-804
ISBN (Print)978-1-4503-1963-8
DOIs
Publication statusPublished - 2013
EventGenetic and Evolutionary Computation Conference (GECCO 2013) - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013
http://www.sigevo.org/gecco-2013/

Conference

ConferenceGenetic and Evolutionary Computation Conference (GECCO 2013)
CountryNetherlands
CityAmsterdam
Period06/07/201310/07/2013
Internet address

Keywords

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

Cite this

Gießen, C. (2013). Hybridizing Evolutionary Algorithms with Opportunistic Local Search. In Proceedings of the 15th annual conference on Genetic and evolutionary computation (GECCO'13) (pp. 797-804). Association for Computing Machinery. https://doi.org/10.1145/2463372.2463475