Speaker: Xin Yao
Chair (Full Professor) of Computer Science at the University of Birmingham, UK
Time: 10:00 am, Oct. 13
Place: Room 1501, East Guanghua Tower
Abstract:
The evolutionary computation field has progressed significantly and steadily in the last decade. Numerous applications of evolutionary algorithms (EAs) in the real world have been reported. However, theoretical analyses of EAs are still lagging behind successful applications. It is still unclear when an EA is expected to work well and why. This talk will introduce drift analysis as an intuitive approach to analysing EAs. In particular, we will analyse the computational time complexity of EAs on combinatorial optimisation problems. This study brings the new research field of evolutionary computation much closer to classical theoretical computer science, and hence promotes crossfertilisation between the two fields. Some of the key issues addressed in this talk include: (1) when is a problem hard for a given EA? (2) when is a population useful in problemsolving? (3) under what conditions can an EA solve a given problem in polynomial run time? (4) how good is an EA in finding approximate solutions?
Selected References:
[1] J. He and X. Yao, ``Drift Analysis and Average Time Complexity of Evolutionary Algorithms,'' Artificial Intelligence, 127(1):5785, March 2001. (Erratum in 140(1):245248, September 2002.)
[2] J. He and X. Yao, ``From an Individual to a Population: An Analysis of the First Hitting Time of PopulationBased Evolutionary Algorithms,'' IEEE Transactions on Evolutionary Computation, 6(5):495511, October 2002. (According to Essential Science Indicators$^{SM}$, the number of citations this paper received places it in the top 1% within its field.)
[3] J. He and X. Yao, ``Towards an analytic framework for analysing the computation time of evolutionary algorithms,'' Artificial Intelligence, 145(12):5997, April 2003.
[4] Other papers: http://www.cs.bham.ac.uk/~xin/journal_papers.html
