组合优化问题的机器学习求解初探:以图匹配问题的研究进展为例  

Towards Machine Learning for Combinatorial Optimization: a Methodological Study on the Problem of Graph Matching

作　　者：严骏驰[1] YAN Junchi(Shanghai Jiao Tong University,Shanghai 200240)

机构地区：[1]上海交通大学,上海200240

出　　处：《中国基础科学》2022年第3期63-68,共6页China Basic Science

基　　金：科技创新2030项目(2020AAA0107600)

摘　　要：组合优化涉及离散域的带约束问题求解,在求解复杂性上极具挑战,是运筹学乃至应用数学的重要分支,且在国计民生中扮演着重要的角色。在面临大规模复杂问题(如NP难问题)时,传统的求解算法一般是基于人工设计的启发式规则和策略,大多依赖对问题特定结构的深入理解和洞察。而人工智能,特别是机器学习,则采用数据驱动的方式力图自动发现求解策略,自动生成高效求解算法,降低人工设计成本。同时,通过神经网络等模块引入显卡等硬件提高并行计算能力和计算速度。本文以NP难的图匹配问题为主线,介绍国内外近期相关研究进展,涵盖整体端到端的一次性求解模型和基于深度强化学习的贯序求解模型两个代表性求解范式,简要对比了其耗时与求解质量,并对未来发展方向做出展望。Combinatorial optimization refers to the constrained optimization in the discrete domain,which is often computationally challenging,and serves as an important branch of operation research and even applied mathematics.It also plays a more and more important role in benefiting the national economy and people’s livelihood.In face of the largescale very hard problems e.g.NP-hard ones,the traditional algorithms are often based on the expert-designed heuristics or mechanisms,which can be(heavily)dependent on the knowledge and insights on the specific problem structure at hand.By contrast,artificial intelligence,especially machine learning,opens a new way of utilizing data-driven approach to automatically discover the solving policy,leading to the design of more efficient and effective algorithms with(much)reduced human cost.Meanwhile,the introduction of neural networks enables the AI-friendly hardware like GPUs that accelerates the computing process via the high parallelization ability.This paper centers around the NP-hard graph matching problem,with a focus on the recent progress by the research group of the author,particularly including the two representative paradigms:1)one-shot solving and 2)sequential solving based on deep reinforcement learning.The quantitative performance and cost time evaluation are also briefly presented.An outlook is given in the end of the paper.

关 键 词：组合优化 机器学习 图匹配 人工智能 求解器 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]