Title:   How Powerful Is Your Evolutionary Algorithm

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 cross-fertilisation 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 problem-solving? (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):57-85, March 2001. (Erratum in 140(1):245-248, September 2002.)
 [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. (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(1-2):59-97, April 2003.
 [4] Other papers: http://www.cs.bham.ac.uk/~xin/journal_papers.html

 Bio Sketch of the Speaker:
Xin Yao is a Chair (Full Professor) of Computer Science at the University of Birmingham, UK, and a Distinguished Visiting Professor of the University of Science and Technology of China (USTC) in Hefei, China. He is the Director of CERCIA (the Centre of Excellence for Research in Computational Intelligence and Applications, http://www.cercia.ac.uk) at the University of Birmingham, UK, which is specialised in applied research and knowledge transfer. He is an IEEE Fellow and a Distinguished Lecturer of IEEE Computational Intelligence Society. He won the 2001 IEEE Donald G. Fink Prize Paper Award, IEEE Transactions on Evolutionary Computation Outstanding 2008 Paper Award (bestowed in 2010), 2010 BT Gordon Radley Award for Best Author of Innovation (2nd Prize), and many other best paper awards. He was a Cheung Kong Scholar (Changjian Chair Professor) and the Editor-in-Chief (2003-08) of IEEE Transactions on Evolutionary Computation. He is an associate editor or editorial board member of 12 international journals, and the editor of the World Scientific book series on "Advances in Natural Computation". He currently serves as the Vice President for Publications of the IEEE Computational Intelligence Society. He has been invited to give more than 60 keynote/plenary speeches at international conferences. His major research interests include evolutionary computation and neural network ensembles.