基于自然选择策略的蚁群算法求解TSP问题

doi:10.3969/j.issn.1000-436x.2013.04.020

Abstract

Abstract:

To solve basic ant colony algorithm's drawbacks of low convergence rate,easiness of trapping in local optimal solution,an improved ant colony algorithm based on natural selection was proposed.The improved algorithm employed evolution strategy of survival the fittest in natural lection to enhance pheromones in paths whose random evolution factor was bigger than threshold of evolution drift factor in each process of iteration.It could accelerate convergence rate effectively.Besides the introduction of random evolution factor reduced probability of trapping local optimal solution notably.The proposed algorithm was applied to classic TSP problem to find better solution for TSP.Simulation results depict the improved algorithm has better optimal solution and higher convergence rate.

Key words: ant colony algorithm, natural selection, TSP, random evolution factor, threshold of evolution drift

Hua-feng WU,Xin-qiang CHEN,Qi-huang MAO,Qian-nan ZHANG,Shou-chun ZHANG. Improved ant colony algorithm based on natural selection strategy for solving TSP problem[J]. Journal on Communications, 2013, 34(4): 165-170.

Figures/Tables 5

References 17

[1]	朱献文, 李福荣．求解旅行商问题的几种智能算法[J]．计算机与数字工程， 2010,32(1):32-35. ZHU X W , LI F R . Several intelligent algorithms for so ving traveling salesman problem[J]. Computer ＆ Digital Engineering, 2010,32(1):32-35.
[2]	林冬梅，王东，李娅．一种求解多旅行商问题双层降解混合算法[J]. 计算机应用研究， 2011,28(8):2876-2879. LIN D M , WANG D , LI Y . Two-level degradation hybrid algorithm for multiple traveling salesman problem[J]. Applicatio Research of Computers, 2011,28(8):2876-2879.
[3]	廖飞雄, 马良 . 自调节种群的演化算法求解旅行商问题[J]．系统仿真学报， 2009,21(9):2595-2598. LIAO F X , MA L . Self-asjusting population evolutionary algorithm for travleing salesman problem[J]. Journal of System S mulation, 2009,21(9):2595-2598.
[4]	刘好斌，胡小兵，赵吉东．动态调整路径选择的蚁群优化算法[J]．计算机工程， 2010,36(17):201-203. LIU H B , HU X B , ZHAO J D . Ant colony optimization algorithm with path choice of dynamic transition[J]. Computer Engineering, 2010,36(17):201-203.
[5]	COLORINI A , DORIGO M , MANIEZZO V , et al. Distributed optimization by ant colonies[A]. Proceedings of the 1st European Conference on Artificial Life[C]. Paris,France, 1991. 134-142.
[6]	DORIGO M , MANIEZZO V , COLORINI A , et al. Ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics-Part B, 1996,26(1): 29-41.
[7]	吴斌, 史忠植 . 一种基于蚁群算法的TSP问题分段求解算法[J]．计算机学报， 2001,24(12):1-6. WU B , SHI Z Z . An ant colony algorithm based partition algorithm for TSP[J]. Chinese J.Computers, 2001,24(12):1-6.
[8]	CIORNEI I , KYRIAKIDES E . Hybrid ant colony-genetic algorithm (GAAPI) for global continuous optimization[J]. IEEE Transactions on Systems Man and Cybernetics-Part B CYBERNETICS, 2012,42(1): 234-245.
[9]	ZHOU Y R . Runtime analysis of an ant colony optimization algorithm for TSP instances[J]. IEEE Transactions on Evolutionary Computation, 2009,13(5): 1083-1092.
[10]	孙力娟, 王良俊, 王汝传．改进的蚁群算法及其在TSP中的应用研究[J]．通信学报, 2004,25(10):111-116. SUN L J , WANG L J , WANG R C . Research of using an improved ant colony algorithm to solve TSP[J]. Journal on Communications, 2004,25(10):111-116.
[11]	徐江乐, 肖志涛, 赵京华 . 基于遗传算法的改进智能优化蚁群算法[J]. 微电子学与计算机， 2011,28(8):47-50. XU J L , XIAO Z T , ZHAO J H . An improved intelligent ant colony optimization based on genetic algorithm[J]. Microelectronics ＆ Computer, 2011,28(8):47-50.
[12]	丛爽, 贾亚军．进化策略与蚁群算法融合的求解旅行商问题[J]．控制工程， 2011,18(1):83-87. CONG S , JIA Y J . Traveling salesman problem based on integration of evolution strategies and ant colony algorithm[J]. Control Engineering of China, 2011,18(1):83-87.
[13]	袁东辉, 刘大有, 申世群 . 基于蚁群—遗传算法的改进多目标数据关联方法[J]．通信学报, 2011,32(6):17-23. YUAN D H , LIU D Y , SHEN S Q . Improved AC-GA based data as-sociation method for multi-target tracking[J]. Journal on Communications, 2011,32(6):17-23.
[14]	徐金荣, 李允, 刘海涛等. 一种求解TSP的混合遗传蚁群算法[J]．计算机应用， 2008,28(8):2084-2087. XU J R , LI Y , LIU H T , et al. Hybrid genetic ant colony algorithm for traveling salesman problem[J]. Computer Applications, 2008,28(8):2084-2087.
[15]	TSPLIB[EB/OL]. .
[16]	WANG L , ZHU Q . An efficient approach for solving TSP:rapidly convergent ant colony algorithm[A]. Fourth International Conference on Natural Computation,IEEE[C]. Jinan,China, 2010. 448-452.
[17]	TERAI Y M , MEIJO H U . Nagoya:architecture for high-speed ant colony optimization[A]. Information Reuse and Integration,IEEE[C]. Las Vegas,USA, 2007. 1-5.

Metrics

Recommended 0

No Suggested Reading articles found!

参数名称	参数值
信息素	1
启发式因子权重	2
信息素挥发常系数	0.2
信息素浓度增强常系数	100
智能蚂蚁数量M	22
算法最大迭代次数	100

算法	参数名称	参数值
遗传—蚁群算法	交叉概率ρ_c	0.75
遗传—蚁群算法	变异概率ρ_m	0.05
ACANS算法	进化阈值EDT	0.6
ACANS算法	路径贡献度阈值q₀	0.4

Improved ant colony algorithm based on natural selection strategy for solving TSP problem

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 17

Related Articles 12

Metrics

Recommended 0

[1]	Tong WANG, Shan GAO, Huiwen GONG, Bo SUN. Research on forecast and recommendation technology of taxi passengers based on time-varying Markov decision process [J]. Journal on Communications, 2021, 42(2): 37-51.
[2]	Fang LYU,Jun BAI,Junheng HUANG,Bailing WANG. Discovering the backbone network with a novel designed ant colony algorithm [J]. Journal on Communications, 2020, 41(11): 74-85.
[3]	Xuesen MA,Shuai GONG,Jian ZHU,Hao TANG. Ant colony algorithm of partially optimal programming based on dynamic convex hull guidance for solving TSP problem [J]. Journal on Communications, 2018, 39(10): 59-71.
[4]	Zhong-an JIANG,Ming WANG,Ya CHEN. Path recommendation based on geographic coordinates and trajectory data [J]. Journal on Communications, 2017, 38(5): 165-171.
[5]	. Improved ant colony algorithm based on natural selection strategy for solving TSP problem [J]. Journal on Communications, 2013, 34(4): 20-170.
[6]	Nyuan YUA,Yu-xing PENG,Shan-shan LI,Wen-sheng TANG. Efficient heuristic algorithm for the mobile sink routing problem [J]. Journal on Communications, 2011, 32(10): 107-117.
[7]	Jiang-qing WANG,Jun QIN,Zi-mao LI. Hybrid optimization algorithm for routing problem in dynamic networks [J]. Journal on Communications, 2008, 29(7): 135-140.
[8]	Yi-ling ZENG,Hong-bo XU. Research on Internet hotspot information detection [J]. Journal on Communications, 2007, 28(12): 141-146.
[9]	Qiu-yu ZHANG,Zhan-ting YUAN,Qi-kun ZHANG,Rui-fang WANG. Multi-domain authentication mechanism based on lattice and adaptive algorithm [J]. Journal on Communications, 2007, 28(11A): 82-86.
[10]	Jiao-long WEI,Zhao-hui CEN. Optimization of regional coverage satellite constellations based on ant colony algorithm [J]. Journal on Communications, 2006, 27(8): 62-66.
[11]	Gang WANG,Hua WANG,Ning LIAO. Modified ant colony algorithm based on orientation factor in solving the multi-constraint QoS routing problem [J]. Journal on Communications, 2006, 27(11A): 189-193.
[12]	Xue-hui LUO,Xia LI,Ji-hong ZHANG. Vector quantization codebook design algorithm based on hybrid ant colony algorithm [J]. Journal on Communications, 2005, 26(9): 135-139.