目录

1. 问题描述
2. 蚁群算法基本原理
3. 最短路径规划模型建立
4. MATLAB代码实现
5. 验证

1.问题描述

存在一个简化的网格，如下图所示，在一定空间范围内，每一点都有一个确定的值与之对应，求一条最优路径A→B，使这条路径上所有点对应值之和取平均值最小。要求从A点出发，下一个点的位置只能取上一个点的下侧、右侧、右下侧位置中的一个，按此方法依次往下搜索，最终到达B结束。

图1.简化网格图

2.蚁群算法基本原理

1）蚁群算法：蚁群算法(ant colony optimization)最早是由Marco Dorigo等人在1991年提出，他们在研究新型算法的过程中，发现蚁群在寻找食物时，通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标，据此提出了基于信息正反馈原理的蚁群算法。蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理，根据昆虫科学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。蚂蚁在寻找食物源的时候，能在其走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时，信息素也就越来越多，蚂蚁们选择这条路径的概率也就越高，结果导致这条路径上的信息素又增多，蚂蚁走这条路的概率又增加，生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。这就是群体智能。

2）蚁群算法原理及matlab代码参见：https://www.omegaxyz.com/2018/01/26/aco/

3）本文的最短路径规划思想源于基于蚁群算法的最短路径规划，全文链接及matlab代码请见：https://blog.csdn.net/COCO56/article/details/100060632

4）本文代码适用于任意矩阵（正方形矩阵和非正方形矩阵均可）

3.最短路径规划模型建立

1）模型建立
如下图所示，采用序号标记法标平面内的每一点，即从起始位置开始，从序号1依次累加直到标记到最后一个网格。图中每一个网格代表平面内的每一点，起点序号为1，终点序号为100。
图2.序号标记法示意图

假设网格规模为m行n列，将网格序号转换成坐标点，则第i个网格对应的坐标点位置计算公式下式所示：

2）D矩阵建立
建立矩阵D，记录每个点至其相邻可行点的代价值，如图3所示，该网格规模为33，共有9个点，则矩阵D的大小就为（33，3*3），其中列将网格中所有点作为起点，行是将所有点作为邻域到达点，各点至其各相邻点的代价值已知，非相邻的点设为0.
图3.3x3网格图

图4.3x3网格图对应点的值

图5.网格上每一点可走路径示意图

图6.转化后得到的D矩阵

图7.含每个点对应值的D矩阵

3）求解流程
图8.求解流程图

4.MATLAB代码实现
在MATLAB中随机生成一组数据（50*rand(20,30)),用来仿真分析，求取最短路径，其收敛曲线变化趋势和最短运动路径如下图所示.：
图9.收敛趋势变化趋势
图10.最短路径运动轨迹

5.验证
以33的网格为例验证本文算法的正确性，网格内每一点的序号及其对应值如下图所示，取迭代次数K=200，蚂蚁个数M=50。
图11.33网格数据

手动计算所有可行路径及其对应值之和的平均值，如下所示：
1→2→3→6→9：3.094
1→2→5→6→9：4.806
1→2→5→8→9：4.376
1→2→5→9：4.1625
1→2→6→9：3.7975
1→4→5→6→9：4.456
1→4→5→8→9：4.026
1→4→5→9：3.725
1→4→7→8→9：2.482（最短路径）
1→4→8→9：2.8225
1→5→6→9：5.0775
1→5→8→9：4.54
1→5→9：4.31

程序仿真结果

图12.收敛曲线变化趋势

图13.最短路径运动轨迹