蟻群算法求解最大團(tuán)問題研究與應(yīng)用.pdf

1、蟻群算法是模擬螞蟻覓食行為的一種群體智能算法。蟻群算法最初用來解決旅行商問題，目前為止蟻群算法已經(jīng)成為解決組合優(yōu)化問題的有效方法。最大團(tuán)問題是一種經(jīng)典的組合優(yōu)化問題，并在社會網(wǎng)絡(luò)、計(jì)算機(jī)視覺、故障診斷等領(lǐng)域有非常廣泛的應(yīng)用。因此，論文主要研究蟻群算法解決最大團(tuán)問題。
　　總結(jié)了最大團(tuán)問題、蟻群算法的研究現(xiàn)狀，詳細(xì)介紹了蟻群算法解決最大團(tuán)問題及其研究現(xiàn)狀。針對蟻群算法解決最大團(tuán)問題中信息素的釋放位置——節(jié)點(diǎn)和邊進(jìn)行了詳細(xì)的分析，并對

2、蟻群算法解決最大團(tuán)的重要參數(shù)進(jìn)行了實(shí)驗(yàn)分析。針對目前蟻群算法求解最大團(tuán)易陷于局部最優(yōu)、收斂速度較慢的問題進(jìn)行分析和改進(jìn)。通過增加解的多樣性解決陷入局部最優(yōu)問題。提出一種混合螞蟻轉(zhuǎn)移策略，包括輪盤賭選點(diǎn)策略和補(bǔ)充選點(diǎn)策略。補(bǔ)充選點(diǎn)策略主要用來提高較少被搜索到的節(jié)點(diǎn)被選擇的概率。補(bǔ)充選點(diǎn)策略擴(kuò)大了螞蟻搜索空間，增加了解的多樣性。多樣性的增加會導(dǎo)致收斂時(shí)間增加，因此引入局部改善策略，通過局部改善策略提高算法的收斂速度和算法的求解精度。DIMA

3、CS是國際上用來衡量求解最大團(tuán)問題算法性能的基準(zhǔn)圖庫。改進(jìn)后的蟻群算法在DIMACS基準(zhǔn)圖例上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了新的改進(jìn)策略在求解精度和收斂速度方面均有提高。
　　凝聚子群是一種典型的社會網(wǎng)絡(luò)結(jié)構(gòu)，社會網(wǎng)絡(luò)中完全連接的團(tuán)結(jié)構(gòu)是緊密度最高的凝聚子群，因此，尋找社會網(wǎng)絡(luò)中最大團(tuán)結(jié)構(gòu)成為研究重點(diǎn)之一，具有重要意義。將改進(jìn)后的蟻群算求解社會網(wǎng)絡(luò)的凝聚子群結(jié)構(gòu)，并在社會網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的算法在社會網(wǎng)絡(luò)中也具有較高的