版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.