Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (6): 1837-1843.DOI: 10.11772/j.issn.1001-9081.2021040567
Special Issue: 人工智能
• Artificial intelligence • Previous Articles Next Articles
Xiaoping XU1, Yangli TANG1(), Feng WANG2
Received:
2021-04-14
Revised:
2021-06-28
Accepted:
2021-07-02
Online:
2022-06-22
Published:
2022-06-10
Contact:
Yangli TANG
About author:
XU Xiaoping, born in 1973, Ph. D., professor. His research interests include intelligent algorithm.Supported by:
通讯作者:
唐阳丽
作者简介:
徐小平(1973—),男,陕西蓝田人,教授,博士,主要研究方向:智能算法基金资助:
CLC Number:
Xiaoping XU, Yangli TANG, Feng WANG. Artificial cooperative search algorithm for solving traveling salesman problems[J]. Journal of Computer Applications, 2022, 42(6): 1837-1843.
徐小平, 唐阳丽, 王峰. 求解旅行商问题的人工协同搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1837-1843.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021040567
TSP测试集 | 评价标准 | ACS | S-ACS | D-ACS | Q-ACS | SQACS |
---|---|---|---|---|---|---|
Oliver30 | 最优解 | 453.27 | 441.23 | 428.25 | 434.12 | 420.00 |
平均值 | 475.23 | 466.37 | 444.36 | 451.58 | 421.31 | |
平均时间/s | 29.41 | 29.54 | 31.25 | 24.21 | 26.17 | |
Att48 | 最优解 | 34 663.41 | 34 121.63 | 33 528.21 | 33 578.47 | 33 516.02 |
平均值 | 35 721.39 | 34 365.27 | 33 547.38 | 33 621.15 | 33 583.17 | |
平均时间/s | 56.26 | 56.61 | 58.31 | 43.23 | 49.02 | |
Eil51 | 最优解 | 484.05 | 465.54 | 435.27 | 447.36 | 426.00 |
平均值 | 496.55 | 478.20 | 449.36 | 464.71 | 427.71 | |
平均时间/s | 64.25 | 64.57 | 66.31 | 50.23 | 55.27 | |
Eil76 | 最优解 | 572.93 | 562.16 | 542.41 | 552.64 | 538.00 |
平均值 | 586.33 | 575.05 | 557.42 | 568.51 | 543.79 | |
平均时间/s | 91.23 | 91.56 | 93.24 | 81.41 | 85.16 |
Tab. 1 Ablation experimental results of SQACS algorithm
TSP测试集 | 评价标准 | ACS | S-ACS | D-ACS | Q-ACS | SQACS |
---|---|---|---|---|---|---|
Oliver30 | 最优解 | 453.27 | 441.23 | 428.25 | 434.12 | 420.00 |
平均值 | 475.23 | 466.37 | 444.36 | 451.58 | 421.31 | |
平均时间/s | 29.41 | 29.54 | 31.25 | 24.21 | 26.17 | |
Att48 | 最优解 | 34 663.41 | 34 121.63 | 33 528.21 | 33 578.47 | 33 516.02 |
平均值 | 35 721.39 | 34 365.27 | 33 547.38 | 33 621.15 | 33 583.17 | |
平均时间/s | 56.26 | 56.61 | 58.31 | 43.23 | 49.02 | |
Eil51 | 最优解 | 484.05 | 465.54 | 435.27 | 447.36 | 426.00 |
平均值 | 496.55 | 478.20 | 449.36 | 464.71 | 427.71 | |
平均时间/s | 64.25 | 64.57 | 66.31 | 50.23 | 55.27 | |
Eil76 | 最优解 | 572.93 | 562.16 | 542.41 | 552.64 | 538.00 |
平均值 | 586.33 | 575.05 | 557.42 | 568.51 | 543.79 | |
平均时间/s | 91.23 | 91.56 | 93.24 | 81.41 | 85.16 |
算法 | 参数设置 |
---|---|
SSA | 安全阈值 |
DE | 杂交概率 |
IWO | 初始杂草个数 |
AOA | 归一化上限 |
Tab. 2 Algorithm parameter setting
算法 | 参数设置 |
---|---|
SSA | 安全阈值 |
DE | 杂交概率 |
IWO | 初始杂草个数 |
AOA | 归一化上限 |
TSP测试集 | 评价标准 | SSA | DE | IWO | AOA | ACS | IACS1 | IACS2 | SQACS |
---|---|---|---|---|---|---|---|---|---|
Oliver30 | 最优值 | 423.74 | 423.11 | 431.34 | 424.94 | 453.27 | 452.12 | 434.67 | 420.00 |
平均值 | 427.18 | 435.94 | 449.98 | 429.57 | 475.23 | 468.21 | 440.62 | 421.31 | |
平均时间/s | 29.03 | 28.28 | 29.67 | 27.33 | 29.41 | 27.85 | 28.26 | 26.17 | |
Att48 | 最优值 | 33 842.67 | 33 793.06 | 33 596.81 | 33 982.17 | 34 663.41 | 34 527.23 | 33 742.84 | 33 516.02 |
平均值 | 34 103.32 | 34 183.58 | 33 637.86 | 34 173.61 | 35 721.39 | 35 123.31 | 34 081.82 | 33 583.17 | |
平均时间/s | 51.50 | 49.42 | 50.21 | 52.73 | 56.26 | 50.85 | 51.97 | 49.02 | |
Eil51 | 最优值 | 438.92 | 436.81 | 471.36 | 441.15 | 484.05 | 478.67 | 442.43 | 426.00 |
平均值 | 451.78 | 451.08 | 482.90 | 448.62 | 496.55 | 480.89 | 449.76 | 427.71 | |
平均时间/s | 60.37 | 55.35 | 58.36 | 58.30 | 64.25 | 57.78 | 58.02 | 55.27 | |
Eil76 | 最优值 | 561.39 | 547.13 | 562.20 | 548.08 | 572.93 | 568.37 | 543.00 | 538.00 |
平均值 | 582.04 | 583.11 | 578.37 | 556.73 | 586.33 | 581.81 | 552.45 | 543.79 | |
平均时间/s | 89.30 | 85.28 | 86.23 | 88.46 | 91.23 | 86.54 | 87.15 | 85.16 |
Tab. 3 Comparison of experimental results of eight algorithms
TSP测试集 | 评价标准 | SSA | DE | IWO | AOA | ACS | IACS1 | IACS2 | SQACS |
---|---|---|---|---|---|---|---|---|---|
Oliver30 | 最优值 | 423.74 | 423.11 | 431.34 | 424.94 | 453.27 | 452.12 | 434.67 | 420.00 |
平均值 | 427.18 | 435.94 | 449.98 | 429.57 | 475.23 | 468.21 | 440.62 | 421.31 | |
平均时间/s | 29.03 | 28.28 | 29.67 | 27.33 | 29.41 | 27.85 | 28.26 | 26.17 | |
Att48 | 最优值 | 33 842.67 | 33 793.06 | 33 596.81 | 33 982.17 | 34 663.41 | 34 527.23 | 33 742.84 | 33 516.02 |
平均值 | 34 103.32 | 34 183.58 | 33 637.86 | 34 173.61 | 35 721.39 | 35 123.31 | 34 081.82 | 33 583.17 | |
平均时间/s | 51.50 | 49.42 | 50.21 | 52.73 | 56.26 | 50.85 | 51.97 | 49.02 | |
Eil51 | 最优值 | 438.92 | 436.81 | 471.36 | 441.15 | 484.05 | 478.67 | 442.43 | 426.00 |
平均值 | 451.78 | 451.08 | 482.90 | 448.62 | 496.55 | 480.89 | 449.76 | 427.71 | |
平均时间/s | 60.37 | 55.35 | 58.36 | 58.30 | 64.25 | 57.78 | 58.02 | 55.27 | |
Eil76 | 最优值 | 561.39 | 547.13 | 562.20 | 548.08 | 572.93 | 568.37 | 543.00 | 538.00 |
平均值 | 582.04 | 583.11 | 578.37 | 556.73 | 586.33 | 581.81 | 552.45 | 543.79 | |
平均时间/s | 89.30 | 85.28 | 86.23 | 88.46 | 91.23 | 86.54 | 87.15 | 85.16 |
TSP测试集 | TSPLIB最优解 | 评价标准 | SQACS算法 | 文献[ | 文献[ | 文献[ | 文献[ | 文献[ |
---|---|---|---|---|---|---|---|---|
Oliver30 | 420.00 | 最优解 | 420.00 | — | 420.00 | 420.00 | 423. 74 | 423.74 |
时间/s | 23.15 | — | 23.04 | 20.26 | 30.45 | 23.26 | ||
Att48 | 33 503.00 | 最优解 | 33 516.00 | 36 441.00 | — | 33 522.00 | — | — |
时间/s | 48.21 | 63.40 | — | 49.75 | — | — | ||
Eil51 | 426.00 | 最优解 | 426.00 | 479.00 | 428.87 | 428.00 | 426.00 | 431. 53 |
时间/s | 53.47 | 72.82 | 61.00 | 55.30 | 67.53 | 53.49 | ||
Eil76 | 538.00 | 最优解 | 538.00 | — | 544.37 | 547.00 | 538.00 | — |
时间/s | 81.61 | — | 91.43 | 83.07 | 110.00 | — |
Tab.4 Comparison of calculation results of SQACS algorithm and algorithms in literatures [5-9]
TSP测试集 | TSPLIB最优解 | 评价标准 | SQACS算法 | 文献[ | 文献[ | 文献[ | 文献[ | 文献[ |
---|---|---|---|---|---|---|---|---|
Oliver30 | 420.00 | 最优解 | 420.00 | — | 420.00 | 420.00 | 423. 74 | 423.74 |
时间/s | 23.15 | — | 23.04 | 20.26 | 30.45 | 23.26 | ||
Att48 | 33 503.00 | 最优解 | 33 516.00 | 36 441.00 | — | 33 522.00 | — | — |
时间/s | 48.21 | 63.40 | — | 49.75 | — | — | ||
Eil51 | 426.00 | 最优解 | 426.00 | 479.00 | 428.87 | 428.00 | 426.00 | 431. 53 |
时间/s | 53.47 | 72.82 | 61.00 | 55.30 | 67.53 | 53.49 | ||
Eil76 | 538.00 | 最优解 | 538.00 | — | 544.37 | 547.00 | 538.00 | — |
时间/s | 81.61 | — | 91.43 | 83.07 | 110.00 | — |
1 | WANG K P, HUANG L, ZHOU C G, et al. Particle swarm optimization for traveling salesman problem[C]// Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. Piscataway: IEEE, 2003: 1583-1585. |
2 | 王建忠,唐红. TSP问题的一种快速求解算法[J]. 微电子学与计算机, 2011, 28(1): 7-10. |
WANG J Z, TANG H. A fast algorithm for TSP[J]. Microelectronics and Computer, 2011, 28(1): 7-10. | |
3 | DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91. 10.1287/mnsc.6.1.80 |
4 | 葛海明. 改进的遗传算法求解TSP问题的应用与研究[D]. 赣州:江西理工大学, 2016: 36-42. |
GE H M. Application and research of improved genetic algorithm for TSP problem[D]. Ganzhou: Jiangxi University of Science and Technology, 2016: 36-42. | |
5 | 何庆,吴意乐,徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33(2): 219-225. 10.13195/j.kzyjc.2016.1666 |
HE Q, WU Y L, XU T W. Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision, 2018, 33(2): 219-225. 10.13195/j.kzyjc.2016.1666 | |
6 | 戚远航,蔡延光,黄戈文,等. 带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题[J]. 计算机应用研究, 2021, 38(6): 1642-1647. 10.19734/j.issn.1001-3695.2020.09.0241 |
QI Y H, CAI Y G, HUANG G W, et al. Discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt for traveling salesman problem[J]. Application Research of Computers, 2021, 38(6): 1632-1647. 10.19734/j.issn.1001-3695.2020.09.0241 | |
7 | 汤雅连,杨期江. 求解旅行商问题的蚁群优化算法参数设计[J]. 东莞理工学院学报, 2020, 27(3): 48-54. |
TANG Y L, YANG Q J. Parameter design of ant colony optimization algorithm for traveling salesman problem[J]. Journal of Dongguan Institute of Technology, 2020, 27(3): 48-54. | |
8 | 陈科胜,鲜思东,郭鹏. 求解旅行商问题的自适应升温模拟退火算法[J]. 控制理论与应用, 2021, 38(2): 245-254. 10.7641/CTA.2020.00090 |
CHEN K S, XIAN S D, GUO P. Adaptive temperature rising simulated annealing algorithm for traveling salesman problem[J]. Control Theory and Applications, 2021, 38(2): 245-254. 10.7641/CTA.2020.00090 | |
9 | 唐天兵,朱继生,严毅. 基于量子优化的人工蜂群算法求解旅行商问题[J]. 大众科技, 2020, 22(12): 7-9, 13. 10.3969/j.issn.1008-1151.2020.12.003 |
TANG T B, ZHU J S, YAN Y. An artificial bee colony algorithm based on quantum optimization to solve the traveling salesman problem[J]. Popular Science and Technology, 2020, 22(12): 7-9, 13. 10.3969/j.issn.1008-1151.2020.12.003 | |
10 | JAILLET P. A priori solution of a traveling salesman problem in which a random subset of the customers are visited[J]. Operations Research, 1998, 36(6): 929-936. |
11 | HERNÁNDEZ-PÉREZ H, SALAZAR-GONZÁLEZ J J. The one-commodity pickup-and-delivery traveling salesman problem[M]// JÜNGER M, REINELT G, RINALDI G. Combinatorial Optimization - Eureka, You Shrink!, LNCS 2570. Berlin: Springer, 2003: 89-104. |
12 | NIENDORF M, KABAMBA P T, GIRARD A R. Stability of solutions to classes of traveling salesman problems[J]. IEEE Transactions on Cybernetics, 2016, 46(4): 973-985. 10.1109/tcyb.2015.2418737 |
13 | 卓雪雪,苑红星,朱苍璐,等. 蚁群遗传混合算法在求解旅行商问题上的应用[J]. 价值工程, 2020, 39(2): 188-193. 10.3969/j.issn.1006-4311.2020.02.081 |
ZHUO X X, YUAN H X, ZHU C L, et al. The application of ant colony and genetic hybrid algorithm on TSP[J]. Value Engineering, 2020, 39(2): 188-193. 10.3969/j.issn.1006-4311.2020.02.081 | |
14 | XUE J K, SHEN B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science and Control Engineering, 2020, 8(1): 22-34. 10.1080/21642583.2019.1708830 |
15 | PRICE K, STORN R. Differential evolution: a simple evolution strategy for fast optimization[J]. Dr. Dobb’s Journal, 1997, 22(4): 18-24. |
16 | MEHRABIAN A R, LUCAS C. A novel numerical optimization algorithm inspired from weed colonization[J]. Ecological Informatics, 2006, 1(4): 355-366. 10.1016/j.ecoinf.2006.07.003 |
17 | HASHIM F A, HUSSAIN K, HOUSSEIN E H, et al. Archimedes optimization algorithm: a new metaheuristic algorithm for solving optimization problems[J]. Applied Intelligence, 2021, 51(3): 1531-1551. 10.1007/s10489-020-01893-z |
18 | CIVICIOGLU P. Artificial cooperative search algorithm for numerical optimization problems[J]. Information Sciences, 2013, 229: 58-76. 10.1016/j.ins.2012.11.013 |
19 | TURGUT M S, TURGUT O E. Hybrid artificial cooperative search — crow search algorithm for optimization of a counter flow wet cooling tower[J]. International Journal of Intelligent Systems and Applications in Engineering, 2017, 5(3): 105-116. 10.17678/beujst.63201 |
20 | TSELVARAJU R K, SOMASKANDAN G. Artificial cooperative search algorithm based load frequency controller for multi-area deregulated power system with coordinated controlof TCPS, RFB and AC-DC parallel Tie-lines[J]. ARPN Journal of Engineering and Applied Sciences, 2015, 10(14): 6080-6091. |
21 | 张萧,黄晞,仲伟汉,等. Sigmoid函数及其导函数的FPGA实现[J]. 福建师范大学学报(自然科学版), 2011, 27(2): 62-65. |
ZHANG X, HUANG X, ZHONG W H, et al. Implementation of Sigmoid function and its derivative on FPGA[J]. Journal of Fujian Normal University (Natural Science Edition), 2011, 27(2): 62-65. | |
22 | MAHDAVI S, RAHNAMAYAN S, DEB K. Opposition based learning: a literature review[J]. Swarm and Evolutionary Computation, 2018, 39: 1-23. 10.1016/j.swevo.2017.09.010 |
23 | TURGUT O E. Improved artificial cooperative search algorithm for solving nonconvex economic dispatch problems with valve-point effects[J]. International Journal of Intelligent Systems and Applications in Engineering, 2018, 6(3): 228-241. |
24 | KABOLI S H A, SELVARAJ J, RAHIM N A. Long-term electric energy consumption forecasting via artificial cooperative search algorithm[J]. Energy, 2016, 115(Pt 1): 857-871. 10.1016/j.energy.2016.09.015 |
[1] | Qiangkui LENG, Xuezi SUN, Xiangfu MENG. Oversampling method for imbalanced data based on sample potential and noise evolution [J]. Journal of Computer Applications, 2024, 44(8): 2466-2475. |
[2] | Fengfeng WEI, Weineng CHEN. Distributed data-driven evolutionary computation for multi-constrained optimization [J]. Journal of Computer Applications, 2024, 44(5): 1393-1400. |
[3] | Yawei HUANG, Xuezhong QIAN, Wei SONG. Improved differential evolution algorithm based on dual-archive population size adaptive method [J]. Journal of Computer Applications, 2024, 44(12): 3844-3853. |
[4] | Jian LIN, Jingxuan YE, Wenwen LIU, Xiaowen SHAO. Multimodal differential evolution algorithm for solving capacitated vehicle routing problem [J]. Journal of Computer Applications, 2023, 43(7): 2248-2254. |
[5] | Qianshun GAO, Chunlong FAN, Yanda LI, Yiping TENG. Universal perturbation generation method of neural network based on differential evolution [J]. Journal of Computer Applications, 2023, 43(11): 3436-3442. |
[6] | Qingqing NIE, Dingsheng WAN, Yuelong ZHU, Zhijia LI, Cheng YAO. Hydrological model based on temporal convolutional network [J]. Journal of Computer Applications, 2022, 42(6): 1756-1761. |
[7] | Rongrong DAI, Honghui LI, Xueliang FU. Data center flow scheduling mechanism based on differential evolution and ant colony optimization algorithm [J]. Journal of Computer Applications, 2022, 42(12): 3863-3869. |
[8] | JIA Heming, JIANG Zichao, LI Yao, SUN Kangjian. Simultaneous feature selection optimization based on improved spotted hyena optimizer algorithm [J]. Journal of Computer Applications, 2021, 41(5): 1290-1298. |
[9] | WANG Binrong, TAN Dailun, ZHENG Bochuan. Solving auto part spraying sequence by transforming to traveling salesman problem and genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 881-886. |
[10] | YANG Jidong, SUN Zhaoqi, WANG Feilong. Optimal path control of parallel truss manipulator based on visual grasping [J]. Journal of Computer Applications, 2019, 39(3): 913-917. |
[11] | FENG Shuaidong, CHEN Lijia, LIU Mingguo. Random structure based design method for multiplierless ⅡR digital filters [J]. Journal of Computer Applications, 2018, 38(9): 2621-2625. |
[12] | ZHANG Xin, ZOU Dexuan, SHEN Xin. Hybrid two-norm particle swarm optimization algorithm with crossover term [J]. Journal of Computer Applications, 2018, 38(8): 2148-2156. |
[13] | LIU Bao, DONG Minggang, JING Chao. Multi-objective differential evolution algorithm with improved ranking-based mutation [J]. Journal of Computer Applications, 2018, 38(8): 2157-2163. |
[14] | YUAN Yichuan, YANG Zhou, LUO Tingxing, QIN Jin. Multi-population-based competitive differential evolution algorithm for dynamic optimization problem [J]. Journal of Computer Applications, 2018, 38(5): 1254-1260. |
[15] | LI Longshu, WENG Qingqing. Self-adaptive differential evolution algorithm based on opposition-based learning [J]. Journal of Computer Applications, 2018, 38(2): 399-404. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||