1 TSP问题数学模型
2 改进的禁忌搜索算法
3 仿真实验
3.1 本文算法参数设置
3.1.1 禁忌长度的选择
3.1.2 候选集选择
3.2 初始解选择
3.2.1 文献[13]算例
表3 文献[13]算例实验结果 |
算法 | 1 | 2 | 3 | 4 | 5 | AVG |
---|---|---|---|---|---|---|
随机生成初始解算法 | 274 | 262 | 271 | 274 | 274 | 271 |
ICA算法 | 268 | 262 | 268 | 274 | 272 | 268 |
CW节约算法 | 263 | 269 | 265 | 271 | 262 | 266 |
贪婪算法 | 268 | 269 | 262 | 263 | 262 | 264 |
3.2.2 文献[12]算例
表4 文献[12]算例实验结果 |
算法 | 1 | 2 | 3 | 4 | 5 | AVG |
---|---|---|---|---|---|---|
随机生成初始解算法 | 15 551 | 15 603 | 15 398 | 15 475 | 15 525 | 15 510 |
ICA算法 | 15 433 | 15 641 | 15 428 | 15 482 | 15 508 | 15 498 |
CW节约算法 | 15 559 | 15 594 | 15 382 | 15 455 | 15 554 | 15 508 |
贪婪算法 | 15 410 | 15 475 | 15 387 | 15 505 | 15 447 | 15 444 |
3.3 邻域结构
表5 不同邻域算法结果 |
邻域 | 1 | 2 | 3 | 4 | 5 | AVG |
---|---|---|---|---|---|---|
Insert | 15 536 | 15 501 | 15 495 | 15 528 | 15 498 | 15 511 |
Swap | 15 429 | 15 447 | 15 449 | 15 398 | 15 474 | 15 439 |
2-opt | 15 398 | 15 410 | 15 457 | 15 472 | 15 399 | 15 427 |
3.4 算例比较
3.4.1 文献[12]算法与本文算法计算结果比较
表6 文献[12]与本文算法计算结果比较 |
迭代次数 | 实验次数 | a | b | 偏差率/% |
---|---|---|---|---|
100 | 1 | 16 905 | 15 483 | 9.18 |
2 | 17 609 | 15 498 | 13.62 | |
3 | 17 703 | 15 536 | 13.95 | |
4 | 17 152 | 15 619 | 9.81 | |
5 | 17 394 | 15 520 | 12.07 | |
500 | 1 | 16 526 | 15 464 | 6.87 |
2 | 16 587 | 15 387 | 7.80 | |
3 | 16 550 | 15 410 | 7.40 | |
4 | 16 852 | 15 422 | 9.27 | |
5 | 17 178 | 15 399 | 11.55 | |
1000 | 1 | 15 800 | 15 433 | 2.38 |
2 | 16 037 | 15 398 | 4.15 | |
3 | 15 382 | 15 382 | 0 | |
4 | 16 006 | 15 410 | 3.87 | |
5 | 15 824 | 15 382 | 2.87 |
3.4.2 TSPLIB数据库算例与本文算法计算结果的比较
表7 TSPLIB最优解与本文算法实验结果比较 |
算例 | n | AVG | opt | ref | 偏差率/% |
---|---|---|---|---|---|
Dantzig42 | 42 | 705 | 699 | 699 | 0 |
Berlin52 | 52 | 7 694 | 7 656 | 7 542 | 1.51 |
St70 | 70 | 699 | 692 | 675 | 2.52 |