【正文】 呢？網(wǎng)絡(luò)成為描述博弈個體間相互作用的做好方法。就博弈論而言，參與博弈的個體就可以抽象表示為網(wǎng)絡(luò)中的節(jié)點(diǎn)；而個體間的相互關(guān)系或相互作用就可以抽象為網(wǎng)絡(luò)的邊。雖然節(jié)點(diǎn)和邊可以具體表達(dá)很多特性，但我們通常只關(guān)心節(jié)點(diǎn)之間有沒有邊相連，而不考慮節(jié)點(diǎn)的位置，以及邊的長短、形狀等等。我們把網(wǎng)絡(luò)這種不依賴于節(jié)點(diǎn)的具體位置和邊的其體形態(tài)就能表現(xiàn)出來的性質(zhì)叫做網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，相應(yīng)的結(jié)構(gòu)叫做網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。但是，真實(shí)網(wǎng)絡(luò)到底是怎么樣的呢？從古至今人們從來沒有停止去探索。隨著計(jì)算機(jī)技術(shù)的迅猛發(fā)展，人們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)具有小世界效應(yīng)和無標(biāo)度效應(yīng)。美國康奈爾大學(xué)的Watts 及其Strogatz教授在Nature上發(fā)表了題為《“小世界”網(wǎng)絡(luò)的集體動力學(xué)》的文章，闡述了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)，并建立了相應(yīng)的模型。美國Notre Dame大學(xué)的Barabasi教授及其博士生Albert在science上發(fā)表《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》一文，闡述了復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，并建立了相應(yīng)的模型。至今，復(fù)雜網(wǎng)絡(luò)主要有規(guī)則網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)這四種基本模型。 規(guī)則網(wǎng)絡(luò)節(jié)點(diǎn)按照確定的規(guī)則連接起來，這樣得到的網(wǎng)絡(luò)就稱為規(guī)則網(wǎng)絡(luò)。規(guī)則網(wǎng)絡(luò)又被稱為格圖或d一格。一個d一格是帶標(biāo)號、無權(quán)、無方向的簡單圖。規(guī)則網(wǎng)絡(luò)具有均勻的度分布，并且具有較大的聚類系數(shù)和較小的平均路徑長度。，列舉了兩種規(guī)則網(wǎng)絡(luò):圖（a）一個個體對應(yīng)著四個鄰居 （b）一個個體對應(yīng)著三個鄰居 規(guī)則網(wǎng)絡(luò)示意圖資料來源: Christoph Hauert amp。 Michael Doebeli Spatial structure often inhibits the evolution of cooperation in the snowdrift game, Nature 428，643(2004) 隨機(jī)網(wǎng)絡(luò)在本文中主要是研究“囚徒困境”模型在隨機(jī)網(wǎng)絡(luò)上演化產(chǎn)生的自適應(yīng)行為，所以，本文就主要介紹隨機(jī)網(wǎng)絡(luò)。隨機(jī)網(wǎng)絡(luò)的幾何性質(zhì)以及模型，是由Paul Erd246。s，Alfr233。d R233。nyi 和B233。la Bollob225。s在五六十年代提出的。它的模型建立如下：首先生成n個節(jié)點(diǎn)，這n個節(jié)點(diǎn)中的任意兩個之間以概率p連接起來形成一條邊。這個模型看起來非常簡單，但是當(dāng)時的提出還是非常困難的。隨機(jī)網(wǎng)絡(luò)的特征是平均聚集程度低而平均路程長度較短，但大規(guī)模的隨機(jī)網(wǎng)絡(luò)沒有聚類特性。并且隨機(jī)網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)都是隨著概率p的變化而變化的，它的很多重要性質(zhì)都是在某個臨界p值處突然涌現(xiàn)出來。=10，、資料來源:Hisashi Ohtsuki，ChristoPh Hauert，Erez Lieberman amp。 Martin A. Nowak. A simple rule for the evolution of cooperation on graphs and social networks，Nature441，502(2006) 小世界網(wǎng)絡(luò)從真實(shí)的世界來看，真實(shí)網(wǎng)絡(luò)不可能像上述的規(guī)則網(wǎng)絡(luò)那樣完全規(guī)則，也不可能像隨機(jī)網(wǎng)絡(luò)那樣完全隨機(jī)。就比如在人類社會中，人們總會跟自己的親人和朋友一起形成一個小團(tuán)體，即有一定的聚類特性；但同時，人們也會有一定的幾率去認(rèn)識新的朋友，即有一定的隨機(jī)性。于是，正如前所述，美國康奈爾大學(xué)的Watts 及其Strogatz教授在Nature上發(fā)表了題為《“小世界”網(wǎng)絡(luò)的集體動力學(xué)》的文章，闡述了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)，并建立了相應(yīng)的模型，簡稱WS模型，這個模型具有較高的聚類特性和較短的平均路程。WS模型的構(gòu)造算法如下: 給定一個含有N 個節(jié)點(diǎn)的一維環(huán)狀有限規(guī)則網(wǎng)絡(luò)，其中每個節(jié)點(diǎn)都與它最近鄰的K=2m個節(jié)點(diǎn)相連。以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的其中一個端點(diǎn)保持不變，而另一個端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個節(jié)點(diǎn)。在隨機(jī)化重連的過程中應(yīng)該保證沒有重邊和自環(huán)。 無標(biāo)度網(wǎng)絡(luò)述三種網(wǎng)絡(luò)結(jié)構(gòu)都是有一個平均度的，但是事實(shí)上并非如此。1998 年,AL Barabasi等開展一項(xiàng)描繪萬維網(wǎng)的研究。他們發(fā)現(xiàn)網(wǎng)絡(luò)的節(jié)點(diǎn)是呈冪率分布的，即大多數(shù)節(jié)點(diǎn)的度很小，而少部分節(jié)點(diǎn)的度很大。因此如前所述，美國Notre Dame大學(xué)的Barabasi教授及其博士生Albert在science上發(fā)表《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》一文，闡述了復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，并建立了相應(yīng)的模型，簡稱BA模型。其模型的建立過程如下：首先，給定一個具有n0個節(jié)點(diǎn)的網(wǎng)絡(luò)，在每一步長中增加一個新的節(jié)點(diǎn)連接到n≤n0個已存在的節(jié)點(diǎn)上，并且新節(jié)點(diǎn)連接到另一個點(diǎn)的概率正比于這個點(diǎn)的度k，重復(fù)這個過程，就形成了BA網(wǎng)絡(luò)。2 囚徒困境博弈在隨機(jī)網(wǎng)絡(luò)中的演化 復(fù)雜系統(tǒng)及合作現(xiàn)象由于復(fù)雜系統(tǒng)中的個體具有自適應(yīng)性，即個體能夠依據(jù)環(huán)境進(jìn)行自我反饋節(jié)，因此復(fù)雜系統(tǒng)有時又被稱為復(fù)雜自適應(yīng)系統(tǒng)。 復(fù)雜自適應(yīng)系統(tǒng)的一些概念和研究模型與基于自然選擇的達(dá)爾文進(jìn)化理論具有緊密的聯(lián)系。達(dá)爾文認(rèn)為演化有兩個驅(qū)動力，即選擇和變異。在此基礎(chǔ)上，哈佛大學(xué)Nowak教授認(rèn)為合作是演化過程中的第三個原動力[3]。在本文中，我們研究的是囚徒困境博弈模型，所以我們主要討論的就是合作的演化。在自然界中，合作現(xiàn)象是非常普遍的，從微生物到植物到動物再到人類社會，你都會發(fā)現(xiàn)生物體間的合作。比如我們比較熟悉的有螞蟻在尋找食物時的合作。當(dāng)一只螞蟻發(fā)現(xiàn)了食物的時候，由于自身比較弱小，根本不可能獨(dú)自把食物搬走，所以它就會返回蟻穴，將這個消息以他們的方式告訴其它的螞蟻。然后它們就會一起前往食物所在地，然后一起搬食物。這種在捕食上的合作還會發(fā)生在蜜蜂等其它一些生物種群中。還有一些生物的合作不是在同種生物間的，比如?？图木有贰：？袝r會在寄居蟹的螺殼上，當(dāng)寄居蟹長大要遷入另一個較大的新螺殼時，海葵也會主動地移到新殼上。這樣?？图木有冯p方都得到好處。由于寄居蟹喜好在海中四處游蕩，使得原本不移動的?？S著寄居蟹的走動，擴(kuò)大了覓食的領(lǐng)域。對寄居蟹來說，一則可用?？麃韨窝b，二則由于?？芊置诙疽?，可殺死寄居蟹的天敵，因此保障了寄居蟹的安全 。人類社會中也有許多的合作現(xiàn)象。一支足球隊(duì)的隊(duì)員之間的合作；同學(xué)們在學(xué)習(xí)上的互相合作；一個公司研發(fā)部門和生產(chǎn)部門之間的合作等等。 合作的演化依據(jù)達(dá)爾文的進(jìn)化理論，生物的不同個體間以及不同種群間是相互競爭的關(guān)系，生物個體為了生存總是想把自身取得的利益最大化，那么我們便不能解釋上文所提到的自然界中以及人類社會中的合作例子。那到底是什么促進(jìn)并維持合作的產(chǎn)生，或者說自然界中以及人類社會中到底存在著什么樣的機(jī)制維持著合作的產(chǎn)生，這是很多生物學(xué)家、社會學(xué)家、經(jīng)濟(jì)學(xué)家等在努力研究的問題。為了理解合作的問題，科學(xué)家們也建立了各種各樣的模型，引入了學(xué)習(xí)策略、懲罰策略、記憶、互惠策略等等機(jī)制。 均勻混合體系中的合作演化早期人們通常是在均勻混合群體的框架中研究進(jìn)化行為。所謂均勻混合群體指的是群體中的任意兩個個體之間相遇的概率都相同。關(guān)于均勻混合群體中的進(jìn)化研究最經(jīng)典的模型是Moran過程[6]()。Moran過程步驟如下:在每一個時間的長中，以正比于適應(yīng)度的概率選擇一個個體進(jìn)行后代繁殖，并且其后代帶將會帶有跟它父代同樣的基因或性狀。然后隨機(jī)地選擇一個個體使其死亡，它所空出的位置就被先前選中繁殖個體的后代所取代。不斷進(jìn)行這個過程，直至最后穩(wěn)定。資料來源:Lieberman E，Hauert C， Nawak M A. Evolutionary dynamics on graphs [J].Nature,2005，433:312. Moran過程的收益矩陣為：其中參數(shù)b二T/R表示當(dāng)博弈個體B采取合作策略時，博弈個體A采取背叛策略所獲得的收益與采取合作策略所獲得的收益之比。因此，b值表征背叛的誘惑力，當(dāng)b值增大時，背叛的個體有可能獲得更大的收益，因此背叛行為對個體將具有更大的吸引力。假設(shè)最初群體中的每個個體都隨機(jī)采取合作或背叛的策略，然后在每一個模擬步長中，每個個體隨機(jī)選取群體中的另外一個個體進(jìn)行囚徒困境博弈并記錄各自的收益。再以正比于收益的概率進(jìn)行繁殖、死亡和替代過程