When non-elitism outperforms elitism for crossing fitness valleys

P. Oliveto, T. Paixao, J. Heredia, D. Sudholt, B. Trubenova, in:, Proceedings of the Genetic and Evolutionary Computation Conference 2016 , ACM, 2016, pp. 1163–1170.

Download
OA 979.03 KB

Conference Paper | Published | English
Author
; ; ; ;
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.
Publishing Year
Date Published
2016-07-20
Proceedings Title
Proceedings of the Genetic and Evolutionary Computation Conference 2016
Page
1163 - 1170
Conference
GECCO: Genetic and evolutionary computation conference
Conference Location
Denver, CO, USA
Conference Date
2016-07-20 – 2016-07-24
IST-REx-ID

Cite this

Oliveto P, Paixao T, Heredia J, Sudholt D, Trubenova B. When non-elitism outperforms elitism for crossing fitness valleys. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016 . ACM; 2016:1163-1170. doi:10.1145/2908812.2908909
Oliveto, P., Paixao, T., Heredia, J., Sudholt, D., & Trubenova, B. (2016). When non-elitism outperforms elitism for crossing fitness valleys. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 1163–1170). Denver, CO, USA: ACM. https://doi.org/10.1145/2908812.2908909
Oliveto, Pietro, Tiago Paixao, Jorge Heredia, Dirk Sudholt, and Barbora Trubenova. “When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys.” In Proceedings of the Genetic and Evolutionary Computation Conference 2016 , 1163–70. ACM, 2016. https://doi.org/10.1145/2908812.2908909.
P. Oliveto, T. Paixao, J. Heredia, D. Sudholt, and B. Trubenova, “When non-elitism outperforms elitism for crossing fitness valleys,” in Proceedings of the Genetic and Evolutionary Computation Conference 2016 , Denver, CO, USA, 2016, pp. 1163–1170.
Oliveto P, Paixao T, Heredia J, Sudholt D, Trubenova B. 2016. When non-elitism outperforms elitism for crossing fitness valleys. Proceedings of the Genetic and Evolutionary Computation Conference 2016 . GECCO: Genetic and evolutionary computation conference 1163–1170.
Oliveto, Pietro, et al. “When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys.” Proceedings of the Genetic and Evolutionary Computation Conference 2016 , ACM, 2016, pp. 1163–70, doi:10.1145/2908812.2908909.
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:16:27Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar