咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Hybridizing Evolutionary Algor... 收藏

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

Hybridizing 进化算法与 ? 克服本地 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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分