基于改進(jìn)和聲算法的TSP路徑求解*

吳 瑩，歐 云，姚玄石，丁 雷

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

1 研究背景

旅行商問(wèn)題(Traveling Salesman Problem， TSP)是一個(gè)具有廣泛應(yīng)用背景和重要理論意義的組合優(yōu)化問(wèn)題，它可以描述為[1]：給定一個(gè)城市的集合，尋找一條從某城市出發(fā)，然后遍歷其他各個(gè)城市，且每個(gè)城市能且僅能經(jīng)過(guò)1次，最后回到出發(fā)城市的最短路徑.TSP的數(shù)學(xué)模型描述如下：

xij∈{0,1}i,j=1,…,n.

其中：P為給定城市的集合，P={1,2,…,n}；dij為城市i與城市j之間的距離，距離集合D={dij}；n為城市個(gè)數(shù).TSP的目標(biāo)函數(shù)是求得經(jīng)過(guò)集合中所有城市的最短路徑，約束條件是不重復(fù)經(jīng)過(guò)同一城市且最終回到出發(fā)城市.

TSP是一個(gè)求解最短路徑的經(jīng)典NP-Hard問(wèn)題[2]，目前沒(méi)有統(tǒng)一的解法.近年來(lái)，以粒子群算法、遺傳算法(Genetic Algorithm， GA)、蟻群算法為代表的群智能算法，因采用分布式計(jì)算和基于概率搜索，且具有魯棒性較強(qiáng)和實(shí)現(xiàn)簡(jiǎn)單等特點(diǎn)，被廣泛運(yùn)用在TSP求解中.喬彥平等[1]將GA與模擬退火算法(Simulated Annealing Algorithm， SAA)相結(jié)合，改善了TSP的求解精度；陶麗華等[3]將GA與蟻群算法進(jìn)行動(dòng)態(tài)融合，一定程度上提高了TSP的求解精度和速度.作為現(xiàn)有群智能算法之一，和聲搜索算法(Harmony Search Algorithm， HSA)因其原理簡(jiǎn)單、可調(diào)參數(shù)少和容易實(shí)現(xiàn)等優(yōu)勢(shì)，在函數(shù)參數(shù)優(yōu)化[4]、圖形圖像分割[5]、最優(yōu)路徑[6]和背包問(wèn)題[7]中得到很好的應(yīng)用.但由于受到搜索范圍和和聲記憶庫(kù)(Harmony Memory， HM)種群多樣性的限制，HSA存在早熟和收斂精度低等問(wèn)題，因此眾多研究者對(duì)其進(jìn)行了改進(jìn).如高立群等[8]提出了一種提高初始解質(zhì)量的改進(jìn)HSA；楊樹欣等[9]從優(yōu)化迭代過(guò)程方面改進(jìn)了HSA；張康麗等[10]結(jié)合GA的概率分配方法，對(duì)HM的種群信息的多樣性作了改進(jìn).為了進(jìn)一步提高HSA的收斂速度和準(zhǔn)確度，針對(duì)算法中音調(diào)調(diào)節(jié)概率設(shè)置為固定值而導(dǎo)致HM多樣性受限、易于陷入局部搜索等不足，筆者擬設(shè)計(jì)一個(gè)動(dòng)態(tài)調(diào)節(jié)音調(diào)概率的新算法，即動(dòng)態(tài)和聲搜索算法(Dynamic Harmony Search Algorithm， DHSA)，并將其運(yùn)用到TSP求解中，以期實(shí)現(xiàn)遍歷路徑最優(yōu)化.

2 算法原理

2.1 HSA原理

HSA[11]與粒子群算法[12]來(lái)源于鳥類捕食的思想類似，HSA是仿照音樂(lè)表演過(guò)程，將創(chuàng)作美妙和聲的過(guò)程類比為尋求最優(yōu)解的過(guò)程，本質(zhì)上是一種優(yōu)化設(shè)計(jì)的過(guò)程.HAS中，樂(lè)器i(i=1，2，…，m)相當(dāng)于優(yōu)化問(wèn)題中的第i個(gè)設(shè)計(jì)變量，各樂(lè)器聲調(diào)的和聲Xj(j=1，2，…，M)相當(dāng)于優(yōu)化問(wèn)題的第j個(gè)解向量，評(píng)價(jià)和聲的好壞相當(dāng)于評(píng)價(jià)目標(biāo)函數(shù)f(Xj)解的優(yōu)劣.HAS思想是：首先產(chǎn)生SHMS個(gè)初始解存入HM內(nèi)，以選擇概率PHMCR在HM內(nèi)搜索新解，以概率1-PHMCR在HM外的變量值域中搜索；然后以音調(diào)調(diào)節(jié)概率PPAR和調(diào)節(jié)步長(zhǎng)Bw對(duì)新解產(chǎn)生局部擾動(dòng)；最后判斷新解是否優(yōu)于HM內(nèi)的最差解，若是，則替換之，不斷迭代，直至達(dá)到最大迭代次數(shù)T為止.

2.2 DHSA原理

HSA中，音調(diào)調(diào)節(jié)概率和調(diào)節(jié)步長(zhǎng)這2個(gè)控制參數(shù)在迭代求解過(guò)程中是固定不變的，因此算法在搜索過(guò)程中無(wú)法隨著搜索范圍的變化做出相應(yīng)調(diào)整，容易陷入局部最優(yōu)，限制HM的多樣性，從而算法的求解效率較低.目前，對(duì)HSA性能的改進(jìn)，主要是從修改算法參數(shù)、設(shè)計(jì)合適算子和融合其他智能算法3個(gè)方面進(jìn)行的.筆者擬從調(diào)整算法參數(shù)入手，先動(dòng)態(tài)調(diào)節(jié)音調(diào)概率參數(shù)，以保障HM種群信息的多樣性，避免陷入局部搜索；再對(duì)HM的存儲(chǔ)結(jié)構(gòu)和新和聲的產(chǎn)生方式作改進(jìn)，采用禁忌表存儲(chǔ)及輪盤賭選擇方法來(lái)提高搜索效率.動(dòng)態(tài)調(diào)節(jié)音調(diào)概率參數(shù)公式為

PPAR=PPARmin+(PPARmax-PPARmin)t/T.

(1)

其中：PPARmin，PPARmax分別為和聲音調(diào)調(diào)節(jié)概率的最小值和最大值；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù).

DHSA和HSA的參數(shù)對(duì)比結(jié)果列于表1.

3 DHSA在TSP求解中的應(yīng)用

在利用DHSA求解TSP時(shí)，將TSP路徑庫(kù)表示為HM，2個(gè)城市之間的路徑表示為一個(gè)樂(lè)器的和音，TSP的一個(gè)解(連接所有城市的一條無(wú)重復(fù)且形成回路的訪問(wèn)路徑)表示為由不同樂(lè)器的和音形成的一段和聲.TSP路徑庫(kù)表示為

DHSA的基本步驟如下：

(ⅰ)導(dǎo)入城市坐標(biāo)，初始化參數(shù)，初始化TSP路徑庫(kù).

(ⅱ)遍歷每個(gè)城市，采用禁忌表約束TSP路徑庫(kù)，使每個(gè)城市出現(xiàn)次數(shù)都唯一.

圖1 DHSA流程Fig. 1 Flowchart of DHSA

(ⅲ)生成一個(gè)隨機(jī)數(shù)r(r∈[0,1])，若r

(2)

其中q為城市序號(hào).

(ⅳ)若r≥PHMCR，則隨機(jī)生成1個(gè)城市，得到1個(gè)新解.隨機(jī)生成公式為

Xnew=Xq+θ(Xj-Xq)，

(3)

其中θ服從(0,1)均勻分布，j為城市序號(hào).

(ⅴ)采用輪盤賭選擇算法比較當(dāng)前獲得的最新路徑值f(Xnew)與TSP路徑庫(kù)的最差路徑值，若最新路徑值小于最差路徑值，則替換之，否則不作改變.

(ⅵ)判斷進(jìn)化是否結(jié)束，符合條件時(shí)，輸出當(dāng)前最優(yōu)城市序列，計(jì)算城市之間的距離；否則返回步驟(ⅲ).

DHSA的流程如圖1所示.

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)運(yùn)行環(huán)境：Intel(R) Xeon(R) Sliver 4110 CPU @ 2.10GHz(4處理器)，8G內(nèi)存，Windows10操作系統(tǒng)，集成開(kāi)發(fā)環(huán)境MATLABR2014b.HAS的參數(shù)設(shè)置：PHMCR=0.9，SHMS=300，PPAR=0.33.與HSA相比，DHSA的參數(shù)PHMCR設(shè)置為[PPARmin,PPARmax]范圍內(nèi)自適應(yīng)調(diào)節(jié)，PPARmin=0.1，PPARmax=0.99.

選取TSP案例庫(kù)中的2個(gè)經(jīng)典數(shù)據(jù)集bayg29和ch150，城市個(gè)數(shù)分別為29和150，實(shí)驗(yàn)迭代次數(shù)1 000，種群大小30.對(duì)GA，HAS與DHSA進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如圖2～5所示.

圖2 基于bayg29數(shù)據(jù)集的最優(yōu)路徑連接Fig. 2 Optimal Path Connection Graph Based on Bayg29 Dataset

圖3 基于ch150數(shù)據(jù)集的最優(yōu)路徑連接Fig. 3 Optimal Path Connection Graph Based on CH150 Dataset

圖4 基于bayg29數(shù)據(jù)集的最優(yōu)路徑收斂Fig. 4 Optimal Path Convergence Graph Based on Bayg29 Dataset

圖5 基于ch150數(shù)據(jù)集的最優(yōu)路徑收斂Fig. 5 Convergence of Optimal Path Based on CH150 Dataset

由圖4和圖5可見(jiàn)，相較于HAS和GA，DHSA的收斂精度更好.根據(jù)圖2和圖3，可得3種算法的最優(yōu)路徑距離(表2).

表2 3種算法的最優(yōu)路徑距離

從表2可知：在2個(gè)數(shù)據(jù)集中，利用DHSA獲得的最優(yōu)路徑都最短.bayg29數(shù)據(jù)集中，DHSA獲得的最優(yōu)路徑比HAS的少約763 m，比GA的少約2 940 m；ch150數(shù)據(jù)集中，DHSA獲得的最優(yōu)路徑比HAS的少約668 m，比GA的少約34 070 m.

5 結(jié)語(yǔ)

為了提高HSA的收斂速度和準(zhǔn)確度，設(shè)計(jì)了一個(gè)動(dòng)態(tài)調(diào)節(jié)音調(diào)概率的新算法DHSA.為了驗(yàn)證DHSA的有效性，選取TSP案例庫(kù)中的2個(gè)經(jīng)典數(shù)據(jù)集bayg29和ch150，通過(guò)Matlab軟件對(duì)GA，HSA，DHSA進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，相較于HSA和GA，DHSA在收斂精度方面更優(yōu)，最優(yōu)路徑更短.后續(xù)工作考慮將微調(diào)候選解的方法與其他智能算法相結(jié)合，使得算法在解決大規(guī)模的TSP時(shí)具有更大的優(yōu)勢(shì).