4.3 Article Proceedings Paper

How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism

期刊

ALGORITHMICA
卷 80, 期 5, 页码 1604-1633

出版社

SPRINGER
DOI: 10.1007/s00453-017-0369-2

关键词

Evolutionary algorithms; Runtime analysis; Population genetics; Strong selection weak mutation regime; Metropolis algorithm; Simulated annealing; Black box optimisation

资金

  1. Engineering and Physical Sciences Research Council [EP/M004252/1] Funding Source: researchfish
  2. EPSRC [EP/M004252/1] Funding Source: UKRI

向作者/读者索取更多资源

Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The () EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the () EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据