How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism.
Autor: | Oliveto PS; 1University of Sheffield, Sheffield, S1 4DP UK., Paixão T; 2IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria., Pérez Heredia J; 1University of Sheffield, Sheffield, S1 4DP UK., Sudholt D; 1University of Sheffield, Sheffield, S1 4DP UK., Trubenová B; 2IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria. |
---|---|
Jazyk: | angličtina |
Zdroj: | Algorithmica [Algorithmica] 2018; Vol. 80 (5), pp. 1604-1633. Date of Electronic Publication: 2017 Sep 06. |
DOI: | 10.1007/s00453-017-0369-2 |
Abstrakt: | 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. |
Databáze: | MEDLINE |
Externí odkaz: |
načítá se...