.png){kind=icon}
返回
Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2020.103345.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Memetic algorithms integrate local search into an evolutionary algorithm to combine the advantages of rapid exploitation and global optimisation. We provide a rigorous runtime analysis of memetic algorithms on the Hurdle problem, a landscape class of tunable difficulty with a big valley structure, a characteristic feature of many hard combinatorial optimisation problems. A parameter called hurdle width describes the length of fitness valleys that need to be overcome. We show that the expected runtime of plain evolutionary algorithms like the (1+1) EA increases steeply with the hurdle width, yielding superpolynomial times to find the optimum, whereas a simple memetic algorithm, (1+1) MA, only needs polynomial expected time. Surprisingly, while increasing the hurdle width makes the problem harder for evolutionary algorithms, it becomes easier for memetic algorithms. We further give the first rigorous proof that crossover can decrease the expected runtime in memetic algorithms. A (2+1) MA using mutation, crossover and local search outperforms any other combination of these operators. Our results demonstrate the power of memetic algorithms for problems with big valley structures and the benefits of hybridising multiple search operators. (C) 2020 Elsevier B.V. All rights reserved.
Keyword:
Search heuristics
Hybridisation
Evolutionary algorithms
Black-box optimisation
Memetic algorithms
Time complexity
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
引用论文
Selection is not required to produce invariant T-cell receptor γ-gene junctional sequences.png)
Nature
NatureIF0
PREAI
分享收藏EB-GLS: an improved guided local search based on the big valley structureMEMETIC COMPUTING
MEMETIC COMPUTINGIF2.3
PREAI
分享收藏分享收藏
查看更多内容