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

裴小兵,于秀燕,王尚磊

Solution of traveling salesman problem by hybrid imperialist competitive algorithm

Xiao-bing PEI,Xiu-yan YU,Shang-lei WANG

表 1 HICA与ICA及GA实验结果对比

Tab.1 The comparison of experimental results between HICA、ICA and GA

序号	实例	C_u	HICA				ICA				GA
序号	实例	C_u	$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	−¹⁾	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