Authors: Jansen, Thomas
Wegener, Ingo
Title: Evolutionary Algorithms - How to Cope With Plateaus of Constant Fitness and When to Reject Strings of the Same Fitness
Language (ISO): en
Abstract: The most simple evolutionary algorithm,the so-called (1+1)EA accepts a child if its fitness is at least as large (in the case of maximization) as the fittness of its parent. The variant (1 +1)*EA only accepts a child if its fitness is strictly larger than the fitness of its parent. Here two functions related to the class of long path functions are presented such that the (1 +1)EA maximizes one of it i polynomial time and needs exponential time for the other while the (1+1)*EA has the opposite behavior. These results prove that small changes of a evolutionary algorithm may change its behavior significantly. Since the (1 +1)EA and the (1 +1)*EA differ only o plateaus of constant fitness, the results also show how evolutionary algorithms behave on such plateaus. The (1 +1)EA can pass a path of constant fitness and polynomial length in polynomial time. Finally, for these functions it is shown that local performance measures like the quality gain and the progress rate do not describe the global behavior of evolutionary algorithms.
Issue Date: 2001-10-17
Provenance: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
ci96.pdfDNB197.59 kBAdobe PDFView/Open
ci96.ps913.31 kBPostscriptView/Open

This item is protected by original copyright

Items in Eldorado are protected by copyright, with all rights reserved, unless otherwise indicated.