基于遺傳聚類的社團(tuán)發(fā)現(xiàn)算法研究.pdf

1、現(xiàn)實(shí)世界中存在著電力系統(tǒng)、通信系統(tǒng)及交通系統(tǒng)等大量的復(fù)雜系統(tǒng)。復(fù)雜網(wǎng)絡(luò)是對復(fù)雜系統(tǒng)結(jié)構(gòu)的一種抽象表示，具有小世界現(xiàn)象和無標(biāo)度等特性。在復(fù)雜網(wǎng)絡(luò)的諸多特性中，網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是除小世界現(xiàn)象和無標(biāo)度等特性外的又一重要特性，發(fā)現(xiàn)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)即社團(tuán)發(fā)現(xiàn)對于了解網(wǎng)絡(luò)的性質(zhì)和功能具有重要意義。目前，雖然復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)問題的研究已經(jīng)取得了長足的發(fā)展，但是算法的劃分結(jié)果的準(zhǔn)確性和算法的運(yùn)行時(shí)間仍然是社團(tuán)發(fā)現(xiàn)問題的核心問題，如何提高算法的準(zhǔn)確性和降低算

2、法運(yùn)行時(shí)間仍然是今后國內(nèi)外學(xué)者研究的熱點(diǎn)。
　　本文在分析已有復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法的基礎(chǔ)上，針對現(xiàn)有算法中存在的問題，探討了改進(jìn)算法性能的方法，結(jié)合遺傳算法和聚類分析K-MEANS算法思想，構(gòu)造了用于無權(quán)無向網(wǎng)絡(luò)的具有較高準(zhǔn)確度和較少運(yùn)行時(shí)間的遺傳K-MEANS社團(tuán)發(fā)現(xiàn)算法。本文首先基于社團(tuán)發(fā)現(xiàn)問題與數(shù)據(jù)挖掘中聚類分析問題的相似性分析，將聚類分析算法中時(shí)間復(fù)雜度小并適合處理較大規(guī)模網(wǎng)絡(luò)的K-MEANS算法用于求解社團(tuán)發(fā)現(xiàn)問題。分析

3、了用聚類分析法來尋找社團(tuán)結(jié)構(gòu)的最關(guān)鍵一點(diǎn)——網(wǎng)絡(luò)連接關(guān)系如何轉(zhuǎn)換成聚類分析算法研究的數(shù)據(jù)結(jié)構(gòu)。其次，分析了K-MEANS算法的聚類收斂判別準(zhǔn)則——誤差平方和準(zhǔn)則有可能導(dǎo)致的局部最優(yōu)現(xiàn)象，針對該問題，討論了密度法、模擬退火法、遺傳算法等多種解決方案，鑒于遺傳算法的并行搜索特性，選定遺傳算法對K-MEANS算法進(jìn)行改進(jìn)，從問題空間選出多個(gè)代表不同初始聚類中心的個(gè)體，對每個(gè)個(gè)體同時(shí)進(jìn)行K-MEANS算法聚類，根據(jù)適應(yīng)度函數(shù)進(jìn)行遺傳操作，最后選

4、出最優(yōu)解。在算法K值已知情況下設(shè)計(jì)了用于提高算法性能的適應(yīng)度函數(shù)、編碼方法、遺傳操作方法;通過實(shí)驗(yàn)驗(yàn)證了不同適應(yīng)度函數(shù)對算法準(zhǔn)確度和運(yùn)行時(shí)間的影響以及本文算法的優(yōu)越性，討論了不同的算法參數(shù)對算法的影響;進(jìn)而研究了K值未知情況下算法的設(shè)計(jì)，并通過實(shí)驗(yàn)驗(yàn)證了該算法的有效性。最后，針對單目標(biāo)優(yōu)化算法中求解社團(tuán)發(fā)現(xiàn)問題時(shí)所存在的解限制問題，即不能找出大規(guī)模網(wǎng)絡(luò)中存在的小規(guī)模社團(tuán)問題，提出了多目標(biāo)優(yōu)化算法，確定了適應(yīng)度函數(shù)，并通過實(shí)驗(yàn)驗(yàn)證了多目標(biāo)