改进蚁群算法在TSP中的应用研究  

Application Research of Improved Ant Colony Algorithm in TSP

作　　者：郑娟毅 程秀琦 付姣姣 ZHENG Juan-yi;CHENG Xiu-qi;FU Jiao-jiao(School of Communication and Information Engineering,Xi'an University of Posts&Telecommunications,Xi'an Shanxi 710121,China)

机构地区：[1]西安邮电大学通信与信息工程学院,陕西西安710121

出　　处：《计算机仿真》2021年第5期126-130,167,共6页Computer Simulation

基　　金：国家自然科学基金资助项目(61402365);陕西省国际合作项目(2017KW-011S)。

摘　　要：针对现有路径动态诱导算法在交通问题规模增大时存在的性能急剧下降的问题,提出了一种改进的混合遗传蚁群算法。为解决蚁群算法对信息素的强依赖性导致的局部最优解现象,及遗传算法存在的全局搜索性能强但收敛速度慢等问题,将蚁群算法与遗传算法相结合,基于遗传算法的交叉变异因子,改进了信息素浓度的设定方式,加强了传统蚁群算法的全局搜索能力;利用蚁群算法的局部搜索能力较强的特点,提高了传统遗传算法的收敛速度。仿真结果表明,相比于遗传算法与蚁群算法,所提算法在求解不同规模的旅行商问题时具有更强的全局搜索性及快速收敛性。Aiming at the problem that the existing path dynamic induction algorithm has a sharp decline when the scale of traffic problem increases, the paper proposes an improved hybrid genetic ant colony algorithm. In order to solve the problems of the local optimal solution phenomenon caused by the strong dependence of ant colony algorithm on pheromone, the strong global search performance of genetic algorithm and the slow convergence speed, this paper combined ant colony algorithm with genetic algorithm, the cross-variation factor based on genetic algorithm can improve the setting method of pheromone concentration and strengthen the global search ability of traditional ant colony algorithm. On the other hand, the convergence speed of traditional genetic algorithm is improved by using the strong local search ability of ant colony algorithm. The simulation results show that compared with genetic algorithm and ant colony algorithm, the proposed algorithm has stronger global search ability and fast convergence when solving traveling salesman problems of different scales.

关 键 词：动态路径诱导系统 蚁群算法 遗传算法 旅行商问题 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]