On Non-Elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau
We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions with a plateau of second-best fitness in a Hamming ball of radius r around a unique global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of non-elitist EA based on unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels
The fitness level method is an easy-to-use tool for estimating the hitting time of elitist evolutionary algorithms. Recently, linear lower and upper bounds by fitness levels have been constructed. But these bounds requir…
Evolutionary AlgorithmsOn the Easiest and Hardest Fitness Functions
The hardness of fitness functions is an important research topic in the field of evolutionary computation. In theory, the study can help understanding the ability of evolutionary algorithms. In practice, the study may pr…
Evolutionary AlgorithmsAverage Drift Analysis and Population Scalability
This paper aims to study how the population size affects the computation time of evolutionary algorithms in a rigorous way. The computation time of an evolutionary algorithm can be measured by either the expected number …
Evolutionary AlgorithmsQuantum-Enhanced Selection Operators for Evolutionary Algorithms
Genetic algorithms have unique properties which are useful when applied to black box optimization. Using selection, crossover, and mutation operators, candidate solutions may be obtained without the need to calculate a g…
Evolutionary AlgorithmsDrift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the…
Evolutionary Algorithms