Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2019, Vol. 53 Issue (10): 2003-2012    DOI: 10.3785/j.issn.1008-973X.2019.10.018
自动化技术、计算机技术     
混合帝国竞争算法求解旅行商问题
裴小兵(),于秀燕,王尚磊
天津理工大学 管理学院，天津 300384
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
 全文: PDF(1128 KB)   HTML
摘要：

针对旅行商组合优化问题，提出混合帝国竞争算法（HICA）. 以帝国竞争算法为框架，引入概率模型用以记录并更新可行解，利用概率矩阵挖掘可行解中的优秀可行解片段组合区块，用以降低帝国同化的复杂度及提高可行解的质量；利用贪婪准则及插入搜寻算子操作进行可行解重组，以加快收敛速度及提高种群多样性. 提出反复搜索策略在不同的解空间进行有效的搜索，找出被遗漏的关键信息，避免局部最优化；通过对TSPLIB标准案例的仿真测试及结果比较，验证了混合帝国竞争算法的有效性.
关键词： 混合帝国竞争算法（HICA）;  旅行商问题;  概率模型;  组合区块;  贪婪准则;  反复搜索策略    
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
收稿日期: 2018-08-05 出版日期: 2019-09-30
CLC:  TP 18  
作者简介: 裴小兵（1965—），男，教授，博士，从事精益生产、物流配送研究. orcid. org/0000-0002-3053-878X. E-mail： peixiaobing100@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
裴小兵
于秀燕
王尚磊

引用本文:

裴小兵,于秀燕,王尚磊. 混合帝国竞争算法求解旅行商问题[J]. 浙江大学学报(工学版), 2019, 53(10): 2003-2012.

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.

链接本文:

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

图 1)  混合帝国竞争算法流程图
图 2  概率矩阵更新示意图
图 3  HICA求解复杂度比较
图 4  区块挖掘示意图
图 5  新同化殖民地的生成
图 6  贪婪准则重组可行解
图 7  插入搜寻算子重组可行解
图 8  改变母体搜索范围
序号 实例 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
表 1  HICA与ICA及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
表 2  HICA与其他不同算法求解TSP问题的性能比较
图 9  eil51最优路线图
图 10  kroA200最优路线图
图 11  eil51收敛图
图 12  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] 何雪军, 王进, 陆国栋, 陈立. 基于蚁群算法的机器人图像绘制序列优化[J]. 浙江大学学报(工学版), 2015, 49(6): 1139-1145.
[2] 莫愿斌 陈德钊 胡上序. 粒子群复形法求解旅行商问题[J]. J4, 2007, 41(3): 369-373.
[3] 张庆彬 吴惕华 刘波. 克隆选择单变量边缘分布算法[J]. J4, 2007, 41(10): 1715-1718.