演化算法在多目标组合优化问题上的近似性能分析

There exist a large number of multi-objective combinatorial optimization problems in the fields of science, engineering, economics, etc. These problems are usually NP-hard even in the case of two objectives. Surprisingly, Paradimitri and Yannakakis have proven that there exists for each multi-objective (combinatorial) optimization problem an ε-approximation Pareto front of polynomial size, where ε is a constant number greater than zero. However, it is usually hard to construct such an ε-approximation Pareto front. A lot of experiments show that evolutionary algorithms (EAs) are efficient for multi-objective combinatorial optimization problems. Since multi-objective combinatorial optimization problems tend to be NP-hard, we cannot expect that EAs solve them in polynomial time. Therefore, we focus on the approximation performances of EAs on these problems. In this project, we will study the approximation performances of EAs on multi-objective combinatorial optimization problems, such as the multi-objective minimum spanning tree problem and the multi-objective traveling salesman problem, etc. We also plan to construct the framework for the approximation performance analysis of EAs on multi-objective combinatorial optimization problems. The research in this project will help us understand how EAs work and will provide guidance to the application of EAs on multi-objective combinatorial optimization problems.

多目标组合优化问题在科学、工程、经济等领域大量存在，即便是只含两个目标的多目标组合优化问题也往往是NP-难问题。令人惊讶的是，Papadimitri和Yannakakis证明，每个多目标（组合）优化问题均存在一个多项式规模的ε-近似Pareto前沿，这里，ε是大于零的常数。然而，构造这样一个ε-近似Pareto前沿通常很困难。大量实验显示演化算法在多目标组合优化问题上有效。鉴于多目标组合优化问题倾向于NP-难，我们不能期待演化算法在多项式时间内将其求解，转而关注演化算法在这类问题上能有效获得怎样的近似性能。本项目研究演化算法在多目标最小生成树、多目标旅行商等多目标组合优化问题上的近似性能，建立演化算法在多目标组合优化问题上的近似性能分析框架。本项目研究将有助于理解演化算法的工作机理并指导其在多目标组合优化问题上的应用。

大量实验显示演化算法在多目标组合优化问题上有效。鉴于多目标组合优化问题倾向于NP-难，我们不能期待演化算法在多项式时间内将其求解，转而关注演化算法在这类问题上能有效获得怎样的近似性能。.研究紧扣计划，围绕演化算法在多目标组合优化问题上的近似性能分析主题。我们分析了多目标演化算法在双目标旅行商(1,2)问题、最小权重最小标签双目标生成树问题上的性能，结果表明多目标演化算法可以在多项式平均时间内获得双目标旅行商(1,2)问题的3/2-近似Pareto前沿，在具体实例上的时间复杂度可能是多项式级别也可能是指数级别。另外，在拟布尔函数上的分析结果表明交叉操作可以降低基于分解的多目标演化算法的时间复杂度。.我们也研究了演化算法在单目标组合优化问题上的性能。在Steiner树问题、银行账户位置问题、及TSP(1,2)问题上的分析结果表明，演化算法均能在多项式平均时间内获得一定程度的近似性能，且在某些具体实例上非常有效。.我们也将研究扩展到混合算法的性能分析。在最大可满足性问题上，我们证明在最大可满足性问题的某些实例上混合算法可能获得比部分个体算法更高的成功率，而不是所有个体算法。同时，在双模态最大可满足性问题的两个实例上的分析表明，某些混合算法并不能提高成功率。.最后，我们研究了启发式算法设计与应用。我们设计了自适应并行粒子群算法，在一系列函数上的测试结果表明所提算法有效，特别是高维函数。我们使用蚁群算法快速搜索矩阵乘法中满足三元组乘积属性的三元组且使得三元组大小之积最大，实验结果表明蚁群算法比暴力算法更有效。我们还提出了结合局部搜索算法的多目标人工蜂群算法，测试结果表明所提算法有能力找到一组收敛性好且分布均匀的非支配解。.目前，项目组成员已发表（含录用）基金项目标记的学术论文10篇：7篇SCI期刊论文，2篇EI期刊论文，1篇EI议论论文。其中，1篇SCI一区，3篇SCI二区，1篇SCI三区。