基于微分進化算法的消息傳播網(wǎng)構(gòu)建

鄧柯+閆述

摘 要：某事件發(fā)生時，除消息以廣播的方式通知相關人員外，還需依賴個體之間的責任關系傳播，消除信息孤島問題。社會網(wǎng)絡（Social Network）中的個體之間存在復雜的責任關系，針對該問題，以滑坡事件發(fā)生時為例，創(chuàng)建帶責任制的消息傳播網(wǎng)模型，并采用微分進化算法評估關系屬性和來往交流等因素對責任關系的影響權重，同時加入責任弱化（Responsibility Decline，RD）效應模擬消息傳播過程。結(jié)果表明，關系屬性和面對面交流對責任關系的影響較大，緊急消息的傳播過程也會受距離的影響。實現(xiàn)了一對多的責任分派機制，多對多的責任分派方式則有待進一步研究。

關鍵詞：消息傳播網(wǎng)；責任關系；影響權重；微分進化算法

DOIDOI：10.11907/rjdk.162758

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2017）007-0005-06

0 引言

滑坡是我國多發(fā)的地質(zhì)災害。在面向區(qū)內(nèi)全體人員的WSN（Wireless Sensor Network）滑坡監(jiān)測預警系統(tǒng)[1-2]方面，手機作為配備最普遍的個人通信工具，是監(jiān)測系統(tǒng)信息傳遞與接收的理想節(jié)點。但在事關生命安全的緊急情況下，必須使撤離警報無遺漏地傳達到每一個人，包括老人、病人、嬰幼兒等無行為能力的人員。由于人機分離、遺漏等造成的信息孤島問題是監(jiān)測系統(tǒng)中需要解決的問題。因此，除以消息廣播的方式傳播緊急預警信息給具有接收信息能力的移動設備外，為解決信息孤島的問題還需將消息傳播的責任劃分到個體，這意味著收到消息的責任個體需要將消息傳播給被負責對象。傳統(tǒng)的消息傳播網(wǎng)以網(wǎng)絡社交平臺為傳輸媒介，研究節(jié)點、邊的特征及信息特征對消息傳播的影響，強調(diào)消息的擴散性[3]，但滑坡緊急事件發(fā)生時的報警消息傳達強調(diào)及時性和知曉性?；卤O(jiān)測系統(tǒng)將區(qū)域中的居民依據(jù)責任關系構(gòu)造成一個消息傳播網(wǎng)，責任關系主要受關系屬性和來往交流等因素的影響，且影響權重不同。針對多屬性決策問題有主觀賦權法、客觀賦權法[4-5]，解決該問題的采納率達到了85.8%[1]。為實現(xiàn)滑坡報警消息無遺漏地通知，這里引入主要解決實參數(shù)優(yōu)化問題的微分進化算法[6-8]，確立了影響因子的權重，使得模擬消息傳播過程中采納率在居民之間的百米范圍內(nèi)達到97.8%，同時這種方案考慮了滑坡事件的緊急特殊性，加入受傳播距離影響的RD效應，使消息在電話傳播和走動傳遞兩種方式中自由切換，與實際情況結(jié)合更靈活。根據(jù)自定義的目標函數(shù)解決優(yōu)化與責任關系相關的權重組合問題，能夠?qū)崿F(xiàn)一對多的責任分派問題。結(jié)果顯示，關系屬性和各種交流方式對責任關系的影響各占一定比重，但關系屬性和面對面交流方式影響更大。同時解決該問題的方案可以運用到其它緊急事件發(fā)生并需要傳播緊急消息的場景，具有應用拓展性。

1 消息傳播網(wǎng)模型構(gòu)建

1.1 問題描述

滑坡監(jiān)測系統(tǒng)中的消息傳播網(wǎng)由具有信息傳播能力的正常人和無知曉能力的老人、病人、嬰幼兒等責任關系構(gòu)成，責任關系主要考慮由關系屬性和來往交流頻數(shù)綜合決定。若收到緊急消息的居民不能以電話的方式傳播消息給未收到緊急消息的居民，則以走動的方式傳遞消息，走動傳遞消息會受到距離的影響。依據(jù)以上問題構(gòu)建網(wǎng)絡模型如下：

（1）建立消息傳播網(wǎng)絡。滑坡區(qū)的居民依據(jù)責任關系構(gòu)建一個帶權有向的消息傳播網(wǎng)絡G（V，E，W），V是網(wǎng)絡中的節(jié)點集合，V={v1，v2，v3，…，vN}，W是邊的權值集合，W={wij|i≠j，1≤i≤N，1≤j≤N }，wij表示節(jié)點vi與節(jié)點vj之間的相互權值，代表居民之間的責任關系強度，其中wij≠wji。

（2）加入RD效應。假設電話傳播信息失敗，則需要個體移動傳播信息給被負責對象。這時需要考慮與距離相關的傳播時間，存在隨時間延遲的RD效應。假設有正常居民A、B、C，其中居民A、B收到緊急信息，居民C沒有收到緊急信息且電話聯(lián)系不上，wAC>wBC，理應由A負責通知C，但A到C的距離遠大于B到C 的距離，在緊急事件發(fā)生時需要考慮消息傳達的及時性，應由距離C較近的B負責傳遞消息給C，傳播時間更短。因此，A的責任因消息傳播時間間隔變大而弱化了。

（3）網(wǎng)絡中存在普通節(jié)點和特殊節(jié)點。以居民為節(jié)點構(gòu)成的網(wǎng)絡圖G（V，E，W），存在老人、病人、嬰幼兒等無知曉能力的個體形成的節(jié)點，可以視為特殊節(jié)點（vs），其余視為普通節(jié)點（vg）。

1.2 特征提取

信息傳播以責任制的要求進行，對于任意用戶u（假設該用戶沒有收到廣播消息），存在wuv=max{wui|u≠i，1≤i≤N }，與其責任關系最強的用戶v負責傳播信息給用戶u。wuv受居民u與居民v之間關系屬性以及來往交流頻數(shù)的影響。

（1）關系屬性。任何兩個有關聯(lián)的用戶之間存在某種關系屬性，這些關系可以分為家庭關系、朋友關系、情侶關系、鄰里關系等。這里可以用情感系數(shù)來表示情感的強弱，4種情感系數(shù)表示為Rfamily、Rfriend、Rflover、Rneighbor。這幾種系數(shù)一般存在以下大小關系：

（2）來往交流頻數(shù)。居民之間存在走訪（視為一種面對面的交流方式）、短信通話、微信、QQ等多種交流方式，交流會影響人與人之間的關系，因此來往交流頻數(shù)在影響責任關系中占有一定的權重。

走訪頻數(shù)（visits）：統(tǒng)計居民之間一年內(nèi)的走訪頻數(shù)，用集合Fvisits表示。v_fuv表示居民u與居民v之間的走訪頻數(shù)。

短信通話頻數(shù)（calls）：統(tǒng)計居民之間一年內(nèi)的短信通話頻數(shù)，用集合Fcalls表示。c_fuv表示居民u與居民v之間的短信通話頻數(shù)。

微信和QQ交流頻數(shù)（QQs）：統(tǒng)計居民之間在一年內(nèi)用QQ或者微信通信的總頻數(shù)，用集合FQQs表示。q_fuv表示居民u與居民v之間的微信QQ交流頻數(shù)。

以上幾種特征所占的影響比重不同，各個特征取值范圍不一，需要作進一步的標準化處理。這里采用Min-Max標準化方法，將以上特征集合的取值分別映射到[0，1]區(qū)間：

其中，fuv和f′uv分別表示標準化處理前后的特征值。

1.3 模型建立

關系屬性和來往交流對責任關系各有一定的影響權重，設定關系屬性所占權重為wR，來往交流中走訪方式所占權重為wvisits，短信通話所占權重為wcalls，微信QQ交流所占權重為wQQs，用戶u與用戶v的責任關系強度wuv可以表示如下：

節(jié)點之間的影響力或信息傳播能力隨著時間間隔增大存在指數(shù)衰減規(guī)律[9]。假設居民u在tu時刻收到緊急信息，在tv時刻居民v才收到居民u傳來的緊急信息。居民v在時刻tv收到居民u緊急信息的概率為fp（（v，tv）|（u，tu）），這個概率會隨著時間間隔Δt=tv-tu的增大而降低。同時wuv越大代表居民之間的責任關系越強，傳播概率p（u，v，c）越大，居民之間緊急消息的初始傳播概率p（u，v，c）與wuv成正比關系。C為不大于1的常量，c為傳播信息，設定：

RD效應可以視為傳播概率隨時間衰減。融合時間衰減因素的傳播概率模型通常有3種表示方法，如表1所示的3種傳播概率模型，分別是指數(shù)模型[10-11]、冪率模型和瑞利模型。指數(shù)模型和冪率模型中的傳播概率隨著Δt的增大單調(diào)遞減，冪率模型中傳播概率的演化還具有長尾特征。瑞利模型中傳播概率先是隨Δt增大而增加，到達峰值后開始緩慢降低，該模型研究傳染病傳播概率增長和衰退的演化規(guī)律[12]。初始傳播概率與責任關系強度正相關，隨著傳播時間增大會產(chǎn)生RD效應，這里選擇指數(shù)模型來刻畫傳播概率隨Δt的衰減規(guī)律。

在指數(shù)模型中τ（u，v，c）代表傳播延遲，傳播延遲受傳播主體、傳播客體、傳播內(nèi)容等因素的影響。當緊急事件發(fā)生時，傳播主體需立即將緊急消息傳遞給傳播客體，在居民之間傳播延遲無差別（忽略電話通話時延），因此τ（u，v，c）可以視為一個常量Llatency。變換指數(shù)模型后，隨時間變化的傳播概率fp（（v，tv）|（u，tu））表示為：

其中，Suv表示u與v之間的傳播距離，人員行動平均速率為v。

在1.1問題描述中，問題（1）和問題（2）是預選的兩種消息傳播方式，傳播主體首選電話傳播方式，當電話傳播方式失敗時再選擇人員走動傳播方式。設電話傳播方式成功的概率為P，采用人員走動傳播方式的概率為1-P，若普通節(jié)點vg收到緊急消息概率Pr（vg，par（vg）），par（vg）表示傳遞消息給vg的父節(jié)點，有：

問題（3）考慮到消息傳播網(wǎng)中老人、病人、嬰幼兒等這些無知曉能力的信息孤島點，針對這類節(jié)點選擇采用人員走動的方式傳遞消息，則：

將式（4）、式（5）分別帶入式（6）、式（7），得到式（8）、式（9）：

從式（3）、式（8）、式（9）可以看出，在確定父節(jié)點收到消息的情況下，節(jié)點收到消息的概率與父節(jié)點之間的關系屬性以及來往交流頻度相關，同時受節(jié)點之間距離的影響。

2 權重評估

權重值是責任劃分的重要因素，責任劃分主要受關系屬性和來往交流的影響，需確定wR、wvisits、wcalls、wQQs的最佳值。找出最佳權重值有兩種方法可以選擇，一種是典型的確定性最優(yōu)算法，比喻窮舉搜索，可以返回最優(yōu)解。但這種方法需要搜索整個解空間，時間復雜度太大。為了減少計算量，且4個權重值之和為1，權重的取值范圍限制在0.000 001～0.999 997。這些權重值的組合就有999 9973種情況，即需要從9.999 91×1017個權值組合中評估最佳權重組合。窮舉算法找出這4個權重值，在時間上代價太高，不利于快速決策。另一種是選擇一種元啟發(fā)式方法搜索最佳權重組合。這種智能技術能夠搜索解空間并減少評估次數(shù)，且在能接受的合理時間內(nèi)完成，針對目標函數(shù)，元啟發(fā)式方法往往獲得近似最優(yōu)解。微分進化（Differential Evolution）搜索算法，這種元啟發(fā)式算法非常適用于尋找最優(yōu)值問題[13-14]。

微分進化算法是一種以人群為基礎的算法，人群中的個體對應于目標問題的一個候選解，每個個體是一個存放實際值的向量[15]。設xi表示人群中一個個體，xi[j]元素存放影響因素的權重值，有：

微分進化算法首先隨機產(chǎn)生有N個個體的人群，個體中元素的初始值從區(qū)間[0.000 01，0.999 97]中選擇。參數(shù)組在G次換代中不斷變化和重組，獲得最優(yōu)解。算法偽代碼如下：

//F代表突變因子，CR代表重組因子popl=N；Evaluate（popl）；g=0；while（g

表2為實驗中微分進化算法的參數(shù)配置，這些值是在調(diào)試和測試之后選定的。針對該問題確定了一個目標函數(shù)F（xi），微分進化算法需要實現(xiàn)該函數(shù)的最小化。目標函數(shù)F（xi）由兩部分組成：

（1）本實驗需要收集與每個居民有責任關系的人員信息。根據(jù)居民u的主觀判斷將這些人員按與自己的責任強弱降序排列，設這個主觀序列為Au={y1，y2，y3，…，yn}。求出式（3）在xi組合條件下有責任關系的人員與u的綜合權值wuv（v表示與u有責任關系的其他居民），依據(jù)綜合權值的大小降序排列，設該理論序列為Bu={z1，z2，z3，…，zn}。求序列Bu相對于序列Au的逆序數(shù)Inversion_Count（u，xi）。

（2）求xi中超出允許范圍的變量數(shù)Invalid_Params（xi）：

F（xi）需要考慮（1）和（2）兩部分：

為方便采集實驗數(shù)據(jù)，以長咀村為實驗基地，約980人。長咀村分7個小區(qū)，為便捷調(diào)查人員關系，以太子廟小區(qū)作為調(diào)查代表，調(diào)查中病人、幼兒、老人、外出、正常人的人數(shù)各為1、3、19、36、33。收集居民之間的日常情感關系屬性和來往交流信息，經(jīng)標準化后帶入模型求解最小F（xi），并獲取最優(yōu)權重組合。

表3、表4為實驗在Visual C++ 6.0 Win32環(huán)境下運行出的部分結(jié)果。在實驗中依據(jù)式（1）設置不同的日常情感關系屬性，本次實驗設置了4組不同關系屬性值進行了4組模擬，表1中的兩張子表分別為4組模擬的候選解，選取最小F（xi）值為最優(yōu)解，對應的權重組合為最優(yōu)權重組合。從兩張子表可以看出，不同關系屬性值的設定會影響最優(yōu)解。但依據(jù)圖3候選解的散點分布圖來看，整體上日常情感關系和走訪頻數(shù)對責任關系的影響比重較大，其次是短信/電話頻數(shù)，由于居民不常使用QQ/微信，因此這種交流方式對責任關系的影響很小。同時，觀察（a）（b）（c）（d）4張子圖發(fā)現(xiàn)走訪頻數(shù)即面對面的交流頻數(shù)對責任關系的影響可見一斑，這可以解釋為在同種日常情感關系中，面對面的交流方式會增進人與人之間的感情，產(chǎn)生更強的責任關系。

3 模型驗證

依據(jù)問題（2）描述中的責任弱化效應，責任分派過程還需加入距離影響因素。式（8）、式（9）體現(xiàn)了節(jié)點收到消息的概率隨距離呈指數(shù)衰減的規(guī)律，將按概率大小模擬分派任務，概率高者會有較大的責任去傳遞消息給被負責對象。

模擬前階段隨機設定一些個體為廣播消息接受者，這些節(jié)點為種子節(jié)點。同時，隨機初始化個體之間的距離（在現(xiàn)實生活中該距離可以由定位系統(tǒng)測量）。在第3部分的權重評估中分析了各因素對責任關系的影響比重，從結(jié)果中選擇F（xi）值最小的權重組合xi=（0.250 365，0.391 904，0.235 851，0.092 311）加入模擬運算。將消息傳播網(wǎng)中的點集合V分成4部分，Vg1為種子節(jié)點集合，Vg2為未收到消息的正常節(jié)點集合，Vs1為收到消息的特殊節(jié)點集合，Vs2為未收到消息的特殊節(jié)點集合。

以太子廟為緊急事件發(fā)生點，初始狀態(tài)下|Vs1|=0，| Vs2|=23，| Vg1|+| Vg2|=69。決策中的責任分派過程如下：①對任意節(jié)點vg1∈Vg1，vg2∈Vg2，vs2∈Vg2，求出所有Pr（vg2，vg1），Pr（vs2，vg1）的值；②從求出的值中找出最大Pr（vg2，vg1）和Pr（vs2，vg1）的值，確定對應的消息傳播節(jié)點vg1和消息接收節(jié)點vg2 、vs2。vg1傳遞消息給被負責對象；③更新集合，Vg1= Vg1∪{ vg2}，Vg2= Vg2-{ vg2}，Vs1= Vs1∪{ vs2}，Vs2= Vs2-{ vs2}，同時更新距離；④循環(huán)重復過程①～③，直到| Vg2|=0，| Vs2|=0，消息傳播結(jié)束。

這里模擬了一對多的責任分派問題，即一個人可能會被分派到同時通知兩個或更多人的任務，還需要決策出優(yōu)先任務。責任分派的過程依然在Visual C++ 6.0 Win32環(huán)境下模擬運行，在此過程中隨機初始化居民之間的距離在100m內(nèi)，同時記錄了正常居民的消息傳遞路徑、距離以及通知人員數(shù)量。表5為在不同P值設定下，各人員的最大可能行走距離。

表5中Si表示編號為i的行動人員在消息傳遞過程中的最大可能行動距離。當P值越小時，即電話接受消息的概率減小，通過走動傳播消息概率的增大，由于RD效應，距離產(chǎn)生的影響增大。從表4可以看出，部分人員的責任分派會受到距離的影響，如編號為0、27、71、52、83的人員本身會依據(jù)責任關系獲得分派任務，但隨著距離影響的增大不會傳遞消息。編號為12、72的人員存在距離優(yōu)勢，在距離影響變大時也會參與消息傳遞。從現(xiàn)實生活來看，居民手機基本隨身攜帶，電話接收到消息的概率會較大，因此整體來說，系統(tǒng)主要依靠責任關系分派任務，表中也體現(xiàn)出在百米范圍內(nèi)大部分人員的責任劃分不會受到距離的很大影響。同時考慮信息傳達的及時性，若以100m的行動時間為期限，則這種模型的決策方案的采納率可以達到97.8%。

4 結(jié)語

緊急事件發(fā)生時，為確保消息無遺漏地傳達到每一個人，需要增加責任分派機制。面對復雜的人際關系，本文主要考慮了日常情感和來往交流頻數(shù)對人際責任關系的影響，該模型后期還可以加入其它多元變化因素，如傳播主體、傳播客體、傳播內(nèi)容等。人員消息傳播過程是復雜多樣的，這里只考慮了一對多的責任分派問題，多對多的責任分派問題還待進一步研究。同時該方案可以運用到其它自然災害所引起的緊急事件中，有一定的應用拓展性。

參考文獻：

[1]盧子龍.無線網(wǎng)絡滑坡監(jiān)測的信息處理與知曉概率的研究[D].鎮(zhèn)江：江蘇大學，2015.

[2]MANEESHA V RAMESH.Design，development，and deployment of a wireless sensor network for detection of landslides[J].Ad Hoc Networks，2014（2）：18.

[3]周東浩，韓文報，王勇軍.基于節(jié)點信息特征的社會網(wǎng)絡信息傳播模型[J].計算機研究與發(fā)展，2015，52（1）：156-166.

[4]徐玖平，吳巍.多屬性決策的理論與方法[M].北京：清華大學出版社，2006.

[5]張全.復雜多屬性決策研究[M].沈陽：東北大學出版社，2008.

[6] STRON R，PRICE K.Differential evolution a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization，1997（11）： 341-359.

[7]SU HAIJUN，YANG YUPU，WANG YUJIA.A review of differential evolution algorithms[J].Department of Automation from Shanghai Jiaotong University，2012.

[7]蘇海軍，楊煜普，王宇嘉.微分進化算法的研究綜述[J].上海：上海交通大學，2012.

[8]J C CORTS，J M COLMENAR，J I HIDALGO.Modeling and predicting the Spanish Bachillerato academic results over the next few years using a random network model[J].Physica A，2016（2）： 36-49.

[9]GOMEZ-RODRIGUEZ M，BALDUZZI D，SCHLKOPF B.Uncovering the temporal dynamics of diffusion networks[C].Proc of the 28th Int Conf on Machine Learning.New York： ACM，2011： 561-568.

[10]GOYAL A，BONCHI F，LAKSHMANAN LVS.Learning influence probabilities in social network[C].Proc of the 3rd ACM Int Conf on Web Search and Data Mining，New York： ACM，2010： 241-250.

[11]GOMEZ-RODRIGUEZ M，LESKOVEC J，KRAUSE A.Inferring networks of diffusion and influence[C].Proc of the 16th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining，New York：ACM，2010：1019-1028.

[12]WALLINGA J，TEUNIS P.Different epidemic curves for severe acute respiratory syndrome reveal similar impact of control measures[J].American Journal of Epidemiology，2004，160（6）：509-516.

[13]K V PRICE.An introduction to differential evolution[Z].New optimization platform，1999：79-108.

[14]R STORN.System design by constraint adaptation and differential evolution[J].IEEE Trans.Evol.Comput，1999，3 （1）：22-34.

[15]K P WONG，Z DONG.Differential evolution，an alternative approach to evolutionary algorithm[C].Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems，2005（2）：73-83.