多種群遺傳算法及其在復(fù)雜網(wǎng)絡(luò)社區(qū)劃分中的應(yīng)用研究.pdf

1、復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分問題是近年來研究的熱點問題,如何對復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)進行探測和劃分對于了解整個網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)具有非常重要的意義。到目前為止,已經(jīng)提出了許多復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分算法,但大部分算法還存在一定的缺陷,如有些算法需要事先知道社區(qū)內(nèi)的節(jié)點數(shù)目以及社區(qū)個數(shù)等預(yù)知條件,部分算法還需要知道其它的一些門限值,而大部分算法則是由于時間復(fù)雜度過高,不適合用于對大型復(fù)雜網(wǎng)絡(luò)的分析?；诖?本論文提出了一種基于多種群遺傳算法的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的

2、新方法,即 IMPGA算法,并且通過實驗驗證了該算法的優(yōu)越性。
　　本論文的主要工作及創(chuàng)新點如下:
　　(1)提出了一種改進的多種群遺傳算法的結(jié)構(gòu)形式。傳統(tǒng)的多種群遺傳算法采用串行的思路求解復(fù)雜網(wǎng)絡(luò)社區(qū)劃分問題,IMPGA算法采用三個子種群并行進化的結(jié)構(gòu)形式,其中一個為精英種群,而另外兩個為普通種群,并使用多線程技術(shù)實現(xiàn)多種群的并行操作,使三個子種群并行進化,最終獲得全局最優(yōu)解。結(jié)構(gòu)形式的改進使得算法在效率上得到了明顯的提高

3、。
　　(2)提出了一種改進的自適應(yīng)交叉概率與變異概率。傳統(tǒng)的多種群遺傳算法采用的是固定的交叉與變異概率,在IMPGA算法中,交叉概率根據(jù)個體的差異性進行判斷,若差異性小則交叉概率大,反之則小,這樣有利于個體性狀的分離,增加種群的多樣性;自適應(yīng)的變異概率根據(jù)個體適應(yīng)值進行判斷,若適應(yīng)值大則變異概率小,反之則大,這樣既保護了適應(yīng)值大的優(yōu)秀個體,使其優(yōu)良基因不受破壞,又可以讓適應(yīng)值小的劣質(zhì)個體得以變異,使其劣質(zhì)基因得到改良。改進的自適

4、應(yīng)交叉變異概率降低了傳統(tǒng)交叉與變異操作的破壞性,提高了算法對參數(shù)的配置能力,使得算法在尋優(yōu)質(zhì)量以及收斂效率上都得到了很大的提高。
　　(3)提出了一種改進的遷移算子。在傳統(tǒng)的多種群遺傳算法中,一代進化結(jié)束后進行精英遷移,這樣不但給算法帶來效率上的負擔,同時忽略了低劣個體的發(fā)展,不利于種群的進化。在 IMPGA算法中,經(jīng)過設(shè)定代數(shù)的進化,采用遷移算子進行遷移操作。兩個普通種群分別產(chǎn)生最優(yōu)個體,然后將其遷移到精英種群中,同時將兩個普通

5、種群中各自的最劣個體和最優(yōu)個體與對方的最劣個體和最優(yōu)個體進行互換,這樣既可以保留住低劣個體中的優(yōu)良基因,甚至可以通過環(huán)境的改變使得低劣基因得到改良。改進的遷移算子促進了種群間個體的信息交互,增強了種群的多樣性。
　　(4)提出了一種基于多種群遺傳算法的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的新方法,即IMPGA算法。算法克服了傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分中出現(xiàn)的受先驗信息限制、算法復(fù)雜度大以及局限于網(wǎng)絡(luò)規(guī)模等問題，IMPGA算法只需要較少的先驗信息,算法的效