基于拥挤度因子的动态信息素更新策略蚁群算法

doi:10.16180/j.cnki.issn1007-7820.2020.08.010

摘要/Abstract

摘要：

针对蚁群算法易陷入局部最优、收敛速度慢的问题,文中提出了一种基于拥挤度因子的动态信息素更新策略的蚁群算法(CFACS)。引入鱼群算法中拥挤度的思想,扩大种群中蚂蚁分布范围,使其探索更大的解空间,提高算法全局搜索能力;采用动态信息素更新策略,在每一次迭代中,自适应调整当前最优路径所释放的信息素浓度,保证蚁群前期的多样性,同时保证算法在后期的收敛性。求解TSP问题的仿真实验表明,改进算法求得解的质量和求解的收敛速度都明显优于传统蚁群算法,较好地平衡了种群多样性与收敛速度之间的矛盾。

关键词: 拥挤度因子, 动态信息素更新策略, 旅行商问题, 蚁群算法, 鱼群算法, 收敛性

Abstract:

Aiming at the problem that the ant colony algorithm is easy to fall into local optimum and the convergence speed is slow, this paper proposed an ant colony optimization based on CFACS. The idea of crowding degree in the Fish Swarm algorithm was introduced to expand the distribution range of ants in the population, which made the ants explored more solution space and improve the global search ability of the algorithm. The dynamic pheromone update strategy was adopted to adaptively adjust the pheromone concentration released by the current optimal path in each iteration to ensure the diversity of the ant colony in the early stage and to ensure the convergence of the algorithm in the later stage. The simulation experiments for solving the TSP problem showed that the improved algorithm could obtain the solution quality and the convergence speed of the solution were better than the traditional ant colony algorithm, which balanced the contradiction between population diversity and convergence speed.

Key words: congestion factor, dynamic pheromone update strategy, traveling salesman problem, ant colony optimization, fish swarm algorithm, convergence

中图分类号:

TP18

朱宏伟,张海南. 基于拥挤度因子的动态信息素更新策略蚁群算法[J]. 电子科技, 2020, 33(8): 59-64.

ZHU Hongwei,ZHANG Hainan. Ant Colony Optimization for Dynamic Pheromone Update Strategy Based on Congestion Factor[J]. Electronic Science and Technology, 2020, 33(8): 59-64.

图/表 4

表1

表2

图1

图2

参考文献 17

[1]	张驰, 汪海涛, 姜瑛, 等. 改进模拟退火算法在TSP中的应用[J]. 软件, 2017,38(7):1-5.
	Zhang Chi, Wang Haitao, Jiang Ying, et al. Application of improved simulated annealing algorithm in TSP[J]. Software, 2017,38(7):1-5.
[2]	文艺, 潘大志. 用于求解TSP问题的改进遗传算法[J]. 计算机科学, 2016,43(s1):90-92.
	Wen Yi, Pan Dazhi. Improved genetic algorithm for solving TSP problems[J]. Computer Science, 2016,43(s1):90-92.
[3]	王鑫, 彭绍雄. 基于改进的禁忌搜索算法求解旅行商问题[C]. 北京:中国指挥控制大会, 2015.
	Wang Xin, Peng Shaoxiong. Solving traveling salesman problem based on improved tabu search algorithm[C]. Beijing:China Command and Control Conference, 2015.
[4]	赵惠光, 何胜学, 黄清, 等. 基于改进蚁群算法的公交疏散策略研究[J]. 电子科技, 2017,30(4):68-71,75.
	Zhao Huiguang, He Shengxue, Huang Qing, et al. Research on bus evacuation strategy based on improved ant colony algorithm[J]. Electronic Science and Technology, 2017,30(4):68-71,75.
[5]	Dorigo M, Birattari M, Stutzle T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2007,1(4):28-39. doi: 10.1109/MCI.2006.329691
[6]	Dorigo M, Maniezzo V, Colorni A. Ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics,Part B(Cybernetics), 1996,26(1):29-41.
[7]	张家善, 王志宏. 基于信息素的改进蚁群算法及其在TSP中的应用[J]. 数学的实践与认识, 2013,43(22):157-161.
	Zhang Jiashan, Wang Zhihong. Improved ant colony algorithm based on pheromone and its application in TSP[J]. Mathematics in Practice and Theory, 2013,43(22):157-161.
[8]	王娟, 王建. 一种求解TSP问题的改进蚁群算法[J]. 计算机技术与发展, 2008,18(12):50-52.
	Wang Juan, Wang Jian. An improved ant colony algorithm for solving TSP problems[J]. Journal of Computer Technology and Development, 2008,18(12):50-52.
[9]	张于贤, 丁修坤, 薛殿春, 等. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学, 2017,39(8):1576-1580.
	Zhang Yuxian, Ding Xiukun, Xue Dianchun, et al. Improved ant colony algorithm for solving traveling salesman problem[J]. Computer Engineering & Science, 2017,39(8):1576-1580.
[10]	Mahi M, Baykan Ö K, Kodaz H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem[J]. Applied Soft Computing, 2015,30(7):484-490. doi: 10.1016/j.asoc.2015.01.068
[11]	张慕雪, 张达敏, 杨菊蜻, 等. 基于禁忌搜索的蚁群优化算法[J]. 通信技术, 2017,50(8):1658-1663.
	Zhang Muxue, Zhang Damin, Yang Juqing, et al. Ant colony optimization algorithm based on tabu search[J]. Communications Technology, 2017,50(8):1658-1663.
[12]	Gomez Cabrero D, Ranasinghe D N. Fine-tuning the ant colony system algorithm through particle swarm optimization[J]. arXiv Preprint arXiv, 2018,18(3):8353-8366.
[13]	李晓磊, 邵之江, 钱积新. 一种基于动物自治体的寻优模式:鱼群算法[J]. 系统工程理论与实践, 2002,22(11):32-38.
	Li Xiaolei, Shao Zhijiang, Qian Jixin. An optimization model based on animals’ autonomy: fish school algorithm[J]. Systems Engineering Theory & Practice, 2002,22(11):32-38.
[14]	Siemiński A. TSP/ACO parameter optimization[J]. Information Systems Architecture and Technology, 2011(5):151-161.
[15]	高国磊, 李英娜, 段效琛, 等. 基于ACO优化LS-SVM的变压器故障诊断[J]. 电子科技, 2018,31(6):59-62,74.
	Gao Guolei, Li Yingna, Duan Xiaochen, et al. Transformer fault diagnosis based on ACO optimized LS-SVM[J]. Electronic Science and Technology, 2018,31(6):59-62,74.
[16]	Deif D, Gadallah Y. An ant colony optimization approach for the deployment of reliable wireless sensor networks[J]. IEEE Access, 2017(3):1-16.
[17]	Xu M, You X, Liu S. A novel heuristic communication heterogeneous dual population ant colony optimization algorithm[J]. IEEE Access, 2017(9):9-15.

算法参数	CFACS	ACS	MMAS
α	1.0	0.5	1.0
β	2.0	2.0	2.0
ρ	0.1	0.1	0.2
q	0.8	0.8	0.7
m	50	20	n

TSP最优解	算法	最优解	均值	偏差/%	标准差	迭代次数	N
Eil51 (426)	ACS MMAS CFACS	439 429 426	445.00 435.60 427.75	3.05 0.70 0.00	7.82 9.83 0.54	190 453 200	0 0 8
St70 (675)	ACS MMAS CFACS	678 678 675	684.52 692.10 683.00	0.44 1.04 0.00	2.64 3.28 1.45	634 710 532	0 0 5
Eil76 (538)	ACS MMAS CFACS	540 547 538	544.50 548.50 540.50	0.37 1.67 0.00	4.12 2.85 0.68	602 500 450	0 0 3
Berlin52 (7542)	ACS MMAS CFACS	7 542 7 542 7 542	7 601.20 7 591.70 7 565.20	0.00 0.00 0.00	25.30 13.45 2.86	105 170 26	3 2 9
KroA100 (21282)	ACS MMAS CFACS	22 105 21 460 21 282	22 407.86 21 994.00 21 304.05	3.87 0.84 0.00	35.42 101.54 18.56	1 056 801 701	0 0 3
KroB100 (22141)	ACS MMAS CFACS	22 304 22 356 22 184	22 358.00 22 651.50 22 304.50	0.77 0.97 0.19	19.74 32.43 36.50	1 638 1 896 1 385	0 0 0
Pr107 (44303)	ACS MMAS CFACS	44 610 44 669 44 303	44 694.50 44 784.00 44 601.00	0.69 0.83 0.00	64.77 104.90 133.27	1 150 1 590 1 425	0 0 5
Ch130 (6110)	ACS MMAS CFACS	6 286 6 236 6 191	6 306.00 6 259.77 6 199.00	2.88 2.06 1.33	23.09 13.72 26.30	1 730 1 582 1 226	0 0 0
KroA200 (29368)	ACS MMAS CFACS	30 161 29 594 29 477	30 205.33 30 015.40 29 658.20	2.70 0.77 0.37	177.45 126.74 98.12	1 226 2 929 1 348	0 0 0