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%。

數據驅動的優化：通過從歷史數據中學習模式和規律，機器學習模型能夠自動調整求解器的行為，以適應特定問題的結構，減少了手動調優的工作量。

多任務優化：競賽涵蓋了從尋找可行解到證明最優性以及配置求解器的多個方面，展示了機器學習在組合優化中的多功能性和潛力。

實踐相關性：競賽所使用的數據集來源于實際應用，如大規模能源分配網絡、工作負載分配和海運庫存路由，驗證了機器學習方法在現實世界問題中的適用性。