6-4 浅谈组合优化问题求解中的机器学习方法.pdf

1、浅谈组合优化问题求解中的机器学习方法南开大学计算机学院 蔡庆琼 01组合优化问题02机器学习方法03求解组合优化的机器学习算法04未来研究方向目录 组合优化问题组合优化问题组合优化领域一些基本问题求解组合优化问题的传统方法组合优化问题4旅行售货商问题TSP(Traveling salesman problem)组合优化问题5组合优化问题在实际中的应用图片来源：Recent Advances in Integrating，Machine Learning and Combinatorial Optimization，AAAI 2021组合优化问题6组合优化问题(Combinatorial Opt

2、imization Problem,COP)是一类在离散状态下求极值的最优化问题，数学模型为：min().()0 其中()为目标函数，()为约束条件，为决策变量，表示离散的决策空间，为有限个点组成的集合。例如：（TSP问题）给定一个完全图G，顶点集V(G)=0,1,.,n-1，边权重：()，求=01(),(+1).0,1,.,n-1上的置换组合优化问题7P问题：可以用确定性算法在多项式时间内解决的问题。NP问题：可以在多项式时间内验证解是否正确的问题。NP-complete(NPC)问题：它是一个NP问题，同时所有的NP问题都能在多项式时间内约化到它。如果这种问题如果存在多项式时间的算法，那么

3、所有NP问题都是多项式时间可解的，即P=NP；NP-hard问题：所有NP问题都能在多项式时间内约化到它，但它不一定是一个NP问题。少数组合优化问题是P问题，如最小生成树、最短路；大多数组合优化问题没有精确的多项式时间算法；许多组合优化问题是NP-hard的，如TSP、MVC等。组合优化领域一些基本问题8背包问题(Knapsack Problem,KP)背包问题涉及一个具有有限容量的背包以及一个具有个物品的集合=1,2,，其中每件物品都有一个重量 和一个价值，不失一般性，假设,+,=1,且=1。可行解集合由物品子集组成，中的物品总重量不超过，最大化目标函数为()=。旅行商问题(Travelli

4、ng Salesman Problem,TSP)TSP问题由一组城市定义，目标是找到只访问每个城市一次并返回起点的最短(耗费最小)的路线。TSP问题定义在一个无向边权图=,上，()是边 的权重，可行解集合由构成哈密顿圈的边的子集构成，最小化目标函数()=()。组合优化领域一些基本问题9车辆路径问题(Vehicular Routing Problem,VRP)VRP问题是TSP问题的一个推广，目标是找到访问所有节点(城市)的最佳路线，使得总成本(路线长度、时间、或车辆数量等)最小化，同时保证所有其他约束(如容量)被满足。基本形式中，每个节点只被一辆有限容量的车访问一次。给定一个完全图=,，其中一

5、个节点 是depot，其余为待访问节点。边权重()反映cost。每个节点有一个需求，并且车辆的容量至少与节点需求一样大。最小顶点覆盖(Minimum Vertex Cover,MVC)给定无向图=,，找到最小节点子集，使得图中每条边 都与中至少一个节点关联。最大独立集(Maximal Independent Set,MIS)给定无向图=,，找到最大节点子集 使得中任意两点之间没有边相连，即对于中的节点对,，,。求解组合优化问题的传统方法10方法举例优缺点精确算法分支定界法、动态规划法优点：能够得到问题的精确解。缺点：问题规模扩大时，该类算法将消耗巨大的计算量，难以扩展到大规模问题。近似算法贪心

6、算法、局部搜索算法优点：在可接受的时间内得到一个近似解，能够对解的质量提供理论保证。缺点：当问题规模很大时，仍然会导致较大的计算耗时。启发式算法模拟退火算法、禁忌搜索、遗传算法、蚁群优化算法、粒子群算法优点：比精确算法、近似算法速度快。缺点：对解的质量没有保证。传统算法面临的挑战111.为一个组合优化问题设计的算法一般很难用来求解其他组合优化问题；2.对于问题的每一个实例，都要从头运行算法，迭代很多次求出解。对实例稍作修改时，也需要重新运行算法。3.现实中新出现的问题规模和复杂度都越来越大，只依靠人工设计算法越来越困难。ML+CO12机器学习算法的优势131.机器学习算法可以从大量的数据或经历