Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis

用于优化的进化近似算法：算法设计和复杂性分析

• 批准号: EP/I010297/1
• 负责人: Xin Yao
• 金额: $ 61.22万
• 依托单位: University of Birmingham
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2011
• 资助国家: 英国
• 起止时间: 2011 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FI010297%2F1
• 关键词: Evolutionary; Approximation; Algorithms; Optimisation; Algorithm

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.

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

项目成果

Dynamic selection of evolutionary operators based on online learning and fitness landscape analysis

• DOI: 10.1007/s00500-016-2126-x
• 发表时间: 2016-04
• 期刊: Soft Computing
• 影响因子: 4.1
• 作者: Pietro A. Consoli;Yi Mei;Leandro L. Minku;X. Yao

Stochastic Ranking Algorithm for Many-Objective Optimization Based on Multiple Indicators

基于多指标的多目标优化随机排序算法

• DOI: 10.1109/tevc.2016.2549267
• 发表时间: 2016-12-01
• 期刊: IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
• 影响因子: 14.3
• 作者: Li, Bingdong;Tang, Ke;Yao, Xin
• 通讯作者: Yao, Xin

An efficient local search heuristic with row weighting for the unicost set covering problem

• DOI: 10.1016/j.ejor.2015.05.038
• 发表时间: 2015-11
• 期刊: Eur. J. Oper. Res.
• 作者: Chao Gao;Xin Yao;T. Weise;Jinlong Li

Design and Analysis of Schemes for Adapting Migration Intervals in Parallel Evolutionary Algorithms.

并行进化算法中适应迁移间隔的方案的设计和分析。

• DOI: 10.1162/evco_a_00153
• 发表时间: 2015
• 期刊: Evolutionary computation
• 影响因子: 6.8
• 作者: Mambrini A

On the Easiest and Hardest Fitness Functions

• DOI: 10.1109/tevc.2014.2318025
• 发表时间: 2012-03
• 期刊: IEEE Transactions on Evolutionary Computation
• 影响因子: 14.3
• 作者: Jun He;Tianshi Chen;X. Yao