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

doi:10.16180/j.cnki.issn1007-7820.2020.08.010

Abstract

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

CLC Number:

TP18

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.

Figures/Tables 4

Table 1

Table 2

Figure 1.

Figure 2.

References 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

Ant Colony Optimization for Dynamic Pheromone Update Strategy Based on Congestion Factor

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 17

Related Articles 15

Metrics

Comments

Recommended 10

[1]	SUN Shuai,LIU Zilong,WAN Wei. Improvement of RLS Algorithm Based on Regularization Model [J]. Electronic Science and Technology, 2021, 34(11): 26-30.
[2]	ZHAO Shiyan, XIE Zidian, DING Kangkang, CUI Hanqing. Particle Swarm Optimization BP-PID of Rotor Variable Frequency Speed in Mine Hoisting System [J]. Electronic Science and Technology, 2021, 34(1): 43-49.
[3]	DING Jiahui,ZHANG Zhaojun. Adaptive Genetic Algorithm Based on Individual Ordering [J]. Electronic Science and Technology, 2020, 33(3): 6-11.
[4]	YANG Yu,ZENG Guohui,HUANG Bo. A Transformer Fault Diagnosis Method Integrating Artificial Fish Swarm Algorithm with Least Square Support Vector Machine [J]. Electronic Science and Technology, 2020, 33(11): 36-40.
[5]	HU Huimian. An Improved Path Planning Algorithm With Variable Probability Bidirectional RRT [J]. Electronic Science and Technology, 2019, 32(6): 16-21.
[6]	CHEN Xiaoguang,WU Zhilu,JIANG Xu,ZHANG Xiaojun. Artificial Fish Swarm Algorithm Based on Multiuser Detection for Data Relay Satellite System [J]. Electronic Science and Technology, 2019, 32(10): 1-6.
[7]	LI Yi-Hong, QIU Gui. The Particle Swarm Optimization Algorithm Merged with Ant Colony Optimization Algorithm of Fire Rescue Way Research [J]. , 2018, 31(1): 58-.
[8]	LI Yulin，XIANG Yu，WU Song. Noise Source Identification Based on Acoustic Holography and DSP Implementation [J]. , 2017, 30(4): 27-.
[9]	ZHAO Huiguang 1，HE Shengxue 1，HUANG Qing 2，XIANG Lejia 3. Study on the Strategy of Bus Evacuation Based on Improved ant Colony Optimization [J]. , 2017, 30(4): 68-.
[10]	ZHAO Yuelu,JI Lei. Research on Narrowband Interference Suppression Algorithm for Satellite Navigation Receiver [J]. , 2016, 29(3): 53-.
[11]	YANG Lei, ZHU Lingkang, GAO Guowei, XU Kai, YANG Han, JIN Hao. Worm Gear Fault Identification Based on FSAACO Mixed Improved Algorithm [J]. , 2016, 29(11): 133-.
[12]	SU Yuxiao. Application of BP Neural Network Based on Genetic Algorithm in Multi-objective Optimization [J]. , 2015, 28(6): 51-.
[13]	XUE Haiwei,FENG Dazheng,LI Jin. Study of the Fast Semi-Blind Equalization Algorithm for the QAM Communication System [J]. , 2015, 28(4): 4-.
[14]	FANG Xuan,ZHONG Bocheng. Four-rotor Unmanned Aerial Vehicles Control System Based on PID Controller of Artificial Fish Swarm Algorithm [J]. , 2015, 28(12): 52-.
[15]	LI Hanyi,CHEN Jiaqi. Research on Task Scheduling Algorithm In Cloud Computing Environment [J]. , 2015, 28(11): 43-.