When non-elitism outperforms elitism for crossing fitness valleys

Oliveto, Pietro S and Paixão, Tiago and Heredia, Jorge P and Sudholt, Dirk and Trubenová, Barbora (2016) When non-elitism outperforms elitism for crossing fitness valleys. In: GECCO: Genetic and Evolutionary Computation Conference, July 20 - 24, 2016, Denver, CO, USA.

[img] Text
p1163-oliveto.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2016-650-v1+1]
Download (956Kb)
Official URL: http://dx.doi.org/10.1145/2908812.2908909

Abstract

Crossing fitness valleys is one of the major obstacles to function optimization. In this paper we investigate how the structure of the fitness valley, namely its depth d and length â„“, influence the runtime of different strategies for crossing these valleys. We present a runtime comparison between the (1+1) EA and two non-elitist nature-inspired algorithms, Strong Selection Weak Mutation (SSWM) and the Metropolis algorithm. While the (1+1) EA has to jump across the valley to a point of higher fitness because it does not accept decreasing moves, the non-elitist algorithms may cross the valley by accepting worsening moves. We show that while the runtime of the (1+1) EA algorithm depends critically on the length of the valley, the runtimes of the non-elitist algorithms depend crucially only on the depth of the valley. In particular, the expected runtime of both SSWM and Metropolis is polynomial in â„“ and exponential in d while the (1+1) EA is efficient only for valleys of small length. Moreover, we show that both SSWM and Metropolis can also efficiently optimize a rugged function consisting of consecutive valleys.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: theory, Simulated annealing, Natural evolution, Runtime analysis, Strong selection weak mutation regime, Fitness valley, Metropolis algorithm, Non-elitism, Valley path
Subjects: 500 Science > 570 Life sciences; biology > 576 Genetics and evolution
Research Group: Barton Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 09 Nov 2016 14:42
Last Modified: 30 Aug 2017 07:55
URI: https://repository.ist.ac.at/id/eprint/650

Actions (login required)

View Item View Item