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.
- 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
- 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,
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,
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.
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,
Available as ipl95.ps.Z.
- X. Yao (1992a), ``Finding approximate solutions to NP-hard problems by
neural networks is hard,'' Information Processing Letters,
Last update: 29 March 2003