| EPSRC Reference: |
EP/C520696/1 |
| Title: |
Computational Complexity Analysis of Evolutionary Algorithms |
| Principal Investigator: |
Yao, Professor X |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Computer Science |
| Organisation: |
University of Birmingham |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 May 2005 |
Ends: |
31 October 2008 |
Value (£): |
291,439
|
| EPSRC Research Topic Classifications: |
| Artificial Intelligence |
Fundamentals of Computing |
| Mathematical Aspects of OR |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
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.
|
|
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: |
http://www.cs.bham.ac.uk/~xin/research/ea_complexity.html |
| Further Information: |
|
| Organisation Website: |
http://www.bham.ac.uk |