(1) The 12 month Honda project on “Evolutionary Computation Benchmarking” aims at creating a web-based system that includes a comprehensive set of benchmark problems for different types of real-world problems, from single objective optimisation to multi-objective optimisation, from unconstrained optimisation to constraint handling, from static problems to dynamic ones, etc. The web-based system will also include tutorials on how to compare different algorithms empirically on a statistically sound basis. To gain a better understanding of empirical results, a preliminary classification and characterisation of different types of benchmark problems will be given.

(2)The EPSRC project on “Computational Complexity Analysis of Evolutionary Algorithms” is a three year basic research project worth GBP291,439. In this project, we will analyse the computational time complexity of different evolutionary algorithms (EAs) in order to gain a deeper understanding of when an EA is expected to work well (or poorly) for a given problem and why. EAs have been applied widely to solve various combinatorial optimisation problems in many scientific and engineering fields. Although some EA theories exist, EA’s computational complexity is still far from being understood in depth. It is still unclear how powerful theoretically EAs are in solving combinatorial optimisation problems, and where the real theoretical power of EAs is in comparison with more traditional deterministic algorithms. A computational complexity theory for EAs will provide not only a solid foundation for EAs, but also insights and guidance in designing more efficient EAs in practice. We will produce two types of results. One is the computational complexity results of realistic EAs, not (1+1) EAs, on selected well-known combinatorial optimisation problems. The other is the complexity classes we will build. Such complexity classes enable us to characterise problems from the EA’s point of view and reveal what problems are hard (or easy) for which kind of EAs. Because EAs are often used to find good approximate solutions in practice, this project will use some of the ideas and tools in analysing approximate algorithms to study theoretically the relationship between the quality of the solutions found by an EA and the EA’s computation time. Experimental studies will be carried out to validate and complement our theoretical analysis. The expected outcomes of this project will not only deepen our understanding of how and when EAs work, but also guide the design of more efficient EAs in practice. (We have a fully funded PhD position opening for this project).