结合竞争交互策略和淘汰重组机制的异构多蚁群算法

doi:10.16182/j.issn1004731x.joss.22-1009

摘要/Abstract

摘要：

针对传统的蚁群算法在解决旅行商问题时(traveling salesman problem, TSP)存在着收敛速度慢、容易陷入局部最优等问题，提出了一种结合竞争交互策略和淘汰重组机制的异构多蚁群算法。建立一个异构多种群系统，算法采用竞争交互策略，根据不同时期各种群的汉明距离来自适应的调节交互周期；并利用竞争系数来差异化匹配交互对象，经过匹配后的交互对象之间通过最优解和信息素矩阵进行交互，通过该机制实现了算法收敛速度和多样性的平衡。算法采用了淘汰重组机制，会定期对寻优能力差的种群进行淘汰与重组，以加快算法的求解精度。采用多组不同规模的TSP算例进行仿真实验，结果表明，该算法在提高求解精度和收敛速度方面表现更优。

关键词: 蚁群算法, 异构多种群, 竞争交互, 淘汰重组, 旅行商问题

Abstract:

The traditional ant colony algorithm has many problems in convergence and diversity when solving the traveling salesman problem (TSP). Therefore, this paper proposes a heterogeneous multi-ant colony algorithm that combines the competitive interaction strategy and the eliminating-reconstructing mechanism (CEACO) to overcome these shortcomings. Firstly, the algorithm uses a competitive interaction strategy, which adjusts the interaction period adaptively according to the Hamming distance of different groups in different periods. Competition coefficients are adopted to differentiate matching interaction objects for interaction. The matched objects interact with each other through the optimal solution and pheromone matrix. This mechanism achieves a balance between algorithm convergence speed and diversity. Secondly, the algorithm uses the eliminating-reconstructing mechanism, which periodically eliminates and reconstructs the poor-searching populations to improve the solution accuracy of the algorithm.Finally, several groups of simulation experiments prove that the algorithm outperforms other methods in improving the solution accuracy and convergence speed.

Key words: ant colony optimization(ACO), heterogeneous multiple population, competitive interaction, eliminating-reconstructing, traveling salesman problem

中图分类号:

TP18

冯晨,游晓明,刘升 . 结合竞争交互策略和淘汰重组机制的异构多蚁群算法[J]. 系统仿真学报, 2024, 36(1): 232-248.

Feng Chen,You Xiaoming,Liu Sheng . Heterogeneous Multi-ant Colony Algorithm Combining Competitive Interaction Strategy and Eliminating-reconstructing Mechanism[J]. Journal of System Simulation, 2024, 36(1): 232-248.

图/表 19

图1

图2

图3

表1

各步骤的时间复杂度

序号	内容	时间复杂度
1	初始化参数	$O (n 2 + m)$
2	蚂蚁构建路径	$O (m · n)$
3	信息素更新	$O (n 2)$
4	计算汉明距离	$O (n)$
5	计算竞争系数	$O (m · n)$
6	执行竞争交互策略	$O (n 2)$
7	执行淘汰重组操作	$O (n 2)$
8	输出最优路径	$O (1)$

表1

表2

CEACO算法中的基础参数设置

参数	ACS参数值	MMAS参数值
$α$	1	1
$β$	4	4
$ρ$	0.3	0.2
$ξ$	0.1
$q 0$	0.8
$T m a x$	2 000	2 000
$m$	30	30
$D$	50	50
$H$	2	2

表2

表3

图4

图5

图6

表4

表5

图7

表6

图8

图9

图10

图11

图12

表7

参考文献 19

1	Dorigo M, Stützle Thomas. Ant Colony Optimization[M]. Cambridge: MIT Press, 2004.
2	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.
3	Rodammer F A, White K P. A Recent Survey of Production Scheduling[J]. IEEE Transactions on Systems, Man and Cybernetics, 1988, 18(6): 841-851.
4	Admane L, Benatchba K, Koudil M, et al. Using Ant Colonies to Solve Data-mining Problems[C]//2004 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ, USA: IEEE, 2004: 3151-3157.
5	Chu C H, Gu Junhua, Hou Xiangdan, et al. A Heuristic Ant Algorithm for Solving QoS Multicast Routing Problem[C]//Proceedings of the 2002 Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2002: 1630-1635.
6	Dorigo M, Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
7	Stützle Thomas, Hoos Holger H. MAX-MIN Ant System[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.
8	Zhao Haitong, Zhang Changsheng. An Ant Colony Optimization Algorithm with Evolutionary Experience-guided Pheromone Updating Strategies for Multi-objective Optimization[J]. Expert Systems with Applications, 2022, 201: 117151.
9	Tuani A F, Keedwell E, Collett M. Heterogenous Adaptive Ant Colony Optimization with 3-opt Local Search for the Travelling Salesman Problem[J]. Applied Soft Computing, 2020, 97, Part B: 106720.
10	Sangeetha V, Krishankumar R, Ravichandran K S, et al. Energy-efficient Green Ant Colony Optimization for Path Planning in Dynamic 3D Environments[J]. Soft Computing, 2021, 25(6): 4749-4769.
11	王铁, 胡泓. 基于K-means信息挥发速率动态调整的改进蚁群算法[J]. 机械与电子, 2020, 38(2): 25-29.
	Wang Tie, Hu Hong. An Improved Ant Colony Algorithm Based on K-means and Dynamic Volatility Rate Adjustment Strategy[J]. Machinery & Electronics, 2020, 38(2): 25-29.
12	Gambardella L M, Taillard E D, Agazzi G. A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows[EB/OL]. (2016-04-28) [2022-08-17]. .
13	Wang Yuan, Wang Ling, Peng Zhiping, et al. A Multi Ant System Based Hybrid Heuristic Algorithm for Vehicle Routing Problem with Service Time Customization[J]. Swarm and Evolutionary Computation, 2019, 50: 100563.
14	刘双双, 黄宜庆. 多策略蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2022, 58(6): 278-286.
	Liu Shuangshuang, Huang Yiqing. Application of Multi-strategy Ant Colony Algorithm in Robot Path Planning[J]. Computer Engineering and Applications, 2022, 58(6): 278-286.
15	Zhang Dehui, You Xiaoming, Liu Sheng, et al. Multi-colony Ant Colony Optimization Based on Generalized Jaccard Similarity Recommendation Strategy[J]. IEEE Access, 2019, 7: 157303-157317.
16	张鹏, 薛宏全, 原欣伟. 基于相似度的自适应异类多种群蚁群算法[J]. 计算机工程与应用, 2014, 50(19): 37-41.
	Zhang Peng, Xue Hongquan, Yuan Xinwei. Adaptive Heterogeneous Multiple Ant Colonies Algorithm Based on Similarity[J]. Computer Engineering and Applications, 2014, 50(19): 37-41.
17	陈斌, 刘卫国. 基于SAC模型的改进遗传算法求解TSP问题[J]. 计算机科学与探索, 2021, 15(9): 1680-1693.
	Chen Bin, Liu Weiguo. SAC Model Based Improved Genetic Algorithm for Solving TSP[J]. Journal of Frontiers of Computer Science & Technology, 2021, 15(9): 1680-1693.
18	Wang Yong, Han Zunpu. Ant Colony Optimization for Traveling Salesman Problem Based on Parameters Optimization[J]. Applied Soft Computing, 2021, 107: 107439.
19	赵家波, 游晓明, 刘升. 结合价格波动策略与动态回溯机制的蚁群算法[J]. 计算机科学与探索, 2022, 16(6): 1390-1404.
	Zhao Jiabo, You Xiaoming, Liu Sheng. Ant Colony Algorithm Based on Price Fluctuation Strategy and Dynamic Back-tracking Mechanism[J]. Journal of Frontiers of Computer Science & Technology, 2022, 16(6): 1390-1404.

种群数量	ACS与MMAS种群不同比例的最优解
种群数量	1:1	1:2	2:1
2	29 583
4	29 459
6	29 482	29 631	29 529
9		29 660	29 586

方案	策略组合
A	多种群
B	多种群+竞争交互机制
C	多种群+竞争交互机制+淘汰重组机制

TSP	标准最优解	算法模型	最优解	最差解	平均解	误差率	迭代次数
eil51	426	A	426	428	426.8	0	220
		B	426	427	426.5	0	125
		C	426	427	426.3	0	60
eil76	538	A	538	543	539.6	0	642
		B	538	543	538.7	0	519
		C	538	542	539.2	0	210
kroA100	21 282	A	21 282	21 379	21 310.9	0	1 210
		B	21 282	21 379	21 306.8	0	679
		C	21 282	21 379	21 302.8	0	523
kroA200	29 368	A	29 401	30 005	29 547.2	0.11	1 450
		B	29 382	29 777	29 518.9	0.05	834
		C	29 368	29 722	29 489.5	0	520
a280	2 579	A	2 597	2 668	2 624.6	0.69	1 540
		B	2 584	2 650	2 610	0.19	1 220
		C	2 579	2 634	2 604.4	0	1 134
lin318	42 029	A	42 608	43 577	43 180	1.38	1 409
		B	42 475	43 464	43 053.4	1.06	1 091
		C	42 297	43 524	42 803.8	0.64	775

TSP	标准最优解	算法	最优解	最差解	平均解	误差率/%	迭代次数
eil51	426	ACS	427	436	428.0	0	306
		MMAS	426	432	428.0	0	139
		CEACO	426	427	426.3	0	60
eil76	538	ACS	538	549	543.5	0.00	410
		MMAS	541	552	546.6	0.56	580
		CEACO	538	542	539.2	0	210
korA100	21 282	ACS	21 282	21 673	21 392.6	0	656
		MMAS	21 292	21 841	21 467.6	0.04	1 226
		CEACO	21 282	21 379	21 302.8	0	523
kroB100	22 141	ACS	22 199	22 885	22 315.5	0.26	500
		MMAS	22 220	22 649	22 420.8	0.36	638
		CEACO	22 141	22 320	22 235.6	0	355
ch130	6 110	ACS	6 150	6 364	6 220.6	0.65	1 190
		MMAS	6 173	6 313	6 221.5	1.03	1 162
		CEACO	6 110	6 173	6 148.8	0	517
ch150	6 528	ACS	6 553	6 650	6 586.6	0.38	233
		MMAS	6 548	6 620	6 580.0	0.31	607
		CEACO	6 528	6 580	6 558.9	0	756
kroA150	26 524	ACS	26 640	27 853	27 179.8	0.44	1 252
		MMAS	26 677	27 130	26 962.1	0.58	1 878
		CEACO	26 524	27 066	26 843.5	0	1 643
kroB150	26 130	ACS	26 141	27 104	26 578.7	0.04	1 654
		MMAS	26 135	26 691	26 404.0	0.02	1 744
		CEACO	26 130	26 502	26 234.4	0.00	310
kroA200	29 368	ACS	29 503	30 275	29 848.0	0.46	1 942
		MMAS	29 401	29 920	29 634.9	0.11	1 714
		CEACO	29 368	29 722	29 489.5	0	520
kroB200	29 437	ACS	29 660	30 466	30 106.9	0.75	1 597
		MMAS	29 586	30 559	30 204.4	0.51	1 920
		CEACO	29 459	30 052	29 811.7	0.07	634
tsp225	3 916	ACS	3 929	4 038	3 984.5	0.33	653
		MMAS	3 935	4 078	3 996.4	0.49	1058
		CEACO	3 920	4 017	3 958.5	0.10	845
a280	2 579	ACS	2 584	2 727	2 634.2	0.19	1 297
		MMAS	2 601	2 699	2 631.3	0.85	1 581
		CEACO	2 579	2 634	2 604.4	0.00	1 134
lin318	42 029	ACS	42 741	44 851	43 385.3	1.69	1 817
		MMAS	43 074	44 695	43 611.5	2.49	1 887
		CEACO	42 297	43 524	42 803.8	0.64	775
f417	11 861	ACS	12 039	12 346	12 153.4	1.50	1 910
		MMAS	12 050	12 506	12 259.5	1.60	1 990
		CEACO	11 971	12 238	12 078.0	0.93	959
pr439	107 217	ACS	108 625	114 208	110 774.5	1.31	1 831
		MMAS	108 322	118 864	110 815.9	1.03	1 896
		CEACO	107 818	113 112	110 112.3	0.56	1 045

TSP	算法	最优解	平均解	误差率/%	TSP	算法	最优解	平均解	误差率/%
eil51	CEACO	426	426.3	0	kroA200	CEACO	29 368	29489.5	0
	GA-SAC	426	427.4	0		GA-SAC	─	─	─
	SOS-ACO	426	428.1	0		SOS-ACO	29 413	29 520.2	0.15
	PBACO	426	427	0		PBACO	29 383	29 768	0.05
eil76	CEACO	538	539.2	0	a280	CEACO	2 579	2 604.4	0
	GA-SAC	538	539.3	0		GA-SAC	2 609	2 640.8	1.16
	SOS-ACO	538	541.7	0		SOS-ACO	─	─	─
	PBACO	538	540	0		PBACO	2 590	2 617	0.42
kroA100	CEACO	21 282	21 302.8	0	lin318	CEACO	42 297	42 803.8	0.64
	GA-SAC	21 282	21 300.1	0		GA-SAC	42 329	42 902.4	0.71
	SOS-ACO	21 282	21 290.1	0		SOS-ACO	42 473	42 762.7	1.05
	PBACO	21 282	21 345	0		PBACO	42 384	42 432	0.84
ch150	CEACO	6 528	6 558.9	0	pr439	CEACO	107 818	110 112.3	0.56
	GA-SAC	─	─	─		GA-SAC	─	─	─
	SOS-ACO	6 558	6 571.2	0.46		SOS-ACO	107 978	108 873.8	0.71
	PBACO	6 533	6 551	0.07		PBACO	─	─	─