混合帝国竞争算法求解旅行商问题
|
裴小兵,于秀燕,王尚磊
|
Solution of traveling salesman problem by hybrid imperialist competitive algorithm
|
Xiao-bing PEI,Xiu-yan YU,Shang-lei WANG
|
|
表 2 HICA与其他不同算法求解TSP问题的性能比较 |
Tab.2 Performance comparison between HICA and other algorithms for solving TSP problem |
|
实例 (已知最优解) | 算法 | $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 |
|
|
|