When non-elitism outperforms elitism for crossing fitness valleys
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.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Department
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 Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
IST-2016-650-v1+1_p1163-oliveto.pdf
979.03 KB
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
a1896e39e4113f2711e46b435d5f3e69