2025深度学习发论文&模型涨点之——机器学习+组合优化

机器学习（ML）与组合优化（CO）的交叉研究已成为运筹学与人工智能领域的前沿方向。传统组合优化方法（如分支定界、动态规划）虽在理论上有严格的性能保证，但在处理高维、不确定性问题时往往面临计算复杂度爆炸的挑战。与此同时，机器学习技术（特别是深度强化学习与图神经网络）展现出强大的特征提取与策略泛化能力，为突破传统方法的局限性提供了新范式。

我整理了一些机器学习+组合优化【论文+代码】合集，需要的同学公人人人号【AI创新工场】发525自取。

论文精选

论文1：

[NIPS] DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization

DeepACO：用于组合优化的神经增强蚁群系统

方法

深度强化学习与蚁群优化结合：提出了一种通用框架DeepACO，利用深度强化学习自动化启发式设计，增强传统蚁群优化（ACO）算法。

神经网络作为启发式函数：使用图神经网络（GNN）作为启发式学习器，将问题实例映射到启发式度量，指导蚁群优化的解构建过程。

局部搜索与神经引导扰动结合：提出了一种新的局部搜索方法，通过神经引导的扰动帮助蚁群优化逃离局部最优解。

单一神经模型与超参数集：DeepACO使用单一神经模型和单一超参数集，在多个组合优化问题（COPs）上表现出色，无需针对每个问题定制。

创新点

性能提升：DeepACO在八个不同的组合优化问题上，使用单一神经模型和超参数集，一致优于其ACO对应算法。例如，在旅行商问题（TSP）上，DeepACO相比于传统ACO算法，平均目标值降低了约10%。

通用性增强：DeepACO能够广泛应用于多种COPs，包括路径规划、分配、调度和子集问题，无需针对每个问题进行专家设计。

探索与利用平衡：提出了三种扩展实现，包括多头解码器、带额外熵损失的训练和带额外模仿损失的训练，以更好地平衡探索和利用，进一步提升了性能。

灵活性与可扩展性：DeepACO可以轻松扩展到不同的蚁群优化变体和不同的信息素模型，例如从基于连续选择的信息素模型扩展到基于物品价值的信息素模型。

论文2：

[NIPS] Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods

优化组合问题的解采样器：策略梯度方法的景观

方法

策略梯度方法：使用深度神经网络作为解生成器，通过策略梯度方法进行训练，以逐步获得更好的解分布。

熵正则化：引入熵正则化来优化目标函数，使优化过程更加平稳，避免梯度消失问题。

快速/慢速混合生成器：提出一种快速/慢速混合生成器，通过结合快速收敛和保持非平凡方差的组件，解决梯度消失问题。

理论框架：建立了一个理论框架，分析了策略梯度方法在组合优化中的有效性，包括解生成器的表达能力、参数数量和优化景观。

创新点

性能提升：通过熵正则化和快速/慢速混合生成器，显著提高了策略梯度方法在组合优化问题上的性能。例如，在Max-Cut问题的小规模实例（15个节点）上，使用正则化目标的模型能够100%找到最优解，而未正则化的模型仅能找到约65%的最优解。

理论保证：提供了理论证据，证明了在广泛的组合优化问题类别中，存在具有多项式参数数量且优化景观良好的解生成器。

优化景观改善：通过熵正则化和混合生成器，设计了一个“准凸”的优化目标，使得梯度下降能够有效地收敛到全局最优解。

普适性：该方法适用于多种组合优化问题，包括Max-Cut、Min-Cut、Max-k-CSP、最大权重二分图匹配和旅行商问题。

论文3：

The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights

机器学习用于组合优化竞赛（ML4CO）：结果与见解

方法

机器学习增强求解器：通过机器学习模型替换传统组合优化求解器中的关键启发式组件，以提高求解器性能。

三个挑战任务：竞赛包含三个任务：寻找最佳可行解（原始任务）、生成最紧的最优性证明（对偶任务）和选择合适的求解器配置（配置任务）。

数据驱动的算法设计：利用历史数据训练机器学习模型，以适应特定问题分布，提高求解效率和解的质量。

统一API接口：通过基于Python的Ecole库提供的类似OpenAI Gym的API，使参与者能够与求解器进行交互。

创新点

性能提升：在多个基准测试中，使用机器学习增强的求解器相比于传统求解器，在寻找最佳可行解、生成最优性证明和配置求解器参数方面表现出显著提升。例如，在平衡物品放置问题上，获胜的机器学习方法相比于基线方法，将原始积分指标降低了约40%。

数据驱动的优化：通过从历史数据中学习模式和规律，机器学习模型能够自动调整求解器的行为，以适应特定问题的结构，减少了手动调优的工作量。

多任务优化：竞赛涵盖了从寻找可行解到证明最优性以及配置求解器的多个方面，展示了机器学习在组合优化中的多功能性和潜力。

实践相关性：竞赛所使用的数据集来源于实际应用，如大规模能源分配网络、工作负载分配和海运库存路由，验证了机器学习方法在现实世界问题中的适用性。