潘 澔, 孫 俐, 高 尚*

(1.蘇州建設(shè)交通高等職業(yè)技術(shù)學校，蘇州 215104) (2.江蘇科技大學 計算機學院，鎮(zhèn)江 212100)

旅行商問題(traveling salesman problem,TSP)可以描述為有一個推銷員從某城市出發(fā)走遍所有的城市，且每個城市只能走一次，最后返回原處，如何選擇路線使所走路程最短.TSP問題是一個NP完全問題，對于一個N個城市的TSP問題，可能的路徑數(shù)是一個組合數(shù)(N-1)!/2, 隨著城市數(shù)目N的增大，問題的規(guī)模呈指數(shù)式增大.TSP問題是組合優(yōu)化領(lǐng)域中的一個典型的問題，解決此問題有較大的現(xiàn)實意義，如印刷電路板的鉆空路線方案，連鎖店送貨路線問題等都可簡化為TSP問題.并且此問題也可作為測試新的算法的標準問題，因此一直是研究的熱點.目前求解TSP問題的主要方法有模擬退火算法[1]，遺傳算法[1-2]，啟發(fā)式搜索法，Hopfield神經(jīng)網(wǎng)絡(luò)算法[1]，蟻群算法[3]，演化算法[4],近似多項式方法[5]等.文中依據(jù)分布估計算法的思想，提出一種蟻群分布估計混合算法來解決旅行商問題.

1 基本蟻群算法

螞蟻個體之間是通過一種稱之為外激素的物質(zhì)進行信息傳遞，從而能相互協(xié)作，完成復雜的任務(wù).螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì)，而且螞蟻在運動過程中能夠感知這種物質(zhì)的存在及其強度，并以此指導自己的運動方向，螞蟻傾向于朝著該物質(zhì)強度高的方向移動.因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大.螞蟻個體之間就是通過這種信息的交流達到搜索食物的目的.蟻群算法首先成功應(yīng)用于旅行商問題，目前在車輛路徑尋優(yōu)[6]、裝配序列規(guī)劃[7]等方面均有應(yīng)用.

設(shè)有m個螞蟻，每個簡單螞蟻有以下特征：它根據(jù)以城市距離和連接邊上外激素的數(shù)量為變量的概率函數(shù)選擇下一個城(設(shè)τij(t)為t時刻邊e(i,j)上外激素的強度).規(guī)定螞蟻走合法路線，除非周游完成，不允許轉(zhuǎn)到已訪問城市，有禁忌表控制(設(shè)tabuk表示第k個螞蟻的禁忌表，tabuk(s)表示禁忌表中第s個元素).它完成周游后，螞蟻在它每一條訪問的邊上留下外激素.

(1)

τij(t+n)=ρ·τij(t)+Δτij

(2)

(3)

(4)

式中：Lk為第k只螞蟻環(huán)游一周的路徑長度；Q為常數(shù).

解旅行商問題的蟻群算法的基本步驟:

步驟1nc←0；(nc為迭代步數(shù)或搜索次數(shù))各τij和Δτij的初始化；將m個螞蟻置于n個頂點.

步驟3 計算各螞蟻的路徑長度Lk(k=1,2,…,m)；記錄當前的最好解.

步驟4 按更新方程修改軌跡強度.

步驟5 對各邊弧(i,j)，置Δτij←0，nc←nc+1.

步驟6 若nc<預定的迭代次數(shù)且無退化行為(即找到的都是相同解)則轉(zhuǎn)步驟2.

步驟7 輸出目前最好解.

2 基本分布估計算法

分布估計算法[8-10]提出了一種全新的進化模式.在傳統(tǒng)的遺傳算法中，用種群表示優(yōu)化問題的一組候選解，種群中的每個個體都有相應(yīng)的適應(yīng)值，然后進行選擇、交叉和變異等模擬自然進化的操作，反復進行，分布估計算法中，沒有傳統(tǒng)的交叉、變異等遺傳操作，而是概率模型的學習和采樣分布估計算法通過一個概率模型描述候選解在空間的分布, 采用統(tǒng)計學習手段從群體宏觀的角度建立一個描述解分布的概率模型,然后對概率模型隨機采樣產(chǎn)生新的種群，如此反復進行, 實現(xiàn)種群的進化，直到終止條件.根據(jù)概率模型的復雜程度以及不同的采樣方法，分布估計算法發(fā)展了很多不同的具體實現(xiàn)方法，但是都可以歸納為兩個主要步驟[8]：首先構(gòu)建描述解空間的概率模型，通過對種群的評估，選擇優(yōu)秀的個體集合，從而采用統(tǒng)計學習等手段構(gòu)造一個描述當前解集的概率模型;然后由概率模型隨機采樣產(chǎn)生新的種群，一般的，采用蒙特卡羅方法，對概率模型采樣得到新的種群.

遺傳算法中的交叉和變異會破壞已經(jīng)優(yōu)化好的個體，分布估計算法用建立概率模型和采樣兩大操作取代了遺傳算法中的交叉算子和變異算子，以一種帶有“全局操控”性的操作模式解決了遺傳算法存在的這一問題.遺傳算法和分布估計算法的流程對比如圖1，并且分布估計算法不需要太多的參數(shù)設(shè)置，編程比遺傳算法簡單.

圖1 分布估計算法與遺傳算法的流程異同點

3 解旅行商問題的蟻群分布估計混合算法

蟻群算法各侯選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)，以期望產(chǎn)生性能更好的解.蟻群算法根據(jù)對所有的候選解的信息進行更新信息素，沒有對優(yōu)解、劣解進行區(qū)分，而分布估計算法通過對種群的評估，選擇優(yōu)秀的個體集合，淘汰劣性解.文中給出2個改進策略，優(yōu)選初始值策略，首先初始化時，隨機產(chǎn)生一些解，選擇較優(yōu)的路徑留下信息素，其他不改變；優(yōu)選路徑策略，螞蟻每次周游結(jié)束后，只有比較好的解才留下信息素，按路徑長度排序，并從中選出最優(yōu)的s個個體才留下信息素.

解旅行商問題的蟻群分布混合算法步驟如下:

步驟1nc←0；(nc為迭代步數(shù)或搜索次數(shù))各τij和Δτij的初始化；將m個螞蟻置于n個頂點上；優(yōu)選初始值策略，隨機產(chǎn)生100個解，選擇較優(yōu)的個路徑留下信息素(文中取30個)，其他不變.

步驟3 計算各螞蟻的路徑長度Lk(k=1,2,…,m)，記錄當前的最好解.

步驟4優(yōu)選路徑策略，按路徑長度排序，并從中選出最優(yōu)的s個個體，對最優(yōu)的s個個體按更新方程修改軌跡強度(種群個數(shù)s占m的比例取30%～90%).

步驟5 對各邊弧(i,j)，置Δτij←0，nc←nc+1.

步驟6 若nc<預定的迭代次數(shù)且無退化行為(即找到的都是相同解)則轉(zhuǎn)步驟2.

步驟7 輸出目前最好解.

4 算法測試

選用Oliver30和att48作為實驗例子，由于各種參考文獻提供Oliver30數(shù)據(jù)不一致，文中采用http://stevedower.id.au/other/oliver30中的數(shù)據(jù).圖2是Oliver30的最好的解(橫軸和縱軸是城市的相對坐標)，總路程為423.740 6(假設(shè)城市間的距離用最接近的整數(shù)近似，總路程為420).圖3是解att48的最好的解，總路程為33 522.

固定資產(chǎn)投資減去折舊等于當年的固定資產(chǎn)增量。如果假定技術(shù)不發(fā)生變化，用非工業(yè)部門當年的增加值相對于上一年的增量除以固定資產(chǎn)增量，就等于非工業(yè)產(chǎn)業(yè)單位增加值所需的直接固定資產(chǎn)含量。

圖2 Oliver30的TSP最好的解

圖3 att48的最好的解

將與模擬退火算法、遺傳算法作對比.模擬退火算法參考文獻[1]，起始溫度T=100 000 ℃，終止溫度T0=1 ℃，退火速度α=0.99；遺傳算法程序的參數(shù)如下：染色體個數(shù)N=30，交叉概率Pc=0.2，變異概率Pm=0.5，迭代次數(shù)100；蟻群算法：α=1.5，β=2，ρ=0.9，nmax=50，C=100，Q=1 000 000，比例為60%.算法各測試100次，統(tǒng)計數(shù)據(jù)如表1.從表1可以看出，蟻群算法+優(yōu)選初始值策略+優(yōu)選路徑策略的混合算法的效果比較有效.

表1 幾種算法測試結(jié)果

影響算法的性能的主要參數(shù)是種群的個數(shù)m和選出的種群個數(shù)s.采用蟻群算法+優(yōu)選初始值策略+優(yōu)選路徑策略，選出的種群個數(shù)s占m的比例不同，結(jié)果也不一樣.不同的比例，算法各測試20次，統(tǒng)計數(shù)據(jù)如表2.

表2 s/m取不同值結(jié)果比較果

從表2可以看出，s/m比例越大，不能體現(xiàn)出選優(yōu)的優(yōu)勢，效果越不好；當然s/m比例太小，也容易陷入局部極值.因此s/m比值取60%～70%，效果比較好.

5 結(jié)論

(1) 提出利用蟻群分布估計混合算法來解決旅行商問題，得到滿意效果.如果與其他方法結(jié)合，如加上2-Opt局部搜尋的方式，解決旅行商問題的效果可能會更好.