賈玉福 陶懿 豐霄

摘 要：利用遺傳算法、社會群體優(yōu)化算法和模擬退火算法等仿生類整體探索算法求解旅行商問題（TSP），往往需要局部優(yōu)化算子促進算法收斂。目前大多采用單一的n-opt算子而沒有考慮利用其它算子或算子組合對旅行商路線進行優(yōu)化。為此定義了P_Swap、FP_Swap和L_Swap等3個算子，在TSPLIB 數(shù)據(jù)集中選取18個實例，分別利用各個算子及組合對旅行商路線問題進行優(yōu)化。對比分析結(jié)果顯示，P_Swap算子的優(yōu)化能力與2-opt算子相當，3個算子組合的優(yōu)化能力明顯強于2-opt算子，組合優(yōu)化算法求得的最優(yōu)解優(yōu)于目前已知的大部分算法。

關(guān)鍵詞：旅行商問題;n-opt 算子;組合優(yōu)化;全局探索能力;隨機擾動

DOI：10. 11907/rjdk. 182712

中圖分類號：TP301文獻標識碼：A文章編號：1672-7800（2019）003-0062-03

0 引言

旅行商問題（TSP）是一個典型的NP-Hard 難題，精確求解大規(guī)模城市節(jié)點算法效率低下，取而代之的是一些啟發(fā)式和仿生類探索性算法，比如社會群體優(yōu)化算法（SGO） [1-2]、細菌覓食優(yōu)化算法[3-4]、遺傳算法[5-6]、蟻群算法[7]和模擬退火算法[8]等。這些算法雖然具有較好的全局探索能力，但往往需要局部優(yōu)化算子促進算法收斂[9-11]。相關(guān)研究有：張子成[12]、韓偉等[13]在利用改進的模擬退火自適應(yīng)離散型布谷鳥算法和離散型貝殼漫步優(yōu)化算法求解TSP時采用2-opt 算子作局部優(yōu)化;姚麗莎等[14]將局部搜索算法與遺傳算法相結(jié)合求解異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度問題，利用3-opt對部分個體優(yōu)化變異;寧桂英等[15]利用離散型差分進化算法求解TSP，王勇臻[16]、宋堯[17]等利用細菌覓食算法求解TSP，陳立云等[18]利用遺傳算法求解運輸車調(diào)度問題，都采用2-opt 算子作局部優(yōu)化。上述方法均采用單一的n-opt交叉算子而沒有考慮其它算子及組合對TSP求解的有效性。為此，本文定義3個優(yōu)化算子，提出利用混合優(yōu)化算子策略進行TSP求解，從而比較 2-opt與各個算子的有效性，以及算法整體得到的TSP最優(yōu)解與其它算法的差距。

1 優(yōu)化算子與算法描述

本文算法的基本思想是先依據(jù)所有節(jié)點坐標進行Delauney三角劃分，隨機選擇一個三角形的3個頂點A、B、C形成環(huán)路，再以該三角形為種子向外擴張，形成一個包含所有節(jié)點的閉合環(huán)路。最后對該環(huán)路利用各種優(yōu)化算子和算子組合進行環(huán)路調(diào)整得到最優(yōu)解。

1.1 定義優(yōu)化算子

在對比不同算子的有效性時，算法可以對步驟③、步驟④、步驟⑤和步驟⑥進行取舍。

2 實驗結(jié)果

本文用國際標準的 TSPLIB 數(shù)據(jù)集[19]中18個實例進行仿真實驗，采用以所有三角形作為種子得到的最優(yōu)解進行比較。從表1可知，P_Swap有8個實例的優(yōu)化效果好于2-opt，1個實例優(yōu)化效果相同，9個實例的優(yōu)化效果比2-opt差。3算子組合的效果有13個實例優(yōu)于2-opt算子。從單個算子來看，F(xiàn)P_Swap比L_Swap好，比P_Swap差，這主要是因為FP_Swap算子只考慮局部連續(xù)4點的合理性，沒有考慮全局優(yōu)化的可能。

為將本文提出的混合算子策略算法與仿生類算法最優(yōu)解進行比較，選取最近文獻發(fā)表的部分實例結(jié)果作為評價標準。表2列出了文獻[20]中提到的幾個經(jīng)典算法的最優(yōu)解，表3列出了文獻[21]中提到的幾個經(jīng)典算法的最優(yōu)解。通過比較可知，本文算法的最優(yōu)解優(yōu)于大部分仿生算法，部分實例接近于文獻[21]提出的DWPA算法結(jié)果。

3 結(jié)語

本文提出利用自定義的3個優(yōu)化算子求解TSP的混合策略，通過對TSPLIB 數(shù)據(jù)集中的實例測試發(fā)現(xiàn)：P_Swap算子的優(yōu)化能力與2-opt算子相當，3個算子組合的優(yōu)化能力明顯強于2-opt算子。算子組合優(yōu)化算法求得的最優(yōu)解優(yōu)于目前已知的大部分算法。下一步研究工作是考慮將算子組合與仿生算法結(jié)合求解TSP。

參考文獻：

[1] SATAPATHY S，NAIK A. Social group optimization（SGO）： a new population evolutionary optimization technique[J]. Complex &Intelligent Systems， 2016（3）：1-31.

[2] NAIK A，SATAPATHY S C，ASHOUR A S，et al. Social group optimization for global optimization of multimodal functions and data clustering problems[J]. Neural Computing & Applications，2016（5）：1-17.

[3] PASSINO K M. Biomimicry of bacteria foraging for distributed optimization and control[J]. IEEE Control Systems Magazine， 2002，22（3）：52-67.

[4] LIU Y，PASSINO K NM. Biomimicry of social foraging bacteria for distributed optimization： models， principles， and emergent behaviors[J]. Journal Optimization Theory Application，2002，115（3）：603-628.

[5] NGUYEN，HUNG DINH. Implementation of an effective hybrid GA for large-scale traveling salesman problems[J]. IEEE transactions on systems， man， and cybernetics，2007，37（1）：92-99.

[6] MARIBEL GUERRERO，OSCAR CASTILLO，MARIO GARCíA VALDEZ. Cuckoo search via lévy flights and a comparison with genetic algorithms[J]. Fuzzy Logic Augmentation of Nature-Inspired Optimization Metaheuristics， 2015（3）：91-103.

[7] DORIGO M， GAMBARDELLA L M. A study of some properties of ant-q[C]. Lecture Notes in Computer Science，1996（1141）：656-665.

[8] KIRKPATRICK S，GELATT JR CD，VECCHI M P. Optimization by simulated annealing[J]. Science，1983，220（4598）：671-680.

[9] 陳彧，韓超. 一種求解旅行商問題的進化多目標優(yōu)化方法[J]. 控制與決策，2017（12）：248-254.

[10] 劉亞軍，陳得寶，鄒鋒，等. 離散社會群體優(yōu)化算法求解旅行商問題[J]. 長春師范大學(xué)學(xué)報，2018，37（6）： 91 - 95.

[11] CHIANG C W，LEE W P，HEH J S. A 2-opt based differential evolution for global optimization[J]. Applied Soft Computing，2010，10（4）：1200 - 1207.

[12] 張子成，韓偉，毛波，等. 基于模擬退火的自適應(yīng)離散型布谷鳥算法求解旅行商問題[J]. 電子學(xué)報，2018，46（8）：1849-1857.

[13] 韓偉，張子成. 求解旅行商問題的離散型貝殼漫步優(yōu)化算法[J]. 模式識別與人工智能， 2016，29（7）： 650-657.

[14] 姚麗莎，王占鳳，程家興. 分層混合局部搜索策略異構(gòu)多核系統(tǒng)調(diào)度[J]. 運籌與管理， 2016，29（7）： 193-199.

[15] 寧桂英，曹敦虔，周永權(quán). 求解TSP問題的離散型差分進化算法[J]. 計算機與數(shù)字工程，2017，45（11）：2136-2142.

[16] 王勇臻，陳燕，李桃迎. 離散型細菌覓食算法求解 TSP[J]. 計算機應(yīng)用研究，2014，31（12）： 3642 - 3650.

[17] 宋堯，葉樺，仰燕蘭. 改進細菌覓食算法在 TSP 問題中的應(yīng)用[J]. 工業(yè)控制計算機，2018，31（8）：86-87.

[18] 陳立云，盧昱，晏杰，等. 基于改進遺傳算法的彈藥運輸車輛調(diào)度問題研究[J]. 裝備學(xué)院學(xué)報，2014，25（2）：106-111.

[19] DOC IN. Symmetric TSPs[EB/OL]. [2018-03-13]. http：//www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/STSP.html.

[20] 王艷，王秋萍，王曉峰. 基于改進螢火蟲算法求解旅行商問題[J]. 計算機系統(tǒng)應(yīng)用，2018，27（8）：219-225.

[21] 黃海松，任竹鵬，魏建安. 改進狼群算法求解旅行商問題[J].計算機應(yīng)用研究，2018，36（12）：1245-1249.

（責(zé)任編輯：杜能鋼）