[發(fā)明專利]一種基于圖深度學習的圖組合優(yōu)化問題求解方法

在審

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

1.一種基于圖深度學習的圖組合優(yōu)化問題求解方法，其特性在于，包括：

獲取輸入圖信息并進行預(yù)處理，得到所述輸入圖的每一個頂點與權(quán)值相關(guān)的特征，通過分析關(guān)于Steiner樹的貪心算法得到更新后的矩陣X；

基于編碼-處理-解碼的架構(gòu)構(gòu)建圖神經(jīng)網(wǎng)絡(luò)，將更新后的矩陣X作為所述圖神經(jīng)網(wǎng)絡(luò)的輸入，得到表示頂點信息的隱藏向量并進行深度強化學習訓練；

利用貪心算法根據(jù)強化學習訓練后的圖神經(jīng)網(wǎng)絡(luò)選擇當前狀態(tài)下價值最大的頂點，完成圖組合優(yōu)化問題的求解。

2.如權(quán)利要求1所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述圖神經(jīng)網(wǎng)絡(luò)的編碼網(wǎng)絡(luò)包括，

整合當前頂點狀態(tài)和初始權(quán)重信息生成一個P維的潛在向量表示，計算公式如下：

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

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

3.如權(quán)利要求1所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述圖神經(jīng)網(wǎng)絡(luò)的處理網(wǎng)絡(luò)包括，

將獲取的所述頂點嵌入向量μ_v處過網(wǎng)絡(luò)進行處理，所述處理網(wǎng)絡(luò)通過來自鄰居節(jié)點的消息傳遞策略更新一個隱藏的頂點嵌入向量μ′_v，即處理網(wǎng)絡(luò)捕捉向量之間的變化，然后將它們拼接到P維向量的后面，所述隱藏的頂點嵌入向量μ′_v計算公式為：

μ′_v＝l_θrelu[μ_v，∑_u∈N(v)(μ_v-μ_u)]

其中，N(v)表示頂點v鄰居節(jié)點的集合。

4.如權(quán)利要求1所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述圖神經(jīng)網(wǎng)絡(luò)的解碼網(wǎng)絡(luò)包括，

將圖上所有頂點的狀態(tài)∑_u∈Vμ′_u和要被添加的頂點隱藏嵌入向量μ′_v共同定義一個評價函數(shù)Q，然后將其參數(shù)化為Q(S，v；θ)，即基于整個圖的狀態(tài)和當前頂點生成頂點的價值，所述Q(S，v；θ)的計算公式為：

其中，θ₄，Q(S，v；θ)表示頂點潛在的權(quán)重。

5.如權(quán)利要求1～4任一項所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述深度強化學習包括，

采用標準的Q學習來更新所述圖神經(jīng)網(wǎng)絡(luò)參數(shù)，每一步都采用SGD優(yōu)化器去最小化均方誤差，所述均方誤差計算公式包括，

J(θ)＝(y-Q(S_t，v_t；θ))²

其中，y來自于目標網(wǎng)絡(luò)。

6.如權(quán)利要求5所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述目標網(wǎng)絡(luò)的計算公式包括，

其中，γ表示折扣率，設(shè)置在0-1之間，表示來自下一狀態(tài)的衰減程度。

7.如權(quán)利要求5所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述目標網(wǎng)絡(luò)的計算公式進一步包括，

在環(huán)境網(wǎng)絡(luò)中找到于最大Q值相對應(yīng)的頂點，計算公式如下：

v′＝argmax_v′Q(S_t+1，v′；θ)

將該計算公式代入所述目標網(wǎng)絡(luò)的計算公式，得到一個新的目標網(wǎng)絡(luò)估計，計算公式如下：

8.如權(quán)利要求1所述的基于圖深度學習的圖組合優(yōu)化問題求解方法，其特征在于：所述矩陣X包括，

通過對所述輸入圖預(yù)處理獲得圖上每一個頂點與權(quán)值相關(guān)的特征；

當每次添加一個鄰接頂點v_i時，計算所述頂點v_i與其他終端頂點的距離，采用一個矩陣來表示最短的距離：

其中，第i行和第j列的元素x_ij表示頂點v_i到終端頂點v_j的最短距離，i∈|V|表示頂點的個數(shù)V，j∈|T|表示終端頂點的個數(shù)|T|。