When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys
Pietro S. Oliveto, Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, Barbora Trubenová · 2016
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 l, influence the runtime of different strategies for crossing these valleys. We present a runtime comparison between the 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.