中文  |  English
学术活动
当前位置 >> 首页 >> 学术活动 >> 2011
How Powerful Is Your Evolutionary Algorithm (Xin Yao)
发表时间:2011-11-29 阅读次数:980次

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

版权所有 复旦大学计算系统生物学中心 技术支持:维程互联
地址:上海市邯郸路220号