Fully-funded EPSRC PhD Studentship / Scholarship at the University of Birmingham, UK

Title: Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

Project Background

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. The theoretical study 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 an exact optimal solution to all instances of any NP-hard problem efficiently, the fundamental research challenge in this project is to study what kind of approximation solutions EAs can find to NP-hard optimization problems. 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). The expected outcomes of the proposed research will deepen our understanding of why, how and when an evolutionary approximation algorithm works significantly.

The Candidate

The successful applicant must have at least a 2.1 or above degree in computer science or a closely related field. We consider outstanding applicants from mathematics, physics and engineering as long as they have sufficient computer science background. The successful applicant must have excellent analytical and computational skills. S/he must be an excellent team player who can work independently and communicate well with others. A good knowledge of optimisation is required, especially a good understanding and practical experience with modern meta-heuristics, including evolutionary algorithms, estimation of distribution algorithms, simulated annealing and others.

The Studentship / Scholarship

Duration: Three years full-time (subject to satisfactory progress).

Payments: Living expenses: GBP13,590 per year (tax-free); plus tuition fees (GBP3,732 per year for 2011-12) fully paid.

Eligibility: Open to European Union/United Kingdom applicants only.

Deadline: The position is available immediately and will be open until it is filled.

How to Apply

For more information on the PhD programme at Birmingham: http://www.cs.bham.ac.uk/admissions/postgraduate-research/

Please apply according to the instructions given in the above website, NOT to the person below.

For technical enquiries only: Prof. Xin Yao (x.yao@cs.bham.ac.uk)