孫 文 彬，王 江

(中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京 100083)

一種基于遺傳算法的TSP問題多策略優(yōu)化求解方法

孫 文 彬，王 江

(中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院，北京 100083)

針對遺傳算法求解TSP問題解質(zhì)量不高的缺陷，該文提出并設(shè)計了一種基于遺傳算法的多策略優(yōu)化求解方法。首先，應(yīng)用最鄰近法構(gòu)建TSP的初始解；接著將路徑長度作為適應(yīng)度評價指標(biāo)，構(gòu)建基于遺傳算法的TSP初始解優(yōu)化方法，并根據(jù)試驗結(jié)果確定適合的遺傳算法參數(shù)；然后，針對遺傳算法易陷入局部最優(yōu)的缺陷，借助去交叉和小角操作進一步優(yōu)化TSP解路徑；在此基礎(chǔ)上，將遺傳算法進行并行化處理，通過增加遺傳算法的多樣性提高TSP解質(zhì)量。最后，應(yīng)用標(biāo)準(zhǔn)測試集(TSPLIB)進行試驗，結(jié)果表明：該算法能有效提高TSP解的質(zhì)量，經(jīng)并行遺傳算法、去交叉和小角優(yōu)化后各測試數(shù)據(jù)集TSP解誤差率平均下降了22.57%；解的誤差率均在7.94%以內(nèi)，質(zhì)量明顯優(yōu)于最鄰近法、插入法、2-Opt優(yōu)化等傳統(tǒng)方法；在節(jié)點數(shù)多的測試數(shù)據(jù)集中算法也獲得了良好加速性能，8進程時算法加速比達2.51。

TSP問題;遺傳算法;優(yōu)化策略;2-Opt

旅行商問題(Traveling Salesman Problem，TSP)是路徑規(guī)劃和組合優(yōu)化領(lǐng)域中著名的NP- hard問題。車輛路徑規(guī)劃[1]、物流貨物配送[2]、飛機航線安排、災(zāi)害應(yīng)急調(diào)度[3]等問題均是典型的TSP問題[4-6]。目前，TSP求解算法主要分兩類：精確算法和近似算法。精確算法包括：群舉法、分支定界法、動態(tài)規(guī)劃法等。精確算法解的質(zhì)量高，但求解所需時間長，無法用于大規(guī)模網(wǎng)絡(luò)TSP問題的求解。近似算法通過先產(chǎn)生初始解再優(yōu)化的方式獲取TSP的解。生成初始解的主要方法有最近鄰法和插入法[7]；初始解優(yōu)化多采用智能算法，主要方法有：貪心算法[8]、2-opt算法[9]、遺傳算法[10-16]、模擬退火算法[17]、蟻群算法[17-22]、免疫算法[23]等。Wang等在分析基于智能算法的TSP求解方法優(yōu)缺點的基礎(chǔ)上[24,25]，指出遺傳算法受參數(shù)選擇和數(shù)據(jù)集分布結(jié)構(gòu)的影響最小，陷入局部最優(yōu)的概率最低。因此，本文設(shè)計了一種基于遺傳算法和多策略優(yōu)化的TSP求解方法，以提高解的質(zhì)量。

1 算法實現(xiàn)

大規(guī)模TSP問題的求解多采用求解速度快的近似算法，即首先生成初始解，再利用智能算法優(yōu)化提高初始解的質(zhì)量。遺傳算法求解速度快[25]，因此，將遺傳算法作為初始解優(yōu)化的主要方法。為了避免遺傳算法出現(xiàn)過早收斂的情況，通過引入去交叉和小角操作盡可能降低遺傳算法收斂至局部最優(yōu)的可能性，進而獲取到高質(zhì)量的TSP解。

1.1 遺傳算法優(yōu)化

遺傳算法通過遺傳變異操作將大量種群中具有不同結(jié)構(gòu)形式的個體進行結(jié)構(gòu)重組優(yōu)化，進而不斷提取出個體中的較優(yōu)結(jié)構(gòu)，然后對它們進行下一步的尋優(yōu)，最終逐漸逼近最優(yōu)解。遺傳算法用于初始解優(yōu)化時，將初始解路徑拆分為多個子路徑，每個子路徑作為獨立種群；將路徑長度作為適應(yīng)度評價指標(biāo)，通過種群間的交叉、變異來獲取更高質(zhì)量的解。遺傳算法中初始種群規(guī)模、遺傳代數(shù)、交叉率、變異率等參數(shù)設(shè)定均會影響算法的優(yōu)化效果。為此，本文應(yīng)用TSPLib(http://www.iwr.uniheidelberg.de/groups/comopt/software/TSP LIB5/tsp/)中的3個標(biāo)準(zhǔn)測試數(shù)據(jù)(kroA200、u1060、pla7397)進行試驗，以確定最優(yōu)的算法參數(shù)。

首先，保持遺傳代數(shù)、交叉率、變異率等參數(shù)不變,通過改變初始種群規(guī)模，分析初始種群規(guī)模對解質(zhì)量的影響，并用誤差率評價TSP解的質(zhì)量(如式(1)所示)。初始種群為500、 1 000、1 500、2 000、2 500、3 000時，測試數(shù)據(jù)集解的誤差率如表1所示。隨著初始種群數(shù)的增加，TSP解的誤差率下降了4%～10%；當(dāng)初始種群數(shù)超過2 000時，TSP解的誤差率基本保持不變。同時，初始種群規(guī)模的擴大會導(dǎo)致算法求解時間增加，因此，綜合考慮上述因素將初始種群數(shù)確定為2 000。

誤差率(P)=(解—最優(yōu)解)/最優(yōu)解×100%

(1)

表1 初始種群數(shù)對解質(zhì)量的影響

按照類似的方法，保持遺傳算法的其他參數(shù)不變，改變遺傳代數(shù)、交叉率、變異率等參數(shù)值，并計算TSP解的誤差率。遺傳代數(shù)為500、1 000、2 000、4 000、5 000時，解的誤差率如表2所示。交叉率為0.6、0.7、0.8和變異率為0.05、0.10、0.15時，TSP解的誤差率如表3所示。由表2可知，當(dāng)遺傳代數(shù)達到4 000時，TSP解誤差率下降1.7%～8.8%；當(dāng)交叉率為0.7，變異率為0.10時，TSP解的質(zhì)量最佳。因此，將遺傳算法中的遺傳代數(shù)設(shè)定為4 000，交叉率設(shè)定為0.7，變異率確定為0.10。

表2 遺傳代數(shù)對解質(zhì)量的影響

表3 交叉率和變異率對解質(zhì)量的影響

1.2 去交叉和小角

由于遺傳算法會出現(xiàn)過早收斂的現(xiàn)象，易陷入局部最優(yōu)，TSP解路徑中的交叉和小角現(xiàn)象是遺傳算法陷入局部最優(yōu)的表現(xiàn)之一。為此，需要通過改變節(jié)點之間連接順序消除TSP解路徑中的交叉和小角現(xiàn)象，以避免遺傳算法出現(xiàn)過早陷入局部最優(yōu)的問題。

交叉現(xiàn)象的探測可通過判斷解路徑中各線段是否相交來確定，若存在線段相交，則說明該TSP解中存在交叉現(xiàn)象。通過調(diào)整節(jié)點之間的連接順序可消除交叉問題，具體實現(xiàn)過程如下：假設(shè)子路徑(i,i+1)與(j+1,j+2)相交(如圖1a所示)，首先交換TSP解路徑序列中節(jié)點i+1和j+1的位置，然后將i+1到j(luò)+1的子路徑序列進行逆序排列，把原來的解{1,…，i-1,i,i+1,i+2…,j-1,j,j+1,…,n}轉(zhuǎn)變?yōu)閧1,…，i-1,i,j+1,j,j-1…i+2,i+1,j+2，…，n}(如圖1b所示)，即可消除交叉現(xiàn)象。

圖1 去交叉的實現(xiàn)原理

TSP解路徑中“小角”現(xiàn)象如圖2a所示。通過改變節(jié)點的連接方式能消除TSP路徑中的小角現(xiàn)象。TSP解是一個閉合回路，若要改變解路徑的連接方式，每次至少需要同時刪除和增加兩條邊。若要消除圖2a中節(jié)點i處的小角，則首先刪除連線(i-1,i)和(i+1,i+2,)，增加連線(i-1,i+1)和(i,i+2)，改變節(jié)點i和i+1的連線方向。若刪除兩條邊的長度之和大于增加兩條邊的和，即D(i-1,i)+D(i+1,i+2)>D(i-1,i+1)+D(i,i+2)(D(i,i+1)為節(jié)點i到i+1的距離)，則能提高TSP解的質(zhì)量。重復(fù)上述的過程，直至任意相鄰3個節(jié)點間不存在小角為止。

圖2 鄰近置換示意

1.3 算法的并行化

增加遺傳算法的多樣性能提高算法求解的精度。而并行算法能利用多機多核的計算資源運行多個遺傳算法，可增加算法的隨機多樣性，進而既可提高遺傳算法的優(yōu)化效果,又能加快算法的收斂速度。為此，本文將遺傳算法進行了并行化，即在TSP求解過程中，利用多機多核的計算資源分別開辟多個進程，運行多個遺傳算法優(yōu)化TSP的初始解；從各進程優(yōu)化結(jié)果中取出最優(yōu)的解，再進行去交叉和小角；重復(fù)上述過程，直到TSP優(yōu)化結(jié)果滿足設(shè)定的退出條件為止。這樣既可提高TSP解的質(zhì)量，又能加快遺傳算法收斂速度，提高TSP求解速度。

2 試驗分析

為了驗證算法的正確性和有效性，本文應(yīng)用標(biāo)準(zhǔn)測試數(shù)據(jù)集TSPLIB進行相關(guān)試驗。以MPI并行編程模型和GDAL地理數(shù)據(jù)操作開源庫為基礎(chǔ)，利用2臺4核計算機搭建Windows集群系統(tǒng)，具體配置如下：CPU的型號為I5-2380P，主頻為3.40 GHz，內(nèi)存大小為8 G。

試驗首先分析了遺傳算法、去交叉和小角對初始解的優(yōu)化效果(表4)。采用最鄰近法生成初始解的誤差率在20.57%～31.01%之間；利用遺傳算法優(yōu)化初始解后，各測試數(shù)據(jù)集解誤差率在5.24%～15.43%之間，解誤差率平均下降了16.8%；再經(jīng)去交叉和小角處理后，TSP解誤差率平均又下降了5.77%。由此可見，采用并行遺傳算法、去交叉和小角多種優(yōu)化策略能極大程度提高初始解的質(zhì)量，使初始解的誤差率平均下降22.57%。

表4 遺傳算法、去交叉和小角的優(yōu)化效果

試驗還對比分析了本文算法與最鄰近法、插入法、最鄰近和插入混合方法、2-Opt解的質(zhì)量。最鄰近法、插入法、最鄰近和插入混合法的試驗數(shù)據(jù)來源于參考文獻[7]。在試驗中，應(yīng)用上述算法進行10次TSP問題的求解，分別統(tǒng)計出各測試數(shù)據(jù)集的最優(yōu)解值，結(jié)果如表5所示。由表5可知，本文算法的最優(yōu)解誤差率在1.85%～7.94%之間(各數(shù)據(jù)集解的最優(yōu)解誤差率如圖3所示),算法解的質(zhì)量明顯高于最鄰近法、插入法、最鄰近和插入混合法、2-Opt法。

表5 不同算法最優(yōu)解誤差率的對比

此外，本文測試了不同數(shù)據(jù)集并行優(yōu)化算法的加速比情況(表6)。當(dāng)測試數(shù)據(jù)集節(jié)點數(shù)較少時，并行算法由于增加了不同進程間的通訊時間，通訊消耗時間抵消了多進程計算節(jié)省的時間，算法加速效果不理想，甚至出現(xiàn)并行算法計算時間多于串行算法的現(xiàn)象。隨著測試數(shù)據(jù)集節(jié)點數(shù)的增加，并行算法獲得良好的加速性能，測試數(shù)據(jù)集Pla 7379在8進程時，加速比達到2.51。

圖3 最優(yōu)解的誤差率

表6 不同測試數(shù)據(jù)集加速比情況

3 結(jié)論

本文設(shè)計了一種基于遺傳算法與多策略優(yōu)化的TSP求解方法，應(yīng)用標(biāo)準(zhǔn)測試數(shù)據(jù)集進行了相關(guān)試驗。結(jié)果表明：經(jīng)遺傳算法、去相交和小角、并行化等多策略優(yōu)化措施處理，TSP解的質(zhì)量得到大幅提高，各測試數(shù)據(jù)集最優(yōu)解的誤差率均在7.94%以內(nèi)；本文算法求取TSP解的質(zhì)量明顯優(yōu)于最鄰近法、插入法、2-Opt優(yōu)化等傳統(tǒng)方法；在節(jié)點數(shù)多的測試數(shù)據(jù)集中，算法也獲得了良好的加速性能，8進程算法加速比均在2.5以上。由于本文采用算法并行的策略實現(xiàn)了遺傳算法的并行化，這導(dǎo)致大多數(shù)測試數(shù)據(jù)集并行加速效果不理想。若要進一步提高算法的并行效率，需設(shè)計細粒度并行模式，即將遺傳算法中交叉變異過程進行并行化，進而獲得良好的加速比。此外，本文算法僅應(yīng)用TSPLIB中的部分測試集進行了試驗，無法保證算法適用于所有的標(biāo)準(zhǔn)測試集，因此，需應(yīng)用更多的測試數(shù)據(jù)集進行試驗，分析本文算法的普適性。

[1] 唐健,史文中,孟令奎.基于遺傳算法的時相關(guān)動態(tài)車輛路徑規(guī)劃模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2008,33(8):875-879.

[2] 李清泉,張金亭,黃經(jīng)南.一個物流配送優(yōu)化算法[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2003,28(1):9-13.

[3] 孟永昌,楊賽霓,史培軍.基于改進遺傳算法的路網(wǎng)應(yīng)急疏散多目標(biāo)優(yōu)化[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2014,39(2):201-205.

[4] 尹大胐,方裕.疏散規(guī)劃的一種優(yōu)化算法[J].地理與地理信息科學(xué),2014,29(2):31-35.

[5] 胡勇,宗真,羅文,等.多條件約束應(yīng)急疏散路徑分析的幾何代數(shù)方法[J].地理與地理信息科學(xué),2012,28(5):47-5.

[6] 方金云,張聰,邱強,等.一種基于網(wǎng)絡(luò)數(shù)據(jù)的LRP并行求解算法[J].地理與地理信息科學(xué),2013,29(4):13-16.

[7] 饒衛(wèi)振,金淳，黃英藝.求解TSP問題的最近領(lǐng)域與插入混合算法[J].系統(tǒng)工程理論與實踐,2011,31(8):1419-1428.

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

[9] 劉荷花,崔超,陳晶.一種改進的遺傳算法求解旅行商問題[J].北京理工大學(xué)學(xué)報,2013,33(4):390-393.

[10] 鄧長春,朱儒明,李詠霞,等.一種求解TSP問題的多種群并行遺傳算法[J].計算機仿真,2008,25(9):187-190.

[11] 趙宏立，龐小紅，吳智銘.基因塊編碼的并行遺傳算法及其在TSP中的應(yīng)用[J].上海交通大學(xué)學(xué)報,2004,38(增刊):213-217.

[12] 許智宏,宋勃,郭艷艷.模擬退火與蟻群混合并行算法解旅行商問題[J].河北工業(yè)大學(xué)學(xué)報,2010,39(2):48-51.

[13] 戚玉濤,焦李成,劉芳.基于并行人工免疫算法的大規(guī)模TSP問題求解[J].電子學(xué)報,2008,36(8):1552-1558.

[14] 唐立新.旅行商問題(TSP)的改進遺傳算法[J].東北大學(xué)學(xué)報(自然科學(xué)版),1999,20(1):40-42.

[15] 謝旻.一種混合例子群優(yōu)化算法在TSP中的應(yīng)用[J].太原理工大學(xué)學(xué)報,2013,44(4):506-509.

[16] 杜鵬楨,唐振民,孫研.一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解[J].控制與決策,2014,29(10):1729-1736.

[17] 楊華芬,魏延.一種求解TSP問題的改進遺傳算法[J].重慶工學(xué)院學(xué)報(自然科學(xué)版),2007,21(5):86-90.

[18] BAI J,YANG G,CHEN Y,HU L,et al.A model induced max-min ant colony optimization for asymmetric traveling salesman problem[J].Applied Soft Computing,2013,13:1365-1375.

[19] ZHU Q,CHEN S.A new ant evolution algorithm to resolve TSP problem[C].Sixth International Conference on Machine Learning and Application(ICMLA 2007),2007.62-66.

[20] ANURAJ M,REMYA G.A parallel implementation of ant colony optimization for TSP based on MapReduce framework[J].International Journal of Computer Application,2014,88(8):8875-8887.

[21] PAN G,LI K,OUYANG A.Hybrid immune algorithm based on greedy algorithm and delete-cross operator for solving TSP[J].Soft Computer,2016,20:555-566.

[22] WANG H.Comparison of several intelligent algorithms for solving TSP problem in industrial engineering[C].The 2nd International Conference on Complexity Science & Information Engineering,2012.226-235.

[23] GU J.Efficient local search with search space smoothing:A case study of the traveling salesman problem (TSP)[J].IEEE Transactions on Systems,Man,and Cybernetics,1994,24(5):728-735.

[24] WANG J,ERSOY O,HE M,et al.Multi-offspring genetic algorithm and its application to the traveling salesman problem[J].Applied Soft Computing,2016,43:415-423.

[25] TOBIAS M,OLA S.Removing and adding edges for the traveling salesman problem[J].Journal of the ACM,2016,63(1):2-29.

An Algorithm for TSP Problem Based on Genetic Algorithm and Multi-optimization Operation

SUN Wen-bin,WANG Jiang

(SchoolofGeo-scienceandSurveyingEngineer,ChinaUniversityofMining&Technology(Beijing),Beijing100083,China)

To overcome the deficiency of poor quality of TSP path by using genetic algorithm,an algorithm based on genetic algorithm and multi-optimization operation is presented.Firstly,initial TSP path is approached by using the nearest neighbor method;then,the length of TSP path is considered as the fitness evaluation index and the optimizing method of TSP initial solution based on genetic algorithm is described.According to the experiment results,the suited genetic algorithm parameter can be determined.Next,pointing to the shortcoming that genetic algorithm is easy to fall into local optimum,to use the cross-removing and small-angle operation optimize the solution path of TSP;on this basis,the genetic parallel algorithm,and increasing the diversity of algorithm can improve the quality of TSP solution.Finally,the experiment is done by using the standard test datasets(TSPLIB).The results show that:this algorithm can effectively improve the quality of TSP solution,after parallel genetic algorithm,cross-removing and small-angle optimization,the TSP solution error rate of every test data set decreases by 22.57 percent on average;the error rate of the solution is within 7.94 percent,obviously better than the nearest neighboring method,inserting method,2-Opt optimization and other traditional methods;among the testing datasets that have many nodes,the algorithm also obtains a good acceleration performance and algorithm acceleration rates are more than 2.51 when it is 8-processes.

Traveling Salesman Problem(TSP);genetic algorithm;optimization strategy;2-Optimization(2-Opt)

2015-12-10；

2016-03-29

國家自然科學(xué)基金資助項目(41201416)

孫文彬(1977-)，男，博士，副教授，從事全球離散格網(wǎng)、智能計算、并行計算等方面的研究。E-mail:swb1996@126.com

10.3969/j.issn.1672-0504.2016.04.001

P208；TP301.6

A

1672-0504(2016)04-0001-04