《一種改進的蟻群算法求解旅行商問題》是劉仁洪撰寫的一篇論文。
基本介紹
- 中文名：一種改進的蟻群算法求解旅行商問題
- 作者：劉仁洪
- 來源：山東大學
- 分類號：TP301.6
論文摘要,引文格式,
論文摘要
20世紀90年代初,義大利學者等人受螞蟻在覓食過程中可以找出從巢穴到食物源的最短路徑的啟發,提出了蟻群算法(ant cp;pmu algorithm),它是繼禁忌搜尋算法、模擬退火算法、遺傳算法、人工神經網路等啟發式搜尋算法之後出現的一種新的啟發式搜尋算法。蟻群算法不僅能夠智慧型搜尋、全局最佳化,而且具有穩健性、正反饋、分散式計算、易與其它算法結合等特點,魯棒性強,在基本蟻群算法模型的基礎上進行修改,便可用於其它問題;正反饋過程使得該方法能很快發現較好解;分散式計算使得該方法易於並行實現,個體之間不斷進行信息交流和傳遞,有利於發現較好解,不容易陷入局部最優;與啟發式算法相結合,可改善算法的性能。它成功套用於解決許多組合最佳化問題。一些初步研究和套用已顯示出蟻群算法在求解複雜最佳化問題方面的一些優越性,特別是離散最佳化問題。因此,蟻群算法已成為當前群智慧型領域中最令人感興趣和最富有魅力的研究課題之一。目前的研究主要集中在比利時、義大利、德國等國家,國內的研究主要在上海、北京、東北少數幾個學校和研究所開展了此項工作,主要圍繞旅行商及相關問題的實驗仿真。本課題的主要工作包括以下三個方面:首先對蟻群算法進行基礎理論研究,旨在對蟻群算法近年來的研究進展進行總結,歸納算法的成功套用領域和存在的不足,並對不足之處進行深入理論分析,目的在於提高蟻群算法的總體性能。第二是針對算法容易陷入局部最優解,在算法中加入擾動量,擴大搜尋範圍,從而有效控制算法陷入局部最優解。針對蟻群算法收斂速度慢,本文充分利用蟻群在最差路徑上的信息,對蟻群算法信息素更新規則上進行了改進。最後,運用MATLAB平台對改進蟻群算法求解經典的旅行商問題進行仿真實驗,實驗結果表明,本課題提出的改進蟻群算法有效的避免程式過早的陷入局部最優解,同時提高了蟻群算法的速度。目前國內外在蟻群算法理論上的研究甚少,所以本課題將改進的蟻群算法套用到旅行商問題,是一次有效的嘗試。
引文格式
劉仁洪. 一種改進的蟻群算法求解旅行商問題[D].山東大學,2008.
