Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/I010297/1 - Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPI0102971.png

Professor X Yao EP/I010297/1 - Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

Principal Investigator - School of Computer Science, University of Birmingham

Scheme

Standard Research

Research Areas

Artificial Intelligence Technologies Artificial Intelligence Technologies

Maths of Computing Maths of Computing

Related Grants

EP/I009809/1

Start Date

04/2011

End Date

04/2015

Value

£469,838

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

In the last two decades, many evolutionary algorithms (EAs), including ant colony optimization, particle swarm optimization and artificial immune systems, have been proposed to tackle NP-hard combinatorial optimization problems. Many papers have been published. Some commercial successes of applying these algorithms in the real world have also been reported. However, the vast majority of such studies rely on computational experiments. Current theoretical studies of EAs are mainly restricted to genetic algorithm and evolutionary strategy, especially for non-population based EAs. Rigorous results about the computational complexity for other types of EAs, e.g. ant colony optimization, artificial immune systems and estimation of distributionalgorithms, have been few. The limited theoretical analysis in recent years has primarily concentrated on the runtime analysis of EAs in finding the exact optimal solution to an optimization problem. Since EAs are not expected to find exact optimal solution to all instances of any NP-hard problem efficiently, the fundamental research challenge here is to study what kind of approximation solutions EAs can find to NP-hard optimization problems, which is the topic of this proposal. Our focus will be on analyzing theoretically what types of problems can be solved approximately and efficiently using what kind of EAs, and why. We are particularly interested in the relationship between problem characteristics and algorithmic features (such as selection, mutation and crossover). As Papadimitriou and Steiglitz pointed out in their 1998 book on Combinatorial Optimization: Algorithms and Complexity: Developing the mathematical methodology for explaining and predicting the performance of these heuristics is one of the most important challenges facing the fields of optimisation and algorithms today. Few theoretical studies exist in anaylsing EAs as approximation algorithms. This project is highly adventurous in trying to tackle the theoretical issue by bringing traditional theoretical computer science and evolutionary computation together. It will study four types of population-based EAs, including genetic algorithms, artificial immune algorithms, ant colony optimization and estimation of distribution algorithms. They are chosen in the proposal because they are all used with success in the real world and because of the need to understand what makes them successful on some problems but not on others and whether they are really different theoretically (or what the fundamental differences are among these algorithms, if any). Two important optimization problems, i.e., scheduling and routing, will be used as case studies in the proposal. These two problems are different but strongly related. Scheduling was the first problem studied for approximation algorithms in 1966 and has wide applications in the real world. Routing is another hard problem with numerous applications in transportation, utility and communication networks, where we have some research experiences. The expected outcomes of the proposed research will deepen our understanding of why, how and when an evolutionary approximation algorithm works significantly.

Structured Data / Microdata


Grant Event Details:
Name: Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis - EP/I010297/1
Start Date: 2011-04-29T00:00:00+00:00
End Date: 2015-04-28T00:00:00+00:00

Organization: University of Birmingham

Description: In the last two decades, many evolutionary algorithms (EAs), including ant colony optimization, particle swarm optimization and artificial immune systems, have been proposed to tackle NP-hard combinatorial optimization problems. Many papers have been publi ...