智能优化方法课程作业
课题名称：基于改进蚁群算法的机器人路径规划
姓名：王伍臣
学号：SC12009057
基于改进蚁群算法（蚁群系统）的机器人路径规划
一、该算法要解决的问题及原理：
机器人路径规划问题简单说就是从机器人起点到终点寻找一条无障碍的最
优路径，不光要避障而且要找到最优路径，在该算法中将机器人路径图简化为
一个 0—1 矩阵，0 表示无障碍，1 表示有障碍，应用改进的蚁群算法中的蚁群
系统思想对其路径进行优化。
二、蚁群算法及改进蚁群算法中的蚁群系统思想简介
蚁群算法(Ant Colony Algorithm, ACA) 是 Dorigo M 等人于 1991 年提出的。
经观察发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在
运动过程中, 蚂蚁能够在它所经过的路径上留下该种信息素, 而且能够感知信
息素的浓度, 并以此指导自己的运动方向 。蚁群的集体行为表现出一种信息正
反馈现象: 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂
蚁个体之间就是通过这种信息的交流达到搜索食物的目的。它充分利用了生物
蚁群通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特
征，以及该过程与旅行商问题求解之间的相似性。同时，该算法还被用于求解
二次指派问题以及多维背包问题等，显示了其适用于组合优化问题求解的优越
特征。
Dorigo M 等在提出基本蚁群算法后不久，又提出了一种新的蚁群算法，并
将其命名为 Ant-Q system。为了避免出现停滞现象，Dorigo M 等在该算法中采
用了确定性选择和随机性选择相结合的选择策略，并在搜索过程中动态调整状
态转移概率。
三、应用改进蚁群算法进行机器人路径规划的主要步骤及原理描述如下：
（1） 输入由 0 和 1 组成的矩阵表示机器人需要寻找最优路径的地图（其中 0 表示
此处可以通过的，1 表示此处为障碍物），初始化各参数，输入循环次数 N，
每轮蚂蚁数 M，令各路径初始信息量为相等的常数，初始时刻信息量增量为
0。输入信息素、期望因子等其他各参量。
（2） 编写子函数生成（1）中 0-1 地图的加权邻接矩阵，此矩阵存储（1）中地图
上两任意方格的连通情况，在这里两方格连通表示蚂蚁可以先后通过这两个
方格即为两相邻或者对角的无障碍方格，对于连通的两方格在邻接矩阵中以
元素值存储它们之间的距离，用元素的行、列下标分别存储两方格在（1）中
地图中的位置，该算法中邻接矩阵与禁忌表一起决定了所有蚂蚁下一步能去
的方格。
（3）开始 N 轮蚂蚁的搜索，设定循环结束条件，初始化禁忌表。
（4）状态转移。状态转移包括两小步：首先根据（2）中求得的邻接矩阵以及禁忌
表求出蚂蚁下一步能前往的方格；然后根据蚁群系统状态转移规则求蚂蚁下一
步所前往的方格，并且更新禁忌表。
蚁群系统的状态转移规则如下：为避免停滞现象的的出现，蚁群系统采用
了确定性选择和随机性选择相结合的选择策略，并在搜索过程中动态调整状态
转移概率。其规则可以用下面两个式子描述，对位于地点 i 的蚂蚁随机数 q 小
于等于算法参数 q
0
按式（2.1）选择下一个地点 j，当 q 大于 q
0
时按照式
（2.2）的概率，利用轮盘赌法确定蚂蚁下一个要去的地点：
j
=
arg
max
𝜏
𝛼
𝑖𝑘
η
𝛽
𝑖𝑘
,
，
𝑞
≤
𝑞
0
式
（
2.2
）
，
其他
（3.1）
��
� � � �
��
� � � �
� �
� �
�
�
�
�
�
�
�
��
�
�
�
�
��
其他,0
,
k
tabuNk
ikik
ijij
k
ij
tabuNj
t
t
p
k
��
��
��
��
（3.2）
其中 arg max f（k） 的结果是使 f（k）达到最大值的 k 值，
��
t
ij
�
为路径
� �
ji,
上的信息素浓度。
ij
�
表示有方格 i 转移到方格 j 的期望程度，
�
表示信息启发
式因子，
�
表示期望启发式因子，
�
�
�
�
�
�
�
�
�
�
�
k
tabuN
表示此时蚂蚁 k 下一步允许
选择的方格。
（5） 更新蚂蚁爬行路径，以及路径长度。
(6) 重复（4）（5）过程，直到蚂蚁到达终点或者陷入死胡同。
（7） 重复（4）（5）（6），直到所有 m 只蚂蚁搜索结束。
（8） 更新信息素矩阵，在这里不再更新不再用于所有蚂蚁，而是只对每一次循环
中找到本轮最短路径的蚂蚁使用。更新规则如下式：
� � � � ��
ijijij
tt
����
������ 11
（3.3）
��
��
�
�
�
�
�
��
jik0
jik
，不经过，如果蚂蚁
，经过，如果蚂蚁
tL
Q
t
k
ij
�
（3.4）
其中
�
为信息素挥发系数。
Q
为信息量增加强度。
��
tL
k
表示第 k 只蚂蚁在本
次循环中所走路径的总长度。
（9）重复（4）~（8），直到满足（3）设定的循环结束条件时循环结束，输出结果。
四、运行结果（图、表等）
将如下程序段输入到 matlab 命令窗口：
L=[0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 ;
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0;
0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 ;
0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 ;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 ;
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0;
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 ;
0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 ;
0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0;
0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0;
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;];
N=100;
M=60;
a=1;
b=6;
p=0.3 ;
Q=1;
q1=0.1;
lujingyouhua_1(L,N,M,a,b,p,Q,q1)
执行一次后程序输出如下结果：
评论0