- Journal Article
It is known that the (1 + 1)-EA with mutation rate c/n optimizes every monotone function efficiently if c<1 , and needs exponential time on some monotone functions (HotTopic functions) if c≥2.2 . We study the same question for a large variety of algorithms, particularly for the (1+λ) -EA, (μ+1) -EA, (μ+1) -GA, their “fast” counterparts, and for the (1+(λ,λ)) -GA. We find that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the (1+(λ,λ)) -GA, this dichotomy is in the parameter cγ , which is the expected number of bit flips in an individual after mutation and crossover, neglecting selection. For the fast algorithms, the dichotomy is in m2/m1 , where m1 and m2 are the first and second falling moment of the number of bit flips. Surprisingly, the range of efficient parameters is not affected by either population size μ nor by the offspring population size λ . The picture changes completely if crossover is allowed. The genetic algorithms (μ+1) -GA and (μ+1) -fGA are efficient for arbitrary mutations strengths if μ is large enough. Show more
Journal / seriesIEEE Transactions on Evolutionary Computation
Pages / Article No.
SubjectComputational and artificial intelligence; evolutionary computation; genetic algorithms
MoreShow all metadata