廣義蟻群算法收斂速度和算法復雜度分析及應用.pdf

1、廣義蟻群優(yōu)化算法是在蟻群算法基礎(chǔ)上的改進和提升，但是目前針對該算法優(yōu)化性能與收斂速度方面的研究理論還很少。算法理論研究的匱乏已經(jīng)成為制約該算法進一步發(fā)展和應用的瓶頸，從理論上對廣義蟻群優(yōu)化算法的收斂速度和算法復雜度進行分析對該算法的發(fā)展有著重要的意義。
　　本文基于吸收態(tài) Markov過程，建立一種通用性較強的過程模型，對廣義蟻群優(yōu)化算法的收斂速度從理論上進行分析。對收斂速度進行具體分析時，采用期望收斂時間作為主要指標，初步給出其

2、估算分析的方法。通過對兩個簡單的廣義蟻群優(yōu)化算法模型的理論分析，初步探索廣義蟻群優(yōu)化算法的時間復雜度與問題規(guī)模和螞蟻數(shù)目的關(guān)系。
　　由收斂速度理論分析結(jié)果可知，對于大規(guī)模TSP問題，適當增加螞蟻數(shù)目，可以減少收斂到最優(yōu)解的迭代次數(shù)；如果最優(yōu)路徑上的概率選擇函數(shù)足夠大，廣義蟻群優(yōu)化算法可以在多項式時間內(nèi)找到最優(yōu)解。實驗證明無論是得到的解的質(zhì)量，還是算法的收斂速度，廣義蟻群算法都要優(yōu)于傳統(tǒng)蟻群算法，且其優(yōu)勢會隨著問題規(guī)模的擴大愈加明