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

P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 80 (2018) 1604–1633.

Download
OA 691.25 KB

Journal Article | Published | English
Author
; ; ; ;
Abstract
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.
Publishing Year
Date Published
2018-05-01
Journal Title
Algorithmica
Volume
80
Issue
5
Page
1604 - 1633
IST-REx-ID

Cite this

Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica. 2018;80(5):1604-1633. doi:10.1007/s00453-017-0369-2
Oliveto, P., Paixao, T., Pérez Heredia, J., Sudholt, D., & Trubenova, B. (2018). How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica, 80(5), 1604–1633. https://doi.org/10.1007/s00453-017-0369-2
Oliveto, Pietro, Tiago Paixao, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” Algorithmica 80, no. 5 (2018): 1604–33. https://doi.org/10.1007/s00453-017-0369-2.
P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “How to escape local optima in black box optimisation when non elitism outperforms elitism,” Algorithmica, vol. 80, no. 5, pp. 1604–1633, 2018.
Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2018. How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica. 80(5), 1604–1633.
Oliveto, Pietro, et al. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” Algorithmica, vol. 80, no. 5, Springer, 2018, pp. 1604–33, doi:10.1007/s00453-017-0369-2.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:08:14Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar