【正文】 逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的發(fā)展前途的方法；SA算法求解速度非常 快，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。 蟻群算法解決車輛路徑問題 給定一個(gè)有n個(gè)城市的TSP問題，人螞蟻的數(shù)量m，每個(gè)人工螞蟻的行為符合下列規(guī)律：（1）根據(jù)路徑上的信息素濃度，以相應(yīng)的概率來選取下一步路徑；（2）不再選取自己本次循環(huán)已經(jīng)走過的路徑為下一步路徑；（3）當(dāng)完成了一次循環(huán)后，根據(jù)整個(gè)路徑長度來釋放相應(yīng)濃度的信息素，并更新走過的路徑上的信息素濃度。實(shí)現(xiàn)步驟如下：開始參數(shù)初始化對每只螞蟻按概率移植下一城市，完成一次循環(huán)計(jì)算各螞蟻的路徑長度，記錄當(dāng)前最優(yōu)解修改信息素是否迭代結(jié)束 否 是輸出最優(yōu)解結(jié)束步驟1：初始化相關(guān)參數(shù)，如螞蟻的數(shù)目，城市的數(shù)量，迭代次數(shù)，總的信息素等；步驟2：對每只螞蟻按概率移至下一城市節(jié)點(diǎn)，完成第一次循環(huán)。每只螞蟻通過訪問各個(gè)城市而形成一個(gè)解，并在訪問的過程中，講已訪問到的城市保留在i中。城市i中每只螞蟻要從沒有訪問過的城市中選擇訪問下一個(gè)城市j時(shí)須根據(jù)概率公式（本文采用輪盤賭選擇來優(yōu)化基本蟻群算法）進(jìn)行選擇，如此循環(huán)，知道所有的螞蟻訪問完所有的城市。步驟3：計(jì)算每只螞蟻行走的總路徑長度，并保存最優(yōu)解。步驟4：按照更新方式更新每一次迭代的最優(yōu)路徑。步驟5：迭代完成，輸出最優(yōu)解步驟6：程序結(jié)束 數(shù)值實(shí)驗(yàn)結(jié)果及分析由上述定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery已證明TSP問題是NP難題，因此，VRP也屬于NP難題。直觀的說，TSP問題就是指一位商人從自己的家出發(fā)，希望能找到一條最短路徑，途徑給定的城市集合中的所有城市，最好返回家。并且，每個(gè)城市都被訪問一次且僅一次。 輪盤賭選擇優(yōu)化前后數(shù)據(jù)對比（1）輪盤賭選擇優(yōu)化前的迭代結(jié)果（優(yōu)化前）ALPHABETAROU總信息數(shù)城市數(shù)量螞蟻數(shù)量迭代次數(shù)迭代結(jié)果1100513820004762100513820004783100513820004764100513820004675100513820004786100513820004787100513820004678100513820004669100513820004671010051382000468（2）輪盤賭選擇優(yōu)化后的迭代結(jié)果（優(yōu)化后）ALPHABETAROU總信息數(shù)城市數(shù)量螞蟻數(shù)量迭代次數(shù)迭代結(jié)果1100513820004452100513820004403100513820004344100513820004395100513820004456100513820004437100513820004388100513820004479100513820004371010051382000441（2）輪盤賭選擇優(yōu)化前后結(jié)果對比表最優(yōu)解平均值優(yōu)化前467優(yōu)化后434 MAX_MIN算法改進(jìn)前后數(shù)據(jù)對比（1）MAX_MIN算法改進(jìn)前的迭代結(jié)果（優(yōu)化前）ALPHABETAROU總信息數(shù)城市數(shù)量螞蟻數(shù)量迭代次數(shù)迭代結(jié)果110051355004762100513550047831005135500476410051355004675100513550047861005135500478710051355004678100513550046691005135500467101005135500468（2）MAX_MIN算法改進(jìn)后的迭代結(jié)果（優(yōu)化后）ALPHABETAROU總信息數(shù)城市數(shù)量螞蟻數(shù)量迭代次數(shù)迭代結(jié)果1100513820004532100513820004673100513820004774100513820004705100513820004736100513820004497100513820004708100513820004499100513820004751010051382000449（3）MAX_MIN算法改進(jìn)前后對比表最優(yōu)解平均值優(yōu)化前467優(yōu)化后449通過迭代結(jié)果數(shù)據(jù)的比較，不難發(fā)現(xiàn)，被優(yōu)化的蟻群算法在相同的參數(shù)下，經(jīng)過同樣多的迭代次數(shù)之后，輸出的最優(yōu)路徑的可能性更大。同時(shí)，證明了，輪盤選擇和最大最小優(yōu)化是可行的。第5章 總結(jié)與展望本文主要對蟻群算法的基礎(chǔ)性理論、優(yōu)化策略，以及蟻群算法在車TSP問題中的應(yīng)用進(jìn)行了講解，基礎(chǔ)理論部分的主要內(nèi)容基本上是對前人的研究成果進(jìn)行具體闡述，蟻群算法的優(yōu)化和蟻群算法在TSP問題的應(yīng)用是本文講解的重點(diǎn)。在整個(gè)設(shè)計(jì)中，學(xué)到了很多，從對蟻群算法不了解到現(xiàn)在能寫出簡單的蟻群算法，同時(shí)，也讓我對算法產(chǎn)生了更深的認(rèn)識(shí)。以前，一直害怕算法，更害怕接觸新的算法，但幸好有負(fù)責(zé)本次設(shè)計(jì)的導(dǎo)師宗欣露老師的幫助，當(dāng)然，也少不了同學(xué)的幫助，正因?yàn)橛兴麄兊膸椭?，此次畢業(yè)設(shè)計(jì)才得以順利完成。在此，表示我對他們的萬分感激！路漫漫其修遠(yuǎn)兮，吾將上下而求索。希望在未來的學(xué)習(xí)工作中，以更豐厚的成果來答謝曾經(jīng)關(guān)心、幫助和支持我的所有老師同學(xué)，朋友，家人。參考文獻(xiàn)1. 楊海，王洪國，徐衛(wèi)志．蟻群算法的應(yīng)用研究與發(fā)展[J]．科學(xué)和技術(shù)信息學(xué)報(bào). 2. 張宗永，孫靜，譚家華．蟻群算法的改進(jìn)及其應(yīng)用[J]．上海交通大學(xué)學(xué)報(bào).3. 劉志碩，申金升，柴躍廷．一種求解車輛路徑問題的混合多蟻群算法[J]．系統(tǒng)仿真學(xué)報(bào)，2007.4. 李士勇. 蟻群算法及其應(yīng)用，哈爾濱工業(yè)大學(xué)出版社.5. 靳蕃，范俊波，譚永東．神經(jīng)網(wǎng)絡(luò)與神經(jīng)計(jì)算機(jī)原理應(yīng)用［M］．成都：西南交通大學(xué)出版社．6. 李士勇．蟻群算法及其應(yīng)用［M］．哈爾濱：哈爾濱工業(yè)大學(xué)出版社．7. 寧春林，田國會(huì)，尹建芹，等．MAX_MIN蟻群算法在固定貨架揀選路徑優(yōu)化中的應(yīng)用［Ｊ］．山東大學(xué)學(xué)報(bào)：工學(xué)版. 8. 王攀，商海燕，潘利群，等．基于混合遺傳算法的中國旅行商問題滿意解［Ｊ］．航空計(jì)算技術(shù).9. 劉士新，宋健海，唐加福. 蟻群最優(yōu)化——模型、算法及應(yīng)用綜述[J]. 系統(tǒng)工程學(xué)報(bào).10. Maniezzo,V.，Colorni,A.，Dorigo,M. The Ant System applied to the Quadratic Assignment Problem. Technical Report IRIDIA/9428，Universite Libre de Bruxelles，Belgium.11. 溫文波，杜維. 蟻群算法概述. 石油化工自動(dòng)化.12. 王小平，曹立明. 遺傳算法——理論、應(yīng)用于軟件實(shí)現(xiàn). 西安交通大學(xué)出版社.13. 潘正君，康立山，陳毓屏. 演化計(jì)算. 北京：清華大學(xué)出版社.14. 高尚，鐘娟，莫述軍. 連續(xù)優(yōu)化問題的蟻群算法研究[J]. 微機(jī)發(fā)展.15. 康立山，謝云，尤失勇等. 非數(shù)值并行算法（一）[M]. 北京：科學(xué)出版社，1998.16. Ansari N，Hou ，邊肇祺譯. 用于最優(yōu)化的計(jì)算智能. 北京：清華大學(xué)出版社。17. 畢軍，付夢印. 一種改進(jìn)的蟻群算法求解最短路徑問題. 計(jì)算機(jī)工程與應(yīng)用.35