基于动态熵进化的异构蚁群优化

doi:10.16180/j.cnki.issn1007-7820.2024.10.002

摘要/Abstract

摘要：

针对蚁群算法在求解旅行商问题(Traveling Salesman Problem,TSP)时收敛速度慢、求解精度低等问题,文中提出了一种基于动态熵进化的异构蚁群优化算法。该算法中,由蚁群系统(Ant Colony System,ACS)和最大最小蚂蚁系统(Max-Min Ant System,MMAS)构成异构双种群,实现种群间优势互补。文中提出动态熵进化策略,通过信息熵来动态控制种群间的交流频率,并将两个种群各自最优解的公共路径的信息素进行融合,以调节低熵种群最优路径上的信息素分布,进而有效保留两个种群的历史搜索信息以及加快算法收敛。将低熵种群最优解的非公共路径进行伪初始化,以扩大其在较优解附近的搜索范围,提高解的精度,从而实现两个种群的协同进化。仿真实验结果表明,所提算法在求解大规模旅行商问题时能有效平衡算法多样性与收敛性之间的关系。

关键词: 蚁群优化, 异构种群, 多样性, 动态熵, 协同进化, 信息素融合, 伪初始化, 旅行商问题

Abstract:

In view of the overcome the problem of the slow convergence speed and low precision of ant colony algorithm in solving TSP(Traveling Salesman Problem), a heterogeneous ant optimization based on dynamic entropy evolution is proposed. In this algorithm, a heterogeneous double population is comprised of ACS(Ant Colony System) and MMAS(Max-Min Ant System),which is helpful to promote the complementary advantages between the populations. And the dynamic entropy evolution strategy is introduced to dynamically control the communication frequency between the populations by information entropy. The pheromones of the two populations' optimal common paths are fused to adjust the distribution of pheromones on the optimal paths of the low entropy populations, thereby effectively preserving the historical search information of the two populations and accelerating the convergence of the algorithm.The non-common path of the optimal solution of low entropy population is pseudo-initialized to expand its search range near the optimal solution and improve the accuracy of the solution, so as to realize the co-evolution of two populations.Simulation results show that the proposed algorithm can effectively balance the relationship between algorithm diversity and convergence when solving large-scale traveling salesman problems.

Key words: ant colony optimization, heterogeneous colony, diversity, dynamic entropy, coevolution, pheromone fusion, pseudo initialization, traveling salesman problem

中图分类号:

TP18

王世科, 游晓明, 尹玲, 刘升. 基于动态熵进化的异构蚁群优化[J]. 电子科技, 2024, 37(10): 6-14.

WANG Shike, YOU Xiaoming, YIN Ling, LIU Sheng. Heterogeneous Ant Optimization Based on Dynamic Entropy Evolution[J]. Electronic Science and Technology, 2024, 37(10): 6-14.

图/表 9

表1

表2

图1

图2

图3

图4

表3

表4

参考文献 28

[1]	朱宏伟, 张海南. 基于拥挤度因子的动态信息素更新策略蚁群算法[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.
[2]	游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J]. 控制与决策, 2017, 32(3):552-556.
	You Xiaoming, Liu Sheng, Lü Jinqiu. Ant colony algori-thm based on dynamic search strategy and its application on path planning of robot[J]. Control and Decision, 2017, 32(3):552-556.
[3]	孙鹏娜, 张忠民. 基于蚁群算法的无人船平滑路径规划[J]. 电子科技, 2023, 36(3):14-20.
	Sun Pengna, Zhang Zhongmin. Path planning and smoothing for unmanned surface vehicle based on improved ant colony optimization[J]. Electronic Science and Technology, 2023, 36(3):14-20.
[4]	Dorigo M, Stützle T. Ant colony optimization[M]. London: The MIT Press,2004:65-66
[5]	Zheng R Z, Zhang Y, Yang K. A transfer learning-based particle swarm optimization algorithm for travelling salesman problem[J]. Journal of Computational Design and Engineering, 2022, 9(3):933-948.
[6]	Ghorab A. An improved immune genetic algorithm and its application on TSP[C]. Deir El-Balah: International Conference on Promising Electronic Technologies,2021:84-88.
[7]	Shirdel G H, Abdolhosseinzadeh M. A simulated annealing heuristic for the online symmetric traveling salesman problem[J]. Journal of Information and Optimization Sciences, 2018, 39(6):1283-1296.
[8]	Dorigo M, Gambardella L. Ant colony system:A cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53-66.
[9]	Guo X B, Liu Y P. Intelligent traffic cloud computing system based on ant colony algorithm[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(4):4947-4958.
[10]	Martin E, Cervantes A, Saez Y, et al. IACS-HCSP:Impr-oved ant colony optimization for large-scale home care scheduling problems[J]. Expert Systems with Applications, 2020, 14(2):112994-113005.
[11]	Dorigo M. The any system optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems,Man and Cybernetics-Part B, 1996, 26(1):1-13.
[12]	Stützle T, Hoos H. MAX-MIN ant system[J]. Future G-eneration Computer Systems, 2000, 16(8):889-914.
[13]	Chitty D. An ant colony optimisation inspired crossover operator for permutation type problems[C]. Kraków: IEEE Congress on Evolutionary Computation,2021:57-64.
[14]	张毅, 权浩, 文家富. 基于独狼蚁群混合算法的移动机器人路径规划[J]. 华中科技大学学报(自然科学版), 2020, 48(1):127-132.
	Zhang Yi, Quan Hao, Wen Jiafu. Mobile robot path pla-nning based on the wolf ant colony hybrid algorithm[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2020, 48(1):127-132.
[15]	胡章芳, 罗磊, 吕元元, 等. 基于势场导向的对数蚁群算法的移动机器人路径规划[J]. 重庆邮电大学学报(自然科学版), 2021, 33(3):498-506.
	Hu Zhangfang, Luo Lei, Lü Yuanyuan, et al. Path planning of mobile robot based on potential field oriented logarithmic ant colony algorithm[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2021, 33(3):498-506.
[16]	许凯波, 鲁海燕, 程毕芸. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6):1686-1691. doi: 10.11772/j.issn.1001-9081.2017.06.1686
	Xu Kaibo, Lu Haiyan, Cheng Biyun. Ant colony optimi-zation algorithm based on improved pheromones double updating and local optimization for solving TSP[J]. Journal of Computer Applications, 2017, 37(6):1686-1691. doi: 10.11772/j.issn.1001-9081.2017.06.1686
[17]	Liu Y H, Cao B Y, Li H H. Improving ant colony optimization algorithm with epsilon greedy and Levy flight[J]. Complex & Intelligent Systems, 2021, 7(4):1711-1722.
[18]	Yu J, You X M, Liu S. Ant colony algorithm based on magnetic neighborhood and filtering recommendation[J]. Soft Computing, 2021, 25(13):8035-8050.
[19]	卜冠南, 刘建华, 姜磊, 等. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6):67-73. doi: 10.3778/j.issn.1002-8331.2003-0296
	Bu Guannan, Liu Jianhua, Jiang Lei, et al. Ant colony algorithm with adaptive grouping[J]. Computer Engineering and Applications, 2021, 57(6):67-73. doi: 10.3778/j.issn.1002-8331.2003-0296
[20]	Zheng Y F, Xu J, Chen H Z. TOPSIS-based entropy measure for intuitionistic trapezoidal fuzzy sets and application to multi-attribute decision making[J]. Mathematical Biosciences and Engineering, 2020, 17(5):5604-5617. doi: 10.3934/mbe.2020301 pmid: 33120568
[21]	李华, 郭皓杰, 谢辉, 等. 基于信息熵的森林火灾应急指挥信息传递分析[J]. 中国安全科学学报, 2023, 33(1):80-87. doi: 10.16265/j.cnki.issn1003-3033.2023.01.2359
	Li Hua, Guo Haojie, Xie Hui, et al. Information transmi-ssion analysis of forest fire emergency command based on information entropy[J]. China Safety Science Journal, 2023, 33(1):80-87. doi: 10.16265/j.cnki.issn1003-3033.2023.01.2359
[22]	Chen Y J, Liu J J, Lan L M, et al. A fast online planning under partial observability using information entropy rewards[J]. Transactions on Industrial Information, 2023, 19(2):1-11.
[23]	张佩, 游晓明, 刘升. 融合动态层次聚类和邻域区间重组的蚁群算法[J]. 计算机应用研究, 2023, 40(6):1666-1672.
	Zhang Pei, You Xiaoming, Liu Sheng. Ant colony algorithm based on dynamic hierarchical clustering and neighborhood recombination[J]. Application Research of Cmputers, 2023, 40(6):1666-1672.
[24]	Karakostas P, Sifaleras A. A double-adaptive general variable neighborhood search algorithm for the solution of the traveling salesman problem[J]. Applied Soft Computing, 2022, 12(1):108746-108752.
[25]	Zhao J B, You X M, Duan Q Q, et al. Multiple ant colony algorithm combining community relationship network[J]. Arabian Journal for Science and Engineering, 2022, 47(8):10531-10546.
[26]	Rahman M, Parvez H. Repetitive nearest neighbor based simulated annealing search optimization algorithm fortraveling salesman problem[J]. OALib, 2021, 8(6):1-17.
[27]	Akhand M A H, Ayon S I, Shahriyar S A, et al. Discrete spider monkey optimization for travelling salesman problem[J]. Applied Soft Computing Journal, 2020, 86(2):105887-105893.
[28]	Wang Y. Hybrid max-min ant system with four vertices and three lines inequality for traveling salesman problem[J]. Soft Computing, 2015, 19(3):585-596.

	α	β	ξ	ρ	q₀	m	N_max
ACS	1	4	0.1	0.3	0.8	20	2 000
MMAS	1	4	0.1	—	—	20	2 000

S/N	城市集	规模	标准最优解	算法	最优解	最差解	平均解	Error/%	Std
1	eil51	51	426	ACS	426	435	429.87	0.00	2.85
				MMAS	426	428	427.53	0.00	0.62
				EHACO	426	428	407.07	0.00	0.68
2	kroA100	100	21 282	ACS	21 282	22 206	21 521.40	0.00	226.21
				MMAS	21 282	21 557	21 360.47	0.00	65.14
				EHACO	21 282	21 369	21 303.27	0.00	26.28
3	kroB100	100	22 141	ACS	22 179	22 901	22 372.87	0.17	162.77
				MMAS	22 193	22 365	22 296.27	0.23	47.57
				EHACO	22 141	22 365	22 269.53	0.00	61.38
4	eil101	101	629	ACS	635	663	644.93	0.95	7.24
				MMAS	631	657	643.00	0.32	7.84
				EHACO	629	645	634.33	0.00	4.45
5	kroA150	150	26 524	ACS	26 801	27 603	27 181.20	1.04	206.95
				MMAS	26 758	27 495	26 998.67	0.88	199.01
				EHACO	26 686	27 111	26 856.27	0.61	126.30
6	kroB150	150	26 130	ACS	26 290	27 221	26 593.33	0.61	267.29
				MMAS	26 152	26 764	26 459.53	0.08	176.21
				EHACO	26 130	26 653	26 317.73	0.00	147.39
7	kroA200	200	29 368	ACS	29 604	30 306	29 946.87	0.80	209.62
				MMAS	29 421	29 963	29 649.47	0.18	137.24
				EHACO	29 387	29 596	29 491.73	0.06	58.78
8	kroB200	200	29 437	ACS	29 911	30 883	30 242.07	1.61	263.76
				MMAS	29 763	30 246	29 965.00	1.11	140.27
				EHACO	29 591	30 149	29 887.40	0.52	136.86
9	pr264	264	49 135	ACS	49 441	51 698	50 258.00	0.62	740.55
				MMAS	49 718	53 353	51 343.53	1.19	1 074.23
				EHACO	49 135	50 531	49 419.33	0.00	465.96
10	lin318	318	42 029	ACS	43 089	45 261	44 285.13	2.52	540.06
				MMAS	42 726	44 084	43 474.80	1.66	330.99
				EHACO	42 153	43 543	42 766.53	0.30	326.74
11	fl417	417	11 861	ACS	12 102	12 610	12 297.07	2.03	154.16
				MMAS	12 038	12 429	12 236.67	1.49	103.91
				EHACO	11 956	12 116	12 025.87	0.80	49.06
12	p654	654	34 643	ACS	36 118	39 664	37 712.40	4.26	1 011.18
				MMAS	35 922	38 970	26 868.33	3.67	841.20
				EHACO	34 843	35 281	35 081.87	0.58	123.70

城市集	标准最优解	HEACO	HNACO (2023)	DA-GVNS (2022)	CACO (2022)	DSMO (2020)
		最优解	最优解	最优解	最优解	最优解
eil51	426	426	426	426	426	428.86
kroA100	21 282	21 282	21 282	21 282	21 282	21 298.21
kroB100	22 141	22 141	22 141	22 165	22 141	22 308.00
eil101	629	629	629	633	-	648.66
kroA150	26 524	26 686	26 621	26 817	26 583	27 591.44
kroB150	26 130	26 130	22 132	2 626 256	-	26 601.94
kroA200	29 368	29 387	29 401	29 807	29 368	30 481.35
kroB200	29 437	29 591	29 508	30 015	29 524	30 716.50

		pr264	lin318	fl417	p654
HEACO	最优解	49 135.00	42 153.00	11 956.00	34 843.00
HNACO(2023)	最优解	-	42 513.00	11 957.00	35 014.00
DA-GVNS(2022)	最优解	49 880.00	43 201.00	12 019.00	-
CACO(2022)	最优解	-	42 365.00	11 950.00	34 932.00
RNN-SA(2021)	最优解	49 197.32	42 862.50	-	-
DSMO(2020)	最优解	-	44 118.66	12 218.98	-
HMMA(2015)	最优解	50 554.58	45 349.62	12 542.84	37 043.68