Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

在过去的二十年中，许多进化算法（EAs）被提出，包括蚁群优化、粒子群优化和人工免疫系统，以解决NP-hard组合优化问题。已经发表了许多论文。在现实世界中应用这些算法的一些商业成功也有报道。然而，绝大多数此类研究依赖于计算实验。目前对遗传算法的理论研究主要局限于遗传算法和进化策略，特别是对非种群遗传算法的研究。对于其他类型的ea，如蚁群优化、人工免疫系统和分布算法的估计，关于计算复杂性的严谨结果很少。近年来有限的理论分析主要集中在求解优化问题的精确最优解的ea运行时分析上。由于ea不期望有效地找到任何NP-hard问题的所有实例的精确最优解，因此这里的基本研究挑战是研究ea可以找到哪种NP-hard优化问题的近似解，这是本提案的主题。我们的重点将是从理论上分析什么类型的问题可以使用什么类型的ea近似而有效地解决，以及为什么。我们对问题特征和算法特征（如选择、突变和交叉）之间的关系特别感兴趣。正如Papadimitriou和Steiglitz在他们1998年出版的《组合优化：算法和复杂性》一书中指出的那样：发展数学方法来解释和预测这些启发式的性能是当今优化和算法领域面临的最重要的挑战之一。将ea作为近似算法进行分析的理论研究很少。这个项目非常冒险，试图通过将传统的理论计算机科学和进化计算结合在一起来解决理论问题。它将研究四种基于群体的ea，包括遗传算法、人工免疫算法、蚁群优化和分布估计算法。之所以在提案中选择这些算法，是因为它们在现实世界中都获得了成功，而且需要了解是什么让它们在某些问题上取得了成功，而在其他问题上却没有成功，以及它们在理论上是否真的不同（或者这些算法之间的根本区别是什么，如果有的话）。两个重要的优化问题，即调度和路由，将在提案中作为案例研究。这两个问题不同，但密切相关。调度是1966年研究的第一个近似算法问题，在现实世界中有着广泛的应用。路由是另一个在交通、公用事业和通信网络中大量应用的难题，我们在这些领域有一些研究经验。所提出的研究的预期结果将加深我们对进化近似算法为何、如何以及何时显著工作的理解。

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.