In this paper we introduce some techniques for the analysis of time complexity of evolutionary algorithms (EAs) based on a finite search space. The Markov property and the decomposition of a matrix are employed for the exact analytic expressions of the mean first hitting times that EAs reach the optimal solutions (FHT-OS). Dynkin’s formula, one-step increment analysis and some other probability methods are adopted for the lower and upper bounds of the mean FHT-OS. The theory of a non-negative matrix, including the Perron–Frobenius theorem, the Jordan standard form, etc., are applied for the convergence of EAs. In addition, some techniques for time complexity and convergence of general adaptive EAs are also involved in this paper. Finally, the theoretical results obtained in this paper are verified effectively by applying them to the analysis of a typical evolutionary algorithm, (1 + 1)-EA.
BeyerHG (2001) The Theory of Evolutionary Strategies. Heidelberg: Springer-Verlag.
2.
ChenTHeJSunGChenGYaoX (2009) A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Transactions on Systems, Man, and Cybernetics39: 1092–1106.
3.
DingLXBiYZ (2007) About the Computation Time of Evolutionary Algorithms. In: WangY (eds) Lecture Notes in Artificial Intelligence. Vol 4456, Heidelberg: Springer-Verlag, 209–219.
4.
DingLXYuJH (2006) Some analysis about the time complexity of evolutionary algorithms. Neural, Parallel and Scientific Computation14: 51–68.
5.
DingLXYuJH (2007) Some theoretical results about the asymptotic behaviors of evolutionary algorithms. In: WangY (eds) Lecture Notes in Artificial Intelligence. Vol 4456, Heidelberg: Springer-Verlag, 156–166.
6.
DingLXYuJH (2008) About the Computation Time of Adaptive Evolutionary Algorithms. In: KangL (eds) Lecture Notes in Computer Science. Vol 5370, Heidelberg: Springer-Verlag, 669–679.
7.
DingLXZengSY (2007) About the Limit Behaviors of the Transition Operators Associated with EAs. In: KangL (eds) Lecture Notes in Computer Science. Vol 4683, Heidelberg: Springer-Verlag, 112–121.
8.
DrosteSJansenTWegenerI (1998) A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for linear functions with Boolean inputs. Evolutionary Computation6: 185–196.
9.
DrosteSJansenTWegenerI (2002) On the analysis of the (1 + 1) evolutionary algorithms. Theoretical Computer Science276: 51–81.
10.
EibenAERudolphG (1999) Theory of evolutionary algorithms: a bird’s eye view. Theoretical Computer Science229: 3–9.
11.
EwensWJ (2004) Population Genetics: A Mathematics Theory. New York: Springer-Verlag.
12.
GarnierJKallelL (2000) Statistical distribution of the convergence time of evolutionary algorithms for long path problems. IEEE Transactions on Evolutionary Computation4: 16–30.
13.
GarnierJKallelLSchoenauerM (1999) Rigorous hitting times for binary mutations. Evolutionary Computation7: 173–203.
14.
HeJKangL (1999) On the convergence rates of genetic algorithms. Theoretical Computer Science229: 23–39.
15.
HeJReevesCWittCYaoX (2007) A note on problem difficulty measures in black-box optimization: Classification, realizations and predictability. Evolutionary Computation15: 58–68.
16.
HeJYaoX (2001) Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence127: 57–85.
17.
HeJYaoX (2002) From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms. IEEE Trans. on Evolutionary Computation6: 495–511.
18.
HeJYaoX (2003) Towards an analytic framework for analyzing the computation time of evolutionary algorithms. Artificial Intelligence145: 59–97.
19.
HeJYaoX (2004) A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing3: 21–35.
20.
MeynSPTweedieRL (1996) Markov Chains and Stochastic Stability, 3rd ed. New York: Springer-Verlag.
21.
NixAEVoseMD (1992) Modeling genetic algorithms with Markov chain. Annals of Mathematics in Artificial Intelligence5: 79–88.
22.
OlivetoPSHeJYaoX (2007) Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing4: 281–293.
23.
OlivetoPSWittC (2008) Simplified drift analysis for proving lower bounds in evolutionary computation. In: RudolphG (eds) Proceedings of the 10th International Conference on Parallel Problem Solving from Nature. Springer-Verlag, Heidelberg, pp. 82–91.
24.
RabaniYRabinovichYSinclairA (1998) A computational view of population genetics. Random Structures and Algorithms12: 313–334.
25.
RudolphG (1996) How mutation and selection solve long path problems in polynomial expected time. Evolutionary Computation4: 195–205.
26.
RudolphG (1997) Convergence Properties of Evolutionary Algorithms. Hamburg: Verlag Dr. Kovač.
27.
RudolphG (1998) Finite Markov chain results in evolutionary computation: A tour d’Horizon. Fundamenta Informaticae35: 67–89.
28.
SasakiGHHajekB (1988) The time complexity of maximum matching by simulated annealing. Journal of the ACM35: 387–403.
29.
SchmittFRothlaufF (2001) On the importance of the second largest eigenvalue on the convergence rate of genetic algorithms. In: BeyerH (eds) Proceedings of GECCO-2001. San Francisco, CA: Morgan Kaufmann, 559–564.
30.
SuzukiJ (1995) A Markov chain analysis on simple genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics25: 655–659.
31.
VoseMD (1999) The Simple Genetic Algorithms: Foundations and Theory. Cambridge, MA: The MIT Press.
32.
WittC (2006) Runtime analysis of the (μ + 1)-EA on simple pseudo-Boolean functions. Evolutionary Computation14: 65–86.
33.
YuYZhouZ (2008) A new approach to estimating the expected first hitting time of evolutionary algorithms. Artificial Intelligence172: 1809–1832.
34.
ZhouYHeJNieQ (2009) A comparative runtime analysis of heuristic algorithms for satisfiability problems. Artificial Intelligence173: 240–257.
