一種改進蟻群算法在TSP問題上的應用

矯德強，常淮陽

（長春工業大學 電氣與電子工程學院，吉林 長春 130012）

一種改進蟻群算法在TSP問題上的應用

矯德強，常淮陽

（長春工業大學 電氣與電子工程學院，吉林 長春 130012）

針對蟻群算法存在的收斂速度慢和容易陷入最優解的問題，用遺傳算法與非線性尋優來優化蟻群算法。在蟻群完成初始迭代之后，所有路徑構成的解為初始種群，然后經過遺傳算法進行選擇、交叉、變異之后，去提升全局搜索的能力。最后，使用非線性尋優算法增強算法局部搜索的能力。通過這樣的改進達到改善蟻群算法收斂速度及容易陷入最優解的問題，經過這樣改進之后應用在旅行商問題上。

改進蟻群算法；TSP問題；機器人；算法優化

1 對算法的改進

1.1 算法改進的思路

遺傳算法是一種比較常用的隨機搜索算法，在機器學習方面有很好的應用，能在很大程度上減少陷入局部最優的情況。經典非線性規劃算法采用梯度下降的方法進行求解，局部搜索能力較強。因此，本文提出的改進算法結合3種算法的優點，首先，蟻群算法快速地完成初始路徑的選擇，所有路徑作為一個初始群落，然后，作為遺傳算法的初始種群進行全局搜索，最后，在經過一定代數的迭代之后，利用非線性規劃算法去進行局部搜索。通過這樣的算法改進TSP問題最優路徑的選擇。

1.2 算法的具體實現

根據算法改進的思路，可畫出算法的流程圖，見圖1.

其算法的步驟具體如下。

步驟1，對參數進行初始化。

對改進算法的各個參數進行初始賦值。

步驟2，解空間構造。

在蟻群算法完成初次尋徑這一過程中，到達終點的螞蟻所經過的路徑組成的集合就是解空間，也是遺傳算法的初始種群。

步驟3，如何選擇下一節點？

首先，可以假設有m只螞蟻從起點S出發最后到達終點T.一只螞蟻在現在位置，下一刻的位置j如何選擇？

通過下面公式計算到達節點j的轉移概率：

步驟4，和遺傳算法結合。

將上述步驟構造的解空間作為遺傳算法的初始種群，然后將初始種群通過編碼表示成遺傳空間的染色體或者個體，最后求得遺傳算法的適應度函數，通過適應度函數的大小判斷個體的好壞。適應度函數為：

選擇操作是指在一定的概率下選擇種群中的個體組成新的種群，通過進化得到更加優秀的下一代個體。某個個體被選中的概率為：

式（4）中：Fi為個體i的適應度值；N為種群個體的數目。

交叉操作是在種群中隨機選擇2個個體，通過交換組合，繼承操作前2個個體的優點，進而產生新的優秀個體。第k個染色體αk和第l個染色體αl在j位進行交叉操作的方法為：

式（5）（6）中：b為[0，1]的隨機數。

變異操作是指種群中的一個體發生一點變異，形成一個更好個體的過程。種群中某一個體i的某一基因片段j發生變異的操作為：

步驟5，信息素更新。

信息素更新策略主要指實時信息素更新和全局路徑信息素更新。

式（8）中：ρ為區間[0，1]的可以調節的參數；τ0為信息素初始值。

式（9）中：Δτij＝1/L*，L*為所有路徑中最短的一條的長度；ρ為[0，1]區間內的可調參數。

步驟6，非線性尋優。

在遺傳算法進化到20代后，將此時所得的結果作為非線性尋優的初始值，然后用MATLAB優化工具箱中的線性規劃函數對目標函數進行局部尋優，最終得到所求的最優解。

2 仿真結果

本文用改進的蟻群算法對TSP問題進行了求解，分析了改進后新算法的優點。設定20個節點坐標：（5，6）、（25，12）、（8，23）、（11，8）、（30，2）、（21，4）、（19，20）、（8，10）、（3，14）、（30，9）、（25，26）、（15，16）、（20，6）、（33，9）、（22，0）、（0，18）、（36，3）、（18，23）、（34，15）、(27，14)。改進算法的仿真結果如圖2所示。

圖1 改進算法流程圖

圖2 改進算法在TSP問題上的仿真結果

3 結束語

本文通過對蟻群算法經過遺傳算法和非線性規劃的改進，增強了算法的搜索能力，加快了收斂速度，同時避免了陷入局部最優。實驗證明，改進蟻群算法能提高精確度，增強自我搜索能力。

TP301.6

A

10.15913/j.cnki.kjycx.2018.01.145

2095－6835（2018）01－0145－02

〔編輯：劉曉芳〕