（圖片來源：網(wǎng)絡(luò)）

組合優(yōu)化問題在科學(xué)和工業(yè)中普遍存在?，F(xiàn)代深度學(xué)習(xí)工具已準(zhǔn)備好以前所未有的規(guī)模解決這些問題，但結(jié)合統(tǒng)計(jì)物理學(xué)見解的統(tǒng)一框架仍然很出色。
這里，亞馬遜量子解決方案實(shí)驗(yàn)室的研究人員，展示了如何使用圖神經(jīng)網(wǎng)絡(luò)來解決組合優(yōu)化問題。
他們的方法廣泛適用于以二次無約束二元優(yōu)化問題形式出現(xiàn)的規(guī)范 NP 難問題，如最大割集、最小頂點(diǎn)覆蓋、最大獨(dú)立集，以及以多項(xiàng)式無約束二元優(yōu)化問題形式出現(xiàn)的 Ising spin glasses 及其高階推廣。
研究人員對(duì)問題哈密頓量應(yīng)用松弛策略以生成可微損失函數(shù)，然后用它來訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)，并在無監(jiān)督訓(xùn)練過程完成后對(duì)整數(shù)變量應(yīng)用簡(jiǎn)單投影。他們展示了針對(duì)典型最大割和最大獨(dú)立集問題的數(shù)值結(jié)果的方法。研究發(fā)現(xiàn)，圖神經(jīng)網(wǎng)絡(luò)優(yōu)化器的性能與現(xiàn)有的求解器相當(dāng)或優(yōu)于現(xiàn)有的求解器，能夠擴(kuò)展到超越現(xiàn)有技術(shù)水平以解決具有數(shù)百萬個(gè)變量的問題。
該研究以「Combinatorial optimization with physics-inspired graph neural networks」為題，于 2022 年 4 月 21 日發(fā)布在《Nature Machine Intelligence》。

優(yōu)化在科學(xué)和工業(yè)中無處不在。具體而言，組合優(yōu)化領(lǐng)域——在有限但往往很大的候選解集中搜索目標(biāo)函數(shù)的最小值，是優(yōu)化領(lǐng)域最重要的領(lǐng)域之一，在幾乎所有行業(yè)（包括私營(yíng)部門和公共部門）都有實(shí)用（但也有著臭名昭著的挑戰(zhàn)性）的應(yīng)用，以及運(yùn)輸和物流、電信和金融等領(lǐng)域。
盡管針對(duì)特定用例存在有效的專用算法，但大多數(shù)優(yōu)化問題仍然難以解決，尤其是在實(shí)際應(yīng)用中，問題更加結(jié)構(gòu)化，因此需要額外的步驟才能使其適應(yīng)傳統(tǒng)的優(yōu)化技術(shù)。盡管算法和計(jì)算能力都取得了顯著進(jìn)步，但實(shí)質(zhì)性但通用的改進(jìn)仍然難以捉摸，這引起了對(duì)廣泛適用且與傳統(tǒng)運(yùn)籌學(xué)工具截然不同的新優(yōu)化方法的興趣增加。
在更廣泛的物理學(xué)界，量子退火設(shè)備（如 D-Wave Systems Inc. 量子退火器）的出現(xiàn)重新激發(fā)了人們對(duì)開發(fā)用于解決離散優(yōu)化問題的啟發(fā)式方法的興趣。一方面，量子科學(xué)和技術(shù)的最新進(jìn)展激發(fā)了新經(jīng)典算法的發(fā)展，有時(shí)被稱為自然啟發(fā)或物理啟發(fā)算法，這提高了新興量子退火硬件的標(biāo)準(zhǔn)。
另一方面，在這些算法發(fā)展的同時(shí)，近年來在基于替代技術(shù)的可編程專用設(shè)備的開發(fā)方面取得了實(shí)質(zhì)性進(jìn)展，例如基于光學(xué)參量振蕩器的相干 Ising 機(jī)、基于自組織邏輯門的數(shù)字 MemComputing 機(jī)，以及基于ASIC的富士通數(shù)字退火機(jī)（ASIC，專用集成電路）。
其中一些方法面臨嚴(yán)重的可擴(kuò)展性限制。例如，在相干伊辛機(jī)中，需要在精度和變量數(shù)量之間進(jìn)行權(quán)衡，而富士通數(shù)字退火器（烘焙到 ASIC 中）目前最多可以處理 8,192 個(gè)變量。因此，尋找新的替代方法來解決大規(guī)模組合優(yōu)化問題具有極大的興趣，這遠(yuǎn)遠(yuǎn)超出了目前量子和自然啟發(fā)方法等可訪問的方法。
在深度學(xué)習(xí)社區(qū)中，圖神經(jīng)網(wǎng)絡(luò) (GNN) 在過去幾年中大受歡迎。本質(zhì)上，GNN 是專門為圖結(jié)構(gòu)數(shù)據(jù)設(shè)計(jì)的深度神經(jīng)網(wǎng)絡(luò)架構(gòu)，能夠?qū)W習(xí)節(jié)點(diǎn)、邊甚至整個(gè)圖的有效特征表示。GNN 應(yīng)用的主要示例包括社交網(wǎng)絡(luò)中的用戶分類、推薦系統(tǒng)中未來交互的預(yù)測(cè)以及分子圖的某些屬性的預(yù)測(cè)。
作為對(duì)各種現(xiàn)實(shí)世界復(fù)雜結(jié)構(gòu)數(shù)據(jù)進(jìn)行建模的便捷通用框架，GNN 已成功應(yīng)用于廣泛的問題，包括社交媒體和電子商務(wù)中的推薦系統(tǒng)、社交媒體中錯(cuò)誤信息的檢測(cè)以及 自然科學(xué)的各個(gè)領(lǐng)域，包括粒子物理學(xué)中的事件分類，僅舉幾例。
盡管存在幾種 GNN 的特定實(shí)現(xiàn)，但在其核心，GNN 通常通過聚合來自其鄰居的信息來迭代更新圖節(jié)點(diǎn)的特征，從而隨著網(wǎng)絡(luò)訓(xùn)練的進(jìn)行迭代地對(duì)圖結(jié)構(gòu)進(jìn)行局部更新。由于其可擴(kuò)展性和固有的基于圖的設(shè)計(jì)，GNN 提供了一個(gè)替代平臺(tái)，可在該平臺(tái)上構(gòu)建大規(guī)模組合啟發(fā)式。

圖示：組合優(yōu)化GNN方法示意圖。（來源：論文）
在本研究中，研究人員提出了一個(gè)高度可擴(kuò)展的基于 GNN 的求解器，以（大約）解決具有數(shù)百萬個(gè)變量的組合優(yōu)化問題。其工作原理如下：
首先，研究人員確定了根據(jù)二元決策變量 xν?∈?{0,?1} 對(duì)優(yōu)化問題進(jìn)行編碼的哈密頓量（成本函數(shù)）H，并且將此變量與無向圖 G=(V,E) 的頂點(diǎn) ν∈V 相關(guān)聯(lián) ) 頂點(diǎn)集 V={1,2,…,n} 和邊集 E={(i,j):i,j∈V} 捕獲決策變量之間的交互。
然后，研究人員將松弛策略應(yīng)用于問題哈密頓量以生成可微分損失函數(shù)，使用它對(duì) GNN 的節(jié)點(diǎn)表示進(jìn)行無監(jiān)督訓(xùn)練。GNN 遵循標(biāo)準(zhǔn)遞歸鄰域聚合方案，其中每個(gè)節(jié)點(diǎn) ν?=?1,?2,?…,?n 收集其鄰居的信息（編碼為特征向量），以計(jì)算其在層 k?=?0,?1,?… , K 的新特征向量 hkν。經(jīng)過 k 次聚合迭代后，節(jié)點(diǎn)由其轉(zhuǎn)換后的特征向量 hkν 表示，該向量捕獲節(jié)點(diǎn)的 k 跳鄰域內(nèi)的結(jié)構(gòu)信息。
對(duì)于二元分類任務(wù)，通常使用卷積聚合步驟，然后應(yīng)用非線性 softmax 激活函數(shù)將最終嵌入 hkν 縮小為一維軟（概率）節(jié)點(diǎn)分配 pν=hkν∈[0,1]。
最后，一旦無監(jiān)督訓(xùn)練過程完成，研究人員應(yīng)用投影啟發(fā)式將這些軟分配 pν 映射回整數(shù)變量 xν?∈?{0,?1}，例如使用 xν?=?int(pν)。

圖示：受物理啟發(fā)的 GNN 優(yōu)化器的端到端工作流程。（來源：論文）

論文中，研究人員在數(shù)值上展示了他們的方法以及典型 NP-hard 優(yōu)化問題的結(jié)果，例如最大割 (MaxCut) 和最大獨(dú)立集 (MIS)，結(jié)果表明基于 GNN 的方法可以與現(xiàn)有完善的求解器相媲美甚至更好， 同時(shí)廣泛適用于一大類優(yōu)化問題。
正如最近的研究所展示的那樣，當(dāng)在機(jī)器集群上以小批量方式利用分布式訓(xùn)練時(shí)，該方法的可擴(kuò)展性還開辟了研究具有數(shù)億個(gè)節(jié)點(diǎn)的前所未有的問題規(guī)模的可能性。

參考鏈接：

https://www.nature.com/articles/s42256-022-00468-6

文：ScienceAI編輯：慕一
注：本文轉(zhuǎn)自“ScienceAI”，不代表量子前哨觀點(diǎn)。