这两年机器学习求解组合优化问题领域取得了显著的进展。ICLR、ICML、NeurIPS等顶会都有多篇成果发表。
 

组合优化：它是一种寻找一组变量的最佳组合的方法，以最小化或最大化一个目标函数。组合优化问题通常具有大量的状态和选择，需要在有限的时间内找到最优解。这类问题广泛存在于计算机科学、数学、经济学、工程等领域，如旅行商问题、最短路问题、资源分配问题等。
 

机器学习：它关注于从数据中学习出模式，以便进行预测或分类。机器学习方法包括监督学习、无监督学习和强化学习等，能够处理和分析大量的数据集。   整理了一些值得学习的最新成果分享，论文以及开源代码也列上了，方便同学们复现

我给大家准备了10种创新思路和源码，一起来看有需要的搜索人人人人人人人工重号（AI科技探寻）免费领取

论文1

标题：

Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching

可撤销深度强化学习与亲和力正则化用于抗异常值的图匹配

方法：

• 可撤销深度强化学习（RGM）：提出了一种基于深度强化学习的图匹配方法，通过序贯节点匹配方案自然适应选择性内点匹配策略，避免匹配异常值。

• 可撤销动作框架：设计了一种可撤销动作机制，允许代理在匹配过程中撤销之前的错误决策，提高灵活性。

• 亲和力正则化：提出了一种基于二次近似的亲和力正则化技术，通过为匹配分数引入惩罚项，避免匹配异常值。

• 关联图表示：将输入图对转换为关联图，将图匹配问题转化为组合优化问题，利用关联图的结构信息进行学习。

创新点：

• 序贯节点匹配：通过序贯决策自然选择内点对应关系，避免匹配异常值，相比传统一次性匹配方法，能够更好地处理异常值问题。

• 可撤销动作机制：允许代理在匹配过程中撤销错误决策，实验表明其性能优于现有的局部重写框架，能够有效提高匹配精度。

• 亲和力正则化：通过二次近似技术对亲和力分数进行正则化，避免匹配异常值，实验表明该方法能够显著提高匹配的鲁棒性，F1 分数相比传统方法提升了约 4%。

• 后端求解器学习：专注于学习图匹配的后端求解器，与现有的前端特征学习方法正交，可以进一步提升前端学习求解器的性能。

论文2

标题：

SurCo: Learning Linear Surrogates for Combinatorial Nonlinear Optimization Problems

SurCo：学习线性代理用于组合非线性优化问题

方法：

• 线性代理成本学习（SurCo）：提出了一种学习线性代理成本的方法，通过线性代理求解器输出对原始非线性成本函数最优的解。

• 端到端训练：通过反向传播通过线性代理求解器，优化代理成本，结合梯度下降方法进行端到端训练。

• SurCo 变体：提出了三种变体，包括 SurCo-zero（针对单个非线性问题）、SurCo-prior（针对问题分布）和 SurCo-hybrid（结合分布和问题特定信息）。

• 理论分析：通过理论分析，证明了预测代理成本比直接预测最优解具有更好的样本复杂度。

创新点：

• 线性代理求解：通过学习线性代理成本，利用高效的组合求解器解决非线性优化问题，相比直接优化非线性成本，SurCo-zero 在多个实际问题中找到了更好的解。

• 离线训练与在线优化：SurCo-prior 通过离线训练学习代理成本模型，避免了在线优化的高计算成本，SurCo-hybrid 进一步通过在线微调提升性能。

• 样本复杂度优化：理论分析表明，预测代理成本的方法比直接预测最优解具有更小的 Lipschitz 常数，从而降低了样本复杂度。

• 性能提升：在嵌入表分片、逆光子设计和非线性路径规划等实际问题中，SurCo 的性能优于现有的最先进方法，例如在嵌入表分片中，SurCo-zero 的延迟比基线方法降低了约 10%。

论文3

标题：

Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver

面向约束组合优化的量子机器学习：量子 QAP 求解器

方法：

• 量子神经网络（QAP-QNN）：提出了一种量子神经网络，将 QAP 转化为受约束的顶点分类任务，通过量子电路学习每个顶点的特征表示。

• 节点排列不变性：设计了排列不变的量子神经网络，确保网络输出与顶点排列顺序无关。

• 辅助约束层：通过量子电路显式建模 QAP 的匹配约束，确保解的可行性。

• 量子感知机层：使用参数化的量子电路作为量子感知机，学习每个顶点的特征表示。

创新点：

• 量子神经网络：提出了第一个用于解决约束组合优化问题的量子神经网络，能够学习到比传统方法更优的解。

• 节点排列不变性：通过量子感知机层和辅助约束层的设计，确保了网络的排列不变性，提高了模型的泛化能力。

• 性能提升：在图匹配和旅行商问题上，QAP-QNN 的性能优于现有的经典和量子方法，例如在图匹配任务中，QAP-QNN 的准确率比传统方法提高了约 10%。

• 量子优势：展示了量子计算在解决约束组合优化问题中的潜力，为未来量子机器学习在该领域的应用提供了新的方向

论文4

标题：

DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization

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

方法：

• 神经增强蚁群优化（DeepACO）：提出了一种基于深度强化学习的蚁群优化框架，自动设计启发式规则，增强现有蚁群优化算法。

• 启发式学习器：通过图神经网络（GNN）学习问题特定的启发式规则，指导蚁群优化的解构造过程。

• 神经引导的局部搜索（NLS）：结合局部搜索和神经引导的扰动，优化解的质量并避免局部最优。

• 多头解码器和熵损失：提出多头解码器和熵损失，增强探索能力，平衡探索与利用。

创新点

• 自动启发式设计：通过深度强化学习自动设计启发式规则，减少了人工设计的复杂性和依赖性，相比传统蚁群优化方法，DeepACO 在多个组合优化问题上的性能提升了约 10%。

• 通用性：DeepACO 是一种通用的神经增强框架，能够应用于多种组合优化问题，包括路径规划、调度和子集选择问题。

• 性能提升：在旅行商问题（TSP）和车辆路径问题（CVRP）等经典组合优化问题上，DeepACO 的性能优于现有的蚁群优化算法和专门的神经组合优化方法。

• 灵活性：DeepACO 可以扩展到不同的信息素模型，并且能够通过简单的调整适应不同的问题规模和类型。