Evolutionary computation researchers appear to use a rather different approach from ``mainstream'' computer scientists to analysing evolutionary algorithms. While most computer scientists use computational time or space complexity to characterise an algorithm's performance on a problem, most results about evolutionary algorithms are on algorithm's convergence and convergence rate. Few computational complexity results are available in evolutionary computation in spite of numerous papers on the application of evolutionary algorithms to various combinatorial optimisation problems. It is unclear whether or not evolutionary algorithms are more powerful than existing algorithms on a particular problem in terms of computational complexity. I am very interested in the complexity issue for so-called modern heuristic algorithms, including evolutionary algorithms, neural networks, tabu search, simulated annealing, etc.

- Analysis of average computation time
of evolutionary algorithms (updated on 29 April 2010)
- Final IGR Report for EPSRC Grant
(GR/R52541/01): Average Computation Time
of Evolutionary Algorithms for Combinatorial Optimisation Problems.
- 2003 CEC Special Session on Computational Time Complexity of Evolutionary Algorithm

- J. He and X. Yao, ``Towards an analytic framework for analysing
the computation time of evolutionary algorithms,''
*Artificial Intelligence*,**145**(1-2):59-97, April 2003.

Available from Elsevier as a PDF file. - J. He and X. Yao, ``From an Individual to a Population: An Analysis
of the First Hitting Time of Population-Based Evolutionary Algorithms,''
*IEEE Transactions on Evolutionary Computation*,**6**(5):495-511, October 2002.

Available fromIEEE Xplore as a PDF file. - J. He and X. Yao, ``Erratum to: Drift analysis and average time
complexity of evolutionary algorithms: : [Artificial Intelligence 127 (2001)
57-85],''
*Artificial Intelligence*,**140**(1):245-248, September 2002.

Available as a PDF file. - J. He and X. Yao, ``Maximum Cardinality Matching by Evolutionary
Algorithms,''
*Proc. of the 2002 UK Workshop on Computational Intelligence (UKCI'02)*, J. A. Bullinaria (ed.), Birmingham, UK, September 2002, pp.53-60. - J. He and X. Yao, ``Drift Analysis and Average Time
Complexity of Evolutionary Algorithms,''
*Artificial Intelligence*,**127**(1):57-85, March 2001.

Available from Elsevier website as a PDF file. - X. Yao, ``Maximum Matching on Boltzmann Machines,''
*Neural Processing Letters*,**7**(1):49-53, 1998. - X. Yao, ``A note on neural sorting networks with O(1) time
complexity,''
*Information Processing Letters*,**56**:253-254, 1995.

Available as ipl95.ps.Z. - X. Yao (1992a), ``Finding approximate solutions to NP-hard problems by
neural networks is hard,''
*Information Processing Letters*,**41**:93-98.

Last update: 29 March 2003