Drift conditions for estimating the first hitting times of evolutionary algorithms

Abstract

For the global optimization problems with continuous variables, evolutionary algorithms (EAs) are often used to find the approximate solutions. The number of generations for an EA to find the approximate solutions, called the first hitting time, is an important index to measure the performance of the EA. However, calculating the first hitting time is still difficult in theory. This paper proposes some new drift conditions that are used to estimate the upper bound of the first hitting times of EAs for finding the approximate solutions. Two case studies are given to show how to apply these conditions to estimate the first hitting times.

Keywords:

• complexity theory
• evolutionary algorithm
• global optimization
• approximate solutions
• first hitting time

2000 AMS Subject Classification :

• 65C50

ACM Computing Classification System Code :

• G1.6

Acknowledgements

This work was supported by Self-research program for Doctoral Candidates (including Mphil-PhD) and new cross-discipline project of Wuhan University in 2008 under Grant 20082010202000002 and Grant 1081001, and the Chinese National Natural Science Foundation under Grant 60573168 and Grant 61070007 for the first two authors and by the UK Engineering and Physical Research Council under Grant (EP/C520696/1) for the third author.