Xin Yao's Research Interests: Computational Complexity

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.

Useful Links

• 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

Selected Papers

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. X. Yao, ``Maximum Matching on Boltzmann Machines,'' Neural Processing Letters, 7(1):49-53, 1998.

7. 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.

8. 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