面向NP难的进化算法理论—近似性能与随机运行时间分析

NP-hardness covers many key problems in the field of science and engineering. Effectively solving NP-hard problems is an important topic in both mathematics and theoretical computer science. Evolutionary algorithms are one of the main methods to solve NP-hard problems in practice, which can quickly give a high-quality solution to NP-hard problems. This proposal focuses on those NP-hard problems which have important theoretical and applied value, such as TSP, 0/1KP, k-median, etc. It aims at improving the efficiency and accuracy of evolutionary algorithms when the problem is NP-hard. Using the idea of approximate algorithms and the technique of stochastic process, the proposed project will investigate the stochastic runtime and approximation performance of evolutionary algorithms. On the one hand, this project intends to build better approximation algorithms based on evolutionary algorithms; on the other hand, this project intends to improve the efficiency of evolutionary algorithms when they are employed to stochastically solve an NP-hard problem from the perspective of parameterized complexity. This will not only expand the NP-hard approximation theory, improve the accuracy and efficiency of solving complex problems in practice, but also play a theoretical role in promoting important scientific issues such as RP v.s. NP.

NP难问题涵盖了科学和工程领域中的许多关键问题。有效的解决NP难问题是数学和理论计算机科学的重要研究课题。进化算法是实际中求解NP难问题的主要方法之一，能快速地给出NP难问题的一个高质量解。本项目以进化算法在NP难问题中的应用需求为背景，从理论分析层面挖掘和提升进化算法求解NP难问题的性能—以TSP、 0/1KP、k-median等具有重要理论和应用价值的NP难问题为重点分析的问题对象，以提升进化算法的求解效率和求解精度为基本目标，结合近似算法设计思想和随机过程分析技术，重点对进化算法的随机运行时间、近似性能等关键问题展开研究。一方面，本项目拟打造基于进化算法的近似比良好的近似算法；另一方面，本项目拟从参数复杂性角度，深入挖掘进化算法随机解决NP难问题的效率。本项目能进一步扩充NP难的近似算法理论，提升实际求解复杂问题的精度和效率，还将对RP v.s. NP等重要科学问题起到理论助推作用。

在项目实际执行过程中，主持人选择有重要理论和实际价值的交通运输网络系统最优计算、极大极小相关聚类，以及深度神经网络参数学习等NP-难相关优化问题为研究对象，探讨相关进化算法的设计理论，研究近似比和参数运行时间等关乎算法性能的关键科学问题，给出了交通运输网络Nash均衡对系统最优的近似比（即，PoA理论），设计了极大极小相关聚类的高效近似进化算法，提出了深度神经网络参数学习的博弈方法。本项目的研究结果有助于完善相关问题的算法设计理论，有利于交通运输网络仿真与优化、机器学习，以及深度学习等领域的进一步研究发展。目前，本项目的部分研究成果已公开发表于Operations Research（一作，运筹优化顶刊，管理科学顶刊，sci和ssci，FMS A，ABS 4*，UTD24）、Mathematics of Operations Research（一作，运筹优化顶刊，应用数学顶刊，FMS A，中科院sci二区）、Mathematical Programming（一作，运筹学顶刊，应用数学顶刊，FMS A，中科院sci一区）、Theoretical Computer Science（通讯，CCF B，理论计算机重要期刊）、Asia-Pacific Journal of Operational Research（通讯， sci，运筹学知名期刊），以及AAIM（通讯，运筹管理知名国际学术会议）等运筹优化领域重要学术期刊和会议，并收获了相关领域重要学者的多次正面引用和高度评价。