Details of Grant 

EPSRC Reference:	GR/R52541/01
Title:	Average Computation Time of Evolutionary Algorithms for Combinatorial Optimisation Problems
Principal Investigator:	Yao, Professor X
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	School of Computer Science
Organisation:	University of Birmingham
Scheme:	Fast Stream
Starts:	01 September 2001	Ends:	28 February 2003	Value (£):	62,432
EPSRC Research Topic Classifications:	Artificial Intelligence Fundamentals of Computing
EPSRC Industrial Sector Classifications:	Information Technologies
Related Grants:
Panel History:
Summary on Grant Application Form
Evolutionary algorithms (EAs) have been used widely in solving a number of combinatorial optimisation problems, e.g., VLSI cell placement, routing, job-shop scheduling, cutting stocks, timetabling, etc. There have been many reported successes for some combinatorial optimisation applications. However, few theoretical results exist that analyse the average computation time of EAs for combinatorial optimisation problems. It is unclear where the EA's real power is theoretically in solving combinatorial optimisation problems. Current theoretical work on EAs are mainly centered around schema theorems, EA's convergence and convergence rate, and dynamical system models of EAs. Average computation time of EAs has only been derived for some simple artificial problems, e.g., the one-max problem. In this project, we will study the average computation time of EAs for two combinatorial optimisation problems and analyse conditions under which an EA will take at least an exponential amount of time (in problem size) to find an optimal solution and those under which it takes no more than a polynomial amount of time. Through our analytical work, we hope to develop a set of techniques that can be used to analyse a wide range of EAs for other combinatorial optimisation problems. In the analysis of algorithms, computational time complexity is an active and important area of research. This does not appear to be the case for EAs, probably due to difficulties in analysing such stochastic search algorithms. The proposed project tries to fill in this gap.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.bham.ac.uk