改進的蟻群算法求解TSP問題的研究.pdf

1、蟻群優(yōu)化算法(ant colony optimization，ACO)由意大利學者 Marco Dorigo，V Maniezzo,A. Colorni于1992年首先提出，是基于螞蟻群體覓食過程中沿著最短路徑行進的這種生物學行為發(fā)展起來的一類群智能優(yōu)化方法。在解決傳統(tǒng)優(yōu)化方法難以奏效的具有NP-hard特性的組合優(yōu)化問題中利用該算法取得了令人鼓舞的效果，因而受到了學術界以及工業(yè)界的廣泛關注。目前，蟻群優(yōu)化算法已經(jīng)成為計算智能方法中的一

2、個重要分支，成為當下蓬勃發(fā)展的熱點研究課題之一。蟻群優(yōu)化算法的理論研究相對滯后，特別是算法的參數(shù)選擇和收斂性證明方面還有待于進一步研究。雖然，該研究方法處于研究的初級階段，但是一些研究成果已經(jīng)顯示出蟻群系統(tǒng)在求解復雜優(yōu)化問題方面的優(yōu)越性。目前，蟻群系統(tǒng)己成功應用于求解旅行商問題(Traveling salesman problem TSP)、二次分配問題(QAP)和job-shop調度問題，取得了很好的實驗效果。
　　TSP（Tr

3、avelling Salesman Problem）也稱作貨郎擔或巡回售貨員問題，在運籌學、管理科學及工程實際中具有廣泛的用途。TSP問題是組合優(yōu)化中的著名難題，一直受到人們的極大關注。由于其NP難題性質，至今尚未完全解決。
　　本文的主要工作如下：
　　1.對蟻群算法的基本理論以及在TSP問題中的應用進行了較為深入和系統(tǒng)的研究。介紹了蟻群算法的基本原理、特點、構成和算法的實現(xiàn)方法。
　　2.基本蟻群算法由于存在搜索時

4、間長，易陷入局部最優(yōu)解等突出缺點，使得求解效果不是很好。針對這些缺陷，提出了利用改進的蟻群算法求解TSP問題。改進主要在參數(shù)的初始化、狀態(tài)轉移概率的選擇策略以及信息素更新方法的改進三個方面。
　　①對于一個初始的TSP，首先考慮對其進行預處理。在利用螞蟻算法求解問題之前，先用近鄰法構造一個初始游歷，并計算信息素初值。
　　②利用Dorigo M等提出的Ant-Q Systems算法，采用確定性和隨機性選擇相結合的選擇策略，并

5、在搜索過程中動態(tài)調整狀態(tài)轉移概率。
　?、坌畔⑺馗虏捎迷诰€單步更新信息素及離線全局更新信息素相結合的方法，即在螞蟻巡游過程中在線單步更新信息素以及在本次迭代結束時離線全局更新信息素。
　　將以上三步算法的改進結合起來，用MATLAB模擬，選取了TSPLIB中的十個TSP問題進行實驗，并與用基本蟻群算法做的結果以及現(xiàn)在應用比較廣泛的遺傳算法的結果做了比較。然后運用改進的蟻群算法對以中國100城市為代表的中國旅行商問題進行了數(shù)