Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism

doi:10.3778/j.issn.1673-9418.2011095

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (6): 1390-1404.DOI: 10.3778/j.issn.1673-9418.2011095

• Artificial Intelligence • Previous Articles Next Articles

Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism

ZHAO Jiabo¹, YOU Xiaoming¹^,⁺(), LIU Sheng²

1. College of Electronic & Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
2. School of Management, Shanghai University of Engineering Science, Shanghai 201620, China

Received:2020-11-30 Revised:2021-03-08 Online:2022-06-01 Published:2021-03-25
About author:ZHAO Jiabo, born in 1997, M.S. candidate. His research interests include intelligent algorithm, path planning of mobile robot and embedded system.
YOU Xiaoming, born in 1963, Ph.D., professor, M.S. supervisor. Her research interests include swarm intelligent systems, distributed parallel processing and evolutionary computing.
LIU Sheng, born in 1966, Ph.D., professor, M.S. supervisor. His research interests include quantum inspired evolutionary computation, distributed parallel processing and evolutionary computing.
Supported by:
National Natural Science Foundation of China(61673258);National Natural Science Foundation of China(61075115)

结合价格波动策略与动态回溯机制的蚁群算法

赵家波¹, 游晓明¹^,⁺(), 刘升²

1. 上海工程技术大学电子电气学院,上海 201620
2. 上海工程技术大学管理学院,上海 201620

通讯作者: + E-mail: yxm6301@163.com
作者简介:赵家波（1997—）,男,河南信阳人,硕士研究生,主要研究方向为智能算法、移动机器人路径规划、嵌入式系统。
游晓明（1963—）,女,江苏兴化人,博士,教授,硕士生导师,主要研究方向为群智能系统、分布式并行处理、进化算法。
刘升（1966—）,男,湖北大冶人,博士,教授,硕士生导师,主要研究方向为量子启发式进化算法、分布式并行处理、进化算法。
基金资助:
国家自然科学基金(61673258);国家自然科学基金(61075115)

Abstract

Abstract:

In order to solve the problems of traditional ant colony algorithm in traveling salesman problem (TSP), such as easy to fall into local optimum and slow convergence speed, this paper proposes an ant colony algorithm based on price fluctuation strategy and dynamic backtracking mechanism. In the price fluctuation strategy, the complete iteration period of ant colony algorithm is classified according to the idea of time series. According to the balance of price fluctuation, the supply-demand relationship that affects the price fluctuation is matched. By analyzing different demands of the algorithm in different classifications, the pheromone volatilization factor is adaptively and dynamically supplied to accelerate the convergence speed of the algorithm and ensure the diversity of the algorithm solution. When the supply relationship of the price fluctuation strategy can not be balanced, the algorithm will face local optimization problem. In this case, the dynamic backtracking mechanism is introduced to trace the path pheromone to the period of significant similarity difference based on the individual similarity of iterative optimal ant, which can effectively jump out of the local optimum while ensuring the convergence speed. Different test sets in TSP are simulated by MATLAB. The results show that the algorithm can effectively improve the quality of solution and balance the relationship between diversity and convergence speed on the basis of ensuring the convergence speed in medium and large scale city set.

Key words: ant colony algorithm, price fluctuation strategy, dynamic backtracking mechanism, individual similarity, traveling salesman problem (TSP)

摘要：

针对传统蚁群算法在旅行商问题（TSP）中易陷入局部最优、收敛速度较慢等问题,提出一种结合价格波动策略与动态回溯机制的蚁群算法。在价格波动策略中,结合时间序列思想将蚁群算法完整迭代周期进行分类,并根据价格波动平衡,将影响价格波动的供求关系进行匹配。通过分析算法在不同分类中的不同需求,对信息素挥发因子进行自适应动态供给,加快算法收敛速度的同时改善解的多样性。当价格波动策略的供给关系无法实现平衡时,算法将面临局部最优问题,此时引入动态回溯机制,以迭代最优蚂蚁的个体相似度作为标准,将路径信息素回溯至相似度差异显著的时期,在保证收敛速度的同时能够有效跳出局部最优。通过MATLAB对TSP中的不同测试集进行仿真,结果表明该算法在保证收敛速度的基础上,有效提高了解的质量,在中大规模城市集上较好地平衡了多样性与收敛速度的关系。

关键词: 蚁群算法, 价格波动策略, 动态回溯机制, 个体相似度, 旅行商问题（TSP）

CLC Number:

TP18

ZHAO Jiabo, YOU Xiaoming, LIU Sheng. Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(6): 1390-1404.

赵家波, 游晓明, 刘升. 结合价格波动策略与动态回溯机制的蚁群算法[J]. 计算机科学与探索, 2022, 16(6): 1390-1404.

Figures/Tables 16

Fig.1 Shortest path convergence graph

Fig.2 Global pheromone volatilization factor

Fig.3 Comparison chart of Fibonacci sequence sampling

Fig.4 Dynamic backtracking diagram

Fig.5 Flow chart of dynamic backtracking mechanism

Table 1 Public parameter setting of PBACO

$α$	$β$	$ξ$	$m$	$q 0$	$T c$
1	4	0.1	50	0.8	2 000

Table 1 Public parameter setting of PBACO

$α$	$β$	$ξ$	$m$	$q 0$	$T c$
1	4	0.1	50	0.8	2 000

Table 2 Node allocation combination table

$ρ$	0.1	0.3	0.5	0.7	0.9
0.1	—	0.1~0.3	0.1~0.5	0.1~0.7	0.1~0.9
0.3	—	—	0.3~0.5	0.3~0.7	0.3~0.9
0.5	—	—	—	0.5~0.7	0.5~0.9
0.7	—	—	—	—	0.7~0.9
0.9	—	—	—	—	—

Table 2 Node allocation combination table

$ρ$	0.1	0.3	0.5	0.7	0.9
0.1	—	0.1~0.3	0.1~0.5	0.1~0.7	0.1~0.9
0.3	—	—	0.3~0.5	0.3~0.7	0.3~0.9
0.5	—	—	—	0.5~0.7	0.5~0.9
0.7	—	—	—	—	0.7~0.9
0.9	—	—	—	—	—

Table 3 Effect of different interval ρ in KroA100 on performance of ant colony algorithm

$ρ$	满足误差率0.5%的比例/%	平均解
0.1~0.3	93.33	21 334
0.1~0.5	73.33	21 355
0.1~0.7	60.00	21 450
0.1~0.9	73.33	21 365
0.3~0.5	66.67	21 392
0.3~0.7	73.33	21 387
0.3~0.9	60.00	21 452
0.5~0.7	46.67	21 497
0.5~0.9	60.00	21 373
0.3	73.33	21 390

Table 3 Effect of different interval ρ in KroA100 on performance of ant colony algorithm

$ρ$	满足误差率0.5%的比例/%	平均解
0.1~0.3	93.33	21 334
0.1~0.5	73.33	21 355
0.1~0.7	60.00	21 450
0.1~0.9	73.33	21 365
0.3~0.5	66.67	21 392
0.3~0.7	73.33	21 387
0.3~0.9	60.00	21 452
0.5~0.7	46.67	21 497
0.5~0.9	60.00	21 373
0.3	73.33	21 390

Table 4 Effect of different interval ρ in KroA200 on performance of ant colony algorithm

$ρ$	最小误差率/%	满足误差率0.5%的比例/%	平均解
0.1~0.3	0.05	40.00	29 542
0.1~0.5	0.05	40.00	29 527
0.1~0.9	0.39	20.00	29 546
0.3~0.7	0.15	13.33	29 588
0.5~0.9	0.54	0	29 737
0.3	0.16	13.33	29 760

Table 4 Effect of different interval ρ in KroA200 on performance of ant colony algorithm

$ρ$	最小误差率/%	满足误差率0.5%的比例/%	平均解
0.1~0.3	0.05	40.00	29 542
0.1~0.5	0.05	40.00	29 527
0.1~0.9	0.39	20.00	29 546
0.3~0.7	0.15	13.33	29 588
0.5~0.9	0.54	0	29 737
0.3	0.16	13.33	29 760

Fig.6 Convergence of each test set

Table 5 Optimization scheme table

方案	优化组合
A	ACS
B	ACS+价格波动策略
C	ACS+价格波动策略+动态回溯机制

Table 6 Performance comparison table of optimization scheme

TSP实例	标准最优解	优化方案	最优解	误差率/%	平均解	迭代次数
		A	538	0	544	1 136
eil76	538	B	538	0	541	776
		C	538	0	540	352
		A	26 664	0.53	27 108	1 434
KroA150	26 524	B	26 657	0.50	26 909	1 212
		C	26 605	0.30	26 840	1 442
		A	3 933	0.43	3 997	1 120
tsp225	3 916	B	3 926	0.25	3 964	1 665
		C	3 923	0.17	3 942	1 151

Table 7 Performance comparison of urban datasets of different sizes

TSP实例	标准最优解	算法	最优解	平均解	误差率/%	迭代次数	TSP实例	标准最优解	算法	最优解	平均解	误差率/%	迭代次数
		ACS	426	428	0	1 092			ACS	26 167	26 397	0.14	1 182
eil51	426	ACS+3opt	426	428	0	1 274	KroB150	26 130	ACS+3opt	26 141	26 515	0.04	1 833
		PBACO	426	427	0	309			PBACO	26 130	26 266	0	499
		ACS	538	544	0	1 528			ACS	29 440	29 646	0.25	1 434
eil76	538	ACS+3opt	538	542	0	1 034	KroA200	29 368	ACS+3opt	29 416	29 778	0.16	1 281
		PBACO	538	540	0	352			PBACO	29 383	29 768	0.05	1 142
		ACS	21 282	21 433	0	1 092			ACS	29 819	30 194	1.29	1 021
KroA100	21 282	ACS+3opt	21 282	21 390	0	1 274	KroB200	29 437	ACS+3opt	29 822	30 083	1.31	1 848
		PBACO	21 282	21 345	0	309			PBACO	29 558	29 743	0.41	440
		ACS	22 246	22 311	0.47	1 528			ACS	3 933	3 997	0.66	1 340
KroB100	22 141	ACS+3opt	22 236	22 311	0.43	1 034	tsp225	3 916	ACS+3opt	3 942	3 993	0.66	1 821
		PBACO	22 141	22 253	0	352			PBACO	3 923	3 942	0.17	1 151
		ACS	6 146	6 220	0.59	1 538			ACS	2 605	2 642	1.00	1 114
ch130	6 110	ACS+3opt	6 145	6 221	0.57	1 017	a280	2 579	ACS+3opt	2 604	2 643	0.93	1 256
		PBACO	6 110	6 170	0	639			PBACO	2 590	2 617	0.42	1 059
		ACS	6 554	6 591	0.39	536			ACS	43 203	43 626	2.79	1 076
ch150	6 528	ACS+3opt	6 544	6 569	0.24	850	lin318	42 029	ACS+3opt	43 166	43 603	2.71	1 599
		PBACO	6 533	6 551	0.07	366			PBACO	42 384	42 432	0.84	1 151
		ACS	26 664	27 108	0.53	1 096
KroA150	26 524	ACS+3opt	26 659	26 825	0.51	1 454
		PBACO	26 605	26 840	0.30	1 442

Fig.7 Optimal path of PBACO algorithm for part of city sets

Fig.8 Convergence for part of city sets

Table 8 Comparison of PBACO with other newly improved algorithms

TSP实例	标准最优解	PBACO	CACS	TREEACS	文献[11]
eil51	426	426	426	426	426
eil76	538	538	538	538	538
KroA100	21 282	21 282	21 282	21 282	21 308
KroB100	22 141	22 141	22 220	22 141	—
ch130	6 110	6 110	6 116	—	—
KroA200	29 368	29 383	29 401	29 413	29 581
KroB200	29 437	29 558	29 695	—	—
lin318	42 029	42 384	42 462	42 399	—

References 19

[1]	DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(1): 29-41.
[2]	DORIGO M, BIRATTARI M, STÜTZLE T. Ant colony opti-mization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39. DOI URL
[3]	李霆, 方志坚, 罗义旺, 等. 基于改进蚁群算法的配电网故障定位研究[J]. 微型电脑应用, 2020, 36(9): 86-88.
	LI T, FANG Z J, LUO Y W, et al. Research on fault location of distribution network based on improved ant colony algo-rithm[J]. Microcomputer Applications, 2020, 36(9): 86-88.
[4]	黄钦龙, 刘忠, 童继进. 改进的蚁群算法求解无人艇编队火力分配问题[J]. 电光与控制, 2020, 27(8): 58-63.
	HUANG Q L, LIU Z, TONG J J. An improved ant colony algorithm for solving firepower allocation problem of USV formation[J]. Electronics Optics & Control, 2020, 27(8): 58-63.
[5]	张文柱, 孔维鹏, 高鹏, 等. 基于改进蚁群算法的无线传感网络路由算法研究[J]. 计算机测量与控制, 2020, 28(7): 274-279.
	ZHANG W Z, KONG W P, GAO P, et al. Research on routing algorithm of wireless sensor network based on im-proved ant colony algorithm[J]. Computer Measurement & Control, 2020, 28(7): 274-279.
[6]	王鹏飞. 群智能优化算法及在流水车间调度问题中的应用研究[D]. 长春: 吉林大学, 2019.
	WANG P F. Swarm intelligence optimization algorithm and its application in flow shop scheduling problem[D]. Chang-chun: Jilin University, 2019.
[7]	DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman pro-blem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66. DOI URL
[8]	STÜTZLE T, HOOS H H. Max-min ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914. DOI URL
[9]	刘新亮. 基于遗传蚁群算法的旅行商问题的研究[D]. 青岛: 山东科技大学, 2017.
	LIU X L. Research on traveling salesman problem based on genetic ant colony algorithm[D]. Qingdao: Shandong University of Science and Technology, 2017.
[10]	何亮亮, 王晓东. 基于初始信息素和二次挥发的改进蚁群算法[J]. 西安工程大学学报, 2018, 32(6): 739-744.
	HE L L, WANG X D. Improved ant colony algorithm based on initial pheromone and secondary volatilization[J]. Journal of Xi’an Polytechnic University, 2018, 32(6): 739-744.
[11]	乔东平, 裴杰, 李浩, 等. 改进蚁群算法求解TSP问题研究[J]. 机械设计与制造, 2019(10): 144-149.
	QIAO D P, PEI J, LI H, et al. Research on improving ant colony algorithm to solve TSP problem[J]. Machinery De-sign & Manufacture, 2019(10): 144-149.
[12]	刘振, 王亚蛟. 一种记忆区间蚁群算法及其仿真分析[J]. 舰船电子工程, 2019, 39(9): 27-31.
	LIU Z, WANG Y J. Memory interval ant colony optimization algorithm and its simulation[J]. Ship Electronic Engineering, 2019, 39(9): 27-31.
[13]	卜新苹, 苏虎, 邹伟, 等. 基于非均匀环境建模与三阶Bezier曲线的平滑路径规划[J]. 自动化学报, 2017, 43(5): 710-724.
	BU X P, SU H, ZOU W, et al. Smooth path planning based on non-uniformly modeling and cubic bezier curves[J]. Acta Automatica Sinica, 2017, 43(5): 710-724.
[14]	吕顺风, 马科. 蚁群-鱼群混合算法在差异工件批调度中的应用[J]. 计算机系统应用, 2018, 27(1): 162-167.
	LV S F, MA K. Application of ant colony hybrid algorithm in batch scheduling of differentiated jobs[J]. Computer Sys-tems & Applications, 2018, 27(1): 162-167.
[15]	OSABA E, DEL J, SADOLLAH A, et al. A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem[J]. Applied Soft Computing, 2018, 71: 277-290. DOI URL
[16]	张松灿, 普杰信, 司彦娜, 等. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
	ZHANG S C, PU J X, SI Y N, et al. Adaptive improved ant colony algorithm based on population similarity and its app-lication[J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[17]	李宪强, 马戎, 张伸, 等. 蚁群算法的改进设计及在航迹规划中的应用[J]. 航空学报, 2020, 41(S2): 210-216.
	LI X Q, MA R, ZHANG S, et al. Improved design of ant colony algorithm and its application in path planning[J]. Acta Aeronautica ET Astronautica Sinica, 2020, 41(S2): 210-216.
[18]	张德惠, 游晓明, 刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891.
	ZHANG D H, YOU X M, LIU S. Dynamic grouping ant colony algorithm combined with cat swarm optimization[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 880-891.
[19]	潘晗, 游晓明, 刘升. 考虑动态导向与邻域交互的双蚁型算法[J]. 计算机科学与探索, 2020, 14(6): 1005-1016.
	PAN H, YOU X M, LIU S. Double-type ant colony algo-rithm considering dynamic guidance and neighborhood interaction[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 1005-1016.

Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Backtracking Mechanism

结合价格波动策略与动态回溯机制的蚁群算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 19

Related Articles 11

Recommended Articles

Metrics

[1]	CHEN Bin, LIU Weiguo. SAC Model Based Improved Genetic Algorithm for Solving TSP [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1680-1693.
[2]	MO Yadong, YOU Xiaoming, LIU Sheng. Dynamic Hierarchical Ant Colony Optimization Based on Reward and Punishment Learning Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(9): 1703-1716.
[3]	LIU Yifan, YOU Xiaoming, LIU Sheng. Ant Colony Optimization Algorithm Based on Dynamic Recombination and Co- operative Communication Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1511-1525.
[4]	MENG Jingwen, YOU Xiaoming, LIU Sheng. Double Ant Colony Algorithm Based on Collaborative Mechanism and Dynamic Regulation Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(11): 2206-2221.
[5]	PAN Han, YOU Xiaoming, LIU Sheng. Double-Type Ant Colony Algorithm Considering Dynamic Guidance and Neighborhood Interaction [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 1005-1016.
[6]	ZHANG Dehui, YOU Xiaoming, LIU Sheng. Dynamic Grouping Ant Colony Algorithm Combined with Cat Swarm Optimization [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(5): 880-891.
[7]	FENG Zhiyu, YOU Xiaoming, LIU Sheng. Hierarchical Progressive Improved Clustering Ant Colony Algorithm for Solving TSP Problems [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(8): 1280-1294.
[8]	YUAN Wanghuang, YOU Xiaoming, LIU Sheng. Dual-Population Ant Colony Algorithm on Dynamic Learning Mechanism [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(7): 1239-1250.
[9]	ZHU Hongwei, YOU Xiaoming, LIU Sheng. Heterogeneous Dual Population Ant Colony Algorithm Based on Cooperative Filtering Strategy [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(10): 1754-1767.
[10]	WANG Chunzi, GUO Wei, ZHANG Bin. Algorithm Design and Simulation of Solving Nonlinear Mixed Integer Programming Problem [J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(9): 854-864.
[11]	CHEN Guangpeng+, YANG Yubin. Memory-type Image Retrieval Method Based on Ant Colony Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2011, 5(1): 32-37.