蚁群算法(ACO)旅行商问题(TSP)路径规划MATLAB实现

蚁群算法的由来

蚁群算法(ant colony optimization)最早是由Marco Dorigo等人在1991年提出,他们在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,据此提出了基于信息正反馈原理的蚁群算法。

蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理,根据昆虫科学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并在周围环境发生变化后,自适应地搜索新的最佳路径。

蚂蚁在寻找食物源的时候,能在其走过的路径上释放一种叫信息素的激素,使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时,信息素也就越来越多,蚂蚁们选择这条路径的概率也就越高,结果导致这条路径上的信息素又增多,蚂蚁走这条路的概率又增加,生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说,它并没有要寻找最短路径,只是根据概率选择;对于整个蚁群系统来说,它们却达到了寻找到最优路径的客观上的效果。这就是群体智能。

蚁群算法能做什么

蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法,因此一般而言,蚁群算法用来解决最短路径问题,并真的在旅行商问题(TSP,一个寻找最短路径的问题)上取得了比较好的成效。目前,也已渐渐应用到其他领域中去,在图着色问题、车辆调度问题、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。

函数优化问题MATLAB实现:

蚁群算法(ACO)MATLAB实现

机器人路径规划:

蚁群算法(ACO)最短路径规划(MATLAB)

更多ACO算法:http://www.omegaxyz.com/tag/aco/

TSP问题

旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

本文要实现的代码

①问题建模

31个省市自治区的首都画在笛卡尔坐标系上,用坐标表示,两个城市间的距离用二维距离公式表示。

②初始化参数

m是种群数量,n是节点的多少(这里指城市数量的多少)

③构建解空间

将每个个体随机放到不同的点上,进行迭代更新

④更新信息素

计算本轮中最短路径,更新信息素。

⑤判断是否终止

ACO的优点

①采用正反馈机制,不容易陷入局部最优。

②利用信息素达到个体间的交互,有利于进行信息共享。

③可以并行编程,多个个体并行计算,有效地减少时间

MATLAB代码

效果:

读者评分
[评分人数: 2 平均分: 5]

评论

OmegaXYZ