最大團問題的蟻群算法研究.pdf

1、蟻群優(yōu)化算法是思想源于自然現(xiàn)象的meta-heuristic算法，經(jīng)歷了十多年的發(fā)展已經(jīng)成為解決很多優(yōu)化問題的有效工具。最大團問題是經(jīng)典的NP難的組合優(yōu)化問題，它不僅在理論上有比較重要的地位，在實踐中也很有用處。它是測試各種算法解決問題能力的手段，很多其它問題也可以規(guī)約為圖的最大團問題。有鑒于此，本文在前人研究的基礎(chǔ)上對蟻群算法解決最大團問題的應用進行了進一步的研究。尋找出前人方法中的缺陷與疏忽，提出能更好地平衡算法intensific

2、ation和diversification的手段。本文首先介紹了關(guān)于meta-heuristic和最大團問題的方法的一些基本知識。然后介紹了處理最大團問題的Vertex-AC和Edge-AC算法以及在Vertex-AC基礎(chǔ)上增加局部信息素更新的蟻群優(yōu)化算法。并分析了這些算法在intensification和diversification上的平衡性和不足。然后提出了一種改進局部信息素更新機制的方法，并利用Discrete for Math

3、ematics and Theoretical Computer Science(DIMACS)提供的基準實例進行了比較測試。從測試結(jié)果可以看到，本文方法有更好的求解效果。本文進一步對蟻群算法的性能提升進行探究。首先介紹了目前處理最大團問題效果最好的RLS方法，并指出其性能優(yōu)良的原因。在類似思路指引下提出了以平衡性判斷為依據(jù)來調(diào)整算子以適應不同問題實例的算法，并對評估算法平衡性的手段和各算子對算法平衡性的影響進行了一些分析，進行了一些試