A rigorous complexity analysis of the (1+1) evolutionary algorithmfor linear functions with Boolean inputs

摘要

Evolutionary algorithms (EAs) are heuristic randomized algorithmswhich, by many impressive experiments, have been proven to behave quitewell for optimization problems of various kinds. In this paper, arigorous complexity analysis of the (1+1) evolutionary algorithm forlinear functions with Boolean inputs is given. The analysis is carriedout for different mutation rates. The main contribution of the paper isnot the result that the expected run time of the (1+1) evolutionaryalgorithm is at most Θ(n ln n) for linear functions with nvariables, but the presentation of methods showing how this result canbe proven rigorously