這兩年機器學習求解組合優化問題領域取得了顯著的進展。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 可以擴展到不同的信息素模型，并且能夠通過簡單的調整適應不同的問題規模和類型。