A Rigorous Complexity Analysis of the (1 + 1) Evolutionary Algorithm for Separable Functions with Boolean Inputs
- 1 June 1998
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 6 (2) , 185-196
- https://doi.org/10.1162/evco.1998.6.2.185
Abstract
Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In this paper a rigorous theoretical complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared, and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is Θ(n ln n) for separable functions with n variables but the methods by which this result can be proven rigorously.Keywords
This publication has 3 references indexed in Scilit:
- Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithmsBiosystems, 1996
- The Science of Breeding and Its Application to the Breeder Genetic Algorithm (BGA)Evolutionary Computation, 1993
- Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter OptimizationEvolutionary Computation, 1993