糖心TV

Speaker: Prof Xin Yao, CS@Birmingham

Location: CS1.01

Time: 11am

Title: How Powerful Is Your Evolutionary Algorithm?

Abstract: CERCIA, The University of Birmingham, UK Evolutionary Computation (EC)
has enjoyed a tremendous growth in recent years.  Many new algorithms,
techniques and applications have been proposed.  There have also been
many commercial successes of EC applications.  In comparison with a huge
number of experimental results and practical applications, the progress
in evolutionary computation theory appears to be slow. There seems to be
a perception in the wider scientific community that most EC techniques
are CPU-intensive and scale poorly. This talk will discuss the
computation time of different evolutionary algorithms for selected
combinatorial optimization problems. The aim here is to gain a better
understanding of the behaviors of different algorithms on combinatorial
optimization problems, so that insights can be gained on when a problem
is hard for which algorithm. We will first introduce some analytical
techniques that we have found to be useful in estimating evolutionary
algorithm's average computation time. Then, a few recent results will be
discussed as to when an evolutionary algorithm will have an exponential
(or polynomial) time behavior and when a population is useful. We will
also look at the issue of problem characterization in the context of
evolutionary optimization.