一種利用混合優化算子求解旅行商問題的方法

賈玉福 陶懿 豐霄

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

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

DOI：10. 11907/rjdk. 182712

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

0 引言

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

1 優化算子與算法描述

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

1.1 定義優化算子

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

2 實驗結果

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

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

3 結語

本文提出利用自定義的3個優化算子求解TSP的混合策略，通過對TSPLIB 數據集中的實例測試發現：P_Swap算子的優化能力與2-opt算子相當，3個算子組合的優化能力明顯強于2-opt算子。算子組合優化算法求得的最優解優于目前已知的大部分算法。下一步研究工作是考慮將算子組合與仿生算法結合求解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] 陳彧，韓超. 一種求解旅行商問題的進化多目標優化方法[J]. 控制與決策，2017（12）：248-254.

[10] 劉亞軍，陳得寶，鄒鋒，等. 離散社會群體優化算法求解旅行商問題[J]. 長春師范大學學報，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] 張子成，韓偉，毛波，等. 基于模擬退火的自適應離散型布谷鳥算法求解旅行商問題[J]. 電子學報，2018，46（8）：1849-1857.

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

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

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

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

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

[18] 陳立云，盧昱，晏杰，等. 基于改進遺傳算法的彈藥運輸車輛調度問題研究[J]. 裝備學院學報，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]. 計算機系統應用，2018，27（8）：219-225.

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

（責任編輯：杜能鋼）