基于混合和聲搜索算法求解旅行商問題

曾 毅，朱旭生

（華東交通大學(xué)理學(xué)院，江西 南昌330013）

基于混合和聲搜索算法求解旅行商問題

曾 毅，朱旭生

（華東交通大學(xué)理學(xué)院，江西 南昌330013）

針對旅行商問題，提出了一種新的混合和聲搜索算法?；旌纤惴ɡ煤吐曀惴ê拖伻核惴C(jī)理，重新定義和聲算法的即興創(chuàng)作操作，解決新生成的和聲不能很好地保持和聲記憶庫中和聲的優(yōu)良基因片段的問題。為維持混合算法的多樣性，給出新的記憶庫更新策略。對旅行商問題進(jìn)行測試，仿真結(jié)果表明混合算法的有效性。

旅行商問題；和聲搜索算法；蟻群算法

旅行商問題[1]（traveling salesman problem，TSP）可描述為：給定單個城市和兩兩城市之間的距離，求一條經(jīng)過各城市一次且僅一次后在回到原出發(fā)城市的最短路線。該問題不僅具有廣泛的應(yīng)用背景和重要理論價值，而且是一典型的組合優(yōu)化NP難問題,常常用來驗(yàn)證某一算法的有效性。

求解旅行商問題的算法可分為精確算法和啟發(fā)式算法。精確算法能找到問題的最優(yōu)解，但隨著問題的規(guī)模增大，其運(yùn)行時間按指數(shù)增加，所以僅適合求解小規(guī)模問題。而啟發(fā)式算法由于其獨(dú)特的運(yùn)行機(jī)制能在合理的時間內(nèi)得到問題的滿意解，因而設(shè)計(jì)有效的啟發(fā)式算法是求解旅行商問題一個重要的研究方向[2]。

和聲搜索算法（harmony search algorithm,HS）[3]是Geem Z W等人受音樂家即興創(chuàng)作過程的啟發(fā)而提出的一種元啟發(fā)式全局搜索算法。算法將樂器對應(yīng)于優(yōu)化問題的各個變量，樂器的音調(diào)對應(yīng)于變量的取值，創(chuàng)作的和聲對應(yīng)于解向量，和聲評價結(jié)果對應(yīng)于目標(biāo)函數(shù)，和聲記憶庫對應(yīng)于種群，而音樂的創(chuàng)作過程即為種群的進(jìn)化過程。和聲搜索算法原理簡單，參數(shù)較少，且易于實(shí)現(xiàn)。最近幾年和聲搜索算法成功地應(yīng)用于公交路線設(shè)計(jì)問題[4]、水網(wǎng)調(diào)度問題[5]、競爭選址問題[6]、車輛路徑問題[7]及旅行商問題[8]等組合優(yōu)化問題，本文針對旅行商問題，提出了一種新的混合和聲搜索算法?；旌纤惴ɡ煤吐曀惴ê拖伻核惴ǖ臋C(jī)理，重新定義了和聲算法的即興創(chuàng)作操作，解決了新生成的和聲不能很好地保持和聲記憶庫中和聲的優(yōu)良基因片段問題。為維持算法的多樣性，給出了新的記憶庫更新策略。對旅行商問題進(jìn)行測試，仿真結(jié)果表明混合算法的有效性。

1 和聲搜索算法

設(shè)所求的離散型變量非約束最優(yōu)化問題為

式中：f（X）為目標(biāo)函數(shù)；X為決策變量xi構(gòu)成的解向量；Xi={xi（1），xi（2），…，xi（ki）}為決策變量xi的取值空間,其中ki是決策變量xi可能的取值個數(shù)。

基本和聲搜索算法的步驟如下[9]：

步驟1 初始化算法參數(shù)。和聲搜索算法主要參數(shù)：和聲記憶庫大?。╤armony memory size，HMS），和聲記憶庫的思考概率（harmony memory considering rate，HMCR），音調(diào)微調(diào)概率（pitch adjusting rate,PAR），創(chuàng)作次數(shù)（NI）等。

步驟2 初始化和聲記憶庫。隨機(jī)生成HMS個和聲：X1，X2，…，XHMS，將和聲及相應(yīng)的目標(biāo)函數(shù)值放入和聲記憶庫（harmony memory，HM）。設(shè)最優(yōu)化問題決策變量個數(shù)為n，其和聲記憶庫HM可用如下矩陣表示：

步驟3 創(chuàng)作新和聲。在這一步驟中，和聲搜索算法即興產(chǎn)生一個新的和聲。新和聲的產(chǎn)生基于3種操作：①記憶思考；②音調(diào)微調(diào)；③隨機(jī)選擇音調(diào)。具體操作如下：

式中：rand1表示［0，1］上均勻分布的隨機(jī)數(shù)。

式中：rand2表示［0，1］上均勻分布的隨機(jī)數(shù)；微調(diào)之后的取值；xi（k）為微調(diào)之前的取值，此時xi（k+m）表示在xi（k）的“左右鄰居”中重新選擇。

步驟4 更新和聲記憶庫。若新和聲Xnew好于聲記憶庫中的最差的和聲Xworst，即f（Xnew）＜f（Xworst）=max{f（Xj）｜j=1，2，…，HMS}，那么用新和聲替代和聲記憶庫中的最差和聲。

步驟5 檢查是否達(dá)到算法終止條件。如果創(chuàng)作（迭代）次數(shù)小于設(shè)定的創(chuàng)作（迭代）次數(shù)NI，則返回步驟3；否則，停機(jī)輸出結(jié)果。

2 混合和聲搜索算法

2.1 編碼

旅行商問題采用自然數(shù)編碼，即利用城市在路線中的位置來表示一條路線。這種編碼方式自然、簡單，且適用于不同規(guī)模的旅行商問題。若9城市的旅行商問題的路線為(5-1-7-8-9-4-6-2-3-5)，則相應(yīng)的編碼為(5 1 7 8 9 4 6 2 3)。

2.2 創(chuàng)作新和聲的改進(jìn)

和聲搜索算法最初主要是針對連續(xù)變量的優(yōu)化問題求解。但要使算法成功地求解旅行商問題，關(guān)鍵是要保證迭代過程生成的新和聲滿足2個條件：①新和聲能很好地繼承和聲記憶庫中和聲的優(yōu)良基因片段；②新和聲是一個可行解。而按和聲搜索算法步驟3生成的新和聲很可能是一個不可行解，即生成的和聲編碼中出現(xiàn)重復(fù)的基因碼。為此，文獻(xiàn)[8]提出分散學(xué)習(xí)策略和分塊學(xué)習(xí)策略，將不可行解修復(fù)為可行解，但在修復(fù)的過程中，記憶庫中和聲的優(yōu)良基因片段不能很好地被繼承下來?？紤]到和聲搜索算法的新和聲的生成過程實(shí)質(zhì)上是一個繼承和探索的過程，即新和聲從和聲記憶庫（HM）中以概率HMCR·（1-PAR）所得到的分量就是一個繼承過程，而微調(diào)和隨機(jī)產(chǎn)生的分量就是一個探索過程。為此，我們設(shè)計(jì)了新和聲的生成算法，使生成的新和聲滿足上述的2個條件。

新和聲的生成算法如下：

Step1 置s=1。從旅行商問題中的n個城市中隨機(jī)選擇一個城市作為第一個旅行的城市。設(shè)城市c1為選擇的第一個城市，current_city為當(dāng)前旅行的城市，置current_city=c1。集合unvisited_city={1，2，…，n}-{c1}為未旅行的城市的集合。

Step2 隨機(jī)生成1～HMS之間的整數(shù)k，設(shè)HM中第k個和聲中的current_city之后的城市為j。按式(5)確定下一個旅行的城市next_city。

式中，rand1為 ［0，1］上均勻分布的隨機(jī)數(shù)。城市j′依轉(zhuǎn)移概率按輪盤賭法確定，即先計(jì)算當(dāng)前城市current_city到unvisited_city中各城市的轉(zhuǎn)移概率，然后采用輪盤賭法確定下一個訪問城市j′。設(shè)和聲搜索算法的第t次迭代從城市i轉(zhuǎn)移到城市j概率為Pij（t），Pij（t）的值可按式（6）計(jì)算。待next_city確定后，置current_city=next_city，unvisited_city=unvisited_city-{next_city}。

式中：τij（t）為城市i與城市j連接路徑上的信息素濃度；ηij（t）=1/d（i，j）為啟發(fā)函數(shù)，表示從城市i轉(zhuǎn)移到城市j的期望程度；α為信息素重要程度因子，其值越大，表示信息素的濃度在轉(zhuǎn)移中起的作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大。

Step3 置s=s+1，若s≤n，轉(zhuǎn)Step2；否則，將每次取到的當(dāng)前城市依次排列,得到準(zhǔn)新和聲。

Step4 準(zhǔn)新和聲的微調(diào)及信息素濃度的更新?？紤]到標(biāo)準(zhǔn)的音調(diào)微調(diào)操作不利于旅行商問題的鄰域解的搜索。為此，設(shè)計(jì)基于進(jìn)化逆轉(zhuǎn)操作的和聲微調(diào)操作，即準(zhǔn)新和聲生成后，若隨機(jī)數(shù)rand1＜PAR，對準(zhǔn)新的和聲連續(xù)實(shí)施M次進(jìn)化逆轉(zhuǎn)操作。進(jìn)化逆轉(zhuǎn)操作是遺傳算法求解旅行商問題常用的一個操作。這里的“進(jìn)化”是指逆轉(zhuǎn)操作的單方向性，即經(jīng)進(jìn)化逆轉(zhuǎn)操作后，得到路徑更短的和聲，則用此和聲替換準(zhǔn)和聲，并在此基礎(chǔ)上進(jìn)行下一輪的進(jìn)化逆轉(zhuǎn)操作（注：此時的進(jìn)化逆轉(zhuǎn)操作的次數(shù)小于M）。若實(shí)施M次進(jìn)化逆轉(zhuǎn)操作后沒有得到路徑更短的和聲，則認(rèn)為M次進(jìn)化逆轉(zhuǎn)操作無效，準(zhǔn)新和聲不變。仍以9個城市的旅行商問題為例，說明進(jìn)化逆轉(zhuǎn)操作的過程：

產(chǎn)生2個1～9之間的隨機(jī)整數(shù)r1，r2，且r1＜r2，不妨設(shè)r1=2，r2=7，若逆轉(zhuǎn)操作前的和聲為（1|2 6 4 9 8|7 3 5），則逆轉(zhuǎn)操作后的和聲為（1|8 9 4 6 2|7 3 5）。

準(zhǔn)和聲經(jīng)逆轉(zhuǎn)操作后的和聲稱之為新和聲。當(dāng)新和聲好于和聲記憶庫中的最差和聲時，各個城市間連接路徑上的信息素濃度按（7）式進(jìn)行實(shí)時更新；否則，各個城市間的連接路徑上的信息素濃度不變。

式中：參數(shù)ρ（0＜ρ＜1）表示信息素的揮發(fā)因子；△τij表示在城市i與城市j連接路徑上新增加的信息素濃度，△τij按（8）式計(jì)算。

式中：Q為信息素強(qiáng)度；Lnew為新和聲對應(yīng)的路徑長度。

2.3 和聲記憶庫的更新策略的改進(jìn)

在標(biāo)準(zhǔn)和聲搜索算法中，如果新產(chǎn)生的和聲優(yōu)于和聲記憶庫中的最差和聲，則將新和聲替代和聲記憶庫中最差的和聲。這種更新策略隨迭代的進(jìn)行必然會降低和聲搜索算法的多樣性，導(dǎo)致早熟收斂?？紤]到和聲記憶庫的規(guī)模一般不大，新的更新策略為：將新產(chǎn)生的和聲與和聲記憶庫的和聲逐一比較。當(dāng)且僅當(dāng)和聲與記憶庫中的和聲均不相同，并且好于和聲記憶庫中的最差和聲，則將新和聲替換記憶庫中的最差和聲。

3 仿真分析

選文獻(xiàn)[10-11]中的旅行商問題作為測試問題。這2個旅行商問題分別稱為14-TSP和30-TSP。另外，選遺傳算法（GA）、模擬退火算法（SA）及蟻群算法（ACO）3種算法和本文提出的混合和聲搜索算法（HS-ACO）作對比測試。GA，SA及ACO算法的參數(shù)取值與文獻(xiàn)[11]相同，其中GA算法的參數(shù)：種群規(guī)模Popsize=100，選擇概率Ps=0.9，交叉概率Pc=0.9，變異概率Pm=0.05；SA算法的參數(shù)：初始溫度T0=1 000，結(jié)束溫度Tend=1e-3，降溫速度q=0.966，鏈長L=200；ACO算法的參數(shù)：螞蟻數(shù)量取旅行商問題的城市數(shù)，信息素重要程度因子α=1，啟發(fā)函數(shù)重要程度因子β=5，信息素?fù)]發(fā)因子ρ=0.1，信息素釋放總量Q=20，在初始時刻t=0，各路徑上信息量τij（0）=1。HS-ACO算法的參數(shù)：和聲記憶庫的規(guī)模HMS=10，最大迭代次數(shù)NI=400,和聲記憶庫取值概率HMCR依迭代次數(shù)線性遞增從HMCRstart變到HMCRend，即

本文HMCRstart=0.60，HMCRend=0.95，和聲音調(diào)微調(diào)概率PAR=0.3，逆轉(zhuǎn)操作次數(shù)M=20，其余參量的取值與蟻群算法相同。對選取的2個旅行商問題每種算法重復(fù)運(yùn)行20次，測試結(jié)果如表1和表2所示，表中MEAN，BEST，WORST，SD和SR分別表示算法連續(xù)運(yùn)行20次得到的最優(yōu)解的平均值、最好值、最差值、均方差及達(dá)到最優(yōu)值的比例。圖1為收斂曲線，圖中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為最短路徑平均長度。

表1 4種算法對14-TSP的仿真實(shí)驗(yàn)結(jié)果Tab.1 Simulation results of four kinds of algorithms for 14-TSP

表2 4種算法對30-TSP的仿真實(shí)驗(yàn)結(jié)果Tab.2 Simulation results of four kinds of algorithms for 30-TSP

從測試問題的計(jì)算結(jié)果來看，HS-ACO算法的評價指標(biāo)，即算法最優(yōu)值、平均值、最差值、均方差及達(dá)到最優(yōu)值的比例都好于算法GA，SA，ACO的評價指標(biāo)。隨著旅行商問題的城市數(shù)增加，GA，SA算法的各項(xiàng)評價指標(biāo)明顯變差。雖然ACO算法能找到較優(yōu)的解，均方差也較小，但由于算法具有較強(qiáng)的魯棒性，明顯地出現(xiàn)停滯現(xiàn)象，收斂到局部最優(yōu)解，30-TSP達(dá)到最優(yōu)值比例為0/20。而HS-ACO算法的各項(xiàng)評價指標(biāo)依然很好，與其它算法相比仍然保持了明顯的優(yōu)勢，30-TSP達(dá)到最優(yōu)值比例17/20,遠(yuǎn)遠(yuǎn)高出其它算法。

從圖1測試問題的收斂曲線來看，當(dāng)旅行商問題的城市數(shù)由14個增加到30個時，HS-ACO算法收斂速度和解的質(zhì)量明顯地好于GA，SA，ACO算法。這表明隨旅行商問題城市數(shù)的增加，單一機(jī)制的優(yōu)化算法很難實(shí)現(xiàn)全局優(yōu)化，效率較低，而混合和聲搜索算法將多種優(yōu)化機(jī)制相結(jié)合，取長補(bǔ)短，能較好地保持算法的全局優(yōu)化性能。

圖1 測試問題收斂曲線Fig.1 Convergence curves of test questions

4 結(jié)語

針對旅行商問題，提出一種新的混合和聲搜索算法（HS-ACO）。該算法有以下幾個特點(diǎn)：

1）即興創(chuàng)作的選擇操作與傳統(tǒng)的基于分量的選擇操作不同，利用了旅行商問題中節(jié)點(diǎn)與節(jié)點(diǎn)的強(qiáng)關(guān)聯(lián)性，能較好地繼承記憶庫和聲的優(yōu)良基因片段。測試結(jié)果表明該選擇操作可行性，對其它啟發(fā)性算法在求解旅行商問題有一定的借鑒作用。

2）微調(diào)操作在準(zhǔn)新和聲生成之后，這與和聲搜索算法微調(diào)操作在新和聲生成的過程中進(jìn)行不同，避免了微調(diào)操作的“隨機(jī)性”，能保證新的和聲“好上加好”。

3）采用了新的記憶庫更新策略，保證了算法多樣性，使算法更容易跳出局部最優(yōu)解搜索到全局最優(yōu)解。

接下來的工作是將本文提出的算法運(yùn)用到其它的組合優(yōu)化問題，進(jìn)一步驗(yàn)證算法的性能。

[1]胡能發(fā)，康立山，陳毓屏.構(gòu)建“基因庫”求解TSP問題的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2003，39（11）：75－76.

[2]田貴超，黎明，韋雪潔.旅行商問題(TSP)的幾種求解方法[J].計(jì)算機(jī)仿真，2006，23（8）：153-157.

[3]GEEM Z，KIM J，LOGANATHAN G.A new heuristic optimization algorithm:harmony search[J].Simulation，2001，76（2）：60－68.

[4]GEEM Z W，LEE K S，PARK Y.Application of harmony search to vehicle routing[J].American Journal of Applied Sciences，2005，2（12）：1552－1557.

[5]GEEM Z W.Optimal scheduling of multiple dam system using harmony search algorithm[C]//Computerional and ambient intelligence，Berlin：Springer，2007：316-323.

[6]于宏濤，高立群，呂勇軍.基于混合和聲搜索算法求解競爭選址問題[J].控制與決策，2013，28（7）：1083-1093.

[7]王英博，王琳，李揚(yáng)，等.改進(jìn)的遺傳和聲算法及其在車輛路徑中的應(yīng)用[J].計(jì)算機(jī)測量與控制，2011，19（12）：3068-3071.

[8]李俊青，王玉亭，潘全科，等.混合離散和聲搜索算法求解旅行商問題[J].微電子學(xué)與計(jì)算機(jī)，2009，26（3）：17-21.

[9]趙玉新，YANG XINSHE，劉利強(qiáng).新興元啟發(fā)式優(yōu)化方法[M].北京：科學(xué)出版社，2013：203-204.

[10]敖友云，遲洪欽.基于遺傳算法求解TSP問題的一種算法[J].計(jì)算機(jī)數(shù)字與工程，2006，34（4）：52-55.

[11]史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社，2011：183-185.

Hybrid Harmony Search Algorithm for Traveling Salesman Problem

Zeng Yi，Zhu Xusheng
（School of Science，East China Jiaotong University，Nanchang 330013,China）

Aiming at traveling salesman problem,this paper puts forward a new hybrid harmony search algorithm. By using the mechanism of harmony search algorithm and ant colony algorithm,improvisation operator of hybrid algorithm is redefined so as to solve the problem that the newly-generated harmony doesn’t well maintain the excellent gene segment in harmony memory.In order to maintain the diversity of hybrid algorithm,a new memory updating strategy is given.Finally,the algorithm is applied and tested in traveling salesman problem.The results of simulation indicate the effectiveness of the proposed algorithm.

traveling salesman problem；harmony search algorithm；ant colony optimization

TP301.6

A

1005-0523（2016）06-0131-06

（責(zé)任編輯 劉棉玲）

2016－04－10

國家自然科學(xué)基金項(xiàng)目（11161021）；華東交通大學(xué)科研項(xiàng)目（09111114）

曾毅（1965—），男，副教授，研究方向?yàn)橹悄苡?jì)算。