基于深度神经网络的大规模组合优化问题算法设计与硬件实现的研究

In recent years, solving the large-scale combinatorial optimization problems has become a research hotspot in the academia. There are many kinds of combinatorial optimization problems and a large number of combinatorial optimization problems are NP-hard problems. As a result, when the scale of problem increases to a certain extent, the existing algorithms will face two major issues. First, the deterministic algorithm cannot be solved within an acceptable time. Second, common heuristics and approximation algorithms have poor scalability and solution quality. In this background, our project will go into how to use the characteristics of deep neural networks that are good at solving complex problems and have a good scalability to design the algorithms to solve large-scale combinatorial optimization problems. So that we can overcome the current bottleneck. The project will carry out the research from three aspects. First, we will study the unified representation of different types of combinatorial optimization problems in deep neural network algorithms. Second, we will study the effects of different reinforcement learning strategies on the solution of combinatorial optimization problems and the effective combination with supervised learning. Finally, the hardware implementation of the deep neural network model will be studied, so as to realize the operation with strong versatility, good optimization effect and high portability calculation. This project aims to establish a general algorithm based on deep neural network for solving large-scale combinatorial optimization general problems and implementing the hardware of the algorithm through in-depth study of the problem. The numerical experiment proved its high efficiency, which opened up a new way for solving such problems and extending the application of neural network.

近年来，大规模组合优化问题求解成为学术界的研究热点。由于组合优化问题种类多且很多问题都属于NP-hard问题，当问题规模增大到一定程度时，现有的算法会面临两个主要问题：1）确定性算法无法在可接受的时间内求解；2）常见的启发式和近似算法扩展性差且优化程度低。在此背景下，本项目将研究如何利用深度神经网络擅于解决复杂问题、可扩展性好等特点来设计大规模组合优化问题求解算法，从而突破当前的瓶颈。项目将从三方面开展研究。1）研究组合优化问题在算法中的统一表示方法；2）研究不同强化学习策略对组合优化问题求解的影响以及与监督学习的结合方式；3）研究深度神经网络模型的硬件实现。最终实现通用性强、优化效果好和便携性高的运算。本项目旨在通过对问题的深入研究，建立一种基于深度神经网络求解大规模组合优化一般问题的通用算法并对算法进行硬件实现，通过数值实验证明其高效性，为求解此类难题和拓展神经网络应用开辟新的途径。

组合优化问题在许多研究领域都有着广泛的应用，但目前对于大规模的实际问题很难在短时间内找到近似最优解，同时缺乏解决不同类型组合优化问题的通用算法及其硬件实现。本项目针对上述存在问题，深入研究如何建立一种基于深度神经网络求解大规模组合优化一般问题的通用算法并对算法进行硬件实现。本项目取得了以下几项重要研究成果：（1）基于深度神经网络的大规模组合优化问题通用算法。将多种组合优化问题转换为统一数学模型，并进行优化。结合监督学习和强化学习来训练指针网络，提高了模型的通用性和泛化能力；（2）基于深度神经网络的最大割和最大团问题的求解算法。利用最大割和最大团等问题来验证所提出的模型的性能；（3）基于指针网络的0-1二次规划（BQP）问题的求解算法，将问题进一步扩展到了带线性约束的组合优化问题，并通过图嵌入、注意力机制、掩码机制等方法对指针网络优化，实现了基于指针网络和分层强化学习的BQP问题求解算法；（4）基于图神经网络的BQP问题的求解算法。将多种组合优化问题转换为统一的Graph模型，并采用基于图神经网络和强化学习的算法求解；（5）实现基于FPGA的深度神经网络加速器，改进了深度神经网络参数裁剪的方式，创新地提出了基于构造向量法的权重参数压缩方法。本项目的研究成果，不仅为大规模组合优化问题的求解提供了更好的算法，还为求解此类难题和拓展神经网络应用提供了新思路。