How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism
复制标题
如何在黑盒优化中逃离局部最优：当非精英主义胜过精英主义时
作者：
P. S. Oliveto;T. Paixão;Jorge Pérez Heredia;Dirk Sudholt;Barbora Trubenová
逃避局部最优是函数优化的主要障碍之一。使用健身景观的比喻，局部最优对应于被必须克服的健身山谷隔开的山丘。我们通过考虑它们的长度来定义一类难度可调的适应度谷，代表两个最优值之间的汉明路径及其深度，即适应度下降。对于这个函数类，我们展示了使用不同搜索策略的随机搜索算法之间的运行时比较。 (1+1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt}egin{document}$$1+1$$end{document}) EA 是一种简单且经过充分研究的进化算法它必须跨越山谷到达更高的适应点，因为它不接受恶化的举动（精英主义）。相比之下，Metropolis 算法和强选择弱突变（SSWM）算法（群体遗传学中著名的过程）都能够通过接受恶化的移动来跨越适应度谷。我们证明 (1+1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$1+1$$end{document}) EA 的运行时间关键取决于长度而非精英算法的运行时间主要取决于山谷的深度。此外，我们表明 SSWM 和 Metropolis 也可以有效地优化由连续山谷组成的崎岖函数。
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 (1+1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$1+1$$end{document}) 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 (1+1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$1+1$$end{document}) 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.
影响因子：
14.3
作者：
Jun He;Tianshi Chen;X. Yao
通讯作者：
Jun He;Tianshi Chen;X. Yao