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

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

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

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

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