求解TSP問題的改進(jìn)蟻群算法研究

盧 曦

（南通理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，江蘇 南通 226003）

求解TSP問題的改進(jìn)蟻群算法研究

盧 曦

（南通理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，江蘇 南通 226003）

文章提出了運(yùn)用一種改進(jìn)的蟻群算法，主要用來(lái)求解旅行商問題（Travelling Salesman Problem，TSP）。實(shí)驗(yàn)表明，改進(jìn)的蟻群算法一定程度上彌補(bǔ)了基本的蟻群算法容易陷入收斂停滯的缺點(diǎn)，且更容易發(fā)現(xiàn)更好性質(zhì)的解。

蟻群算法；最優(yōu)化路徑；旅行商問題

1 旅行商問題（TSP問題）

本文需要解決的旅行商問題，即Travelling Salesman Problem，簡(jiǎn)稱TSP問題。假設(shè)有一名商人需要去n個(gè)城市販賣商品，該商人想要選擇一條最合理的線路，線路需要滿足以下要求：（1）每個(gè)城市只能到達(dá)一次；（2）線路需要回到商人第一個(gè)出發(fā)的城市；（3）必須是滿足（1）（2）條件的所有線路中最短的線路。它是組合優(yōu)化中研究最多的問題之一，是一個(gè)經(jīng)典的非確定性（Nondeterministic Poly-nomial，NP）難題。

2 普通蟻群算法

求解TSP問題此類NP問題的算法有很多，本文選取蟻群算法作為主要研究對(duì)象。自然界中螞蟻在尋覓食物時(shí)能夠自發(fā)的發(fā)現(xiàn)最優(yōu)路徑，Marco Dorigo等人由此受到啟發(fā)，于1992年提出的一種新型智能算法即蟻群算法（Ant Colony Algorithm，ACA），又稱螞蟻算法。蟻群算法是一種模擬進(jìn)化算法，通過模擬螞蟻的行為特性中的內(nèi)在搜索機(jī)制來(lái)尋求最優(yōu)解。經(jīng)實(shí)際研究表明，該算法在求解復(fù)雜優(yōu)化問題例如NP問題方面具有諸多優(yōu)良的性質(zhì)。

事實(shí)上，在使用普通蟻群算法求解此類問題時(shí)經(jīng)常會(huì)遇到一些問題，比如：算法所給出最優(yōu)解并不理想，可能只是一些局部的最優(yōu)解，而不是問題所希望的全局最優(yōu)解。這很大程度上是由普通蟻群算法解的性質(zhì)造成的。

在使用算法進(jìn)行迭代求解的時(shí)候，一般開始的時(shí)候迭代收斂速度還比較理想，但當(dāng)?shù)^程進(jìn)行到后期，可能在出現(xiàn)一些糟糕的停滯現(xiàn)象。這些我們不希望遇到的停滯現(xiàn)象通常會(huì)出現(xiàn)在某個(gè)（些）局部最優(yōu)解的鄰域附近。

普通蟻群算法的搜索時(shí)間會(huì)比較久一點(diǎn)。首先這和算法的時(shí)間復(fù)雜度有關(guān)。其次這和算法中多個(gè)螞蟻運(yùn)動(dòng)過程的隨機(jī)處理有關(guān)。

3 改進(jìn)蟻群算法求解TSP問題

3.1 算法設(shè)計(jì)思路

TSP問題屬于NP完全組合問題，通常的解決方法可以分為精確算法（Exact Algorithms）與啟發(fā)式算法（Heuristics Algorithms）。

一般來(lái)說(shuō)，精確算法在能夠求解的情況下，獲得的解通常比啟發(fā)式智能算法要更優(yōu)。但是精確算法基于嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)方式來(lái)求解，必然會(huì)遇到指數(shù)爆炸問題，這使得此類算法難以求只能有效的求解一些中小規(guī)模的確定性NP問題。對(duì)于實(shí)際生活中會(huì)遇到的大規(guī)模NP問題精確算法難以解決，而啟發(fā)式算法卻總可以在有限時(shí)間內(nèi)找到可行解或者較滿意的次優(yōu)解。

蟻群算法是啟發(fā)式算法中的一種，在本文中已經(jīng)具體說(shuō)明了基本蟻群算法的優(yōu)缺點(diǎn)。那么我們是不是可以針對(duì)原有算法的一些不足之處，引進(jìn)Hybrid思想，將啟發(fā)式的蟻群算法和精確計(jì)算相結(jié)合，從而提高算法的計(jì)算效率。

3.2 算法基本原理

以TSP問題為例，首先通過蟻群算法其進(jìn)行初始的全局計(jì)算，這時(shí)候我們可以得到一組數(shù)據(jù)，即每條路徑上的信息量。這組數(shù)據(jù)很關(guān)鍵，螞蟻會(huì)通過路徑上留下的信息量來(lái)選擇路徑，信息量越大螞蟻選擇的概率則越大，這也是對(duì)節(jié)點(diǎn)進(jìn)行分類計(jì)算的判斷根據(jù)。

我們?cè)谒械墓?jié)點(diǎn)中找到一些特殊的節(jié)點(diǎn)，這些節(jié)點(diǎn)與之關(guān)聯(lián)的信息量均比較大。對(duì)這些特殊的節(jié)點(diǎn)再次進(jìn)行蟻群算法，因?yàn)榇蟠蟮亟档土擞?jì)算的規(guī)模，所以無(wú)論是收斂速度還是計(jì)算時(shí)間都在一定程度上得到了提高。如圖1所示，這些節(jié)點(diǎn)是被篩選出的信息量關(guān)聯(lián)度大的相關(guān)節(jié)點(diǎn)，圖中所勾畫的回路是第二次進(jìn)行蟻群算法所得到的最短路徑。

圖1 特殊節(jié)點(diǎn)間的最短路徑

我們可以分別以這些節(jié)點(diǎn)為起點(diǎn)/終點(diǎn)，以兩點(diǎn)間的連線為軸，計(jì)算出非特殊節(jié)點(diǎn)與這些軸之間的距離，從而將其他非特殊節(jié)點(diǎn)進(jìn)行分類。如圖1所示，若某非特殊節(jié)點(diǎn)a與軸8～10的距離比相對(duì)其他軸線的距離都要短，則可以將節(jié)點(diǎn)a劃歸到（8，10）的區(qū)間內(nèi)。如此類推，在圖1中就可以把全部節(jié)點(diǎn)完全劃分成20個(gè)小的局部空間。

在所得到的局部范圍內(nèi)，由于計(jì)算規(guī)模的大大降低，復(fù)合了精確計(jì)算的條件，所以我們可以選擇精確計(jì)算中的動(dòng)態(tài)規(guī)劃算法，以特殊節(jié)點(diǎn)為起點(diǎn)/終點(diǎn)，找到兩點(diǎn)間的最短路徑。這樣將所有子空間的最短路徑都求出后相連接，即可得到全局的最短路徑。

在求出全局的最短路徑之后，我們對(duì)這條最短路徑上的信息量進(jìn)行更新，這樣一次迭代完成。如此反復(fù)迭代，得到最后的最優(yōu)解。

3.3 改進(jìn)蟻群算法求解TSP問題

3.3.1 蟻群系統(tǒng)模型

以TSP問題為例，說(shuō)明改進(jìn)后的蟻群系統(tǒng)模型。

假設(shè)共有m只螞蟻，n個(gè)城市，dij表示城市i和城市j之間距離，τij（t）表示在t時(shí)刻城市i和城市j之間的信息量，初始時(shí)刻τij（0）=C（C是初始信息量，為常數(shù)）。表示在t時(shí)刻螞蟻k從城市i移動(dòng)到城市j的概率，計(jì)算公式如下。

allowdk表示螞蟻k下一步允許選擇到達(dá)的城市集合，α表示在螞蟻選擇路徑時(shí)受信息量的影響大小，ηij表示螞蟻k從城市i移動(dòng)到城市j的期望值，β表示該期望值ηij的影響大小。經(jīng)過n個(gè)時(shí)刻，這只螞蟻能夠走完所有城市，我們認(rèn)為每只螞蟻所走過的路徑就是一個(gè)解。此時(shí)需要對(duì)路徑上的信息量進(jìn)行更新：

ρ∈（0，1）表示信息量τi（jt）根據(jù)時(shí)間產(chǎn)生的衰減度表示螞蟻k從城市i移動(dòng)到城市j時(shí)在路徑ij上留下的信息量。

參照基本蟻群算法求出特殊節(jié)點(diǎn)的最短路徑，記錄下特殊節(jié)點(diǎn)間的路徑Rij。dRi表示非特殊節(jié)點(diǎn)于這些路徑的垂直距離?？梢詫?duì)非特殊節(jié)點(diǎn)分類：

可以使用固定的迭代次數(shù)停止算法，也可以選擇在收斂趨勢(shì)不明顯的時(shí)候停止計(jì)算。

3.3.2 算法流程圖

改進(jìn)蟻群算法執(zhí)行流程圖，如圖2所示。

3.3.3 算法偽代碼實(shí)現(xiàn)步驟

Step 1：NC ←0（NC為迭代步數(shù)或搜索次數(shù)），NA←0（NA記錄），對(duì)各τi（jt）和Δ（tt））完成初始化，并將m個(gè)螞蟻隨機(jī)地放在n個(gè)頂點(diǎn)上；

Step 4：如果NA=0，計(jì)算出，并且排序選出較大的約1/10的特殊節(jié)點(diǎn)，否則，跳至step 7；

Step 5：NA=NA+1；

Step 6：跳轉(zhuǎn)Step 2；

Step 7：根據(jù)公式（1）將節(jié)點(diǎn)進(jìn)行分類；

Step 8：將分好類的節(jié)點(diǎn)以特殊節(jié)點(diǎn)為始/終點(diǎn)，動(dòng)態(tài)規(guī)劃算法得子空間最好解；

Step 9：合并子解，得到全局最優(yōu)解；

Step 10：按公式（2）更新路徑上的信息量；

Step 12：若NC＜預(yù)定的迭代次數(shù)或者找到的都是相同解，則轉(zhuǎn)Step 2，否則輸出最優(yōu)解。

在求解較大規(guī)模TSP問題時(shí)，可以簡(jiǎn)化計(jì)算，將公式（2）修改為公式（3）：

圖2 改進(jìn)蟻群算法執(zhí)行流程圖

4 結(jié)語(yǔ)

本文首先簡(jiǎn)單介紹了TSP問題的產(chǎn)生，以及使用普通蟻群算法求解TSP問題時(shí)的優(yōu)缺點(diǎn)。然后文章主要針對(duì)其不足之處，對(duì)算法進(jìn)行了改進(jìn)，提出了一種新的蟻群算法。改進(jìn)的蟻群算法主要在局部方面進(jìn)行改進(jìn)，根據(jù)全局信息素對(duì)節(jié)點(diǎn)進(jìn)行分類化，對(duì)計(jì)算空間進(jìn)行劃分，在局部采用動(dòng)態(tài)規(guī)劃精確計(jì)算，而在全局方面仍然保留蟻群算法能夠優(yōu)化控制的優(yōu)勢(shì)。最后本文針對(duì)TSP問題給出改進(jìn)蟻群算法的實(shí)現(xiàn)步驟與計(jì)算機(jī)偽代碼。

［1］馬良，王龍德.背包問題的螞蟻優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2001（8）：4-5.

［2］吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法［J］.計(jì)算機(jī)學(xué)報(bào)，2001（12）：1328-1333.

［3］黎鎖平，張秀媛，楊海波.人工蟻群算法理論及其在經(jīng)典TSP問題中的實(shí)現(xiàn)［J］.交通運(yùn)輸系統(tǒng)工程與信息，2002（3）：25.

［4］項(xiàng)寶衛(wèi)，應(yīng)建健.蟻群算法研究綜述［J］.臺(tái)州學(xué)院學(xué)報(bào)，2007（6）：20.

Study on the improved Ant Colony Algorithm for solving TSP

Lu Xi

（Computer and Information Engineering School of Nantong Institute of Technology，Nantong 226003，China）

This paper proposes an improved ACA（Ant Colony Algorithm），which is mainly used to solve TSP （Travelling Salesman Problem）.The experiments show the improved ACA makes up the shortcomings of the basic ACA which is easy to fall into the stagnation of convergence，and it is easier to find a better solution.

Ant Colony Algorithm；optimization path；Travelling Salesman Problem

南通理工學(xué)院科研項(xiàng)目；項(xiàng)目編號(hào)：201410。

盧曦（1984—），女，江蘇南通，碩士，講師；研究方向：軟件技術(shù)。