Hitting times of local and global optima in genetic algorithms with very high selection pressure
This work provides theoretical runtime guarantees for genetic algorithms, which is incremental but useful for researchers in evolutionary computation and optimization.
The paper derived upper bounds on the expected first hitting times for local and global optima in non-elitist genetic algorithms under very high selection pressure, extending known runtime bounds to scenarios like the Canonical Genetic Algorithm without requiring constant bounds on fitness-decreasing mutation probabilities.
The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant less than one.