Many interesting real-world optimisation problems, which possibly affect everybody's everyday life directly or indirectly, are intractable to be solved to optimality and in full generality (NP-hard). These include, for example, finding the best course timetable within a school that maximises the usage of resources while meeting the conflicting preferences of all parties involved. A second example is finding the best routes for the fleet of buses of the transportation system of a city that guarantee a good service in terms of frequency, coverage and connections, while minimising costs.

In the last two decades, many bio-inspired meta-heuristics of general applicability, including evolutionary algorithms, ant colony optimization, particle swarm optimization and artificial immune systems, have been proposed to tackle NP-hard combinatorial optimization problems. There are plenty of experimental studies showing that these meta-heuristics can produce efficiently good quality solutions most of the times. However, theoretical studies of bio-inspired meta-heuristics are rare and mainly restricted to very simple forms of evolutionary algorithms. Theory is important because it gives us accurate and deeper understanding of why, how and when evolutionary algorithms and other bio-inspired meta-heuristics work effectively. This knowledge, in turn, may be used to inform and guide the design of new algorithms and lead to their successful applications to new combinatorial optimisation problems.

The theoretical analysis in recent years has primarily concentrated on the analysis of the computation time required to find the exact optimal solution to an optimization problem as the problem size increases. Since evolutionary algorithms are not expected to find exact optimal solution to all instances of any NP-hard problem efficiently, a fundamental open research challenge is to study what kind of approximation solutions evolutionary algorithms and other bio-inspired meta-heuristics can find to NP-hard optimisation problems. Two prominent authorities in the field of Combinatorial Optimisation -- 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." The challenge remains current, if not bigger, today.

The "Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis" is an EPSRC funded project that aims to analyse theoretically and computationally what types of problems can be solved approximately and efficiently using what kind of evolutionary algorithms and bio-inspired meta-heuristics, and why. In particular, the project intends to investigate the relationship between problem characteristics and algorithmic features (such as selection, mutation and crossover). Four types of population- based bio-inspired meta-heuristic are considered for investigation: evolutionary algorithms, artificial immune algorithms, ant colony optimization and estimation of distribution algorithms. Two important optimization problems -- scheduling and routing -- are used as case studies.