用于求解旅行商問題的多策略離散型和聲搜索算法*

王勇臻　陳燕　張金松

(大連海事大學(xué) 交通運輸管理學(xué)院, 遼寧 大連 116026)

?

用于求解旅行商問題的多策略離散型和聲搜索算法*

王勇臻陳燕張金松

(大連海事大學(xué) 交通運輸管理學(xué)院, 遼寧 大連 116026)

摘要：基于求解旅行商問題(TSP),提出了一種多策略離散型和聲搜索算法.文中通過引入-opt算法設(shè)計了一種離散型即興創(chuàng)作過程,并結(jié)合3種策略來提高全局尋優(yōu)能力:采取教學(xué)優(yōu)化策略給出了產(chǎn)生和聲的新方式,以改善和聲記憶庫的質(zhì)量;采用精英擾動策略探索最優(yōu)和聲的鄰域進行精細搜索,以提高算法的收斂精度;通過排序選擇更新策略保持和聲記憶庫的多樣性,避免算法早熟收斂.實驗結(jié)果分析表明,該算法能夠有效求解TSP,具有可靠的全局收斂性和較快的收斂速度.

關(guān)鍵詞：和聲搜索算法;旅行商問題;-opt算法;離散型即興創(chuàng)作;多策略

旅行商問題(TSP)是典型的NP難問題,在計算機科學(xué)、運籌學(xué)及工程優(yōu)化等領(lǐng)域都有著廣泛的應(yīng)用.隨著人工智能的發(fā)展,出現(xiàn)了許多求解TSP的群智能優(yōu)化算法并不斷改進.文獻[1]采取連續(xù)優(yōu)化子路徑策略,提出了一種兩階段局部優(yōu)化混合遺傳算法(GA).文獻[2]將粒子群優(yōu)化(PSO)、蟻群優(yōu)化(ACO)和3-opt算法融合應(yīng)用于TSP的求解.文獻[3]通過改進的空間擴散機制,設(shè)計了一種離散型雜草入侵算法用于求解TSP.文獻[4]將蟻群系統(tǒng)中的螞蟻分成兩種角色,提出了一種用于求解TSP的擴展型ACO算法.目前,群智能優(yōu)化算法已成為人們求解TSP的最有效方法.

和聲搜索(HS)算法是由Geem等[5- 6]提出的一種群智能優(yōu)化算法，已成功應(yīng)用于許多實際優(yōu)化問題.然而,HS算法通常用于解決連續(xù)優(yōu)化問題,目前離散型HS的研究成果大多只針對解決二進制編碼問題[7],較少用于排列編碼問題.為改善和聲記憶庫的質(zhì)量,提高算法的收斂精度,避免算法早熟收斂,文中基于求解TSP提出了一種多策略離散型和聲搜索(MDHS)算法,并通過對TSPLIB中20個不同規(guī)模、不同類型的實例進行數(shù)值實驗來分析MDHS算法的性能.

1基本和聲搜索算法

基本HS算法的流程如下[5]:

(1)初始化和聲記憶庫大小SHM、和聲記憶庫考慮概率PHMCR、基音調(diào)整概率PAR、和聲微調(diào)步長bw、最大迭代次數(shù)NI.

(1)

(3)基于PHMCR、PAR和bw進行即興創(chuàng)作,依次執(zhí)行式(2)、(3)產(chǎn)生新的和聲,其中U(1,SHM)表示[1,SHM]上均勻分布的隨機整數(shù).

(2)

(3)

(4)更新和聲記憶庫.判斷新和聲xnew是否優(yōu)于當(dāng)前HM內(nèi)最差和聲xworst,若是則用xnew代替xworst.

(5)如果當(dāng)前迭代次數(shù)n大于最大迭代次數(shù)NI,則終止運行HS算法,否則返回步驟(3).

圖1　2-opt和3-opt示意圖Fig.1　Schematic diagram of 2-opt and 3-opt

3多策略離散型和聲搜索算法

3.1　離散型即興創(chuàng)作過程

針對TSP的求解,文中采用基于路徑表示的編碼.分析式(2)可知,新和聲的產(chǎn)生過程實質(zhì)上是記憶庫中的所有和聲與一個隨機和聲編碼交叉的過程.由此可定義一種離散型記憶庫考慮.

隨機產(chǎn)生一個和聲xinitial并隨機選擇一個城市c,計數(shù)器i=1.產(chǎn)生一個隨機數(shù)ri,若riSHM為止,如圖3所示.

圖2　t1的t3、t5鄰域示意圖Fig.2　Schematic diagram of the t3 and t5 neighborhood of t1

圖3　離散型記憶庫考慮示意圖Fig.3　Schematic diagram of the discrete harmony memory consideration

3.2　教學(xué)優(yōu)化策略TLO

基本HS算法僅通過即興創(chuàng)作方式產(chǎn)生新和聲,為了充分利用和聲記憶庫中的模式,文中提出了一種教學(xué)優(yōu)化策略TLO.令xbest表示最優(yōu)和聲,xo1和xo2為生成的兩個子代,隨機產(chǎn)生起始出發(fā)城市為c.

圖4　離散型基音調(diào)整流程圖Fig.4　Flowchart of discrete pitch adjustment

首先按照正向添加規(guī)則[10]生成xo1,分別計算在xbest和xHM,i中c與下一鄰近城市cnext1和cnext2的距離,選擇最近的城市加入xo1中,并將其作為出發(fā)城市,繼續(xù)尋找直至添加完畢.然后按照逆向規(guī)則生成xo2,計算c與上一近鄰城市cprevious1和cprevious2的距離.最后計算并比較xHM,i與xo1和xo2的路徑長度,選擇路徑長度最短的個體作為新的xHM,i.圖5給出了教學(xué)優(yōu)化的一個例子,假設(shè)6個城市的坐標(biāo)分別為c1(10,75)、c2(36,9)、c3(91,78)、c4(54,53)、c5(8,51)、c6(78,51),xHM,3在經(jīng)過一次教學(xué)后,路徑長度由326.729減小到266.042,優(yōu)于當(dāng)前xbest的268.832.

圖5　教學(xué)優(yōu)化示意圖Fig.5　Schematic diagram of teaching-learning-based optimization

3.3　排序選擇更新策略SSU

基本HS算法采用最差和聲更新策略,隨著算法迭代種群的平均目標(biāo)函數(shù)值逐漸減小,即興創(chuàng)作產(chǎn)生的新和聲很難有機會進入和聲記憶庫[11].為了保持算法的探索性,避免陷入局部最優(yōu),文中提出了一種排序選擇更新策略SSU.首先,將和聲記憶庫中的和聲從好到壞進行排序,然后計算順序表中位置k被選中的概率Ps(k),其中

(4)

(5)

選中的和聲將被新和聲直接替換.容易看出,k越大對應(yīng)的和聲質(zhì)量越差,被選中的概率越高.該策略保證了新和聲能夠進一步優(yōu)化,同時k=1時概率Ps(1)=0,即最優(yōu)和聲永遠不會被替換,保證了算法不會發(fā)生退化.

3.4　精英擾動策略EP

群智能優(yōu)化算法后期,單純通過增加新個體來提高多樣性,對精英個體的進化不會產(chǎn)生影響,而提高算法性能的關(guān)鍵在于增加精英個體所在鄰域的多樣性[12].基于此想法,文中提出了一種精英擾動策略EP.

每迭代一次后,執(zhí)行雙橋算子對最優(yōu)和聲進行擾動,如圖6所示,它可以幫助2-opt、3-opt發(fā)現(xiàn)新的鄰域結(jié)構(gòu),然后再調(diào)用離散型基音調(diào)整進一步優(yōu)化.若得到的新和聲優(yōu)于原和聲則進行替換.該策略通過不斷地探索最優(yōu)和聲的鄰域來改善算法的收斂精度.

圖6　雙橋算子示意圖Fig.6　Schematic diagram of double-bridge operation

3.5　時間復(fù)雜度分析

對于離散型即興創(chuàng)作,生成隨機和聲的時間復(fù)雜度為O(N),執(zhí)行一次編碼倒位的時間復(fù)雜度為O(N),則記憶庫考慮的時間復(fù)雜度為O(NSHM+N),對新和聲執(zhí)行基音調(diào)整的時間復(fù)雜度為O(CN+C2N),C為α-nearness候選集的勢,總時間復(fù)雜度為O(N(SHM+C+C2+1)).

對于教學(xué)優(yōu)化策略,選中最優(yōu)和聲的時間復(fù)雜度為O(SHM),按照正向/逆向添加規(guī)則生成子代的時間復(fù)雜度均為O(2N),擇優(yōu)選擇新和聲的時間復(fù)雜度為O(1),總時間復(fù)雜度為O(SHM+4N+1)≈

O(SHM+4N).

對于排序選擇更新策略,采用快速排序?qū)吐曈洃泿炫判虻臅r間復(fù)雜度為O(SHMlog2SHM),從和聲記憶庫中選中一個位置的時間復(fù)雜度為O(SHM),總時間復(fù)雜度為O(SHM(log2SHM+1)).

對于精英擾動策略,采用雙橋算子生成鄰域個體的時間復(fù)雜度為O(1),然后執(zhí)行基音調(diào)整,總時間復(fù)雜度為O(N(C+C2)+1)≈O(N(C+C2)).

綜上所述,MDHS迭代一次的時間復(fù)雜度為

O(N(SHM+C+C2+1)+SHM+4N+

SHM(log2SHM+1)+N(C+C2))=

O(N(SHM+2C+2C2+5)+SHM(log2SHM+2)).

3.6　算法描述

MDHS算法的求解步驟如下:

(1)初始化算法和問題參數(shù);

(2)根據(jù)TSP編碼方式初始化和聲記憶庫;

(3)基于離散型即興創(chuàng)作過程產(chǎn)生新和聲;

(4)使用排序選擇更新策略;

(5)使用教學(xué)優(yōu)化策略;

(6)使用精英擾動策略;

(7)如果當(dāng)前迭代次數(shù)n大于最大迭代次數(shù)NI,則終止運行MDHS算法,否則返回步驟(2).

4實驗結(jié)果與分析

文中使用Java語言編寫程序?qū)崿F(xiàn)MDHS算法,并在一臺配置為Inter(R)Core(TM)i7-3770 CPU@3.40 GHz的PC上運行程序進行數(shù)值實驗.MDHS參數(shù)設(shè)置如下:對于N<200的實例,SHM取N的1/5,對于N≥200的實例,SHM取40;PHMCR參考文獻[13]進行取值,即

(6)

4.1　算法性能分析

為了驗證所提出的3種策略的有效性和互助性,從TSPLIB中選取Eil101和Krob150實例采用5種算法(算法1:SDHS算法,不含3種策略;算法2:SDHS算法+TLO;算法3:SDHS算法+TLO+SSU;算法4:SDHS算法+TLO+EP;算法5:SDHS算法+TLO+EP+SSU,即MDHS)進行數(shù)值實驗分析.

使用5種算法分別獨立運行20次,α-nearness候選集的勢取5,NI分別取2 000和3 000.表1給出了5種算法獨立運行20次的計算結(jié)果統(tǒng)計,其中LB表示最短路徑長度,LA表示平均路徑長度.圖7給出了5種算法求解Eil101和Krob150的收斂曲線.

表15種算法的計算結(jié)果統(tǒng)計

Table1Statisticsofcomputingresultsobtainedby5algorithms

算法LBLAEil101Krob150Eil101Krob150算法1903.5358268.81965.5963128.04算法2666.3026960.13684.7827656.26算法3644.9126302.53655.3526591.92算法4640.2126140.30644.2226289.29算法5640.2126140.30641.2426201.79

從圖7可以看出:除算法1以外,其余4種算法在迭代100次后的路徑長度收斂到了比較低的水平,后續(xù)迭代中算法2早熟收斂,算法5的開發(fā)能力最強并最終收斂到全局最優(yōu)解附近;由算法2 和算法1的比較可知,教學(xué)優(yōu)化策略不僅加快了算法的收斂速度,還大幅度提高了收斂精度;由算法2與 算法4、算法3與算法5的比較可知,精英擾動策略進一步地改善了算法的收斂精度;由算法2與算法3、 算法4與算法5的比較可知,排序選擇更新策略能夠讓種群保持較高的多樣性,避免早熟收斂.

綜上所述,在相同計算條件下文中提出的3種策略對提升算法性能都能起到積極的作用,三者的融合能夠更進一步地促進算法性能的提升.

4.2　與知名算法的對比實驗與分析

為了更好地驗證文中MDHS算法的性能,引進知名算法ASA-GA[14]和HGA[15]作為比較對象.MDHS獨立運行20次,實驗中α-nearness候選集的勢取10,NI取5 000.表2是3種算法的最好結(jié)果對比,其中OPT為TSPLIB提供的最優(yōu)解,O為LB與OPT之間的偏差,NP為20次獨立運行中MDHS達到最優(yōu)路徑的次數(shù).

從表2可知,MDHS算法在全部實例(20個)上均獲得了3種算法中最好的結(jié)果,而ASA-GA和HGA都只獲得11個最好的結(jié)果,并且MDHS算法的平均偏差僅為0.23%,優(yōu)于ASA-GA和HGA的0.34%、0.98%.特別地,在實例Pr136和Krob150上MDHS算法得到的最短路徑分別為96 770.91和26 127.36,比TSPLIB提供的最優(yōu)路徑長度分別小1.08和2.64.圖8給出了MDHS算法在部分實例上得到的最優(yōu)路徑圖.

為了檢驗3種算法計算結(jié)果的差異是否顯著,文中進行了單因素方差分析.圖9給出了3種算法的計算偏差分布圖,檢驗的p值為0.027 5，小于0.05.

圖7　5種算法求解Eil101和Krob150的收斂曲線Fig.7　Convergence curves obtained by five algorithms on Eil101 and Krob150

表23種算法的最好實驗結(jié)果對比

Table 2　Comparison of the best experimental results obtained by three algorithms

圖8　MDHS算法在部分實例上得到的最優(yōu)路徑圖Fig.8　The optimal circuit graphs of partial instances via MDHS algorithm

從圖9可知,3種算法的計算偏差有著非常顯著的差異,直觀上MDHS算法的計算偏差要小于ASA-GA與HGA算法.圖10給出了3種算法的多重比較,由于MDHS與HGA算法的線段到橫軸的投影互不重疊,可知MDHS與HGA算法計算偏差的差異是顯著的.

為了考察α-nearness候選集的勢取不同值對MDHS算法運行結(jié)果的影響,選取實例Pr124、Kroa200、Lin318和Pcb442進行數(shù)值實驗.在實驗中α-nearness候選集的勢分別取5、10和15,NI取5 000,分別獨立運行20次,實驗結(jié)果如圖11所示.

圖9　3種算法的計算偏差分布圖Fig.9　Distribution of computing deviations obtained by three algorithms

圖10　3種算法的多重比較Fig.10　Multiple comparison of three algorithms

圖11　勢取不同值時的平均偏差對比Fig.11　Comparison of average deviations with different values of cardinality

由圖11可以看出,α-nearness候選集的勢從5增大到10時,平均偏差明顯減小,但候選集的勢從10增大到15時,平均偏差變化并不顯著,反而增加了程序運行時間.因此,建議分析具體實例所屬的候選集的勢,或者是選擇其他更優(yōu)秀的候選集來進一步提高MDHS算法的性能.

5結(jié)論

參考文獻:

[1]于宏濤,高立群,韓希昌.求解旅行商問題的離散人工螢火蟲算法 [J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2015,43(1):126-131.

YU Hong-tao,GAO Li-qun,HAN Xi-chang.Discrete artificial firefly algorithm for solving traveling salesman problems [J].Journal of South China University of Technology(Natural Science Edition),2015,43(1):126-131.

[2]MAHI M,BAYKAN O K,KODAZ H.A new method based on particle swarm optimization,ant colony optimization and 3-opt algorithms for traveling salesman problem [J].Applied Soft Computing,2015,30:484- 490.

[3]ZHOU Y Q,LUO Q F,CHEN H,et al.A discrete invasive weed optimization algorithm for solving traveling salesman problem [J].Neurocomputing,2015,151(11):1227-1236.

[4]ESCARIO J B,JIMENEZ J F,GIRON-SIERRA J M.Ant colony extended:experiments on the traveling salesman problem [J].Expert Systems with Applications,2015,42(1):390- 410.

[5]GEEM Z W,KIM J H,LOGANATHAN G V.A new heuristic optimization algorithm:harmony search [J].Simulation,2001,76(2):60- 68.

[6]MANJARRES D,LANDA-TORRES I,GIL-LOPEZ S,et al.A survey on applications of harmony search algorithm [J].Engineering Applications of Artificial Intelligence,2013,26(8):1818-1831.

[7]WANG L,YANG R,XU Y,et al.An improved adaptive binary harmony search algorithm [J].Information Sciences,2013,232:58-87.

[8]LIN S,KERNIGHAN B W.An effective heuristic algorithm for the traveling salesman problem [J].Operation Research,1973,21(2):498-516.

[9]VOLGENANT T,JONKER R.The symmetric traveling salesman problem and edge exchanges in minimal 1-trees [J].European Journal of Operational Research,1983,12(4):394- 403.

[10]于瑩瑩,陳燕,李桃迎.改進的遺傳算法求解旅行商問題 [J].控制與決策,2014,29(8):1483-1488.

YU Ying-ying,CHEN Yan,LI Tao-ying.Improved gene-tic algorithm for solving TSP [J].Control and Decision,2014,29(8):1483-1488.

[11]黃鑒,彭其淵.多樣性保持的和聲搜索算法及其TSP求解 [J].計算機應(yīng)用研究,2013,30(12):3583-3585.

HUANG Jian,PENG Qi-yuan.Diversity maintaining harmony search algorithm and its TSP solution [J].Application Research of Computers,2013,30(12):3583-3585.

[12]趙新超,劉國笠,劉虎球,等.基于非均勻變異和多階段擾動的粒子群優(yōu)化算法 [J].計算機學(xué)報,2014,37(9):2058-2070.

ZHAO Xin-chao,LIU Guo-li,LIU Hu-qiu,et al.Particle swarm optimization algorithm based on non-uniform mutation and multiple stages perturbation [J].Chinese Journal of Computers,2014,37(9):2058-2070.

[13]KONG X,GAO L,OUYANG H,et al.A simplified binary harmony search algorithm for large scale 0-1 knapsack problems [J].Expert Systems with Applications,2015,42(12):5337-5355.

[14]GENG X,CHEN Z,YANG W,et al.Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search [J].Applied Soft Computing,2011,11(4):3680-3689.

[15]WANG Y.The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem [J].Computer & Industrial Engineering,2014,70:124-133.

Multi-Strategy Discrete Harmony Search Algorithm for

Solving Traveling Salesman Problem

WANGYong-zhenCHENYanZHANGJin-song

(Transportation Management College, Dalian Maritime University, Dalian 116026, Liaoning, China)

Abstract:Proposed in this paper is a multi-strategy discrete harmony search (MDHS) algorithm for solving traveling salesman problem (TSP). In the algorithm, a discrete improvisation is designed by combining a -opt algorithm, and three strategies are employed together to improve its global optimization ability. The teaching-learning-based optimization strategy is adopted to provide a new way of producing new harmonies, so as to improve the quality of harmony memory (HM). The elite perturbation strategy is constructed to explore the neighborhoods of the best harmony constantly to perform a fine local search, so that the convergence precision of the proposed algorithm can be increased. The sort-selection-based update strategy is designed to preserve the diversity of HM for the sake of avoiding premature convergence. Experimental results show that MDHS can solve TSP effectively, and it holds an excellent search performance no matter in convergence speed or precision.

Key words:harmony search algorithm;traveling salesman problem;-opt algorithm;discrete improvisation;multi-strategy

doi：10.3969/j.issn.1000-565X.2016.01.019

中圖分類號：TP18

作者簡介：王勇臻(1990-),男,博士生,主要從事數(shù)據(jù)挖掘、智能計算研究.E-mail:KuaDMU@163.com

*基金項目：國家自然科學(xué)基金資助項目(71271034);遼寧省自然科學(xué)基金資助項目(2014025015)

收稿日期：2015-07-21

文章編號：1000-565X(2016)01- 0131- 08

Foundation items： Supported by the National Natural Science Foundation of China(71271034) and the Natural Science Foundation of Liaoning Province(2014025015)