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

doi:10.3778/j.issn.1673-9418.2011095

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (6): 1390-1404.DOI: 10.3778/j.issn.1673-9418.2011095

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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)

中图分类号:

TP18

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

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.

图/表 16

图1 最短路径收敛图

Fig.1 Shortest path convergence graph

图2 全局信息素挥发因子

Fig.2 Global pheromone volatilization factor

图3 斐波那契数列抽样对比图

Fig.3 Comparison chart of Fibonacci sequence sampling

图4 动态回溯示意图

Fig.4 Dynamic backtracking diagram

图5 动态回溯机制流程图

Fig.5 Flow chart of dynamic backtracking mechanism

表1 PBACO的公共参数设置

Table 1 Public parameter setting of PBACO

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

表1 PBACO的公共参数设置

Table 1 Public parameter setting of PBACO

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

表2 节点分配组合表

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	—	—	—	—	—

表2 节点分配组合表

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	—	—	—	—	—

表3 不同区间 ρ在KroA100对蚁群算法性能的影响

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

表3 不同区间 ρ在KroA100对蚁群算法性能的影响

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

表4 不同区间 ρ在KroA200对蚁群算法性能的影响

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

表4 不同区间 ρ在KroA200对蚁群算法性能的影响

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

图6 各测试集收敛情况

Fig.6 Convergence of each test set

表5 优化方案表

Table 5 Optimization scheme table

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

表6 优化方案性能对比表

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

表7 不同规模城市数据集的性能对比

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

图7 PBACO算法在部分城市集最短路径

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

图8 部分城市集收敛情况

Fig.8 Convergence for part of city sets

表8 PBACO与其他最新改进算法比较

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	—

参考文献 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

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 19

相关文章 14

编辑推荐

Metrics

[1]	陈斌, 刘卫国. 基于SAC模型的改进遗传算法求解TSP问题[J]. 计算机科学与探索, 2021, 15(9): 1680-1693.
[2]	莫亚东, 游晓明, 刘升. 融合奖惩学习策略的动态分级蚁群算法[J]. 计算机科学与探索, 2021, 15(9): 1703-1716.
[3]	刘一凡, 游晓明, 刘升. 基于动态重组和协同交流策略的蚁群优化算法[J]. 计算机科学与探索, 2021, 15(8): 1511-1525.
[4]	孟静雯，游晓明，刘升. 结合协同机制与动态调控策略的双蚁群算法[J]. 计算机科学与探索, 2021, 15(11): 2206-2221.
[5]	殷绍伟, 彭力, 戴菲菲. 融合改进A*蚁群和滚动窗口法的平滑路径规划[J]. 计算机科学与探索, 2021, 15(10): 1969-1979.
[6]	潘晗，游晓明，刘升. 考虑动态导向与邻域交互的双蚁型算法[J]. 计算机科学与探索, 2020, 14(6): 1005-1016.
[7]	张德惠，游晓明，刘升. 融合猫群算法的动态分组蚁群算法[J]. 计算机科学与探索, 2020, 14(5): 880-891.
[8]	冯志雨，游晓明，刘升. 分层递进的改进聚类蚁群算法解决TSP问题[J]. 计算机科学与探索, 2019, 13(8): 1280-1294.
[9]	郭羽含，胡芳霞. 考虑匹配可行性的长期合乘问题建模与求解[J]. 计算机科学与探索, 2019, 13(11): 1894-1910.
[10]	朱宏伟，游晓明，刘升. 协同过滤策略的异构双种群蚁群算法[J]. 计算机科学与探索, 2019, 13(10): 1754-1767.
[11]	任珂欣，王兴伟，马连博，黄敏. 蚁群分工启发的ICN负载均衡机制[J]. 计算机科学与探索, 2018, 12(7): 1109-1116.
[12]	王纯子，郭伟，张斌. 求解非线性混合整数规划的算法设计与仿真[J]. 计算机科学与探索, 2013, 7(9): 854-864.
[13]	陈光鹏+, 杨育彬. 利用蚁群算法的记忆式图像检索方法[J]. 计算机科学与探索, 2011, 5(1): 32-37.
[14]	冀俊忠,刘椿年,黄振. 蚁群算法中信息素增量和扩散模型的研究*[J]. 计算机科学与探索, 2007, 1(1): 87-94.