基于信息熵的改进蚁群算法求解TSP问题  

Improved ant colony algorithm based on information entropy for solving TSP problems

作　　者：杨一健 李明[2,3] 方赛银 YANG Yi-jian;LI Ming;FANG Sai-yin(School of Machinery and Transportation,Southwest Forestry University,Kunming 650224,China;Key Laboratory of Advanced Perception and Intelligent Control of High-End Equipment of Ministry of Education,Anhui University of Engineering,Wuhu 241000,China;School of Electrical Engineering,Anhui University of Engineering,Wuhu 241000,China)

机构地区：[1]西南林业大学机械与交通学院,云南昆明650224 [2]安徽工程大学高端装备先进感知与智能控制教育部重点实验室,安徽芜湖241000 [3]安徽工程大学电气工程学院,安徽芜湖241000

出　　处：《计算机工程与设计》2024年第9期2874-2880,F0003,共8页Computer Engineering and Design

基　　金：国家自然科学基金项目(32160345、31760182);云南省教育厅科学研究基金项目(2021J0156)。

摘　　要：针对蚁群算法求解精度低、易陷入局部最优的缺点,提出一种基于信息熵的自适应改进蚁群算法。通过算法自身特性定义结合熵值对种群参数进行自适应优化;采用分组合作的信息素更新策略,通过较活跃性个体引导整个种群,扩大搜索范围;通过对较优路径的奖励,平衡收敛速度和搜索范围之间的关系;在种群信息熵过低时,加入局部搜索策略,进一步提高算法精度。实验结果表明,相较于蚁群算法,改进算法具有较好的求解精度以及跳出局部最优的能力。An adaptive improved ant colony algorithm based on information entropy was proposed for the disadvantages of low solution accuracy and easiness to fall into local optimum of ant colony algorithm.The population parameters were adaptively optimized by the algorithm’s own characteristic definition combined with the entropy value.The pheromone updating strategy of group cooperation was used to expand the search range by guiding the whole population through more active individuals,the relationship between convergence speed and search range was then balanced by rewarding the better path.When the population information entropy was too low,a local search strategy was added to further improve the accuracy of the algorithm.Experimental results show that the improved algorithm has higher solution accuracy and the ability to jump out of the local optimum compared with the ant colony algorithm.

关 键 词：信息熵 蚁群算法 自适应 旅行商问题(TSP) 信息素 路径 局部搜索 种群 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]