报告题目：组合优化问题的机器学习求解方法

报告人: 郭田德, 中国科学院大学数学科学学院

时 间: 2019年8月6日9:00

地 点: 河南大学数学与统计学院一楼报告厅

摘 要:  

最优化是人工智能的重要的支撑学科之一，对人工智能的发展起着重要作用。反过来，人工智能又为求解最优化问题提出了新的思路。组合优化问题，特别是大规模的组合优化问题，其快速求解具有重要的理论意义和实际应用价值。为了达到快速求解的目的，一般主要是设计近似算法，这类算法都是基于问题而设计，对于相同问题的不同实例，前面实例的求解经验对后面的实例求解基本没有帮助。AlphaGo（AlphaZero）技术的成功表明，深度学习技术可以用来求解一些组合问题，并且在求解实例过程中可以通过逐步积累经验来指导未来实例的求解。

本报告首先介绍近年来已经出现的一些利用深度学习求解组合优化问题的开创性工作，包括利用循环神经网络结合有监督的训练方式求解凸包、德洛内三角剖分、二部图匹配等问题；利用强化学习，扩大求解NP-hard问题的规模，求解旅行商问题和背包问题等。然后介绍我们在这方面的最近的一些研究成果，包括利用指向型网络，结合多标签分类的思想，在有监督的训练方式下，求解点集匹配问题，并且网络模型可以直接推广求解德洛内三角剖分等带结构的组合优化问题；针对图匹配问题，我们提出矩阵对称压缩的全局特征提取以及基于双向循环神经网络的局部特征提取方式，结合Actor-Critic强化学习训练方式，在人工数据集以及实际指纹公开库中验证了模型和算法的有效性。

专家简介：

郭田德，中国科学院大学长聘教授、博士生导师。现任中国科学院大学数学科学学院常务副院长、中国科学院大数据挖掘与知识管理重点实验室副主任、中国科学院数学与系统科学研究院优化与应用研究中心副主任。国务院政府特殊津贴获得者。主持多项国家和省部级项目，包括国家高技术研究发展计划（863项目）、国家自然科学基金重点项目和面上项目、中国科学院知识创新重要方向项目、公安部重点课题和中国移动等多项横向课题等。分别获得公安部科学技术奖二等奖、北京市科学技术奖三等奖、中国运筹学应用奖一等奖、国际运筹学会运筹学发展奖(IFORS prize for OR in development)二等奖。现任中国运筹学会图论与组合分会理事长、基金委数理学部会评专家、国家科学技术奖函评和会评评审专家、北京市科学技术奖评审专家。