几十年来,运筹学(OR)和机器学习(ML)一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学,尽管每个机器学习实践者都应该至少了解一些优化技术,因为每个机器学习问题本质上都是一个优化问题。在本文中,我将把运筹学和机器学习视为一个整体话题,回顾它们之间的联系,并分享一些近些年这两个领域之间协同作用的最新进展,以充分发挥两个领域的优势。 下面的图示从三个方面说明了运筹学和机器学习之间的联系:运筹学帮助训练机器学习模型,机器学习为运筹学提供输入,机器学习改进运筹学的求解方法。接下来的段落将详细阐述这三个方面。
1. 运筹学帮助训练机器学习模型 OR的核心是优化。OR学者已经开发出了许多技术来找到决策变量的最优值,以最小化或最大化优化问题的目标函数。根据优化问题是否有约束条件,优化问题可以分为有约束优化和无约束优化。根据目标函数和约束条件的形式,优化问题可以大致分为线性优化和非线性优化。 在ML中最常遇到的优化问题可能是非线性优化问题,因为在监督学习的分类任务和回归任务中,损失函数(例如交叉熵或均方误差)通常相对于ML模型的参数呈非线性形式。梯度下降算法通常能够有效地解决这些问题。如果存在正则化项,我们最终会得到一个带有约束的非线性优化问题(例如岭回归、LASSO、支持向量机)。在这种情况下,我们应用拉格朗日乘数并处理原始优化问题的拉格朗日松弛形式,这是一种典型的OR技术,用于解决复杂的约束。例如,在岭回归中,我们尝试解决以下问题:
![](/i/l/?n=23&i=blog/3196675/202305/3196675-20230519165430220-1777223839.png)
![](/i/l/?n=23&i=blog/3196675/202305/3196675-20230519165622486-1661762965.png)
![](/i/l/?n=23&i=blog/3196675/202305/3196675-20230519171050250-636444187.png)
![](/i/l/?n=23&i=blog/3196675/202305/3196675-20230519172214964-868574916.png)
以上图为例,如果在原问题的线性规划松弛问题(即LP0)的最优解中,x_1 = 2.5,我们选择对它进行分支,那么我们将在第一分支中添加 x_1 ≤ 2 的限制,第二分支中添加 x_1 ≥ 3 的限制。然后,在每个新节点中,我们求解带有新添加的约束的LP松弛问题。以上过程称为分支,我们在开发树的过程中重复此过程。在某一节点上,如果带有整数约束的决策变量都是整数,则我们到达了一个叶节点。 请注意,在搜索树时,每当我们在一个节点上遇到整数解时,我们会更新当前最优解。当前最优解提供了MIP最优目标值的上界。如果在某个节点上,LP松弛问题的最优目标值大于当前最优解,则没有必要进一步探索此节点,该节点将被剪枝。这样的剪枝过程通过消除到达树的每个叶节点的必要性,显著减少了树搜索的工作量。 然而,即使进行了剪枝,实际问题通常也非常庞大,执行基本的分支定界算法仍然非常耗时。学者们提出了几种改进分支定界算法的思路。其中一个想法是在某些节点上为LP松弛问题添加割平面。这些割平面可以排除非整数解,但不能排除整数解。通过在某些节点为线性松弛问题添加割平面,我们可以缩小线性松弛问题的可行域,使通过求解线性松弛问题找到整数解更加容易。该算法被称为分支切割法。 添加割平面是一个好的想法,但有时找到好的割平面本身就是一项不容易的任务。在这种情况下,对某些节点应用启发式算法是寻找整数解非常有用的方法。其中一个常用的启发式算法是松弛导向邻域搜索(relaxation induced neighborhood search)。这种启发式算法查看当前最佳整数解和当前节点的LP松弛问题的非整数解,固定这两个解中取值一致的决策变量的值,再将其余决策变量作为子MIP求解。 在分支界定法中,每个整数解都为原始MIP提供了最优解的一个上界(假设我们解决一个最小化问题),而在活性节点上(未被剪枝的节点)的线性松弛问题的每个非整数解都是原始MIP最优解的一个下界。因此,添加割平面有助于改善最优解的下界,应用启发式方法有助于改善最优解的上界,这两者共同帮助分支定界算法更快地收敛。 回到OR和ML之间的相互作用,利用ML改进分支定界法的核心思想是将ML应用于: 1. 学习分支——即在节点上选择哪个决策变量进行分支, 2. 学习如何切割——即如何找到有效的约束条件添加到LP松弛问题中, 3. 学习如何找到好的启发式方法 - 帮助找到更好的整数解, 4. 学习如何配置优化求解器的参数——如何配置求解器(例如,终止准则,应用启发式算法的频率),以便更快地解决问题。 我们通常需要一个大型的MIP问题实例集来训练ML模型,然后该ML模型将把其学到的应用于特定MIP问题实例。 利用ML来帮助求解MIP问题是一个新兴的研究领域,大部分工作集中在理论研究方面,而不是在商业或非商业MIP求解器中进行实际实现。可通过以下一些有用的资源,进一步了解这一领域。 1. ML4CO是一个与此领域相关的比赛,旨在鼓励参赛者使用ML解决组合优化(与整数规划概念类似)问题。该比赛设置了三个任务:原始任务、对偶任务和配置任务,每个任务专注于分支定界算法的不同方面。假设我们求解一个最小化MIP问题,原始任务要求参与者使用ML在根节点找到更好的整数解,以降低最优解的上界。对偶任务要求参与者关注如何使用ML进行分支决策,以增加最优解的下界。最后,在配置任务中,参赛者尝试使用ML为非商业求解器SCIP找到更好的参数设置,以解决MIP问题。 2. “Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon” 这篇论文对利用ML技术来解决组合优化问题的尝试进行了概述。作者总结了使用ML解决组合优化问题的两个动机:从专家给出的示范中学习,在搜索最优解的过程当中以做出决策(例如分支决策);从经验中学习,从而探索如何制定新的决策(例如分支决策)以推进最新技术。第一个概念符合模仿学习,而第二个概念更符合强化学习。本文开头给出的图示中的红色箭头展现了OR和ML之间这方面的相互作用。 3. 另一篇值得注意的论文是由Google DeepMind团队撰写的 “Solving Mixed Integer Programs Using Neural Networks”。该论文创建了一个MIP的图表示,并使用神经网络生成整数变量的部分赋值和学习如何做出分支决策。该论文在提高分支定界法的效率方面取得了有希望的结果。 在本文中,我从三个方面介绍了OR和ML之间的联系。虽然前两个方面已经有了成熟的技术在实际实现中,但是最后一个方面尽管非常有前途,仍然需要更多的研究努力来进行实际的可扩展的实现。OR和ML在本质上是密切相关的,并且随着两个领域的发展,两者将携手前进。也许将来还会有其他更有趣和令人兴奋的OR和ML之间的协同作用。 (本文由作者译自作者本人在Towards Data Science平台上发表的英文博客 “Some Thoughts on Synergies between Operations Research and Machine Learning" https://link.medium.com/RyIRzTxb0zb。欢迎关注作者的Medium平台账号以阅读有关运筹学与机器学习的最新英文博客。) 标签:协同,ML,问题,思考,MIP,优化,节点,运筹学,分支 From: https://www.cnblogs.com/currycrab/p/17405336.html