本文選題：圖挖掘　切入點(diǎn)：進(jìn)化計(jì)算　出處：《西南大學(xué)》2017年碩士論文

【摘要】：圖作為一種重要的數(shù)據(jù)結(jié)構(gòu),常用于刻畫自然界或社會中事物間的復(fù)雜關(guān)系。隨著信息技術(shù)的發(fā)展,圖模型逐漸覆蓋生活各個方面,相關(guān)數(shù)據(jù)迅速增加,如社交、交通、蛋白質(zhì)之間相互作用等都可以用圖模型進(jìn)行刻畫。挖掘圖中信息可以幫助人們優(yōu)化推薦系統(tǒng)、設(shè)計(jì)高效網(wǎng)絡(luò)、預(yù)測蛋白質(zhì)功能等。如何高效的進(jìn)行圖挖掘已經(jīng)成為一個研究熱點(diǎn)。隨著圖數(shù)據(jù)增加,求解圖挖掘問題的算法近年來也得到了長足發(fā)展。根據(jù)求解基本策略不同主要分為優(yōu)化算法和啟發(fā)式算法。但優(yōu)化算法面對大規(guī)模問題時仍然存在搜索效率低的問題,啟發(fā)式算法也面臨易陷入局部最優(yōu)解等問題。無論基于優(yōu)化的算法還是啟發(fā)式算法,如何提高算法效率,高效進(jìn)行圖挖掘問題求解是當(dāng)前亟待解決的問題。生物啟發(fā)一直都是推動算法發(fā)展的重要動力。最近研究中,一種名為多頭絨泡菌的粘菌在覓食過程中展現(xiàn)出自組織、自優(yōu)化等智能特性引起廣泛關(guān)注。利用多頭絨泡菌仿生模型,本文對現(xiàn)有圖挖掘算法進(jìn)行優(yōu)化,以期提高算法效率。本文著眼于圖挖掘中子圖挖掘問題和圖聚類問題進(jìn)行研究。首先對多頭絨泡菌仿生模型的圖挖掘能力進(jìn)行進(jìn)一步探究,擴(kuò)展其求解問題范圍。然后利用多頭絨泡菌仿生模型的特性,對代表性的圖挖掘問題設(shè)計(jì)了針對性的算子和算法,對當(dāng)前圖挖掘算法進(jìn)行優(yōu)化。本文的主要貢獻(xiàn)包括以下兩個方面:1)針對子圖挖掘中典型的組播樹問題,本文提出了基于多頭絨泡菌仿生模型的遺傳交叉算子,以提高遺傳算法的局部搜索能力。首先對多頭絨泡菌仿生模型進(jìn)行了修改,使得模型可以求解最短路徑樹問題。之后針對多頭絨泡菌最短路徑樹模型計(jì)算復(fù)雜度較高的問題,優(yōu)化了模型中的迭代過程。最后基于優(yōu)化后的多頭絨泡菌最短路徑樹模型,本文提出了一種新的遺傳交叉算子(PMcrossover),并將PMcrossover嵌入到三種典型的遺傳算法中。通過和原算法在四個數(shù)據(jù)集上進(jìn)行對比,說明基于多頭絨泡菌的交叉算子可以有效的提高算法的搜索效率和魯棒性,驗(yàn)證了PMcrossover的有效性。2)針對圖聚類中典型的社團(tuán)挖掘問題,本文從優(yōu)化算法中的進(jìn)化算法和啟發(fā)式算法中的馬爾可夫聚類算法兩個方面進(jìn)行求解。進(jìn)化算法以遺傳算法和蟻群算法為代表。為了探究多頭絨泡菌仿生模型在圖聚類問題上的潛力,本文對多頭絨泡菌網(wǎng)絡(luò)模型進(jìn)行修改,使得其可以一定程度上區(qū)分社團(tuán)間和社團(tuán)內(nèi)的邊。之后將多頭絨泡菌仿生模型對邊的識別作為先驗(yàn)知識整合到了遺傳算法的初始化過程和蟻群算法的啟發(fā)式因子中,提出了進(jìn)化算法優(yōu)化策略。對于啟發(fā)式算法,本文以馬爾可夫聚類算法為代表。通過進(jìn)一步研究發(fā)現(xiàn),多頭絨泡菌模型中的正反饋系統(tǒng)和馬爾可夫聚類算法中的動態(tài)系統(tǒng)基于類似的基本假設(shè)。根據(jù)這個特點(diǎn),模仿多頭絨泡菌仿生模型中的正反饋關(guān)系,在馬爾可夫聚類算法中建立了新的反饋流。同時,本文對典型馬爾可夫聚類算法中主要算子進(jìn)行優(yōu)化,提出多頭絨泡菌啟發(fā)的馬爾可夫聚類算法。最后在12個數(shù)據(jù)集上,從準(zhǔn)確率、魯棒性、時間復(fù)雜度等方面驗(yàn)證了提出方法的效果。綜上,本文在對多頭絨泡菌仿生模型進(jìn)行研究的基礎(chǔ)上,充分挖掘其圖挖掘潛力,并對現(xiàn)有進(jìn)化算法和馬爾可夫聚類算法進(jìn)行優(yōu)化,對典型的子圖挖掘問題和圖聚類問題進(jìn)行求解。同時,通過廣泛實(shí)驗(yàn)證明了基于多頭絨泡菌模型的優(yōu)化策略能有效提高圖挖掘算法的搜索效率和魯棒性,多頭絨泡菌啟發(fā)的算法能高效的完成圖挖掘任務(wù)。
[Abstract]:......
【學(xué)位授予單位】：西南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5;TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 鄧小波;曹聰聰;龍倫海;康耀紅;;蟻群算法搜索熵研究[J];海南大學(xué)學(xué)報(自然科學(xué)版);2007年04期

2 任慶生,曾進(jìn),戚飛虎;自交叉算子[J];控制理論與應(yīng)用;2001年04期

3 田東平;;遺傳算法中的交叉算子研究(英文)[J];內(nèi)蒙古師范大學(xué)學(xué)報(自然科學(xué)漢文版);2007年03期

4 張文修,梁怡;遺傳算法的數(shù)學(xué)基礎(chǔ)[J];西安交通大學(xué)學(xué)報;2000年10期

5 陳琨;張志明;;一種改進(jìn)遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)[J];貴州大學(xué)學(xué)報(自然科學(xué)版);2006年01期

6 胡蘭萍;黃海斌;;遺傳算法及其在化學(xué)領(lǐng)域中的應(yīng)用[J];海南師范學(xué)院學(xué)報(自然科學(xué)版);2006年03期

7 王珊珊;;遺傳算法的理論基礎(chǔ)及應(yīng)用[J];科協(xié)論壇(下半月);2008年09期

8 高翔;海洋;;遺傳算法應(yīng)用[J];赤峰學(xué)院學(xué)報(自然科學(xué)版);2009年03期

9 劉定理;;遺傳算法綜述[J];中國西部科技;2009年25期

10 歐陽柏平;;基于遺傳算法優(yōu)化獨(dú)立分量分析[J];科技信息;2010年07期

相關(guān)會議論文 前10條

1 何敏;陳中顯;梅松濤;;蟻群算法的研究與進(jìn)展[A];中國計(jì)量協(xié)會冶金分會2010年會論文集[C];2010年

2 陳家照;廖海濤;張中位;羅寅生;;一種改進(jìn)的遺傳算法及其在路徑規(guī)劃中的應(yīng)用[A];2009系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會議論文集[C];2009年

3 李國云;劉穎;薛梅;鄔志敏;;遺傳算法在高溫空冷冷凝器優(yōu)化設(shè)計(jì)中的應(yīng)用[A];第五屆全國制冷空調(diào)新技術(shù)研討會論文集[C];2008年

4 王志軍;李守春;張爽;;改進(jìn)的遺傳算法在反演問題中的應(yīng)用[A];新世紀(jì) 新機(jī)遇 新挑戰(zhàn)——知識創(chuàng)新和高新技術(shù)產(chǎn)業(yè)發(fā)展（上冊）[C];2001年

5 任燕翔;姜立;劉連民;從滋慶;;改進(jìn)遺傳算法在三維日照方案優(yōu)化中的應(yīng)用[A];工程三維模型與虛擬現(xiàn)實(shí)表現(xiàn)——第二屆工程建設(shè)計(jì)算機(jī)應(yīng)用創(chuàng)新論壇論文集[C];2009年

6 韓娟;;遺傳算法概述[A];第三屆河南省汽車工程科技學(xué)術(shù)研討會論文集[C];2006年

7 龐國仲;王元西;;基于遺傳算法控制步長的定性仿真方法[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會論文集[C];2000年

8 張忠華;楊淑瑩;;基于遺傳算法的聚類設(shè)計(jì)[A];全國第二屆信號處理與應(yīng)用學(xué)術(shù)會議�？痆C];2008年

9 何翠紅;區(qū)益善;;遺傳算法及其在計(jì)算機(jī)編程中的應(yīng)用[A];1995年中國智能自動化學(xué)術(shù)會議暨智能自動化專業(yè)委員會成立大會論文集（下冊）[C];1995年

10 靳開巖;張乃堯;;幾種實(shí)用遺傳算法及其比較[A];1996年中國智能自動化學(xué)術(shù)會議論文集（下冊）[C];1996年

相關(guān)重要報紙文章 前1條

1 林京;《神經(jīng)網(wǎng)絡(luò)和遺傳算法在水科學(xué)領(lǐng)域的應(yīng)用》將面市[N];中國水利報;2002年

相關(guān)博士學(xué)位論文 前10條

1 楊擴(kuò)軍;TIADC系統(tǒng)校準(zhǔn)算法研究與實(shí)現(xiàn)[D];電子科技大學(xué);2015年

2 黃亞魁;幾類優(yōu)化問題的BB型算法研究[D];西安電子科技大學(xué);2015年

3 王戈;通信信號若干聯(lián)合處理技術(shù)研究[D];解放軍信息工程大學(xué);2013年

4 易雯帆;非線性偏微分方程多解計(jì)算大范圍收斂算法及其應(yīng)用研究[D];湖南師范大學(xué);2016年

5 蔡永智;分布式電力系統(tǒng)狀態(tài)估計(jì)研究[D];華南理工大學(xué);2016年

6 蘇雪平;基于交叉多模信息的新聞圖像人物標(biāo)識算法[D];西北工業(yè)大學(xué);2015年

7 謝侃;稀疏盲分離的理論與算法研究[D];廣東工業(yè)大學(xué);2016年

8 Amjad Mahmood;半監(jiān)督進(jìn)化集成及其在網(wǎng)絡(luò)視頻分類中的應(yīng)用[D];西南交通大學(xué);2015年

9 李險峰;基于改進(jìn)遺傳算法的汽車裝配生產(chǎn)線平衡問題研究[D];北京科技大學(xué);2017年

10 孫秋紅;基于遺傳算法的水質(zhì)數(shù)據(jù)挖掘與應(yīng)用研究[D];燕山大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 楊展;城軌列車自動調(diào)整系統(tǒng)模型與算法研究[D];西南交通大學(xué);2015年

2 馬英鈞;基于人工蜂群算法的約束優(yōu)化問題研究[D];華中師范大學(xué);2015年

3 錢其;電網(wǎng)諧波和間諧波功率的計(jì)量算法研究[D];中國科學(xué)技術(shù)大學(xué);2015年

4 蔣玉冰;無線通信信號到達(dá)角跟蹤算法研究[D];電子科技大學(xué);2014年

5 孫方亮;基于粒子群與中心引力的一種新混合算法及應(yīng)用[D];西安電子科技大學(xué);2014年

6 于詩杰;基于無波前探測的大氣光通信自適應(yīng)補(bǔ)償方法研究[D];西安電子科技大學(xué);2014年

7 柯家龍;壓縮感知算法及其在成像中的應(yīng)用[D];南京郵電大學(xué);2015年

8 劉光泓;并行磁共振圖像全變分恢復(fù)一階算法研究[D];南京郵電大學(xué);2015年

9 張德祥;基于改進(jìn)蟻群算法的機(jī)器人三維路徑規(guī)劃研究[D];青島科技大學(xué);2015年

10 黎鵬;一種改進(jìn)的灰度直方圖跟蹤算法[D];中國科學(xué)院研究生院(光電技術(shù)研究所);2016年

，

本文編號：1663702