王勇臻　陳燕　張金松

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

?

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

王勇臻陳燕張金松

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

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

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

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

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

1基本和聲搜索算法

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

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

(1)

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

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

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

首先按照正向添加規(guī)則[10]生成xo1,分別計(jì)算在xbest和xHM,i中c與下一鄰近城市cnext1和cnext2的距離,選擇最近的城市加入xo1中,并將其作為出發(fā)城市,繼續(xù)尋找直至添加完畢.然后按照逆向規(guī)則生成xo2,計(jì)算c與上一近鄰城市cprevious1和cprevious2的距離.最后計(jì)算并比較xHM,i與xo1和xo2的路徑長(zhǎng)度,選擇路徑長(zhǎng)度最短的個(gè)體作為新的xHM,i.圖5給出了教學(xué)優(yōu)化的一個(gè)例子,假設(shè)6個(gè)城市的坐標(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é)后,路徑長(zhǎng)度由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)生的新和聲很難有機(jī)會(huì)進(jìn)入和聲記憶庫(kù)[11].為了保持算法的探索性,避免陷入局部最優(yōu),文中提出了一種排序選擇更新策略SSU.首先,將和聲記憶庫(kù)中的和聲從好到壞進(jìn)行排序,然后計(jì)算順序表中位置k被選中的概率Ps(k),其中

(4)

(5)

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

3.4　精英擾動(dòng)策略EP

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

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

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

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

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

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

O(SHM+4N).

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

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

綜上所述,MDHS迭代一次的時(shí)間復(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編碼方式初始化和聲記憶庫(kù);

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

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

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

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

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

4實(shí)驗(yàn)結(jié)果與分析

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

(6)

4.1　算法性能分析

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

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

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

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次后的路徑長(zhǎng)度收斂到了比較低的水平,后續(xù)迭代中算法2早熟收斂,算法5的開發(fā)能力最強(qiáng)并最終收斂到全局最優(yōu)解附近;由算法2 和算法1的比較可知,教學(xué)優(yōu)化策略不僅加快了算法的收斂速度,還大幅度提高了收斂精度;由算法2與 算法4、算法3與算法5的比較可知,精英擾動(dòng)策略進(jìn)一步地改善了算法的收斂精度;由算法2與算法3、 算法4與算法5的比較可知,排序選擇更新策略能夠讓種群保持較高的多樣性,避免早熟收斂.

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

4.2　與知名算法的對(duì)比實(shí)驗(yàn)與分析

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

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

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

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

表23種算法的最好實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

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

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

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

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

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

5結(jié)論

參考文獻(xiàn):

[1]于宏濤,高立群,韓希昌.求解旅行商問題的離散人工螢火蟲算法 [J].華南理工大學(xué)學(xué)報(bào)(自然科學(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ìn)的遺傳算法求解旅行商問題 [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].計(jì)算機(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]趙新超,劉國(guó)笠,劉虎球,等.基于非均勻變異和多階段擾動(dòng)的粒子群優(yōu)化算法 [J].計(jì)算機(jī)學(xué)報(bào),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

中圖分類號(hào)：TP18

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

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

收稿日期：2015-07-21

文章編號(hào)：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)