求解多旅行商問題的改進分組遺傳算法

王勇臻 陳 燕 于瑩瑩

?

求解多旅行商問題的改進分組遺傳算法

王勇臻*陳 燕 于瑩瑩

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

該文針對總路徑長度最小的多旅行商問題，提出一種改進分組遺傳算法。在該算法中，設(shè)計了一種有序分組編碼，采用新編碼方式的個體與多旅行商問題有效解之間具有一一對應(yīng)的關(guān)系。為了減少算法的運行時間，根據(jù)編碼的特點構(gòu)造了一種快速交叉算子。同時，結(jié)合貪婪算法和2-opt算法設(shè)計了一種新的局部搜索算子，以提高算法的收斂精度。實驗結(jié)果分析表明，所提算法能夠有效地解決多旅行商問題，具有可靠的全局收斂性，較高的計算效率。

分組遺傳算法；多旅行商問題；編碼；2-opt算法

1 引言

多旅行商問題(Multiple Traveling Salesman Problem, MTSP)是對經(jīng)典旅行商問題(TSP)的推廣，即給定個城市，個旅行商從同一(或不同)城市出發(fā)，分別走一條旅行路線，使得每個城市有且僅有一個旅行商經(jīng)過(除出發(fā)城市)，同時花費最小[1,2]。相較于TSP, MTSP具有更廣泛的工程背景，如車輛路徑規(guī)劃[3]、應(yīng)急物資配送[4]、無人機覆蓋搜索[5]和不合格品控制[6]等，已被證明屬于NP-hard問題。所以，如何快速、有效地解決MTSP具有很高的實際應(yīng)用價值。

MTSP本質(zhì)上屬于分組問題，其求解過程包含了城市的分組優(yōu)化以及組內(nèi)遍歷次序優(yōu)化兩個環(huán)節(jié)[7]。因此，相應(yīng)的啟發(fā)式算法大多計算復(fù)雜，并且過于依賴問題本身的特征，容易發(fā)生早熟收斂[1,8]。近年來，人們從生物機理中得到啟發(fā)，提出了多種進化算法應(yīng)用于MTSP，如遺傳算法[9,10]、蟻群算法[11,12]、蜂群算法[13]和雜草入侵算法[14]。而編碼方式作為進化算法的核心，直接影響著MTSP的求解性能，常見的有單染色體、雙染色體和組合染色體3種編碼[4,9]。然而，這些編碼方式將兩個優(yōu)化環(huán)節(jié)融合在一起，不但使得進化算子通常難以設(shè)計，而且算法運行過程中容易產(chǎn)生大量的冗余解[9,10]。隨著研究的深入，文獻[9]提出了一種分組遺傳算法(GGA-SS)用于求解MTSP，其基本思想是先將各旅行商的路徑編碼為個組，然后按照一定規(guī)則對組執(zhí)行交叉、變異操作，計算結(jié)果優(yōu)于早前算法。在此基礎(chǔ)之上，文獻[14]通過借鑒不同的生物智能，分別提出了3種群體進化算法(ABCFC, ABCVC和IWO)，并且在多數(shù)實例上得到了目前最優(yōu)的計算結(jié)果。但是，上述算法仍然存在兩類問題：解空間存在冗余，以及缺乏有效的進化算子。

本文提出了一種改進分組遺傳算法(IGGA- SS)，設(shè)計了一種有序分組編碼，將解空間進一步縮小了倍，并基于該編碼構(gòu)造了一種快速交叉算子，以減少算法的運行時間。同時，結(jié)合貪婪算法和2-opt算法設(shè)計了一種新的局部搜索算子，以進一步提高算法的收斂精度。實驗結(jié)果分析表明，所提算法可以有效地解決MTSP，計算結(jié)果比目前同類算法給出的結(jié)果更優(yōu)。

圖1 GGA-SS編碼示意圖

2 GGA-SS求解MTSP

2.1 GGA-SS核心步驟

(2)交叉算子：GGA-SS采用一種兩階段交叉算子：

階段1：從兩個父代中隨機選擇一個，根據(jù)式(1)計算各組的，選擇值最大的組并復(fù)制給子代。

階段2：將階段1中未分配的城市逐個插入到子代中，且保證每次插入都使得總路徑長度增加最少。

(5)穩(wěn)態(tài)保留：新生成的子代與當前種群進行比較，若唯一則替換當前最差個體，否則丟棄該子代。

2.2 GGA-SS存在的問題

通過分析GGA-SS主要計算過程可知，其存在3個問題：

(1)編碼不考慮組的排列，存在冗余。

(3)階段2本質(zhì)上是貪婪算法，雖然在一定程度上能夠得到滿意解，但是隨著問題規(guī)模的增大容易陷入局部極值。

3 IGGA-SS求解MTSP

3.1有序分組編碼

由于GGA-SS編碼不考慮組的排列，以圖1為例，考慮如下編碼方案：

{{4,7,10}, {6,1,3,11}, {12,5,2,8,9}},

{{4,7,10}, {12,5,2,8,9}, {6,1,3,11}},

{{6,1,3,11}, {4,7,10}, {12,5,2,8,9}},

{{6,1,3,11}, {12,5,2,8,9}, {4,7,10}},

{{12,5,2,8,9}, {4,7,10}, {6,1,3,11}},

{{12,5,2,8,9}, {6,1,3,11}, {4,7,10}}

對于MTSP，組本身所代表的旅行商沒有任何意義，以上6個編碼表達了同一個MTSP有效解。為了避免這種冗余，本文提出一種有序分組編碼。上述例子中，假設(shè)3個組{4,7,10}, {12,5,2,8,9}和{6,1,3,11}的路徑長度分別是100, 110和120，計算可得,和。反映了一個組屬于最優(yōu)解的可能性，越小則其屬于最優(yōu)解的概率越大[9]。然后將3個組按照進行升序排列，則{{12,5,2,8,9}, {6,1,3,11}, {4,7,10}}是有序分組編碼后的唯一個體。

顯然，有序分組編碼的個體與MTSP有效解之間是一一對應(yīng)的關(guān)系，其解空間大小是，較GGA-SS編碼縮小了倍，有利于減小算法的復(fù)雜度，對大規(guī)模MTSP的求解具有重要意義。

3.2快速交叉算子(階段1)

圖2是快速交叉算子示意圖。可見，該算子并未反復(fù)計算父代中各組的，提高了算法的計算效率。同時，該算子可以有效地保留父代中的部分分組，而基于有序分組編碼，使得更具潛力的組優(yōu)先得到保留。對于該階段未分配的城市，將通過3.3節(jié)的局部搜索算子(階段2)進行處理。

圖2 快速交叉算子示意圖

圖3 2-opt算法示意圖

3.3局部搜索算子(階段2)

為了克服貪婪算法容易早熟收斂的缺陷，本文通過結(jié)合2-opt算法來引入新的信息，以維持種群的多樣性，提出一種新的局部搜索算子，具體過程如下：

該算子既結(jié)合貪婪算法和2-opt算法來提高收斂精度，又引入了隨機性保證種群不早熟收斂，平衡了算法的開發(fā)性和探索性。

3.4算法描述

在GGA-SS主要計算過程基礎(chǔ)之上，下面給出IGGA-SS的求解步驟：

步驟1 算法和問題參數(shù)初始化；

步驟4 執(zhí)行快速交叉算子，轉(zhuǎn)步驟6；

步驟5 執(zhí)行變異算子；

步驟6 執(zhí)行局部搜索算子；

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

(3)計算各組的r并排序的時間復(fù)雜度。

綜上所述，IGGA-SS迭代一次的時間復(fù)雜度為

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

本文采用Java語言編寫程序?qū)崿F(xiàn)算法，并在一臺配置為Inter(R) Core(TM) i7-3770 CPU @3.40 GHz的PC上運行程序。參考文獻[9,14]的做法，使用TSPLIB中距離對稱的實例(設(shè)置不同的旅行商數(shù)目)進行數(shù)值實驗。

為了便于控制選擇壓力，本文采用等級選擇方法選取父代[17]，如式(2)，式(3)所示。其中，表示種群中第個個體被選中的概率，表示選擇壓力，,越大則選中最優(yōu)個體的概率越大。

(3)

4.1參數(shù)設(shè)置及其影響

(3)選擇壓力SP從小到大取1.2~1.8，間隔為0.2；同樣，偏好閾值取0.35~0.65，間隔為0.10。

表1參數(shù)水平

參數(shù)水平1水平2水平3水平4 SP1.21.41.61.8 pc0.60.70.80.9 pcp0.750.80.850.9 pd0.350.450.550.65

表2正交表和AVG統(tǒng)計(m)

NoSPpcpcppdAVG 1111123340.69 2122223450.00 3133323417.98 4144423327.05 5212323381.95 6221423506.34 7234123349.79 8243223428.10 9313423417.27 10324323410.60 11331223360.12 12342123394.59 13414223457.01 14423123342.49 15432423459.94 16441323540.87

表3各參數(shù)響應(yīng)值(m)

水平SPpcpcppd 123383.9323399.2323437.0123356.89 223416.5423427.3623421.6223423.81 323395.6523396.9623401.4623437.85 423450.0823422.6523386.1123427.65 極差66.1530.4050.8980.96 等級2431

4.2算法性能分析

表4 3種算法20次獨立運行結(jié)果統(tǒng)計

綜合表4，圖5和圖6分析，可得出如下結(jié)論：

(1)對比GGA-SS和IGGA-SS2可知，快速交叉算子可以大幅度減少算法的耗時，計算可得IGGA-SS2相較于GGA-SS耗時減少了75.73%~ 78.28%，并且隨著的增大其差距單調(diào)遞增。但是，由于該算子不重新計算父代中各組的，將會影響各組保留的優(yōu)先次序，隨著的增大其收斂精度下降比較明顯。

進一步地，由3.5節(jié)可知：交叉算子執(zhí)行過程中，兩者除了首次計算的耗時相同之外，GGA-SS反復(fù)計算的時間復(fù)雜度為其中，。易知，隨著,，或者，亦或,的增大，這部分耗時累積將單調(diào)遞增。在本文參數(shù)設(shè)置下，兩者耗時差距已達到75%以上。

(2)對比IGGA-SS和IGGA-SS2可知，局部搜索算子可以進一步改善算法的收斂精度，計算可得IGGA-SS相較于IGGA-SS2收斂精度提高了4.11%~10.13%，并且隨著的增大其差距單調(diào)遞增，同時，兩者耗時差距則單調(diào)遞減。

(3)對比IGGA-SS和GGA-SS可知，本文所做改進可以有效地提高算法的收斂精度、減少算法的耗時。計算可得IGGA-SS相較于GGA-SS收斂精度提高了7.90%~11.97%。同時，隨著的增大IGGA-SS耗時單調(diào)遞減，除了之外(14.04%), IGGA-SS耗時均少于GGA-SS(3.58%和28.54%)。

4.3與知名算法的對比分析

為了更好地驗證IGGA-SS求解MTSP的性能，引進目前最優(yōu)秀算法：兩種蜂群算法ABCFC, ABCVC和雜草入侵算法IWO作為比較對象[14]，需要說明的是，這3種算法都是GGA-SS的變體。選取eil101, ch150()和kroB200()進行數(shù)值實驗。設(shè)定為100,為1000，其余參數(shù)取自4.1節(jié)，所對比算法參數(shù)取自文獻[14], 4種算法在每組實驗上獨立運行20次，結(jié)果如表5所示?？芍琁GGA-SS在全部10組實驗上均獲得了4種算法中最好的結(jié)果，并且耗時最少。

圖5 m對3種算法收斂精度的影響 圖6 m對3種算法耗時的影響

表5 4種算法20次獨立運行結(jié)果統(tǒng)計

為了檢驗4種算法計算結(jié)果的差異在統(tǒng)計上是否顯著，本文進行了單因素方差分析[19]。表6是4種算法的計算差異性對比，其中分別表示行所代表算法計算結(jié)果劣于、無區(qū)別和優(yōu)于列所代表算法。從表6可知，IGGA-SS在全部10組實驗上計算結(jié)果均優(yōu)于ABCFC和ABCVC，在9組實驗上計算結(jié)果優(yōu)于IWO，整體性能最優(yōu)；IWO整體性能僅次于IGGA-SS；而ABCFC與ABCVC整體性能相近。

從表5中4種算法耗時對比可見，IGGA-SS的耗時遠少于其余3種算法，計算可得IGGA-SS相較于ABCFC, ABCVC與IWO耗時分別減少了61.77%~70.67%, 57.05%~67.91%和79.49%~ 84.93%。由3.5節(jié)與文獻[14]可知，4種算法迭代一次的時間復(fù)雜度均為(·(變異算子+子代保留))，且均取1000。同時，(變異算子)的最高次冪都是的2次冪，且(變異算子)(子代保留)，因此耗時差距主要源于取值不同。對比可知，IGGA-SS中取100，而ABCFC, ABCVC和IWO分別取250, 250和300，遠大于IGGA-SS。這也說明，在種群規(guī)模較小的情況下，IGGA-SS依然可以得到比其余3種算法更高的收斂精度。

圖7是4種算法收斂曲線對比?？芍?，IGGA-SS的收斂速度最快，幾乎是垂直收斂，并且迭代過程中始終處于其余3種算法的下方。ABCFC在迭代前期收斂速度較快，然而容易早熟收斂。IWO和ABCVC雖然沒有陷入局部極值，但是收斂速度與IGGA-SS存在明顯差距。

表6 4種算法的計算差異性對比

綜上所述，IGGA-SS在收斂速度、精度以及耗時方面均優(yōu)于所對比的3種算法。

5 結(jié)束語

本文提出了一種改進分組遺傳算法，用于求解總路徑長度最小的MTSP。實驗結(jié)果分析表明，IGGA-SS具有比最新用于解決該問題的ABCFC, ABCVC和IWO更優(yōu)的性能。今后工作仍需進行更多的數(shù)值實驗和對算法的效率作進一步改進，并將所提算法應(yīng)用于解決港口自動調(diào)度這類大規(guī)模MTSP。

圖7 4種算法收斂曲線對比

[1] SOYLU B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J].&, 2015, 90(11): 390-401. doi: 10.1016/j.cie.2015.10.010.

[2] KOTA L and JARMAI K. Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming[J]., 2015, 39(12): 3410-3433. doi: 10.1016/j.apm. 2014.11.043.

[3] 謝秉磊, 李穎, 劉敏. 帶臨時補充點的融雪劑撒布車輛路徑問題[J]. 系統(tǒng)工程理論與實踐, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.

XIE Binglei, LI Ying, and LIU Min. Vehicle routing problem with temporary supplementary points for spreading deicing salt[J].&, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.

[4] 劉明, 張培勇. 求解多旅行商問題的新混合遺傳算法: 以應(yīng)急物資配送為例[J]. 系統(tǒng)管理學(xué)報, 2014, 23(2): 247-254.

LIU Ming and ZHANG Peiyong. New hybrid genetic algorithm for solving the multiple traveling salesman problem: An example of distribution of emergence materials[J].&, 2014, 23(2): 247-254.

[5] ANN S, KIM Y, and AHN J. Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method[J]., 2015, 48(9): 204-209. doi: 10.1016/j.ifacol.2015.08.084.

[6] KIRALY A, CHRISTIDOU M, CHOVAN T,. Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem[J]., 2016, 111: 253-261. doi: 10.1016/j.jclepro.2015.05.036.

[7] KASHAN A H, AKBARI A A, and OSTADI B. Grouping evolution strategies: an effective approach for grouping problems[J]., 2015, 39(9): 2703-2720. doi: 10.1016/j.apm.2014.11.001.

[8] BEKTAS T. The multiple traveling salesman problem: An overview of formulations and solution procedures[J]., 2006, 34(3): 209-219. doi: 10.1016/j.omega.2004.10.004.

[9] SINGH A and BAGHEL A S. A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]., 2009, 13(1): 95-101. doi: 10.1007/s00500-008-0312-1.

[10] YUAN S, SKINNER B, HUANG S,. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]., 2013, 228(1): 72-82. doi: 10.1016/j.ejor.2013.01.043.

[11] LIU W, LI S, ZHAO F,. An ant colony optimization algorithm for the multiple traveling salesmen problem[C]. Proceedings of IEEE Conference on Industrial Electronics and Applications, ICIEA, Xi’an, China, 2009: 1533-1537. doi: 10.1109/ ICIEA.2009.5138451.

[12] NECULA R, BREABAN M, and RASCHIP M. Performance Evaluation of Ant Colony Systems for the Single-depot Multiple Traveling Salesman Problem[M]. Springer International Publishing, 2015: 257-268. doi: 10.1007/ 978-3-319-19644-2_22.

[13] XUE M, WANG T, and MAO S. Double evolutsional artificial bee colony algorithm for multiple traveling salesman problem[C]. Preoeedings of MATEC Web of Conferences, EDP Sciences, 2016: 44. doi: 10.1051/ matecconf/20164402025.

[14] VENKATESH P and SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]., 2015, 26: 74-89. doi: 10.1016/ j.asoc.2014.09.029.

[15] 韓麗霞, 王宇平, 蘭紹江. 基于有序劃分編碼的圖著色算法[J]. 電子學(xué)報, 2010, 38(1): 146-150.

HAN Lixia, WANG Yuping, and LAN Shaojiang. Graph coloring algorithm based on ordered partition encoding[J]., 2010, 38(1): 146-150.

[16] HELSGAUN K. General k-opt submoves for the Lin–Kernighan TSP heuristic[J]., 2009, 1(2/3): 119-163. doi: 10.1007/s12532- 009-0004-6.

[17] ALIJLA B O, WONG L P, LIM C P,. A modified intelligent water drops algorithm and its application to optimization problems[J]., 2014, 41: 6555-6569. doi: 10.1016/j.eswa.2014.05.010.

[18] WANG S, WANG L, LIU M,. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J]., 2013, 145(1): 387-396. doi: 10.1016/j.ijpe.2013.05.004.

[19] 王軍強, 郭銀洲, 崔福東, 等. 基于多樣性增強的自適應(yīng)遺傳算法的開放式車間調(diào)度優(yōu)化[J]. 計算機集成制造系統(tǒng), 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

WANG Junqiang, GUO Yinzhou, CUI Fudong,. Diversity enhancement-based adaptive genetic algorithm for open-shop scheduling problem[J]., 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

王勇臻： 男，1990年生，博士生，研究方向為智能計算、數(shù)據(jù)挖掘等.

陳 燕： 女，1952年生，教授，研究方向為管理科學(xué)與決策、知識管理、數(shù)據(jù)倉庫與數(shù)據(jù)挖掘等.

于瑩瑩： 女，1987年生，博士生，研究方向為數(shù)據(jù)挖掘、信息檢索等.

Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem

WANG Yongzhen CHEN Yan YU Yingying

(,,116026,)

In order to solve the total-path-shortest Multiple Traveling Salesman Problem (MTSP), an improved grouping genetic algorithm is proposed. This algorithm employs a new encoding scheme called ordered grouping encoding, which makes the adjusted individuals corresponding one by one to valid solutions of MTSP. According to the features of the encoding scheme, a fast crossover operator is constructed for the sake of reducing the running time of the algorithm. For enhancing its local search ability, the algorithm combines the greedy algorithm and the 2-opt algorithm to design a new local search operator. The comparison of results shows that the proposed algorithm can solve MTSP effectively and has an excellent search performance no matter in computing efficiency or convergence precision.

Grouping Genetic Algorithm (GGA); Multiple Traveling Salesman Problem (MTSP); Encoding; 2-opt algorithm

TP18

A

1009-5896(2017)01-0198-08

10.11999/JEIT160211

2016-03-07；改回日期：2016-07-22；

2016-10-09

王勇臻 kuadmu@163.com

國家科技支撐計劃(2014BAH24F04)，國家自然科學(xué)基金(71271034)

The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2014BAH24F04), The National Natural Science Foundation of China (71271034)