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

曾 毅，朱旭生

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

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

曾 毅，朱旭生

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

針對旅行商問題，提出了一種新的混合和聲搜索算法。混合算法利用和聲算法和蟻群算法機理，重新定義和聲算法的即興創作操作，解決新生成的和聲不能很好地保持和聲記憶庫中和聲的優良基因片段的問題。為維持混合算法的多樣性，給出新的記憶庫更新策略。對旅行商問題進行測試，仿真結果表明混合算法的有效性。

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

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

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

和聲搜索算法（harmony search algorithm,HS）[3]是Geem Z W等人受音樂家即興創作過程的啟發而提出的一種元啟發式全局搜索算法。算法將樂器對應于優化問題的各個變量，樂器的音調對應于變量的取值，創作的和聲對應于解向量，和聲評價結果對應于目標函數，和聲記憶庫對應于種群，而音樂的創作過程即為種群的進化過程。和聲搜索算法原理簡單，參數較少，且易于實現。最近幾年和聲搜索算法成功地應用于公交路線設計問題[4]、水網調度問題[5]、競爭選址問題[6]、車輛路徑問題[7]及旅行商問題[8]等組合優化問題，本文針對旅行商問題，提出了一種新的混合和聲搜索算法。混合算法利用和聲算法和蟻群算法的機理，重新定義了和聲算法的即興創作操作，解決了新生成的和聲不能很好地保持和聲記憶庫中和聲的優良基因片段問題。為維持算法的多樣性，給出了新的記憶庫更新策略。對旅行商問題進行測試，仿真結果表明混合算法的有效性。

1 和聲搜索算法

設所求的離散型變量非約束最優化問題為

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

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

步驟1 初始化算法參數。和聲搜索算法主要參數：和聲記憶庫大小（harmony memory size，HMS），和聲記憶庫的思考概率（harmony memory considering rate，HMCR），音調微調概率（pitch adjusting rate,PAR），創作次數（NI）等。

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

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

式中：rand1表示［0，1］上均勻分布的隨機數。

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

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

步驟5 檢查是否達到算法終止條件。如果創作（迭代）次數小于設定的創作（迭代）次數NI，則返回步驟3；否則，停機輸出結果。

2 混合和聲搜索算法

2.1 編碼

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

2.2 創作新和聲的改進

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

新和聲的生成算法如下：

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

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

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

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

Step3 置s=s+1，若s≤n，轉Step2；否則，將每次取到的當前城市依次排列,得到準新和聲。

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

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

準和聲經逆轉操作后的和聲稱之為新和聲。當新和聲好于和聲記憶庫中的最差和聲時，各個城市間連接路徑上的信息素濃度按（7）式進行實時更新；否則，各個城市間的連接路徑上的信息素濃度不變。

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

式中：Q為信息素強度；Lnew為新和聲對應的路徑長度。

2.3 和聲記憶庫的更新策略的改進

在標準和聲搜索算法中，如果新產生的和聲優于和聲記憶庫中的最差和聲，則將新和聲替代和聲記憶庫中最差的和聲。這種更新策略隨迭代的進行必然會降低和聲搜索算法的多樣性，導致早熟收斂。考慮到和聲記憶庫的規模一般不大，新的更新策略為：將新產生的和聲與和聲記憶庫的和聲逐一比較。當且僅當和聲與記憶庫中的和聲均不相同，并且好于和聲記憶庫中的最差和聲，則將新和聲替換記憶庫中的最差和聲。

3 仿真分析

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

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

表1 4種算法對14-TSP的仿真實驗結果Tab.1 Simulation results of four kinds of algorithms for 14-TSP

表2 4種算法對30-TSP的仿真實驗結果Tab.2 Simulation results of four kinds of algorithms for 30-TSP

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

從圖1測試問題的收斂曲線來看，當旅行商問題的城市數由14個增加到30個時，HS-ACO算法收斂速度和解的質量明顯地好于GA，SA，ACO算法。這表明隨旅行商問題城市數的增加，單一機制的優化算法很難實現全局優化，效率較低，而混合和聲搜索算法將多種優化機制相結合，取長補短，能較好地保持算法的全局優化性能。

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

4 結語

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

1）即興創作的選擇操作與傳統的基于分量的選擇操作不同，利用了旅行商問題中節點與節點的強關聯性，能較好地繼承記憶庫和聲的優良基因片段。測試結果表明該選擇操作可行性，對其它啟發性算法在求解旅行商問題有一定的借鑒作用。

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

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

接下來的工作是將本文提出的算法運用到其它的組合優化問題，進一步驗證算法的性能。

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

[2]田貴超，黎明，韋雪潔.旅行商問題(TSP)的幾種求解方法[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]王英博，王琳，李揚，等.改進的遺傳和聲算法及其在車輛路徑中的應用[J].計算機測量與控制，2011，19（12）：3068-3071.

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

[9]趙玉新，YANG XINSHE，劉利強.新興元啟發式優化方法[M].北京：科學出版社，2013：203-204.

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

[11]史峰，王輝，郁磊，等.MATLAB智能算法30個案例分析[M].北京：北京航空航天大學出版社，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

（責任編輯 劉棉玲）

2016－04－10

國家自然科學基金項目（11161021）；華東交通大學科研項目（09111114）

曾毅（1965—），男，副教授，研究方向為智能計算。