蟻群優(yōu)化算法研究及應用.pdf

1、復雜的組合優(yōu)化問題呈現于許多不同的領域,例如經濟、商業(yè)、工程、工業(yè)和醫(yī)療。然而,在實際中這些種類的問題都非常難以解決?？梢詮睦碚撚嬎銠C科學中攝取解決此類問題的內在困難,即很多這樣的問題都是NP-難問題,這意味著迄今找不到在多項式時間內解決它們的算法。而且這些問題通常擁有較大的規(guī)模,傳統(tǒng)的方法因其需要大量的計算時間而不再可行。
　　 在20世紀90年代早期,一種用于解決優(yōu)化的蟻群優(yōu)化技術被成功提出。蟻群優(yōu)化的靈感來自于真實螞蟻群體

2、的覓食行為。利用這種行為開發(fā)了人工螞蟻群體,用以求解很多復雜組合優(yōu)化問題的近似解,例如離散優(yōu)化問題、連續(xù)優(yōu)化問題以及電信通信中的路由和負載平衡的重要問題。從實驗上已經證明了蟻群優(yōu)化是群體智能中的成功算法種類。群體智能算法由簡單個體組成,這些個體通過自組織來相互協作來完成工作,沒有任何形式的對群體成員的中心控制。在大量的實驗工作已經展示了蟻群優(yōu)化在解決不同的組合優(yōu)化問題上是行之有效之后,要加深對這種方法的內在機制的理解,不僅需要越來越多的

3、復雜實驗,更需要借助于基于數學而建立的理論。解答算法是怎樣工作和為什么這樣工作之類的問題是重要的,因為這有助于改進算法的應用。因此,理論方面的研究是必須的。
　　 本論文首先回顧一些關于組合優(yōu)化和計算復雜性的基礎理論,研究了蟻群優(yōu)化算法的生物學靈感來源,并展示了如何將生物學的啟發(fā)靈感轉化為一個用于解決離散優(yōu)化問題的簡單算法。然后,論文以更通用的形式概括了在離散優(yōu)化背景下的蟻群優(yōu)化模型,并且描述了一些當今最流行和性能最好的蟻群優(yōu)化

4、算法變種。通過基于旅行商問題的蟻群優(yōu)化算法的實現,本論文力圖在各種不同的蟻群優(yōu)化算法中進行比較性分析,并且將蟻群優(yōu)化算法和其他的元啟發(fā)式算法進行了性能比較,如貪心隨機自適應搜索過程和禁忌搜索。之后,論文提供關于蟻群優(yōu)化元啟發(fā)式的理論研究成果,理論研究的努力會直接讓我們加深對蟻群優(yōu)化算法的行為的理解。然后,論文闡述了蟻群優(yōu)化的一些典型成功的應用,并總結了一些如何把蟻群優(yōu)化算法應用到不同種類的問題上的原則和步驟。最后一節(jié)總結了全文內容,得出