蟻群算法求解最大團問題研究與應用.pdf

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

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

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