基于蚁群算法求解对称非对称旅行商问题

资 源 简 介

应用背景 蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它分布式特性，鲁棒性强并且容易与其它算法结合，但是同时也存在这收敛速度慢，容易陷入局部最优（local optimal）等缺点。 TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种，是一种NP-hard问题，此类问题用一般的算法是很大得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。 关键技术

详 情 说 明

应用背景

蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它具有分布式特性，鲁棒性强并且容易与其他算法结合使用。但是同时也存在一些缺点，比如收敛速度慢，容易陷入局部最优解等。

TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种NP-hard问题。这类问题使用一般的算法很难得到最优解，所以通常需要借助一些启发式算法来求解，比如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。

关键技术

蚁群算法（Ant Colony Optimization，ACO）是一种群智能算法，它由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，为求解复杂问题提供了一个新的可能性。蚁群算法最早由意大利学者Colorni A.和Dorigo M.于1991年提出。经过20多年的发展，蚁群算法在理论和应用研究上已经取得了巨大的进步。

蚁群算法是一种仿生学算法，受到自然界中蚂蚁觅食行为的启发。在自然界中，蚂蚁在觅食过程中总能够找到一条从蚁巢到食物源的最优路径。