求解網(wǎng)絡(luò)最大流問(wèn)題的信念傳播算法

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

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

0 引 言

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

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

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

1 基本知識(shí)

1.1 因子圖

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

(1)

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

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

圖1 因子圖對(duì)應(yīng)關(guān)系

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

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

(2)

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

z*=argmaxz∈{0,1}n

(3)

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

BP是用于在圖模型中近似MAP分配的迭代啟發(fā)式算法。BP是一個(gè)迭代過(guò)程，利用和-積算法實(shí)現(xiàn)信息的傳遞。傳遞的信息被分為兩類：變量到函數(shù)節(jié)點(diǎn)的信息、函數(shù)節(jié)點(diǎn)到變量的信息，每次迭代有如下信息傳遞

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

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

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

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

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

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

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

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

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

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

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

輸出：因子圖模型

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

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

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

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

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

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

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

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

圖4 圖G對(duì)應(yīng)因子圖模型

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

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

3 最大流信念傳播算法

3.1 信念傳播算法方程

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

(4)

(5)

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

(6)

(7)

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

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

(8)

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

(9)

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

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

3.3 最大流信念傳播算法

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

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

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

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

(2)調(diào)用算法1，將問(wèn)題映射為因子圖對(duì)應(yīng)的問(wèn)題。

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

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

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

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

4 數(shù)值實(shí)驗(yàn)及分析

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

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

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

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

圖5 算法收斂

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

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

圖6 不同w收斂性對(duì)比

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

圖7 不同m收斂性對(duì)比

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

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

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

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

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

圖8 BP、EK、F-F算法收斂性對(duì)比

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

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

5 結(jié)束語(yǔ)

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

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

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