基于GEP多基因族編碼的復雜網(wǎng)絡(luò)社團劃分研究.pdf

1、隨著信息技術(shù)的迅猛發(fā)展,人類生活中存在各式各樣的大規(guī)模網(wǎng)絡(luò)。復雜網(wǎng)絡(luò)的廣泛存在,使得對其研究變得非常必要。而對復雜網(wǎng)絡(luò)的研究包括復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)統(tǒng)計特性及分析、復雜網(wǎng)絡(luò)演化模型和生成機制、復雜網(wǎng)絡(luò)的動力學研究和復雜網(wǎng)絡(luò)社團結(jié)構(gòu)及劃分四大方面。其中探測復雜網(wǎng)絡(luò)社團結(jié)構(gòu)及劃分有利于了解整個網(wǎng)絡(luò)的結(jié)構(gòu)及特征,能夠指導人們進行決策,具有很強的現(xiàn)實意義。
　　目前,很多學者已提出了各種復雜網(wǎng)絡(luò)社團劃分算法,并取得了一定的成就。但是,大部分算

2、法還存在一定的缺陷,如社團劃分算法的時間復雜度較高、算法運行時結(jié)果不夠精確、以及需事先知道社團內(nèi)的節(jié)點數(shù)目和社團個數(shù),因而不適用于大型的復雜網(wǎng)絡(luò)分析。鑒于此,本論文提出了一種基于GEP多基因族編碼的復雜網(wǎng)絡(luò)社團劃分算法,并且通過實驗檢驗了該算法的優(yōu)越性。
　　本論文所做研究及創(chuàng)新點如下:
　　(1)提出了一種新的適用于復雜網(wǎng)絡(luò)社團劃分的編碼方案。本文引進了一種新的編碼方案,稱為多基因族編碼。該編碼設(shè)計方法是利用基因表達式編程

3、(GEP)中多基因族編碼的特性,即將節(jié)點和社團類型分別編碼在屬于同一條染色體中的兩個不同的多基因族中,此編碼方案克服了傳統(tǒng)的樹型編碼的缺陷。
　　(2)提出了一種基于GEP多基因族編碼的復雜網(wǎng)絡(luò)社團劃分方法。利用基因表達式編程所具有的組合優(yōu)化的專用算子,如倒置、限制交換、概化交換、基因刪除/插入和序列刪除/插入,比經(jīng)典的遺傳算法更具高效性。在本文中,引入了倒置算子和限制交換算子,促進了算法的收斂,有效降低了算法的時間復雜度。而且仿

4、真實驗結(jié)果說明此算法較傳統(tǒng)的復雜網(wǎng)絡(luò)社團結(jié)構(gòu)劃分方法具有更高的效率和精確度。
　　(3)提出了一種基因表達式編程演化時引進精英遷移策略。將精英遷移策略運用到基因表達式編程演化的各個遺傳階段,如選擇、交叉、倒置、變異、限制交換。即對于某一代種群中的所有染色體,分別找出遺傳算子在修飾前與修飾后的最優(yōu)個體,如果修飾前的最優(yōu)個體優(yōu)于修飾之后的最優(yōu)個體,則用修飾前的最優(yōu)個體替換修飾后種群中最差的個體。不僅可以控制遺傳的演化方向,而且提高了每