基于雪堆博弈的復(fù)雜網(wǎng)絡(luò)最小節(jié)點覆蓋.pdf

1、復(fù)雜網(wǎng)絡(luò)是現(xiàn)實中復(fù)雜系統(tǒng)的抽象，自然界和人類社會中的很多系統(tǒng)都是以網(wǎng)絡(luò)的形式存在的，這些網(wǎng)絡(luò)錯綜復(fù)雜，各式各樣，但擁有一些共通的特性。比如朋友關(guān)系網(wǎng)絡(luò)、電力網(wǎng)、生態(tài)系統(tǒng)網(wǎng)、國家間的競爭與合作關(guān)系、藥物相互作用關(guān)系等等。其中，系統(tǒng)中的個體對應(yīng)于復(fù)雜網(wǎng)絡(luò)中的節(jié)點，系統(tǒng)中個體之間的關(guān)系對應(yīng)于復(fù)雜網(wǎng)絡(luò)中節(jié)點之間的邊。研究復(fù)雜網(wǎng)絡(luò)，對促進(jìn)人類現(xiàn)實社會和科學(xué)技術(shù)的進(jìn)步有深遠(yuǎn)的意義。
　　復(fù)雜網(wǎng)絡(luò)的最小節(jié)點覆蓋問題（MVCP）是一個著名組合優(yōu)化

2、問題，其目的在于找出給定網(wǎng)絡(luò)的最小節(jié)點集合以覆蓋所有的邊?，F(xiàn)實中的很多問題最終都可以歸結(jié)為最小節(jié)點覆蓋問題，其在現(xiàn)實中也有著廣泛的應(yīng)用，比如規(guī)劃問題，網(wǎng)絡(luò)優(yōu)化等方面，同時也是解決一些其他重要問題的關(guān)鍵點，如測算網(wǎng)絡(luò)的魯棒性等。作為一個NP難問題，雖然成為研究熱點已有時日，但已經(jīng)提出的解決該問題的算法大都有不盡人意的地方，我們經(jīng)過研究試驗，結(jié)合進(jìn)化算法的全局搜索能力，與博弈進(jìn)化的局部搜索能力，提出了基于雪堆博弈的自然進(jìn)化算法 GEA和基于

3、雪堆博弈的變異搜索算法SVS，兩個算法各有所長。通過大量實驗，考察算法在解決復(fù)雜網(wǎng)絡(luò)的最小節(jié)點覆蓋問題上的表現(xiàn)，驗證其有效性。本文的主要工作如下：
　　1.基于記憶的最優(yōu)反應(yīng)算法。該算法為復(fù)雜網(wǎng)絡(luò)的最小節(jié)點覆蓋問題提出一種新的解決思路，利用局部信息和理性個體的記憶能力，啟發(fā)式地求得 MVCP問題的解。我們通過充分的實驗，分析該算法的特性以及在不同網(wǎng)絡(luò)上的性能表現(xiàn)，并深刻剖析其原理，以幫助更好地解決最小節(jié)點覆蓋問題。
　　2.

4、基于雪堆博弈的自然進(jìn)化算法。我們借鑒自然進(jìn)化思想，將網(wǎng)絡(luò)的節(jié)點覆蓋結(jié)果，即網(wǎng)絡(luò)中所有節(jié)點的狀態(tài)（覆蓋或不覆蓋）集合看作一個染色體，作為種群進(jìn)化中的個體。將網(wǎng)絡(luò)的節(jié)點覆蓋與博弈理論相結(jié)合，每個節(jié)點與自己的鄰點進(jìn)行雪堆博弈，根據(jù)最優(yōu)反應(yīng)規(guī)則獲得當(dāng)前策略并更新策略，當(dāng)整個網(wǎng)絡(luò)達(dá)到納什均衡狀態(tài)時，完成局部最優(yōu)解搜索。個體組成種群，再通過種群的進(jìn)化更新，完成全局最優(yōu)解搜索。通過實驗對比，這種算法表現(xiàn)出優(yōu)于當(dāng)前經(jīng)典算法的性能。
　　3.基于雪

5、堆博弈的變異搜索算法。我們將網(wǎng)絡(luò)中的節(jié)點視為理性個體，賦予其判斷最優(yōu)策略的能力，并擁有一定的記憶能力。將博弈理論與復(fù)雜網(wǎng)絡(luò)的節(jié)點覆蓋問題相聯(lián)系，引入空間雪堆博弈和基于記憶的最優(yōu)反應(yīng)規(guī)則，個體通過與鄰點的博弈獲得當(dāng)前最優(yōu)策略并更新記憶。所有個體根據(jù)各自的記憶更新策略再博弈，最終網(wǎng)絡(luò)會達(dá)到納什均衡狀態(tài)，完成解的初步搜索。再根據(jù)自然進(jìn)化，對初步解進(jìn)行變異操作，通過進(jìn)化搜索最終達(dá)到全局最優(yōu)。通過實驗，詳細(xì)分析了算法在不同網(wǎng)絡(luò)的表現(xiàn)及背后原理，驗