求解網絡最大流問題的信念傳播算法

左逢源，王曉峰,2+，任雪嬌，張丹丹

(1.北方民族大學 計算機科學與工程學院，寧夏 銀川 750021；2.北方民族大學 寧夏智能信息與大數據處理重點實驗室，寧夏 銀川 750021)

0 引 言

線性規劃(linear programming)是運籌學中研究、發展較成熟的一個重要分支，是一種用來輔助科研人員進行科學研究的數學方法。線性規劃問題特指目標函數和約束條件皆為線性的最優化問題，線性規劃方程用來求解問題最優解[8]。其中，網絡最大流問題是一類特殊的線性規劃問題，在線性規劃方程中用maxf*來表示目標函數，f*代表目標最大流值,各邊容量限制及節點流量守恒定律分別代表兩類約束條件。

信念傳播(belief propagation，BP)算法，又名和-積信息傳遞，是一種迭代求解概率圖模型中統計推斷問題的方法，尤其在組合優化問題的求解中有極好效果，所有信息的傳播可以并行實現[9]。BP算法以實時性以及求解精度高等優點得到了廣泛應用，如權重匹配問題[10]、最短路徑和網絡流匹配問題等[11]。BP算法主要思想定義請參見文獻[12]。過去幾年間，科研人員做了大量的研究工作來了解在組合優化條件下的BP算法性能。特別是幾類圖模型下的組合優化問題，研究了信念傳播算法的收斂性以及正確性。根據一些文獻可知有些特殊的線性規劃問題可以映射成因子圖所對應的問題模型[13],進而利用BP算法求解問題。目前，最大流問題的復雜性隨著實際問題規模的增大而增大，復雜度以指數級增長，而利用BP算法求解線性規劃問題時運算復雜度只與節點線性相關，且節點間信息傳遞并行實現，極大減少了時間復雜度，節省了人力、物力等。在許多問題的求解中得到印證，如旅途商問題[14]、最大權重匹配問題等[15]。

依上述研究，本文把最大流線性規劃問題映射為因子圖對應問題，利用不同規模帶權有向圖，隨機選取源、匯點，按照MFP的一般線性準則，給出一種求解網絡最大流問題的信念傳播算法，利用所提算法對網絡最大流問題進行實驗驗證。實驗結果表明，本算法可以解整數邊容量的網絡最大流問題，與傳統的EK、Ford-Fulkerson算法相比，本算法可以有效解決網絡最大流問題，且時間復雜度較同類算法低。由于實驗條件限制，本文算法只討論流量值為整數時的情況。

1 基本知識

1.1 因子圖

因子圖(factor graph)是將一個具有多個變量的全局函數因子分解，得到幾個局部函數的乘積，以此為基礎得到一個含有函數節點以及變量節點的圖，簡化了邊緣概率分布的計算，因子圖是一個建立在后驗概率密度函數基礎上的圖。網絡最大流問題的后驗概率密度函數是可以因式分解的，分解之后由多個因子組成，因子圖中節點間的獨立關系，使得信息更新可以并行實現。因此因子圖可被定義為n個隨機變量的聯合分布Z=[Zi]∈{0,1}n, 對于Z=[Zi]∈Ωn, 因式分解公式為[16]

(1)

式中： {φα:α∈F} 為非負函數，被稱作變量節點，F是因子的集合：F={α1,α2,…,αk}。

例如：在圖1模型中F={α1,α2,α3}的因子圖關系可以表示為[17]

圖1 因子圖對應關系

Pr[z]∝φα1(z1,z3)φα2(z1,z2,z4)φα3(z2,z3,z4)

其中，αn是變量節點由圓圈表示。zi是函數節點由方形圖表示，對變量節點有

(2)

其中，zα=[zi:i∈α] 是α的自變量，如果Pr[Z=z]>0，z被稱為有效分配，則后驗概率(MAP)分配z*為

z*=argmaxz∈{0,1}n

(3)

則Pr[z]為最大后驗概率。每個αn選擇zi的一個子集。如α1連接 {z1,z3}。

BP是用于在圖模型中近似MAP分配的迭代啟發式算法。BP是一個迭代過程，利用和-積算法實現信息的傳遞。傳遞的信息被分為兩類：變量到函數節點的信息、函數節點到變量的信息，每次迭代有如下信息傳遞

代表t時變量節點與函數節點之間的信息傳遞方程，本文第3章信念傳播算法中會具體描述。

1.2 線性規劃問題與因子圖映射關系

網絡最大流問題是一種特殊的線性規劃問題，我們可以利用線性規劃的性質，利用本文算法把最大流問題轉換為對應因子圖模型。

圖2根據文獻[18]，呈現出一種簡單的線性規劃方程與因子圖之間的映射關系，該線性規劃方程中的4個約束條件分別映射成為因子圖中4個函數節點，由方塊表示；變量x1,x2,x3被映射成因子圖中的變量節點，由圓形表示。連接關系表明了它們之間的約束關系，各節點之間相互獨立，信息進行并行傳播，極大縮減了時間復雜度。

圖2 LP映射關系

2 因子圖轉換算法

根據網絡最大流問題中的流量守恒定律以及邊流量約束等問題特性，提取當前有向圖迭代節點、各個鄰居節點以及各邊流值限制，將其映射為因子圖中的函數節點及變量節點，并獲取各個節點權重信息及節點位置信息，最后生成所對應問題的因子圖模型。

其中，有向圖中有向弧在算法中因流量變化而改變，所以我們把有向邊映射為因子圖中的變量節點；有向邊中的流量約束映射成為函數節點，例如，圖3邊X1上流量約束值為5，則對應圖4因子圖中函數節點C1的值為5，且劃分為0,1,2,3,4,5這6個流量值進行信息傳遞。有向圖中的各個節點，映射成為函數節點。有向圖G中A、D分別為源點、匯點，B、C為中間節點，X1、X2、X3、X4、X5代表各個連接弧。下面，我們給出了最大流問題對應有向圖與因子圖之間的轉換算法。

算法開始時隨機生成有向圖鄰接矩陣及各邊流量約束值。首先計算各邊流量約束條件，映射成函數節點，有向圖中的邊則映射成為對應因子圖中的變量節點，其值受函數節點Cn傳遞信息影響。B、C作為中間節點被映射成函數節點，最后獲得對應因子圖及各權重信息、節點位置信息。具體算法過程如下。

算法1：因子圖轉換算法

輸入：帶權鄰接矩陣

輸出：因子圖模型

因子轉換算法步驟：

(1)生成帶權鄰接矩陣。

(2)計算各邊流量約束條件。

(3)有向圖中的流量邊映射為因子圖中的變量節點。

(4)各邊流量約束條件映射為與變量邊相連接的函數節點，各個鄰居節點映射為函數節點。

(5)獲得各個節點的權重以及節點位置信息。

具體轉化結果如圖3、圖4所示。

圖3 網絡流有向圖G

圖4 圖G對應因子圖模型

圖3有向圖G(V,E) 中，Xn是邊集E的子集，用Cn來表示邊Xn上不同的流量約束條件。

圖4中，Ci代表各個邊的流量約束值，映射成為函數節點，B、C則代表有向圖的兩個中間節點，映射為函數節點。Xn代表各邊流值，映射為變量節點。算法由Ci函數節點傳遞約束消息，改變變量節點Xn中信息，之后由Xn與B、C傳遞消息，若一次迭代結束，則輸出當前最大流，若未達滿足收斂條件，則斷定未得到最優解，節點Xn反饋信息給Ci，Ci調整流值再次傳遞給Xn，進行下一次迭代。

3 最大流信念傳播算法

3.1 信念傳播算法方程

信念傳播算法的迭代方程為[20]

(4)

(5)

信念傳播算法節點間迭代方程定義請參照文獻[21]，若BP迭代方程收斂，則可以利用得到的一組不動點求每個變量i的取值的邊緣概率計算如下[22]

(6)

(7)

3.2 最大流線性規劃方程

最大流問題對應的有向圖G(V,E) 中，定義了f為可行流，c=[cij∶c∈E] 為邊上流量約束。現在我們根據BP算法設計如下LP方程，用來定義BP算法中描述函數

(8)

對于解決網絡最大流問題的描述函數ψv定義如下

(9)

ψv如果節點v的流入流量與流出流量相等，則函數值取1，否則為0，由描述函數具體定義。

本文將這種BP算法與最大流線性規劃方程結合的算法稱為BP-MF(belief propagation-maximum flow)算法。該算法存在正向傳播和反向傳播兩類傳播方式。正向傳播過程中，每條邊的初始概率與邊上流量大小成正比，因該算法與線性規劃方程結合，所以邊的初始信息由指數函數ewx形式定義。在反向傳播的過程中，函數節點傳給變量節點的信息需要根據其它變量節點傳遞的信息來確定，根據線性規劃方程中的容量限制條件，獲得某變量節點的概率分布，至此信息得到一次傳遞，再次利用此次獲得的信息進行下一次迭代，如此往復，直至算法收斂。

3.3 最大流信念傳播算法

算法2：求解最大流的信念傳播算法

輸入：因子圖模型，最大迭代次數t,各邊流量值w

輸出：各邊流值，最大流值

(1)隨機生成帶權有向圖。

(2)調用算法1，將問題映射為因子圖對應的問題。

(3)設置迭代次數t=1,2,3…N。

(5)調用節點間信息迭代方程，使邊上的流值朝較大方向上收斂。

(6)根據信息迭代方程，使算法按照迭代次數t進行循環迭代，當迭代t與t+1數值情況相同時，計算各邊流值，并確定各節點的信息。

(7)輸出最大流、節點信息及各邊流量值。

4 數值實驗及分析

為驗證上述所提BP-MF算法的可行性以及測試影響算法性能的各種不確定因素，進行了如下測試。其中所有算法均用Matlab實現。本文實驗以普通PC為平臺，基本配置：處理器Intel(R) Core(TM) i7，CPU 2.70 GHz，內存16 GB，64位 Windows 10操作系統。

首先驗證所提算法可行性。本文利用隨機生成數據集的方法，按照最大流問題規則將其轉化為帶權有向圖，在數值實驗中隨機選取3組較小節點規模的帶權有向圖,其中節點規模n={5，15，20}。 具體參數見表1。

表1 不同節點的隨機有向圖參數

n表示節點規模，m表示有向邊數，w表示容量總大小。圖5呈現了n={5，15，20} 時本文算法收斂情況，測試結果如圖5所示。算法運行結束后，選取收斂后的結果為有向圖的最大流，且經過的邊為有效邊，節點為有效節點。

圖5 算法收斂

圖5中，X軸表示迭代次數。Y軸表示收斂概率，t表示迭代次數。由圖5可知，各個規模下算法的收斂概率呈現曲折上升態勢，最終達到收斂。n=5時算法經過2次迭代即收斂，n=20時，算法經過4次迭代收斂。實驗結果表明，隨著節點、容量規模的增長，算法收斂性效率有所降低，但尋優質量不變。所以BP-MF算法在求解網絡最大流問題上是可行的，且極少迭代次數收斂得到最優解。

采用不同規模的m、w，測試影響BP-MF算法運算性能的各個因素。圖6是n=10,m=17情況下，不同w尋優效率的比較。當迭代次數大于2時，3類權重趨于高概率收斂，迭代次數小于2時，收斂概率較低，且收斂分散。其中，w=217較w=134時算法的尋優效率降低。w=311時，算法尋優效果最差?？芍狟P-MF算法中w的不同會對算法尋優效率產生一定影響。

圖6 不同w收斂性對比

圖7是n=15,w=236情況下，不同m對尋優效率的比較。當迭代次數大于0時，3類m收斂概率差距較小，算法逐漸收斂。其中m=19和m=25，算法收斂概率基本沒有差別，當m=31時，收斂概率較低于另外兩類，BP-MF算法尋優效率有所降低,但求解問題的最優解不變。

圖7 不同m收斂性對比

綜上所述，相同節點規模、邊規模的情況下，流值的不同對BP-MF算法尋優效率有著較大的影響，過大的流值會降低BP-MF算法的尋優效率，但不會影響算法的尋優質量。相同節點規模、容量大小的情況下，邊規模的不同不會對算法的尋優效率產生較大影響，同樣不會影響尋優結果，由于BP-MF算法各個節點相互獨立，消息傳遞并行傳遞，所需迭代時間極少。

接下來，我們根據文獻[24]中提出的EK算法、Ford-Fulkerson(F-F)算法。在規定規模n、容量w相同規模情況下，設置了幾組對比實驗，用來測試BP-MF算法性能，與BP-MF算法做收斂性測試分析，對比實驗采用5組較小規模的帶權有向圖。實驗執行結果見表2。

表2 EK算法、F-F算法、BP-MF算法執行結果對比

根據表2，可以發現，在問題規模較小時，EK算法優于BP-MF算法,能取得較好效果，由于F-F算法屬于暴力搜索，算法迭代時間較大，但總能尋到最優解。隨著問題規模的增大，BP-MF算法在時間復雜度上優于另外兩種算法，且高概率收斂，不易數據溢出，F-F算法迭代時間最大，尋優效率較低。

收斂曲線如圖8所示，為便于觀察，圖8呈現了最大流問題規模n為30后的收斂結果。當n、w達到一定規模時，3種算法尋找最優解的效率都有所下降，其中，F-F算法時間復雜度較大，EK算法由圖8曲線可知數據易溢出，不能達到收斂性要求，而BP-MF算法較其它兩種算法能取得較好的收斂效果，且算法迭代計算時間較低，優于EK算法、F-F算法。

圖8 BP、EK、F-F算法收斂性對比

最后，我們利用LP、BP-MF算法進行最優解對比測試，實驗采用45個權值較小實例圖。實驗結果如圖9所示，通過對比發現，BP-MF、LP算法在尋優的結果上相較一致，但實驗中個別現象表明，在規模n較小時，BP-MF 算法的迭代計算能力，較低于LP，隨著規模n的增大 BP-MF 算法在尋優質量和尋優能力上會優于LP。

圖9 LP、BP-MFLP最優解對比

5 結束語

組合優化問題的研究由來已久，網絡最大流問題是組合優化問題的經典研究內容。前人已經關于這個問題做了一定的研究，并得出了一系列的經驗結果。我們現在所做的研究都是在他們之前的基礎上深入所得。

針對網絡最大流問題,提出了一種基于線性規劃方程求解最大網絡流的信念傳播算法。使用特定算法把最大流線性規劃問題映射為因子圖對應的問題，利用因子圖的特性以及BP算法傳播特性，隨機選取源、匯節點進行信息傳遞，經過T次迭代后收斂得到實驗結果，并將算法收斂結果作為最大流問題結果。實驗結果表明，該算法較EK、Ford-Fulkerson算法迭代計算時間較低，尋優效率較好，所以在求解網絡最大流問題中具有較好效果。

接下來，將討論如何利用信念傳播算法更快速、更有效求解大規模網絡最大流問題以及網絡最小費用最大流問題。