改进状态转移策略的蚁群算法求解TSP问题
|
摘要
针对蚁群算法在求解TSP问题中易出现算法易早熟难收敛的问题,基于历史搜索信息提出了一种改进状态转移策略的蚁群算法,并引入自适应信息素更新机制引导信息素的更新。实验表明,改进的蚁群算法较传统蚁群算法改善了在求解TSP问题上易早熟难收敛的问题,求解效果和求解稳定性上提升显著。
Aiming at the problem of ant colony algorithm in solving TSP problem,the algorithm is easy to premature and difficult to converge.Based on historical search information,an ant colony algorithm with improved state transition strategy is proposed,and an adaptive pheromone update mechanism is introduced to guide the update of pheromone.Experiments show that the improved ant colony algorithm improves the problem of premature convergence and difficulty in solving the TSP problem compared with the traditional ant colony algorithm.The solution effect and stability of the solution are significantly improved.
Aiming at the problem of ant colony algorithm in solving TSP problem,the algorithm is easy to premature and difficult to converge.Based on historical search information,an ant colony algorithm with improved state transition strategy is proposed,and an adaptive pheromone update mechanism is introduced to guide the update of pheromone.Experiments show that the improved ant colony algorithm improves the problem of premature convergence and difficulty in solving the TSP problem compared with the traditional ant colony algorithm.The solution effect and stability of the solution are significantly improved.
引文
[1]Flood M.The Traveling-Salesman Problem[J].Operations Research,1956,4(1):61-75.
[2]王剑文,戴光明.求解TSP问题算法综述[J].计算机工程与科学,2008,2(30):72-74.
[3]陈文兰,戴树贵.旅行商问题算法研究综述[J].滁州学院学报,2006,8(3):1-6.
[4]Colorni A.Distributed optimization by ant colonies[R].Proc of 1st European Conf Artificial Life.
[5]Dorigo M,T Stützle.The ant colony optimization metaheuristic:Algorithms[J].New Ideas in Optimization,2003,57(3):251--285.
[6]Stutzle T,Hoos H.MAX-MIN ant system and local search for the traveling salesman problem[C]//Proceedings of the 4th IEEE International Conference on Evolutionary Computation.Indianapolis:IEEE,1997:1318-1320.
[7]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[8]Xia Ya-Mei,CHENG Bo.Optimizing Services Composition Based on Improved Ant Colony Algorithm[J].Chinese Journal of Computers.2012,02(54):2270-2281.
[9]Tao L H,Shi P T,Bai J F.Research on Parameter Optimization of ant colony algorithm based on genetic algorithm[M]//Proceedings of the 23rd International Conference on Industrial Engineering and Engineering Management 2016.2017.
[10]杨惠,李峰.粒子群和蚁群融合算法的自主清洁机器人路径[J].计算机工程与应用,2009,45(32):200-202.
[11]张岩岩,侯媛彬,李晨.基于人工免疫改进的搬运机器人蚁群路径规划[J].计算机测量与控制,2015,23(12):4124-4127.
[12]吴冬敏,邵剑平,芮延年.基于蚁群算法和神经网络的数控机床故障诊断技术研究[J].机械设计与制造,2013,(1):165-167.
[13]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,(6):873-878.
[14]张于贤,丁修坤.求解旅行商问题的改进蚁群算法研究[J].计算机工程与科学,2017,8(39):1576-1580.
[15]宋尧,叶桦,仰燕兰.改进细菌觅食算法在TSP问题中的应用[J].工业控制计算机,2018,8(31):86-87.
[2]王剑文,戴光明.求解TSP问题算法综述[J].计算机工程与科学,2008,2(30):72-74.
[3]陈文兰,戴树贵.旅行商问题算法研究综述[J].滁州学院学报,2006,8(3):1-6.
[4]Colorni A.Distributed optimization by ant colonies[R].Proc of 1st European Conf Artificial Life.
[5]Dorigo M,T Stützle.The ant colony optimization metaheuristic:Algorithms[J].New Ideas in Optimization,2003,57(3):251--285.
[6]Stutzle T,Hoos H.MAX-MIN ant system and local search for the traveling salesman problem[C]//Proceedings of the 4th IEEE International Conference on Evolutionary Computation.Indianapolis:IEEE,1997:1318-1320.
[7]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[8]Xia Ya-Mei,CHENG Bo.Optimizing Services Composition Based on Improved Ant Colony Algorithm[J].Chinese Journal of Computers.2012,02(54):2270-2281.
[9]Tao L H,Shi P T,Bai J F.Research on Parameter Optimization of ant colony algorithm based on genetic algorithm[M]//Proceedings of the 23rd International Conference on Industrial Engineering and Engineering Management 2016.2017.
[10]杨惠,李峰.粒子群和蚁群融合算法的自主清洁机器人路径[J].计算机工程与应用,2009,45(32):200-202.
[11]张岩岩,侯媛彬,李晨.基于人工免疫改进的搬运机器人蚁群路径规划[J].计算机测量与控制,2015,23(12):4124-4127.
[12]吴冬敏,邵剑平,芮延年.基于蚁群算法和神经网络的数控机床故障诊断技术研究[J].机械设计与制造,2013,(1):165-167.
[13]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013,(6):873-878.
[14]张于贤,丁修坤.求解旅行商问题的改进蚁群算法研究[J].计算机工程与科学,2017,8(39):1576-1580.
[15]宋尧,叶桦,仰燕兰.改进细菌觅食算法在TSP问题中的应用[J].工业控制计算机,2018,8(31):86-87.