Paper Info
Title
Hybridizing evolutionary algorithms with opportunistic local search
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.
Year
DOI
Venue
2013
10.1145/2463372.2463475
GECCO
Keywords
Field
DocType
artificial problem,variable-depth search,local optimum,new operator,local search algorithm,search space,simple first-improvement local search,evolutionary algorithm,aforementioned conjecture rigorously,opportunistic local search,new local search operator,local search,memetic algorithms
Memetic algorithm,Mathematical optimization,Guided Local Search,Evolutionary algorithm,Local optimum,Computer science,Rastrigin function,Operator (computer programming),Artificial intelligence,Local search (optimization),Machine learning,Iterated local search
Conference
Citations 
PageRank 
References 
4
0.48
7
Authors
1
Name
Order
Citations
PageRank
Christian Gießen1332.66