劉海洋，劉歌群，任寧春，張嘉楠

(上海理工大學 光電信息與計算機工程學院，上海 200093)

基于LabVIEW的復雜網(wǎng)絡演化博弈實驗軟件

劉海洋，劉歌群，任寧春，張嘉楠

(上海理工大學 光電信息與計算機工程學院，上海 200093)

復雜網(wǎng)絡演化博弈能夠揭示豐富的物理現(xiàn)象和規(guī)律，復雜網(wǎng)絡演化博弈實驗軟件對于演化博弈過程的理解和認知具有重要作用。目前對網(wǎng)絡演化博弈進行可視化的軟件并不多見，因此文中基于LabVIEW開發(fā)了一種演示網(wǎng)絡演化博弈過程的實驗軟件。軟件在LabVIEW開發(fā)環(huán)境下，規(guī)劃人機交互界面，實現(xiàn)軟件流程。軟件的輸入包含了網(wǎng)絡模型、博弈模型和策略更新規(guī)則，對節(jié)點策略、節(jié)點收益以及網(wǎng)絡合作頻率進行動態(tài)顯示?？梢詫Ρ姸嗑W(wǎng)絡演化博弈過程進行演示，并文中給出了軟件運行結(jié)果。

復雜網(wǎng)絡；實驗軟件；演化博弈；LabVIEW

隨著博弈論的廣泛應用，博弈個體之間的關(guān)系變得越來越復雜，博弈結(jié)果的形成過程也引起了學者們的關(guān)注，因而誕生了網(wǎng)絡演化博弈論。在網(wǎng)絡演化博弈理論中，將網(wǎng)絡上的節(jié)點看作博弈個體，邊代表博弈關(guān)系，博弈個體隨著時間演化，不斷地與其鄰居進行博弈并更新其策略[1]。網(wǎng)絡演化博弈理論為復雜網(wǎng)絡上的交互行為提供了強有力的解釋和恰當?shù)哪Ｐ?，近些年引起了學術(shù)界廣泛的關(guān)注和興趣。在對網(wǎng)絡演化博弈理論的學習中，理解網(wǎng)絡上博弈和演化的過程至關(guān)重要。

目前進行網(wǎng)絡演化博弈仿真分析，主要使用Matlab[2]、Repast[3]和Netlogo[4]等軟件。但是能夠直觀展示各方博弈策略及其演化過程的專用軟件包尚不多見，因此提供一種對網(wǎng)絡演化博弈過程進行可視化的專用軟件已成為一種需要。

本文設(shè)計開發(fā)了基于LabVIEW的網(wǎng)絡演化博弈實驗軟件，對網(wǎng)絡演化博弈過程中節(jié)點收益、節(jié)點策略以及網(wǎng)絡合作頻率的變化進行可視化，從而可以幫助實驗者更好的理解和掌握網(wǎng)絡演化博弈的理論知識。

1 網(wǎng)絡演化博弈簡述

博弈論為解釋自私個體間的交互行為提供了強有力的理論框架[5]，從而得到了快速發(fā)展和廣泛應用。在傳統(tǒng)博弈論的基礎(chǔ)上，演化博弈論進行了補充和完善，結(jié)合生物演化理論，揭示了個體間的自私行為和群體廣泛的合作行為之間的內(nèi)在統(tǒng)一。而以復雜網(wǎng)絡為框架進行演化博弈稱為網(wǎng)絡演化博弈。

1.1 博弈論

博弈是指參加斗爭或競爭的各方為了達到各自的目標和利益選取對自己最為有利或最為合理的方案[6]，日常生活中的下棋、打牌和著名的囚徒困境[7]等都是博弈。一個完整的博弈應當包括以下幾方面的內(nèi)容：(1)博弈的參與者，即博弈中獨立決策、獨立承擔后果的個人或組織，又稱為局中人；(2)博弈個體的策略，即每個局中人可選擇的全部行為；(3)博弈信息，即博弈者所掌握的對選擇策略有幫助的情報資料；(4)博弈的次序，即局中人做出策略選擇的先后；(5)博弈收益，即博弈方做出決策后的所得與所失。

在博弈過程中每個局中人在選擇博弈策略時必須考慮其他局中人的策略，與此同時每個局中人的博弈收益還依賴于其他個體所采用的策略。博弈論就是研究博弈中是否存在著最合理的行為方案，以及如何找到這個合理的行為方案的數(shù)學理論和方法。博弈論對簡單博弈最直觀的表述就是將博弈用收益矩陣來描述，這種表述形式又稱為矩陣表述。一個典型的矩陣表述舉例如圖1所示。

圖1 博弈的矩陣表述

圖中，博弈局中人分別為vi，vj。局中人vi可以選擇的策略有：A1，A2；局中人vj可以選擇的策略有：B1，B2，B3。矩陣中元素Umn表示局中人vi和vj對于策略組合(Am，Bn)的收益組合。

1.2 經(jīng)典博弈論和演化博弈論

經(jīng)典博弈論在局中人是完全理性的情況下研究博弈的均衡問題，而對均衡的解釋為在均衡狀態(tài)下沒有個體可以通過單方面改變自己的策略而增加收益。但是經(jīng)典博弈論存在一些缺陷:首先，“完全理性”觀點認為局中人總是選擇使自己利益最大化的策略，在復雜環(huán)境下，局中人很難獲取全部信息，因此局中人“完全理性”的觀點是不切實際的；其次，經(jīng)典博弈論雖給出了均衡解釋，但并沒有給出均衡的形成過程[8]。

演化博弈論借鑒生物進化理論對經(jīng)典博弈論進行了完善。演化博弈論使用“有限理性”觀點代替了經(jīng)典博弈論中的“完全理性”觀點。有限理性結(jié)合適者生存的概念，認為局中人通常是在掌握有限信息的情況下，以優(yōu)化自己的收益為目標選擇策略，與此同時借鑒生物種群的進化和穩(wěn)定機制，模擬均衡的動態(tài)實現(xiàn)過程。因此，演化博弈被廣泛地用于研究各式各樣的合作現(xiàn)象[9]。

演化博弈論的關(guān)鍵是如何在具體情況下構(gòu)造動態(tài)機制來模擬局中人的學習和決策過程，最終目標是尋找促進合作行為涌現(xiàn)的動態(tài)機制。目前，支持合作行為產(chǎn)生的機制大體有：親緣選擇，直接互惠，間接互惠，網(wǎng)絡互惠以及群體選擇[10]。親緣互惠是指具有親緣關(guān)系的個體之間的合作關(guān)系，例如：當?shù)卣饋砼R時，父母會奮不顧身的保護子女。直接互惠通常指朋友間相互幫助，這種相互幫助會促進合作的涌現(xiàn)，例如重復對手的策略就是直接互惠。間接互惠則發(fā)生在陌生人之間，傾向合作的個體擁有較高的聲譽，同時可以得到別人的合作。網(wǎng)絡互惠主要指描述個體聯(lián)系的網(wǎng)絡的結(jié)構(gòu)對于合作涌現(xiàn)具有影響。群體選擇指多個群體之間雖然是斗爭的，但是作為一個整體時它們之間卻是合作的，一個形象的例子就是公司內(nèi)部的各個部門之間。

1.3 網(wǎng)絡演化博弈論

以復雜網(wǎng)絡為框架進行演化博弈研究的理論稱為網(wǎng)絡演化博弈論。在演化博弈論中，通常假設(shè)所有個體是相同的，相互之間均勻混合，即群體中任意兩個個體等可能地進行博弈[11]。而現(xiàn)實世界中，種群的個體通常不能與所有的個體相互接觸，他們之間存在復雜且不均勻的相互關(guān)系。復雜網(wǎng)絡理論的飛速發(fā)展，為這種復雜且不均勻的相互關(guān)系提供了描述框架：網(wǎng)絡中的節(jié)點表示博弈個體，邊代表博弈關(guān)系。

局中人在復雜網(wǎng)絡上隨著時間的演化和他的鄰居進行博弈稱為網(wǎng)絡演化博弈，通常用vi，i=1,2,…,N表示第i個局中人；用Si={ei1,ei2,…,eiQ}表示局中人vi采取的策略集合；s=(s1,s2,…,sN)表示N個局中人采取的策略在策略空間的一個策略組合，其中si∈Si；用ui(s)表示此策略集合下第i個局中人的收益。這樣一個演化博弈表述為Y={s1,s2,…,sN;u1,u2,…,uN}。

復雜網(wǎng)絡演化博弈具有3個要素：博弈模型、策略更新規(guī)則以及網(wǎng)絡模型。博弈模型包含經(jīng)典博弈論中的博弈模型等，比如囚徒困境、雪堆模型和獵鹿模型等；網(wǎng)絡模型則包含各式復雜網(wǎng)絡模型：隨機網(wǎng)絡或小世界網(wǎng)絡等。而策略更新規(guī)則的選取對于網(wǎng)絡演化博弈至關(guān)重要，目前主要有如下幾種更新規(guī)則：模仿收益最大的鄰居策略，即個體確定性的選擇收益最大的鄰居策略作為自己下一輪博弈的策略[12]；按概率選擇優(yōu)勝鄰居的策略，即考慮收益高于自己的所有鄰居,按正比于其收益的概率選擇其策略[13]；配對比較個體隨機選擇某個鄰居進行收益比較，以某個概率轉(zhuǎn)變?yōu)閷Ψ降牟呗訹14]。

2 網(wǎng)絡演化博弈實驗軟件設(shè)計

為了直觀演示網(wǎng)絡演化博弈的演化過程，本文所介紹的網(wǎng)絡演化博弈實驗軟件在LabVIEW開發(fā)環(huán)境下開發(fā)。為體現(xiàn)軟件控件的關(guān)聯(lián)性，如圖2所示，將實驗軟件的前面板分為參數(shù)設(shè)置區(qū)、博弈演示區(qū)以及數(shù)據(jù)顯示區(qū)。

根據(jù)網(wǎng)絡演化博弈條件，設(shè)計參數(shù)設(shè)置區(qū)包含復雜網(wǎng)絡演化博弈3個要素和博弈輪數(shù)。為了充分演示復雜網(wǎng)絡演化博弈過程，設(shè)計博弈演示區(qū)包含網(wǎng)絡拓撲結(jié)構(gòu)以及節(jié)點策略進行。同時設(shè)計數(shù)據(jù)顯示區(qū)包括了本輪收益數(shù)組、累積收益數(shù)組以及合作頻率圖表，以顯示博弈過程中網(wǎng)絡和節(jié)點統(tǒng)計信息的變化。

圖2 前面板以及網(wǎng)絡拓撲結(jié)構(gòu)圖生成

復雜網(wǎng)絡演化博弈實驗軟件以網(wǎng)絡演化博弈相關(guān)理論為依據(jù)，設(shè)計了以下功能性步驟：軟件啟動后的初始化狀態(tài)；參數(shù)設(shè)置環(huán)節(jié)；演化博弈過程中的實時動態(tài)演示和數(shù)據(jù)更新；一次完整的演化博弈實驗結(jié)束后的狀態(tài)返回。

為使軟件具有更好的可讀性和拓展性，演化博弈過程分為博弈計算、策略更新以及效果顯示3個子過程。博弈計算過程進行博弈的本輪收益計算。策略更新計算過程則根據(jù)策略更新規(guī)則進行策略的更新計算。效果顯示過程對本輪收益、總體收益和策略進行更新。軟件運行流程如圖3所示。

圖3 軟件流程圖

軟件流程的幾個主要環(huán)節(jié)為初始化、參數(shù)設(shè)置、博弈計算、策略更新計算和效果顯示。

(1)初始化及參數(shù)設(shè)置階段。初始化階段進行前面板按鈕狀態(tài)和數(shù)據(jù)的初始化。參數(shù)設(shè)置相關(guān)控件以組合控件形式，集中在參數(shù)設(shè)置區(qū)。其中網(wǎng)絡模型的設(shè)置采用按鈕的形式，點擊按鈕進入相應子VI進行對應網(wǎng)絡的設(shè)置。可設(shè)置的網(wǎng)絡模型不僅包含了常見的BA無標度網(wǎng)絡、WS小世界網(wǎng)絡和ER隨機網(wǎng)絡，還設(shè)計了自定義網(wǎng)絡按鈕以滿足實驗者的特定需求。對稱博弈模型的設(shè)置則采用二維矩陣的形式。策略更新規(guī)則的設(shè)置采用組合框的形式，包含了兩個比較常見的更新規(guī)則：模仿最優(yōu)更新和隨機更新規(guī)則。此外，參數(shù)設(shè)置階段還包含了博弈演示區(qū)節(jié)點策略的設(shè)置。節(jié)點策略設(shè)置以布爾控件實現(xiàn)，灰色表示合作，黑色表示背叛；

(2)博弈計算階段。博弈計算階段根據(jù)網(wǎng)絡拓撲結(jié)構(gòu)，對有博弈關(guān)系的節(jié)點進行兩兩博弈收益的計算，再通過循環(huán)嵌套完成所有博弈關(guān)系的本輪收益計算，如圖4所示。圖中鄰接矩陣變量為網(wǎng)絡的鄰接矩陣，策略數(shù)組和本輪收益變量分別為16個策略和本輪收益，按節(jié)點編號組成兩個1維數(shù)組。

圖4 博弈計算階段程序圖

如圖4所示，兩兩博弈的博弈收益計算使用“二維索引數(shù)組控件”實現(xiàn)。該控件的數(shù)組接線端連接博弈模型數(shù)組，行和列的索引接線端都連接代表節(jié)點策略的0或1常量。例如：行接線端連接的節(jié)點策略為合作，列接線端連接的節(jié)點策略為背叛，策略轉(zhuǎn)化的常量為(1，0)，對應數(shù)組第二行第一列的數(shù)，即行接線端節(jié)點的本次博弈收益。

由于某一節(jié)點的本輪收益是與其相關(guān)的所有兩兩博弈收益的累加，因此在進行新的兩兩博弈后，需要在本輪收益數(shù)組中對代表該節(jié)點的本輪收益進行更新。在LabVIEW中，使用“替換數(shù)組子集控件”實現(xiàn)這種對數(shù)組元素的更新。替換數(shù)組子集控件的數(shù)組連線端連接“本輪收益數(shù)組”，索引連線端為節(jié)點編號，子集連線端則連接求和后的節(jié)點本輪收益。

所有連邊關(guān)系上的博弈計算，通過多重循環(huán)結(jié)構(gòu)對鄰接矩陣的行和列進行遍歷實現(xiàn)。在循環(huán)過程中，上輪循環(huán)得到的結(jié)果作為下輪循環(huán)的輸入，如圖4使用“移位寄存器”的數(shù)據(jù)處理方式。移位寄存器可實現(xiàn)程序語言中的靜態(tài)局部變量，從而實現(xiàn)隨著每次循環(huán)體的執(zhí)行而累加；

(3)策略更新計算階段。博弈計算階段完成后進入策略更新階段，策略更新階段根據(jù)選定的規(guī)則對博弈策略進行更新。

如圖5所示，使用條件結(jié)構(gòu)判斷所選定的策略更新規(guī)則，在條件結(jié)構(gòu)中使用循環(huán)嵌套計算出每個節(jié)點更新后的策略。圖5中顯示的是模仿最優(yōu)策略更新規(guī)則，即節(jié)點將鄰居中本輪收益最高節(jié)點的策略作為自己的策略。在更新過程中，使用移位寄存器進行循環(huán)結(jié)構(gòu)中節(jié)點策略數(shù)組的更新。

圖5 策略更新計算階段程序圖

(4)效果顯示階段。該階段將對前面板上的數(shù)據(jù)進行更新，其中包括節(jié)點策略，節(jié)點本輪收益數(shù)組、節(jié)點累積收益數(shù)組和網(wǎng)絡的合作頻率圖表。根據(jù)策略更新階段計算獲得的策略，對界面上的節(jié)點策略顯示顏色進行更新。合作頻率經(jīng)計算后以圖表形式顯示，圖表橫坐標表示博弈的輪數(shù)，縱坐標代表合作頻率。圖表形式有助于更加直觀地了解網(wǎng)絡演化博弈的統(tǒng)計特性。

3 軟件運行實例

為了說明軟件對網(wǎng)絡演化博弈過程的演示效果，以文獻[15]中的網(wǎng)絡演化博弈數(shù)據(jù)為例進行演示實驗。設(shè)置節(jié)點初始策略合作和背叛各占1/2，策略更新規(guī)則選取為模仿最優(yōu)更新規(guī)則，博弈模型采用聯(lián)合生產(chǎn)博弈模型，收益矩陣如圖6所示。分別在無標度網(wǎng)絡、小世界網(wǎng)絡，隨機網(wǎng)絡和二維格子網(wǎng)絡模型下進行網(wǎng)絡演化博弈實驗。

圖6 聯(lián)合生產(chǎn)博弈模型

運行軟件后，點擊前面板網(wǎng)絡模型區(qū)域相應的網(wǎng)絡模型按鈕，進入各自的子VI進行網(wǎng)絡模型參數(shù)設(shè)置。網(wǎng)絡模型設(shè)置完成后，將圖6的數(shù)據(jù)輸入博弈模型區(qū)域的矩陣中，選擇模仿最優(yōu)策略更新規(guī)則，設(shè)置博弈演示區(qū)域的節(jié)點策略初始狀態(tài)。點擊設(shè)置完成按鈕，博弈演示區(qū)域顯示所設(shè)置的網(wǎng)絡模型的拓撲結(jié)構(gòu)，如圖1所示。設(shè)置博弈輪數(shù)為25，點擊博弈按鈕開始博弈。在博弈過程中前面板中的本輪收益數(shù)組、累積收益數(shù)組以及博弈演示區(qū)域的節(jié)點策略都在不斷更新，合作頻率圖表中繪制網(wǎng)絡中節(jié)點策略的合作頻率并不斷延伸。

圖7 合作頻率

在第12輪博弈后點擊結(jié)束按鈕，得到合作頻率圖。對4種不同的網(wǎng)絡分別進行實驗，得到4個合作頻率圖如圖7所示，可以發(fā)現(xiàn)，隨著博弈輪數(shù)的增加，合作頻率最終趨于穩(wěn)定。不同網(wǎng)絡下合作頻率變化不盡相同，體現(xiàn)了不同復雜網(wǎng)絡模型對于網(wǎng)絡合作頻率的影響不同，這符合基本常識。而且穩(wěn)定后的合作頻率不同，和文獻[15]的理論結(jié)果相一致。

圖7中小世界網(wǎng)絡模型下的前5輪博弈演示區(qū)節(jié)點策略的變化如圖8所示，灰色表示節(jié)點當前策略為“合作”，黑色表示節(jié)點當前策略為“背叛”，此圖展示了每一輪各個節(jié)點當前的策略，以及策略的變化過程。其中灰色節(jié)點越來越多，表明網(wǎng)絡的合作頻率隨著博弈輪數(shù)的增加在增長，趨勢與圖7(b)一致，體現(xiàn)了所設(shè)計軟件的有效性。

圖8 小世界網(wǎng)絡的前5輪博弈演示區(qū)

4 結(jié)束語

本文在LabVIEW開發(fā)環(huán)境下，設(shè)計了一種基于LabVIEW的網(wǎng)絡演化博弈實驗軟件，對網(wǎng)絡演化博弈過程進行了可視化。軟件的參數(shù)設(shè)置模塊設(shè)計包含了網(wǎng)絡演化博弈的各個要素，方便實驗者根據(jù)不同要求進行試驗，進而了解在網(wǎng)絡演化博弈中各個參數(shù)發(fā)揮的作用。同時，軟件的顯示模塊對網(wǎng)絡演化博弈過程中的各個數(shù)據(jù)進行了展示，并動態(tài)地演示了網(wǎng)絡演化博弈過程中策略與合作頻率的變化。實驗表明，該軟件有助于幫助人們理解和學習網(wǎng)絡演化博弈的理論知識，可在復雜網(wǎng)絡演化博弈的實驗和教學過程中發(fā)揮作用。

[1] 汪小帆,李翔，陳關(guān)榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006.

[2] 范如國,張應青,羅會軍.考慮公平偏好的產(chǎn)業(yè)集群復雜網(wǎng)絡低碳演化博弈模型及其仿真分析[J].中國管理科學,2015(S1):763-770.

[3] 楊中華.基于核心企業(yè)的供應鏈網(wǎng)絡信息共享研究[D].武漢:華中科技大學,2013.

[4] 阮國祥,阮平南.集群網(wǎng)絡企業(yè)間知識轉(zhuǎn)移演化博弈仿真分析[J].圖書情報工作,2011,55(16):77-81.

[5] 榮智海.復雜網(wǎng)絡上的演化博弈與機制設(shè)計研究[D].上海:上海交通大學,2008.

[6] 楊涵新,汪秉宏.復雜網(wǎng)絡上的演化博弈研究[J].上海理工大學學報,2012,34(2):166-171.

[7] 陳維春,尚麗輝.基于獎勵因子的囚徒困境博弈模型研究[J].電子科技,2016,29(3):5-6.

[8] 王文賓.演化博弈論研究的現(xiàn)狀與展望[J].統(tǒng)計與決策,2009(3):158-161.

[9] 姜羅羅,汪秉宏.復雜系統(tǒng)中的合作演化與自組織斑圖[J].上海理工大學學報,2012,34(2):172-184.

[10] Nowak M A.Five rules for theevolution of cooperation[J].Science,2016,314(5805):1560-1563.

[11] 王先甲,全吉,劉偉兵.有限理性下的演化博弈與合作機制研究[J].系統(tǒng)工程理論與實踐,2011,31(S1):82-93.

[12] Nowak M A.evolutionary games and spatial chaos[J].Nature,2002,359(6398): 826-829.

[13] Hauert C,Doebeli M.Spatial structure often inhibits the evolution of cooperation in the snowdrift game[J].Nature,2014,428 (6983):643-646.

[14] Devlin S,Treloar T.Evolution of cooperation through the heterogeneity of random networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009,79(1Pt2):100-115.

[15] 劉歌群,詹志國,胡琦,呂偉臻.聯(lián)合生產(chǎn)博弈模型[J].電子科技,2016,29(3):1-4.

Experimental Software Developed with LabVIEW for Evolutionary Games on Networks

LIU Haiyang,LIU Gequn,REN Ningchun,ZHANG Jianan

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology, Shanghai 200093,China)

Evolutionary games on complex networks can reveal abundant physical phenomena and laws. Experimental software for networked evolutionary games plays an important role in the understanding and cognition of evolutionary game process. Because the visualized software for the networked evolutionary games are rare, so we developed a software with LabVIEW to display the process of networked evolution games. In the LabVIEW development environment, we designed the human-machine interface and programmed the software process. The input of the software includes the network model, the game model and the strategy update rules. The software can dynamically show the nodes strategy, the nodes gains and the networks’ cooperation frequency. The software can demonstrate the process of lots of evolutionary games on several types of networks. At the end of this paper, the software running results.

complex networks; experimental software; evolutionary games; LabVIEW

2017- 01- 17

滬江基金(C14002)；上海理工大學光電信息與計算機工程學院教師創(chuàng)新能力建設(shè)項目(GDCX-Y-1212)；上海市大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(SH2016030)

劉海洋(1993-)，男，碩士研究生。研究方向：復雜網(wǎng)絡。劉歌群(1974-)，男，博士后。研究方向：復雜網(wǎng)絡與計算機控制。

10.16180/j.cnki.issn1007-7820.2017.12.029

TP311.5

A

1007-7820(2017)12-109-05