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

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

0 引 言

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

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

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

1 基本知識

1.1 因子圖

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

(1)

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

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

圖1 因子圖對應關(guān)系

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

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

(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分配的迭代啟發(fā)式算法。BP是一個迭代過程，利用和-積算法實現(xiàn)信息的傳遞。傳遞的信息被分為兩類：變量到函數(shù)節(jié)點的信息、函數(shù)節(jié)點到變量的信息，每次迭代有如下信息傳遞

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

1.2 線性規(guī)劃問題與因子圖映射關(guān)系

網(wǎng)絡(luò)最大流問題是一種特殊的線性規(guī)劃問題，我們可以利用線性規(guī)劃的性質(zhì)，利用本文算法把最大流問題轉(zhuǎn)換為對應因子圖模型。

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

圖2 LP映射關(guān)系

2 因子圖轉(zhuǎn)換算法

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

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

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

算法1：因子圖轉(zhuǎn)換算法

輸入：帶權(quán)鄰接矩陣

輸出：因子圖模型

因子轉(zhuǎn)換算法步驟：

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

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

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

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

(5)獲得各個節(jié)點的權(quán)重以及節(jié)點位置信息。

具體轉(zhuǎn)化結(jié)果如圖3、圖4所示。

圖3 網(wǎng)絡(luò)流有向圖G

圖4 圖G對應因子圖模型

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

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

3 最大流信念傳播算法

3.1 信念傳播算法方程

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

(4)

(5)

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

(6)

(7)

3.2 最大流線性規(guī)劃方程

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

(8)

對于解決網(wǎng)絡(luò)最大流問題的描述函數(shù)ψv定義如下

(9)

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

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

3.3 最大流信念傳播算法

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

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

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

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

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

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

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

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

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

4 數(shù)值實驗及分析

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

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

表1 不同節(jié)點的隨機有向圖參數(shù)

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

圖5 算法收斂

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

采用不同規(guī)模的m、w，測試影響B(tài)P-MF算法運算性能的各個因素。圖6是n=10,m=17情況下，不同w尋優(yōu)效率的比較。當?shù)螖?shù)大于2時，3類權(quán)重趨于高概率收斂，迭代次數(shù)小于2時，收斂概率較低，且收斂分散。其中，w=217較w=134時算法的尋優(yōu)效率降低。w=311時，算法尋優(yōu)效果最差。可知BP-MF算法中w的不同會對算法尋優(yōu)效率產(chǎn)生一定影響。

圖6 不同w收斂性對比

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

圖7 不同m收斂性對比

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

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

表2 EK算法、F-F算法、BP-MF算法執(zhí)行結(jié)果對比

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

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

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

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

圖9 LP、BP-MFLP最優(yōu)解對比

5 結(jié)束語

組合優(yōu)化問題的研究由來已久，網(wǎng)絡(luò)最大流問題是組合優(yōu)化問題的經(jīng)典研究內(nèi)容。前人已經(jīng)關(guān)于這個問題做了一定的研究，并得出了一系列的經(jīng)驗結(jié)果。我們現(xiàn)在所做的研究都是在他們之前的基礎(chǔ)上深入所得。

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

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