一種改進(jìn)蟻群算法在TSP問題上的應(yīng)用

矯德強(qiáng)，?；搓?/p>

（長春工業(yè)大學(xué) 電氣與電子工程學(xué)院，吉林 長春 130012）

一種改進(jìn)蟻群算法在TSP問題上的應(yīng)用

矯德強(qiáng)，?；搓?/p>

（長春工業(yè)大學(xué) 電氣與電子工程學(xué)院，吉林 長春 130012）

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

改進(jìn)蟻群算法；TSP問題；機(jī)器人；算法優(yōu)化

1 對(duì)算法的改進(jìn)

1.1 算法改進(jìn)的思路

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

1.2 算法的具體實(shí)現(xiàn)

根據(jù)算法改進(jìn)的思路，可畫出算法的流程圖，見圖1.

其算法的步驟具體如下。

步驟1，對(duì)參數(shù)進(jìn)行初始化。

對(duì)改進(jìn)算法的各個(gè)參數(shù)進(jìn)行初始賦值。

步驟2，解空間構(gòu)造。

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

步驟3，如何選擇下一節(jié)點(diǎn)？

首先，可以假設(shè)有m只螞蟻從起點(diǎn)S出發(fā)最后到達(dá)終點(diǎn)T.一只螞蟻在現(xiàn)在位置，下一刻的位置j如何選擇？

通過下面公式計(jì)算到達(dá)節(jié)點(diǎn)j的轉(zhuǎn)移概率：

步驟4，和遺傳算法結(jié)合。

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

選擇操作是指在一定的概率下選擇種群中的個(gè)體組成新的種群，通過進(jìn)化得到更加優(yōu)秀的下一代個(gè)體。某個(gè)個(gè)體被選中的概率為：

式（4）中：Fi為個(gè)體i的適應(yīng)度值；N為種群個(gè)體的數(shù)目。

交叉操作是在種群中隨機(jī)選擇2個(gè)個(gè)體，通過交換組合，繼承操作前2個(gè)個(gè)體的優(yōu)點(diǎn)，進(jìn)而產(chǎn)生新的優(yōu)秀個(gè)體。第k個(gè)染色體αk和第l個(gè)染色體αl在j位進(jìn)行交叉操作的方法為：

式（5）（6）中：b為[0，1]的隨機(jī)數(shù)。

變異操作是指種群中的一個(gè)體發(fā)生一點(diǎn)變異，形成一個(gè)更好個(gè)體的過程。種群中某一個(gè)體i的某一基因片段j發(fā)生變異的操作為：

步驟5，信息素更新。

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

式（8）中：ρ為區(qū)間[0，1]的可以調(diào)節(jié)的參數(shù)；τ0為信息素初始值。

式（9）中：Δτij＝1/L*，L*為所有路徑中最短的一條的長度；ρ為[0，1]區(qū)間內(nèi)的可調(diào)參數(shù)。

步驟6，非線性尋優(yōu)。

在遺傳算法進(jìn)化到20代后，將此時(shí)所得的結(jié)果作為非線性尋優(yōu)的初始值，然后用MATLAB優(yōu)化工具箱中的線性規(guī)劃函數(shù)對(duì)目標(biāo)函數(shù)進(jìn)行局部尋優(yōu)，最終得到所求的最優(yōu)解。

2 仿真結(jié)果

本文用改進(jìn)的蟻群算法對(duì)TSP問題進(jìn)行了求解，分析了改進(jìn)后新算法的優(yōu)點(diǎn)。設(shè)定20個(gè)節(jié)點(diǎn)坐標(biāo)：（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)。改進(jìn)算法的仿真結(jié)果如圖2所示。

圖1 改進(jìn)算法流程圖

圖2 改進(jìn)算法在TSP問題上的仿真結(jié)果

3 結(jié)束語

本文通過對(duì)蟻群算法經(jīng)過遺傳算法和非線性規(guī)劃的改進(jìn)，增強(qiáng)了算法的搜索能力，加快了收斂速度，同時(shí)避免了陷入局部最優(yōu)。實(shí)驗(yàn)證明，改進(jìn)蟻群算法能提高精確度，增強(qiáng)自我搜索能力。

TP301.6

A

10.15913/j.cnki.kjycx.2018.01.145

2095－6835（2018）01－0145－02

〔編輯：劉曉芳〕