《改进状态转移策略的蚁群算法求解TSP问题.doc》由会员分享，可在线阅读，更多相关《改进状态转移策略的蚁群算法求解TSP问题.doc（1页珍藏版）》请在三一文库上搜索。
1、改进状态转移策略的蚁群算法求解 TSP 问题熊化峰，孙英华，刘雪庆【摘 要】摘要：针对蚁群算法在求解 TSP 问题中易出现算法易早熟难收敛的问 题，基于历史搜索信息提出了一种改进状态转移策略的蚁群算法，并引入自适 应信息素更新机制引导信息素的更新。实验表明,改进的蚁群算法较传统蚁群算法改善了在求解 TSP 问题上易早熟难收敛的问题，求解效果和求解稳定性上提 升显著。【期刊名称】 青岛大学学报(自然科学版)【年(卷),期】2019(032)001【总页数】 5【关键词】 TSP 问题；蚁群算法；状态转移策略；历史搜索信息旅行商问题(TSP)是典型的NP完全问题，TSP问题最早由Dantzig等提
2、出，并 迅速成为最优化领域研究的热点，成为许多优化算法的一个测试基准 1 。早期 对 TSP 问题的研究主要是使用分支定界、线性规划、动态规划等精确算法对该 问题进行求解。但是，该问题的可行解是所有路径节点的全排列，随着路径节 点的增加，问题的解空间规模会爆炸增长 2 。因此，后来的研究中很多学者使 用遗传算法、模拟退火算法、蚁群算法等近似算法或启发式算法对较大问题规 模的 TSP 问题进行求解 3 。蚁群算法具有健壮性、鲁棒性、逻辑简单、求解组 合问题性能优异等特点。信息素作为蚁群算法中蚂蚁之间信息交流的媒介是算 法的最大特点 4,5 。但蚁群算法在实际应用中很容易因为局部最优路径上信息 素浓度越来越高出现过早收敛的问题，算法在执行中很快陷入到局部最优解的 搜索，难以实现广度搜索 6 。因此在标准算法的基础上对蚁群算法进行改进，