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

何勝學

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

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

何勝學

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 模擬進化解法設計

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

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

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

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

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

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

步驟2個體適應度計算.考慮不滿足約束式(8)的加權懲罰項,計算常數(shù)T=50中各個體的適應度.

步驟3種群進化.

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

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

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

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

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

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

3 算例分析

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

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

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

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

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

4 結束語

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

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

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

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

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

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

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

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

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

[8] 賈東立,鄭國莘.基于混沌和高斯局部優(yōu)化的混合差分進化算法[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] 祝希路,王柏.一種基于社團劃分的小生境遺傳算法[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)秀青年教師基金資助項目(slg08018);上海市教育委員會科技創(chuàng)新項目(10YS105)

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