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

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

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

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

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

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

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

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