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.