潘 澔, 孫 俐, 高 尚*

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

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

1 基本蟻群算法

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

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

(1)

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

(2)

(3)

(4)

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

解旅行商問(wèn)題的蟻群算法的基本步驟:

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

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

步驟4 按更新方程修改軌跡強(qiáng)度.

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

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

步驟7 輸出目前最好解.

2 基本分布估計(jì)算法

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

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

圖1 分布估計(jì)算法與遺傳算法的流程異同點(diǎn)

3 解旅行商問(wèn)題的蟻群分布估計(jì)混合算法

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

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

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

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

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

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

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

步驟7 輸出目前最好解.

4 算法測(cè)試

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

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

圖2 Oliver30的TSP最好的解

圖3 att48的最好的解

將與模擬退火算法、遺傳算法作對(duì)比.模擬退火算法參考文獻(xiàn)[1]，起始溫度T=100 000 ℃，終止溫度T0=1 ℃，退火速度α=0.99；遺傳算法程序的參數(shù)如下：染色體個(gè)數(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%.算法各測(cè)試100次，統(tǒng)計(jì)數(shù)據(jù)如表1.從表1可以看出，蟻群算法+優(yōu)選初始值策略+優(yōu)選路徑策略的混合算法的效果比較有效.

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

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

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

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

5 結(jié)論

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