蟻群優(yōu)化方法中若干問題研究.pdf

1、蟻群優(yōu)化(Ant Colony Optimization，ACO)是一種模擬自然界真實蟻群集體覓食行為的元啟發(fā)式方法?，F(xiàn)已被廣泛用于求解各種工程和科學領域中的復雜優(yōu)化問題。如網絡動態(tài)路由問題，各種經典的組合優(yōu)化難題。ACO算法中螞蟻個體的規(guī)則雖極為簡單，但作為整體卻能將很復雜的問題解決到令人滿意的程度。這使得ACO成為了群體智能的研究熱點之一。很多學者研究了ACO的改進、ACO的應用、ACO的理論等問題，然而仍有不少關于ACO的開放性難

2、題有待解決，比如參數(shù)該如何設置，信息素向量怎樣表示待求解的問題，反饋機制是否一定有益于問題的求解及適合求解什么樣的問題。本文系統(tǒng)地分析了ACO領域的研究工作，并圍繞ACO的求解效率、質量，確定性模型分析，多群設計，信息素表示等方面開展了研究。具體地說，有以下幾點：
　　首先，研究了最大最小螞蟻系統(tǒng)(Max-Min Ant System，MMAS)算法的兩種加速技術。一、是研究了MMAS求解靜態(tài)組合優(yōu)化問題的信息素更新規(guī)則。新規(guī)則在

3、總信息上進行，避免了MMAS在每步迭代中計算總信息和檢查信息素是否越界的操作。二、是研究了利用小規(guī)模實例最優(yōu)解信息來設計MMAS的構造規(guī)則。利用復雜優(yōu)化問題小規(guī)模實例的最優(yōu)解的信息來設計一種MMAS構造解的三段式偽隨機比例規(guī)則，能將有限的搜索能力快速集中到大規(guī)模實例的某一局部解空間。然而，這個規(guī)則弱化了MMAS算法的學習能力。因此研究了一種兩段式隨機比例規(guī)則，以增強算法的學習能力。實驗結果表明，采用這些加速技術能顯著地減少MMAS算法消

4、耗的時間，增強其求解大規(guī)模問題的搜索能力。
　　其次，研究了兩種多群ACO算法的群間信息交換技術。一是通過引入粒子群優(yōu)化(Particle Swarm Optimization，PSO)中“粒子”移動的規(guī)則，研究了基于PSO的信息交換規(guī)則。該規(guī)則所需要的數(shù)據(jù)交換量和信息素更新操作均大大減少。二是通過引入中心引力優(yōu)化(Central Force Optimization，CFO)中“探測器”移動的規(guī)則，研究了基于CFO的信息交換技術

5、。平均而言，該規(guī)則所需要的數(shù)據(jù)交換量和信息素更新操作比原有的方法減少一半。實驗結果表明，與使用經典的技術相比，使用這兩種新的信息交換方法的多群ACO算法在尋優(yōu)能力上有明顯的優(yōu)勢。
　　再次，研究了ACO求解強NP難的背包問題。一、是改進了求解多維背包問題(Multidimensional Knapsack Problem，MdKP)的ACO算法。改進后的算法用簡單的信息素向量表示MdKP，使螞蟻構造一個解的復雜性降低。為了在這種信

6、息素表示中有效使用MdKP的問題知識，設計了新的序啟發(fā)式信息。實驗結果表明，改進后的新算法求解效率和求解質量明顯優(yōu)于文獻中的ACO算法。二、是設計了多維多選擇背包問題(Multidimensional Multichoice Knapsack Problem，MdMcKP)的ACO算法。MdMcKP是MdKP的推廣，具有更強的約束條件。ACO算法中的信息素表示使用了MdMcKP的獨特結構。與其它啟發(fā)式算法的比較實驗表明，ACO算法是當前

7、求解MdMcKP的最好方法之一。
　　最后，研究了確定性ACO模型的收斂性及時間復雜性。建立了一個求解k最小生成樹問題(k-minimum spanning tree，kMST)的競爭平衡的ACO確定性模型。用實驗的方法研究了在典型信息素更新技術下模型的收斂性。然后建立求解一般組合優(yōu)化問題的確定性ACO模型并嚴格地證明其在典型信息素更新技術下是否收斂。最后討論了能收斂的ACO模型的時間復雜性，并得出了ACO算法時間復雜性的一個下界