Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

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.

The impact of this research includes several aspects. First, there will be major impact on the research communities in evolutionary computation, operations research and theoretical computer science because the analysis of meta-heuristics, such as evolutionary algorithms, lies in the heart of these fields. Second, this research will have major impact on the principled applications of evolutionary algorithms, including genetic algorithms, ant colony optimisation, artificial immune systems and estimation of distribution algorithms, especially on scheduling and routing problems. Although the research will not produce a recipe book for the application of evolutionary algorithms, it will generate theoretically sound principles and guidelines in the design of appropriate evolutionary algorithms for a given problem. Third, this research will have an indirect impact on industrial applications of evolutionary algorithms, especially in the domains of scheduling and routing. One of the reasons that some industrialists are relunctant to use evolutionary algorithms is the perception that these algorithms are black boxes, i.e., there is not a sound theory explaining why, how and when an evolutionary algorithm works (or does not work). Through our theoretical analysis, we can answer rigorously at least some of these why, how and when questions.