最大團(tuán)問題的蟻群算法研究.pdf

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

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

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