何勝學(xué)

(上海理工大學(xué)管理學(xué)院,上海 200093)

單向限量最速網(wǎng)絡(luò)消息傳播模型及其進(jìn)化算法

何勝學(xué)

(上海理工大學(xué)管理學(xué)院,上海 200093)

提出了單向限量式最速網(wǎng)絡(luò)消息傳播問題,建立了該問題的數(shù)學(xué)模型,并給出了相應(yīng)的模擬進(jìn)化求解算法.通過分析單向限量式最速網(wǎng)絡(luò)消息傳播問題的特征,包括決策變量的特點(diǎn)、決策的網(wǎng)絡(luò)時(shí)空影響特殊模式及網(wǎng)絡(luò)消息分布狀態(tài)特點(diǎn),構(gòu)建了問題的最優(yōu)化模型.利用決策變量的二元取值特點(diǎn)和單一輪次信息交互模式的相對(duì)獨(dú)立性,設(shè)計(jì)了操作靈活的遺傳算法的復(fù)制、交叉和變異算子,實(shí)現(xiàn)了模型的模擬進(jìn)化求解.數(shù)值算例驗(yàn)證了模型和算法的有效性.最后總結(jié)了最速網(wǎng)絡(luò)消息傳播問題的主要可擴(kuò)展研究方向.

系統(tǒng)工程;網(wǎng)絡(luò)優(yōu)化;消息傳播;遺傳算法

隨著網(wǎng)絡(luò)信息科技的發(fā)展,網(wǎng)絡(luò)交流已成為人們?nèi)粘Ｉ畹囊徊糠?如何快速地將各種信息通過網(wǎng)絡(luò)進(jìn)行傳播成為網(wǎng)絡(luò)通訊、系統(tǒng)管理優(yōu)化以及軍事信息技術(shù)領(lǐng)域的研究熱點(diǎn)問題.及時(shí)準(zhǔn)確的大規(guī)模信息互通已成為解決諸如戰(zhàn)場(chǎng)單兵協(xié)同作戰(zhàn)、局域網(wǎng)絡(luò)最優(yōu)布線以及易損網(wǎng)絡(luò)重建等問題的瓶頸[1-4].但是,相關(guān)理論研究的滯后制約了這些領(lǐng)域的進(jìn)一步發(fā)展.

通過對(duì)單向限量最速網(wǎng)絡(luò)消息傳播問題加以嚴(yán)格的數(shù)學(xué)建模,分析該基本問題的基本約束特征,以及設(shè)計(jì)相應(yīng)的模擬進(jìn)化求解算法,為最速網(wǎng)絡(luò)消息傳播問題的深人研究建立相應(yīng)的理論基礎(chǔ).

1859年達(dá)爾文創(chuàng)立進(jìn)化論,成為人類文明歷史上的一個(gè)里程碑.遵循“生存競(jìng)爭(zhēng),優(yōu)勝劣汰”的進(jìn)化原則而設(shè)計(jì)的進(jìn)化算法主要包括遺傳算法、遺傳規(guī)劃、進(jìn)化策略和進(jìn)化規(guī)劃這4種典型方法[5-6].由于進(jìn)化算法的自適應(yīng)式搜索尋優(yōu)特征、結(jié)構(gòu)化并行的計(jì)算特征、全局優(yōu)化性及廣泛的適用性,目前已經(jīng)被成功地應(yīng)用于各種工程技術(shù)領(lǐng)域[5-11].鑒于單向限量式最速網(wǎng)絡(luò)消息問題的變量離散化特征、多階段非線性優(yōu)化特征及復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),模擬進(jìn)化算法中的遺傳算法成為解決該問題的首選工具.進(jìn)化算法中復(fù)制、交叉和變異操作能較好地適應(yīng)網(wǎng)絡(luò)消息傳播的交互特征,從而使設(shè)計(jì)的具體算法不僅構(gòu)造簡(jiǎn)潔,而且實(shí)施方便.

1 最速網(wǎng)絡(luò)消息傳播問題

假設(shè)存在n個(gè)信息源,每個(gè)信息源在信息交互未發(fā)生前,各有一個(gè)消息須向其他的n-1個(gè)信息源傳達(dá).任意一對(duì)信息源之間均存在一條信息交互通道.一個(gè)信息源至多只能同時(shí)與一個(gè)其他信息源通過信息交互通道傳達(dá)消息,信息交互是單向的,且一次交互中有消息通訊量的上限限制.假設(shè)每一次交互的時(shí)長相等,至少需要進(jìn)行多少次交互才能使所有消息最快傳至所有信息源,這就是單向限量最速網(wǎng)絡(luò)消息傳播的基本問題.

現(xiàn)給出主要的參變量定義：

i、j表示信息源i和j,i,j∈{1,2,…,n},n為信息源總數(shù);t表示是第t輪信息交互,t∈{1,2,表示信息源i和j在第t輪信息交互時(shí)是否建立交互的指標(biāo),存在信息源i向信息源j傳播消息的交互時(shí),其值為1,否則,為0;I表示所有的消息構(gòu)成的集合,即{I1,I2,…In},這里Ij表示

初始階段信息源j打算向外傳遞的信息;表示第t輪信息交互結(jié)束后信息源i已知的消息集合,≡{Ii}表示信息源i起始狀態(tài)的消息集合;δt表

示第t輪信息交互的費(fèi)用系數(shù),有0＜δt＜δt+1,?t∈{1,2,…,2n-1}成立.

如果n個(gè)信息源間每次交互只傳遞自己初始態(tài)時(shí)想傳遞的消息,那么雙向的最速網(wǎng)絡(luò)消息傳播問題退化為類似n個(gè)足球隊(duì)間的錦標(biāo)賽問題.易知,此時(shí)至少需進(jìn)行n(n-1)/2次交互.而每一輪交互中,n個(gè)信息源間至多可進(jìn)行[n/2]-次交互.n為偶數(shù)時(shí),[n/2]-等于n/2;否則,[n/2]-= (n-1)/2.考慮到n[n/2]-≥n(n-1)/2,因此,可設(shè)單向限量最速網(wǎng)絡(luò)消息傳播時(shí),t最大取值為2n.

最速網(wǎng)絡(luò)消息傳播基本問題的最優(yōu)化模型為

式中,Z為最小化加權(quán)后各輪信息交互的總次數(shù);q為單次交互中可以傳遞的消息的最大數(shù)目,滿足1≤q≤n;Uˉt-1j表示信息源j在t-1輪信息交互后,還未了解的信息集合;交集代表信息源j在t-1輪信息交互后,還未了解的信息中,已經(jīng)被信息源i了解的信息構(gòu)成的集合;而集合R(q,U)表示如果集合U的元素個(gè)數(shù)大于q,從集合U隨機(jī)取出q個(gè)元素構(gòu)成的新集合,而如果集合U的元素個(gè)數(shù)小于或等于q,R(q,U)等于集合U.

由目標(biāo)函數(shù)式(1)和約束式(2)～(10)共同構(gòu)成單向限量最速網(wǎng)絡(luò)消息傳播基本問題的規(guī)劃模型.由于0＜δt＜δt+1,?t成立,因此,信息源間的有效交互發(fā)生得越早越好,從而體現(xiàn)最速最簡(jiǎn)潔的信息交互要求.

約束式(2)表示每輪的信息交互過程中單個(gè)信息源不存在與自身的信息交互.約束式(3)表示兩個(gè)信息源之間如發(fā)生信息交互,則交互是單向的.約束式(4)和式(5)共同限制了每一個(gè)信息源在任何一輪的信息交互過程中至多只能進(jìn)行一次交互.約束式(7)表示隨著信息交互的逐輪進(jìn)行,任意信息源所知的消息只能越來越多.約束式(8)和式(9)分別表示信息源掌握消息的初始狀態(tài)和最終狀態(tài).約束式(10)表明任意可能的交互要么發(fā)生,要么沒有發(fā)生.約束式(6)表示如果某輪信息交互中兩個(gè)信息源間發(fā)生信息交互,則該輪信息交互使得兩個(gè)信息源間形成單向限量式的已知消息交互.

在上面給出的優(yōu)化模型基礎(chǔ)上,擴(kuò)展建立其他相關(guān)的最速網(wǎng)絡(luò)消息傳播問題的優(yōu)化模型將非常方便.例如考慮信息交互的雙向性,相應(yīng)的優(yōu)化模型只需將約束式(3)的不等號(hào)變?yōu)榈忍?hào)即可.當(dāng)考慮多樣化的信息源初始狀態(tài)和最終狀態(tài)時(shí),只需對(duì)約束式(8)和式(9)進(jìn)行修改即可.而如果每次信息交互的最大消息數(shù)無上限時(shí),可通過修改約束式(6)中的q值實(shí)現(xiàn).綜上,由式(1)～(10)構(gòu)成的單向限量最速網(wǎng)絡(luò)消息傳播問題的優(yōu)化模型是最速網(wǎng)絡(luò)消息傳播問題族的建?；A(chǔ).

2 模擬進(jìn)化解法設(shè)計(jì)

應(yīng)用模擬進(jìn)化計(jì)算中的遺傳算法需解決的關(guān)鍵問題包括：a.將問題的解進(jìn)行編碼,構(gòu)成遺傳代次中的個(gè)體;b.生成合理的初始群體;c.設(shè)計(jì)方法用以計(jì)算遺傳個(gè)體的適應(yīng)度;d.設(shè)計(jì)相應(yīng)的復(fù)制、交叉和變異算子.現(xiàn)對(duì)上述問題進(jìn)行具體分析,然后給出完整的模擬進(jìn)化求解算法實(shí)施步驟.最速網(wǎng)絡(luò)消息傳播問題的變量只能取值0交互只需由滿足條件的變量,?i＜j構(gòu)成的n(n-1)/2個(gè)變量組合就可代表該輪的信息交互模式.因此,將所有2n輪的上述變量組合依次合并,就可以構(gòu)成一個(gè)滿足算法要求的個(gè)體編碼.

生成一個(gè)滿足約束式(2)～(5)的可行消息交互或1,正好符合遺傳算法中染色體的二進(jìn)制編碼要求.同時(shí)由約束式(2)和式(3)可知,任何一輪的信息模式,即遺傳個(gè)體,需要4個(gè)步驟.首先,生成n個(gè)信息源的一個(gè)隨機(jī)排列.可采取遺傳算法的輪盤選擇原理逐次減少信息源構(gòu)成等分輪盤進(jìn)行信息源選擇,從而形成n個(gè)信息源的一個(gè)隨機(jī)排列.接著,從前向后依次從生成的隨機(jī)排列中選擇兩個(gè)信息源,構(gòu)成一個(gè)可能的有向交互.總共有[n/2]-對(duì)可能的信息源對(duì),即交互.隨后,對(duì)每一個(gè)可能交互生成一個(gè)在0和1之間服從均勻分布的隨機(jī)變量值ε[0,1].比較ε[0,1]與依據(jù)當(dāng)前的輪次t給定一個(gè)判別值εt的大小,如果ε[0,1]＞εt,使對(duì)應(yīng)的可能交互實(shí)現(xiàn);否則,對(duì)應(yīng)的可能交互不予實(shí)現(xiàn).εt的值大于0,小于1.εt隨著輪次t的增大而增大.最后,將所有輪次的交互模式組合,即得到一個(gè)滿足約束式(2)～(5)的可行消息交互模式.重復(fù)上述步驟,可以得到遺傳算法的初始群體.

遺傳個(gè)體的適應(yīng)度計(jì)算分為兩步.第1步依據(jù)問題的目標(biāo)函數(shù)式(1)計(jì)算總的交互次數(shù).由于不是所有的個(gè)體(即信息交互模式)均能使得系統(tǒng)的終態(tài)滿足式(9),因此需要在第2步計(jì)算一個(gè)相應(yīng)的懲罰項(xiàng).對(duì)懲罰項(xiàng)的計(jì)算分兩種情況.第1種情況為至少存在一個(gè)信息源掌握所有消息.因?yàn)?未能掌握所有消息的信息源可以通過與已經(jīng)掌握所有消息的信息源進(jìn)行交互,從而了解所有消息,所以未能掌握所有消息的信息源的未了解的消息總數(shù)可以作為懲罰項(xiàng),加權(quán)后加人該遺傳個(gè)體的適應(yīng)度.第2種情況為所有信息源在n輪交互結(jié)束后,均未能了解所有的消息.此時(shí),首先確定生成一個(gè)掌握所有消息的信息源需進(jìn)行的一個(gè)可行的交互次數(shù),即找到掌握消息最多的信息源,用消息總數(shù)n減去該信息源已經(jīng)掌握的消息數(shù),并除以消息傳播上限q.將這個(gè)可行的交互次數(shù)與(n-1)個(gè)信息源未知消息總量除以消息傳播上限q的值相加,得到的結(jié)果可以作為懲罰項(xiàng),加權(quán)后加人該遺傳個(gè)體的適應(yīng)度.

針對(duì)最速網(wǎng)絡(luò)消息傳播問題設(shè)計(jì)的遺傳算法的復(fù)制算子與常用的復(fù)制算子無異.既可以采取簡(jiǎn)單的依據(jù)適應(yīng)度大小的比例刪除法,也可以利用輪盤選擇原理進(jìn)行選擇.但與常用的交叉和變異算子不同,對(duì)于最速網(wǎng)絡(luò)消息傳播問題,為了滿足生成的新個(gè)體的可行性,交叉和變異應(yīng)以交互的輪次為單位,進(jìn)行對(duì)應(yīng)輪次的交互模式互換和以輪次為單位的染色體變異.這樣可以使新生成的個(gè)體滿足除約束式(9)外的其它基本約束.

求解最速網(wǎng)絡(luò)消息傳播基本問題的遺傳算法基本步驟如下：

步驟1初始化.確定種群規(guī)模N,選擇復(fù)制比例θ,交叉概率Pc,變異概率Pm和最大迭代次數(shù)N=100;隨機(jī)生成θ=0.85個(gè)個(gè)體作為初始種群Pc=0.75;置迭代指標(biāo)Pm=0.15為0.

步驟2個(gè)體適應(yīng)度計(jì)算.考慮不滿足約束式(8)的加權(quán)懲罰項(xiàng),計(jì)算常數(shù)T=50中各個(gè)體的適應(yīng)度.

步驟3種群進(jìn)化.

步驟3.1(復(fù)制) 依據(jù)適應(yīng)度的大小選取占比例為θ的個(gè)體組成新的種群G(τ);

步驟3.2(交叉) 從G(τ)中選擇出M/2對(duì)母體(M≤N),依據(jù)概率Pc執(zhí)行交叉,形成M個(gè)中間個(gè)體;

步驟3.3(變異) 對(duì)M個(gè)中間個(gè)體分別獨(dú)立依概率Pm執(zhí)行變異,形成M個(gè)候選個(gè)體;

步驟3.4(選擇) 計(jì)算M個(gè)候選個(gè)體的適應(yīng)度后,將其加人種群G(τ);依據(jù)適應(yīng)度大小從種群G(τ)中選擇N個(gè)個(gè)體作為新種群X(τ+1).

步驟4終止檢驗(yàn).如果τ+1≤T,則輸出X(τ+1)中具有最大適應(yīng)度的個(gè)體作為最優(yōu)解;否則,令τ：=τ+1,轉(zhuǎn)步驟2.

上述求解步驟中終止準(zhǔn)則也可以采取其他的形式,如當(dāng)連續(xù)多次迭代后,目標(biāo)函數(shù)得不到改進(jìn),即終止計(jì)算.

3 算例分析

分析只有8個(gè)信息源的單向限量式最速網(wǎng)絡(luò)消息傳播問題.設(shè)定種群規(guī)模N=100,復(fù)制比例θ= 0.85,交叉概率Pc=0.75,變異概率Pm=0.15,最大遺傳代次T=100,單向的消息最大交互數(shù)目為4.利用NetBeans6.9.1編寫的JAVA程序,經(jīng)92次迭代計(jì)算得到最少需要交互17次才能完成所有的消息傳播.最優(yōu)的交互模式在表1中給出,最優(yōu)目標(biāo)函數(shù)值隨迭代次數(shù)的增加而減少的變化趨勢(shì)如圖1(a)所示.

如果將信息源增加到16個(gè),每次交互可傳遞的最大消息數(shù)為5,遺傳的最大代次設(shè)定為T=200,經(jīng)179代遺傳計(jì)算得到需要交互82次才能完成所有的消息傳播.最優(yōu)個(gè)體的適應(yīng)值隨遺傳代次的增加而減少的變化趨勢(shì)如圖1(b)所示.

從圖1的最優(yōu)遺傳個(gè)體適應(yīng)度變化趨勢(shì)可以看出,利用遺傳算法求解單向最速網(wǎng)絡(luò)消息傳播問題是比較有效的.但是,遺傳算法需要事先設(shè)定較多的算法參數(shù),并且這些參數(shù)對(duì)隨后的計(jì)算效率有較大影響,因此,只有對(duì)問題的特征有明確認(rèn)識(shí),才能設(shè)計(jì)出高效的算法.

表1 有8個(gè)信息源的最優(yōu)交互模式Tab.1 Best pattern of interchanging with 8 sources of messages

圖1 有8個(gè)和16個(gè)信息源的最優(yōu)遺傳個(gè)體的適應(yīng)度變化趨勢(shì)Fig.1 Variation trend of the fitness of the best genetic individual with 8 and 16 sources of messages

4 結(jié)束語

通過對(duì)單向限量最速網(wǎng)絡(luò)消息傳播問題的建模和求解,為相關(guān)的研究做一個(gè)鋪墊.網(wǎng)絡(luò)消息傳播問題的決策變量形式特殊、決策的時(shí)空影響模式特殊及問題的廣泛適應(yīng)性和強(qiáng)可塑性,使得很難構(gòu)造一個(gè)該問題的普適模型.本文給出的單向限量消息傳播問題最優(yōu)化模型提供了相關(guān)建模研究的基礎(chǔ).利用問題特征設(shè)計(jì)的模擬進(jìn)化算法能方便快捷地求解該問題,同時(shí)具有較強(qiáng)的可塑性.在此算法基礎(chǔ)上可以開發(fā)更有效的問題族求解算法.

最速網(wǎng)絡(luò)消息傳播問題是一族問題的統(tǒng)稱.該問題族存在眾多的擴(kuò)展方向,其中包括：a.事先限定網(wǎng)絡(luò)的信息交互通道的拓?fù)浣Y(jié)構(gòu)問題;b.網(wǎng)絡(luò)信息分布初態(tài)和終態(tài)的可變性問題;c.信息傳播過程中的消息遺忘問題;d.多階段的網(wǎng)絡(luò)信息分布控制優(yōu)化問題等.對(duì)最速網(wǎng)絡(luò)消息傳播問題族的研究才剛剛開始,存在許多基礎(chǔ)理論問題亟待解決,不僅要發(fā)掘問題的有效解決手段,也要對(duì)問題的本質(zhì)特征和規(guī)律進(jìn)行深人的分析.可以期待不久的將來最速網(wǎng)絡(luò)消息傳播問題族研究會(huì)有更多的成果出現(xiàn),也可以相信該問題族將會(huì)有廣闊的實(shí)際應(yīng)用前景.

[1] 羅瑩,劉冰.網(wǎng)絡(luò)信息傳播效果研究[J].情報(bào)科學(xué), 2009,27(9)：1487-1491.

[2] 王慧軍,王有遠(yuǎn),胡振鵬.網(wǎng)絡(luò)信息傳播管理研究[J].科技管理研究,2010,30(6)：140-143.

[3] 孫麗曇.網(wǎng)絡(luò)信息傳播：一種自組織復(fù)雜系統(tǒng)的分析研究[J].現(xiàn)代情報(bào),2007,27(4)：81-84.

[4] 金鎮(zhèn).論網(wǎng)絡(luò)信息傳播的跨學(xué)科研究[J].現(xiàn)代情報(bào), 2007,27(4)：15-17.

[5] 邊霞,米良.遺傳算法理論及其應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2010,27(6)：2425-2434.

[6] 沐士光.遺傳算法在網(wǎng)絡(luò)優(yōu)化問題中的研究與應(yīng)用[J].計(jì)算機(jī)仿真,2010,27(4)：128-131.

[7] 洪瑋,崔杜武.函數(shù)優(yōu)化的遺傳算法策略優(yōu)選[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(13)：3043-3046.

[8] 賈東立,鄭國莘.基于混沌和高斯局部優(yōu)化的混合差分進(jìn)化算法[J].控制與決策,2010,25(5)：899-902.

[9] ALI M M,KAJEE-BAGDADI Z.A local explorationbased differential evolution algorithm for constrained global optimization[J].Applied Mathematics and Computation,2009,208(1)：31-48.

[10] 祝希路,王柏.一種基于社團(tuán)劃分的小生境遺傳算法[J].控制與決策,2010,25(6)：1113-1116.

[11] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(22)： 1-15.

Fastest network message one-way spreading model with bounds of transitive messages and its evolutionary algorithm

HESheng-xue
(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

The fastest network message one-way spreading problem with bounds of transitive messages was introduced.The problem was formulated with strict mathematics.The corresponding simulated evolutionary algorithm was provided.Through analysing the characteristics of the problem,induding the features of decision variables,the special pattern of the spatial and temporal impacts of decision-makings and the distribution features of network messages,the optimization model of the problem was built.Taking advantage of the binary feature of decision variables and the relative independence of the pattern of single round information interchanging,the reproduction operator,the crossover operator and the mutation operator of genetic algorithm were designed,that can be manipulated flexibly.So the simulated evolutionary solution of the model was achieved.The numerical example demonstrates the effectiveness of the model and the algorithm.The main extensible research directions with regard to the problem were summed up.

systems engineering;network optimization;message spreading;genetic algorithm

O 221;O 157.6

A

1007-6735(2011)03-0274-05

2011-03-23

上海市優(yōu)秀青年教師基金資助項(xiàng)目(slg08018);上海市教育委員會(huì)科技創(chuàng)新項(xiàng)目(10YS105)

何勝學(xué)(1976-),男,講師.研究方向：交通網(wǎng)絡(luò)建模.E-mail：lovellhe@126.com.