[發明專利]一種基于圖深度學習的圖組合優化問題求解方法

在審

• 申請號: 202110553836.4
• 申請日: 2021-05-20
• 公開（公告）號: CN113205181A
• 公開（公告）日: 2021-08-03
• 發明（設計）人: 杜海舟;嚴宗
• 申請（專利權）人: 上海電力大學
• 主分類號: G06N3/04
• 分類號: G06N3/04;G06N3/08
• 代理公司: 南京禹為知識產權代理事務所(特殊普通合伙) 32272
• 代理人: 王曉東

本發明公開了一種基于圖深度學習的圖組合優化問題求解方法，包括：獲取輸入圖信息并進行預處理，得到所述輸入圖的每一個頂點與權值相關的特征，通過分析關于Steiner樹的貪心算法得到更新后的矩陣X；基于編碼?處理?解碼的架構構建圖神經網絡，將更新后的矩陣X作為所述圖神經網絡的輸入，得到表示頂點信息的隱藏向量并進行深度強化學習訓練；利用貪心算法根據強化學習訓練后的圖神經網絡選擇當前狀態下價值最大的頂點，完成圖組合優化問題的求解。本發明能夠快速，準確的尋找最佳路徑，簡化求解過程，達到理想效果。

技術領域

本發明涉及圖組合優化問題的技術領域，尤其涉及一種基于圖深度學習的圖組合優化問題求解方法。

背景技術

在應用數學和理論計算機領域中，組合優化是指在具有某些特性的有限集合中，按某種目標找出一個最優子集的一類數學規劃方法。組合優化問題多種多樣，其中NP-hard問題為組合優化問題中最難以解決的一部分，如背包問題，售貨員問題，最大覆蓋集問題，最小Steiner樹問題等等。發展至今，解決這類問題的算法也層出不窮，大致分為精確算法，近似算法，啟發式算法，智能優化算法四個部分。雖然上述的一些算法在求解NP-hard問題時具有一定的可行性，但對于每一種算法又有其劣勢與不足之處，比如精確算法時間復雜度較高，近似解在大規模問題上誤差增大，啟發式和智能優化算法設計過程又很復雜。

近些年來由于圖神經網絡的發展，大部分組合優化問題都可以抽象成圖的形式進行求解，圖神經網絡可以很好的利用圖結構特征，頂點特征，在一些實驗上取得比傳統方法更好的結果，但當前已知圖神經網絡的圖嵌入技術過于原始，無法緊湊的編碼節點相關和路徑相關的信息。

發明內容

本部分的目的在于概述本發明的實施例的一些方面以及簡要介紹一些較佳實施例。在本部分以及本申請的說明書摘要和發明名稱中可能會做些簡化或省略以避免使本部分、說明書摘要和發明名稱的目的模糊，而這種簡化或省略不能用于限制本發明的范圍。

鑒于上述現有存在的問題，提出了本發明。

因此，本發明解決的技術問題是：現有的求解方式是使用手工構造的啟發式算法來逼近最優解，但求解過程復雜，且效果不理想。

為解決上述技術問題，本發明提供如下技術方案：獲取輸入圖信息并進行預處理，得到所述輸入圖的每一個頂點與權值相關的特征，通過分析關于Steiner樹的貪心算法得到更新后的矩陣X；基于編碼-處理-解碼的架構構建圖神經網絡，將更新后的矩陣X作為所述圖神經網絡的輸入，得到表示頂點信息的隱藏向量并進行深度強化學習訓練；利用貪心算法根據強化學習訓練后的圖神經網絡選擇當前狀態下價值最大的頂點，完成圖組合優化問題的求解。

作為本發明所述的基于圖深度學習的圖組合優化問題求解方法的一種優選方案，其中：所述圖神經網絡的編碼網絡包括，整合當前頂點狀態和初始權重信息生成一個P維的潛在向量表示，計算公式如下：

μ_v＝relu(θ₁[s_v，t_v]+θ₂x_v)

其中，表示模型參數，relu表示非線性單元，[，]表示連接操作，x_v表示對輸入圖進行預處理后的初始頂點權值，s_v表示頂點是否被選中的狀態信息，t_v表示是否是終端頂點的狀態，μ_v表示頂點嵌入向量。

作為本發明所述的基于圖深度學習的圖組合優化問題求解方法的一種優選方案，其中：所述圖神經網絡的處理網絡包括，將獲取的所述頂點嵌入向量μ_v處過網絡進行處理，所述處理網絡通過來自鄰居節點的消息傳遞策略更新一個隱藏的頂點嵌入向量μ′_v，即處理網絡捕捉向量之間的變化，然后將它們拼接到P維向量的后面，所述隱藏的頂點嵌入向量μ′_v計算公式為：