Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2019, Vol. 53 Issue (10): 2003-2012    DOI: 10.3785/j.issn.1008-973X.2019.10.018
Automation Technology, Computer Technology     
Solution of traveling salesman problem by hybrid imperialist competitive algorithm
Xiao-bing PEI(),Xiu-yan YU,Shang-lei WANG
School of Management, Tianjin University of Technology, Tianjin 300384, China
Download: HTML     PDF(1128KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A hybrid imperialist competitive algorithm (HICA) was proposed aiming at the problem of traveling salesman problem combinatorial optimization. In the framework of imperialist competitive algorithm, the probability model was introduced to record and update the feasible solution, and the probability matrix was used to mine the excellent feasible solution segment combination block in the feasible solution in order to reduce the complexity of imperialist assimilation and improve the quality of feasible solution. The feasible solution was recombined with greedy criteria and insertion search operators in order to achieve fast convergence speed and improve population diversity. An iterative search strategy was proposed to search effectively in different solution spaces to find out the missing key information and avoid local optimization. The mixed empire competition was verified through the simulation test and comparison of the results of TSPLIB standard cases.

Key words： hybrid imperialist competitive algorithm (HICA)      traveling salesman problem      probability model      combined block      greedy criteria      repeated search strategy     
Received: 05 August 2018      Published: 30 September 2019
CLC:  TP 18  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Xiao-bing PEI
Xiu-yan YU
Shang-lei WANG
Cite this article:

Xiao-bing PEI,Xiu-yan YU,Shang-lei WANG. Solution of traveling salesman problem by hybrid imperialist competitive algorithm. Journal of ZheJiang University (Engineering Science), 2019, 53(10): 2003-2012.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2019.10.018     OR     http://www.zjujournals.com/eng/Y2019/V53/I10/2003


混合帝国竞争算法求解旅行商问题

针对旅行商组合优化问题，提出混合帝国竞争算法（HICA）. 以帝国竞争算法为框架，引入概率模型用以记录并更新可行解，利用概率矩阵挖掘可行解中的优秀可行解片段组合区块，用以降低帝国同化的复杂度及提高可行解的质量；利用贪婪准则及插入搜寻算子操作进行可行解重组，以加快收敛速度及提高种群多样性. 提出反复搜索策略在不同的解空间进行有效的搜索，找出被遗漏的关键信息，避免局部最优化；通过对TSPLIB标准案例的仿真测试及结果比较，验证了混合帝国竞争算法的有效性.


关键词： 混合帝国竞争算法（HICA）,  旅行商问题,  概率模型,  组合区块,  贪婪准则,  反复搜索策略 
Fig.1 Flow chart of hybrid imperialist competitive algorithm
Fig.2 Renewal schematic of probability matrix
Fig.3 Comparison of HICA solution complexity
Fig.4 Schematic of block mining
Fig.5 Generation of new assimilation colonies
Fig.6 Feasible solution of greedy criterion reengineering
Fig.7 Feasible solution of insert search operator
Fig.8 Change search range of parent
序号 实例 Cu HICA ICA GA
$C{\rm{^*}} $ ${\overline C} $ $\psi $/% $\overline t $/s $C{\rm{^*}} $ $\overline C$ $\psi $/% $\overline t $/s $C{\rm{^*} }$ $\overline C $ $\psi $/% $\overline t $/s
注：1)“?”表示利用该算法计算的最优解优于已知的最优解.
1 bier127 118 282 118 282 119 857 0.00 16.01 118 703 121 095 0.36 16.21 120 406 126 845 1.80 17.37
2 ch130 6 110 6 110 6 142 0.00 8.54 6 127 6 204 0.29 8.73 6 303 6 431 3.17 8.71
3 ch150 6 528 6 528 6 600 0.00 10.85 6 543 6 641 0.24 11.21 6 790 68 402 4.02 11.43
4 d198 15 780 15 780 16 583 0.00 24.32 1 587 16 108 0.58 27.10 16 149 16 298 2.34 30.22
5 eil51 426 426 430 0.00 2.85 429 432 0.67 3.94 435 441 2.29 5.03
6 eil76 538 538 546 0.00 4.94 544 558 1.18 6.53 550 565 2.39 9.47
7 eil101 629 629 630 0.00 2.02 640 664 1.78 13.83 660 674 4.96 13.27
8 kroA100 21 282 21 282 21 282 0.00 9.09 21 285 21 508 0.02 11.28 22 353 22 654 5.03 12.03
9 kroA200 29 368 29 373 30 159 0.02 15.12 29 431 31 042 0.21 18.72 31 268 32 416 6.47 21.73
10 lin318 42 029 42 074 42 348 0.11 20.93 42 307 43 051 0.66 29.85 45 548 45 815 8.37 38.36
11 pr107 44 303 44 303 44 538 0.00 14.33 44 302 44 803 ?1) 17.90 46 674 46 856 5.35 16.69
12 Pr136 96 772 96 772 97 431 0.00 10.12 96 771 98 426 ? 16.36 101 189 102 344 4.564 18.71
13 pr152 73 682 73 682 73 624 0.00 11.01 73 684 74 051 0.00 18.62 74 520 75 658 1.1 19.72
14 pr299 48 191 48 199 49 001 0.02 33.99 48 640 49 124 0.93 40.40 51 952 52 104 7.8 48.22
15 pr439 107 217 107 383 111 216 0.15 57.73 107 917 109 859 0.65 59.36 118 084 19 208 10.14 63.23
16 rat575 6 773 6 814 6 942 0.61 71.96 7 037 7 235 3.90 71.68 8 016 8 945 18.36 78.26
17 rat783 8 806 8 889 8 910 0.94 100.5 9 247 9 686 5.04 103.97 10 469 11 502 18.89 122.46
18 tsp225 3 916 3 916 4 011 0.00 24.61 3 907 4 095 ? 28.35 4 220 4 264 7.77 35.34
Tab.1 The comparison of experimental results between HICA、ICA and GA
实例
（已知最优解） 		算法 $C{\rm{^*}} $ ${\overline C} $ $\psi $/% $\overline t $/s 实例
（已知最优解） 		算法 $C^{\rm{*}}$ $\overline C $ $\psi $/% $\overline t $/s
注：1)“?”表示在相应的文献中未找到对应的值.
berlin52（7542） DCS 7 542 7 836.4 0.00 2..24 st70（675） DCS 675 675.3 0.00 2..24
DWCA 7 542 7 542.0 0.00 15.70 DWCA 675 678.6 0.00 90.44
DSOS 7 542 7 542.6 0.00 63.44 DSOS 675 679.2 0.00 82.58
ACE 7 542 7 543.0 0.00 13.36 ACE 675 676.4 0.00 2.69
HICA 7 542 7 542.0 0.00 2.20 IMA 677 684.0 0.30 ?1)
? ? ? ? ? HICA 675 675.1 0.00 9.09
ch130（6110） DCS 6 110 6 135.9 0.00 23.12 kroa100（21282） DCS 21 282 21 282.9 0.00 2.71
ACE 6 110 6 153.9 0.00 26.03 DWCA 21 282 21 348.1 0.00 473.43
IMA 6 220 6 245.0 0.00 ?1) DSOS 21 282 21 409.5 0.00 127.53
HICA 6 110 6 142.1 0.00 8.54 ACE 21 282 21 298.6 0.00 42.46
? ? ? ? ? HICA 21 282 21 282.2 0.00 1.96
pr152（73682） DCS 73 682 73 821.6 0.00 14.86 eil101（629） DCS 629 630.4 0.00 18.87
DWCA 73 682 74 202.6 0.00 4049.5 DWCA 639 645.9 1.50 602.20
DSOS 74 013 74 785.4 0.44 516.68 DSOS 640 650.6 1.74 171.75
ACE 73 682 73 766.8 0.00 149.12 ACE 629 633.6 0.00 3.91
HICA 73 682 73 624.1 0.00 11.01 HICA 629 630.1 0.00 2.02
Tab.2 Performance comparison between HICA and other algorithms for solving TSP problem
Fig.9 Optimal roadmap of eil51
Fig.10 Optimal roadmap of kroA200
Fig.11 Convergence graph of eil51
Fig.12 Convergence graph of kroA200
[1]   BLUM C, ROLI A Metaheuristics in combinatorial optimization: overview and conceptual comparison[J]. ACM Computing Surveys, 2003, 35 (3): 268- 308
doi: 10.1145/937503.937505
[2]   吴虎胜, 张凤鸣, 李浩, 等 求解TSP问题的离散狼群算法[J]. 控制与决策, 2015, 30 (10): 1861- 1867
WU Hu-sheng, ZHANG Feng-ming, LI Hao, et al Discrete wolf group algorithm for solving TSP problem[J]. Control and Decision, 2015, 30 (10): 1861- 1867
[3]   何庆, 吴意乐, 徐同伟 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33 (02): 219- 225
HE Qing, WU Yi-le, XU Tong-wei Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision, 2018, 33 (02): 219- 225
[4]   沈继红, 王侃 求解旅行商问题的混合粒子群优化算法[J]. 智能系统学报, 2012, 7 (02): 174- 182
SHEN Ji-hong, WANG Kan Hybrid particle swarm optimization algorithm for traveling salesman problem[J]. Journal of Intelligent System, 2012, 7 (02): 174- 182
doi: 10.3969/j.issn.1673-4785.201104014
[5]   徐小平, 张东洁 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54 (02): 144- 148
XU Xiao-ping, ZHANG Dong-jie Solving the traveling salesman problem based on the monkey algorithm[J]. Computer Engineering and Application, 2018, 54 (02): 144- 148
[6]   刘荷花, 崔超, 陈晶 一种改进的遗传算法求解旅行商问题[J]. 北京理工大学学报, 2013, 33 (04): 390- 393
LIU He-hua, CUI Chao, CHEN Jing An improved genetic algorithm for traveling salesman problem[J]. Journal of Beijing Institute of Technology, 2013, 33 (04): 390- 393
doi: 10.3969/j.issn.1001-0645.2013.04.013
[7]   ATASHPAZ G E, LUCAS C. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition [C] // Proceedings of IEE Congress on Evolutionary Computation. Singapore: IEE, 2007: 4661-4667.
[8]   郭婉青, 叶东毅 基于帝国分裂的帝国竞争算法优化[J]. 计算机应用, 2013, 33 (增2): 86- 90
GUO Wan-qing, YE Dong-yi Optimization of empire competition algorithm based on empire splitting[J]. Computer Applications, 2013, 33 (增2): 86- 90
[9]   FATHY A, REZK H Parameter estimation of photovoltaic system using imperialist competitive algorithm[J]. Renewable Energy, 2017, 111 (06): 534- 542
[10]   SONG J, YANG G, LI Y, et al Incoherent beam combining based on imperialist competitive algorithm[J]. Optik, 2018, 168: 1- 9
doi: 10.1016/j.ijleo.2018.04.090
[11]   MOSSAD M I, AZAB M, ABU-SIADA A Transformer parameters estimation from nameplate data using evolutionary programming techniques[J]. IEEE Transactions on Power Delivery, 2014, 29 (5): 2118- 2123
doi: 10.1109/TPWRD.2014.2311153
[12]   ZANDIEH M, KHATAMI A R, RAHMATI S H A Flexible job shop scheduling under condition-based maintenance: improved version of imperialist competitive algorithm[J]. Applied Soft Computing, 2017, 58 (01): 213- 233
[13]   KARIMI S, ARDALAN Z, NADERI B, et al Scheduling flexible job-shops with transportation times: mathematical models and a hybrid imperialist competitive algorithm[J]. Applied Mathematical Modelling, 2016, 41 (09): 411- 423
[14]   SADHU A K, RAKSHIT P, KONAR A A modified imperialist competitive algorithm for multi-robot stick-carrying application[J]. Robotics and Autonomous Systems, 2016, 76 (C): 15- 35
[15]   HOSSEINI S, KHALED A A survey on the imperialist competitive algorithm metaheuristic: implementation in engineering domain and directions for future research[J]. Applied Soft Computing, 2014, 24 (11): 1078- 1094
[16]   ARDALAN Z, KARIMI S, POURSABZI O, et al A novel imperialist competitive algorithm for generalized traveling salesman problems[J]. Applied Soft Computing, 2015, 26 (1): 546- 555
[17]   张鑫龙, 陈秀万, 肖汉, 等 一种求解旅行商问题的新型帝国竞争算法[J]. 控制与决策, 2016, 31 (04): 586- 592
ZHANG Xin-long, CHEN Xiu-wan, XIAO Han, et al A new imperial competition algorithm for traveling salesman problem[J]. Control and Decision, 2016, 31 (04): 586- 592
[18]   CHANG P C, CHEN M H A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing, 2014, 18 (6): 1177- 1188
doi: 10.1007/s00500-013-1136-1
[19]   CHANG P C, HUANG W H, TING C J Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications, 2010, 37 (3): 1863- 1878
doi: 10.1016/j.eswa.2009.07.066
[20]   LEE H P Solving traveling salesman problems using generalized chromosome genetic algorithm[J]. Progress in Natural Science: Materials International, 2008, 18 (7): 887- 892
doi: 10.1016/j.pnsc.2008.01.030
[21]   林敏, 刘必雄, 林晓宇 带Metropolis准则的混合离散布谷鸟算法求解旅行商问题[J]. 南京大学学报: 自然科学, 2017, 53 (05): 972- 983
LIN Min, LIU Bi-xiong, LIN Xiao-yu A hybrid discrete Cuckoo algorithm with metropolis criterion for solving traveling salesman problem[J]. Journal of Nanjing University: Natural Science, 2017, 53 (05): 972- 983
[22]   OSABA E, SER J D, SADOLLAH A, et al A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem[J]. Applied Soft Computing, 2018, (07): 103- 114
[23]   EZUGWU E S, ADEWUMI A O Discrete symbiotic organisms search algorithm for travelling salesman problem[J]. Expert Systems with Applications, 2017, 87 (01): 101- 113
[1] HE Xue-jun, WANG Jin, LU Guo-dong, CHEN Li.
Optimization of robot image drawing sequence based on ant colony algorithm
[J]. Journal of ZheJiang University (Engineering Science), 2015, 49(6): 1139-1145.
[2] WANG Xiao-Zhou, JIN Wei-Liang, YAN Yong-Dong. Path probability model of corrosion-crack assessment for existing reinforced concrete structures[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(6): 1191-1196.