Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local Optima

作     者：Sudholt, Dirk 

作者机构：Tech Univ Dortmund D-44221 Dortmund Germany 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2011年第59卷第3期

页      面：343-368页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Deutsche Forschungsgemeinschaft (DFG) [SFB 531] German Academic Exchange Service (DAAD) 

主　　题：Evolutionary algorithms Hybridization Iterated local search Memetic algorithms Simulated annealing Runtime analysis Combinatorial optimization 

摘      要：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 to the rapid development of a highly active field of research, theory lags far behind and a solid theoretical foundation of hybrid metaheuristics is sorely needed. We are aiming at a theoretical understanding of why and when hybrid evolutionary algorithms are successful in combinatorial optimization. To this end, we consider a hybrid of a simple evolutionary algorithm, the (1+1) EA, with a powerful local search operator known as variable-depth search (VDS) or Kernighan-Lin. Three combinatorial problems are investigated: Mincut, Knapsack, and Maxsat. More precisely, we focus on simply structured problem instances that contain local optima which are very hard to overcome for many common metaheuristics. The plain (1+1) EA, iterated local search, and simulated annealing need exponential time for optimization, with high probability. In sharp contrast, the hybrid algorithm using VDS finds a global optimum in expected polynomial time. These results demonstrate the usefulness of hybrid evolutionary algorithms with VDS from a rigorous theoretical perspective.