How to escape local optima in black box optimisation when non elitism outperforms elitism

Oliveto, Pietro S and Paixão, Tiago and Pérez Heredia, Jorge and Sudholt, Dirk and Trubenová, Barbora (2018) How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica, 80 (5). pp. 1604-1633. ISSN 1432-0541

[img] Text
2018_Paixao_Escape.pdf - Published Version
Available under License Creative Commons Attribution.
Download (675Kb)
Official URL:


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+1) 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+1) 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.

Item Type: Article
DOI: 10.1007/s00453-017-0369-2
Uncontrolled Keywords: Population Genetics, Simulated annealing, Runtime analysis, Strong selection weak mutation regime, Metropolis algorithm, Evolutionary algorithms, black box optimisation
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: 22 Apr 2018 14:23
Last Modified: 22 Apr 2018 14:23

Actions (login required)

View Item View Item