蚁群算法最优路径.doc

机器人的路径规划---蚁群算法
众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M．Dorigo等意大利学者在1991年首先提出蚁群算法(名称和经纬度坐标等数据。在道路表中，包括了每条道路的起点和终点对应的编号、道路的长度、级别和所经过的路线等数据。在信息素表中，包括了对应道路上的“巢穴”信息素和“食物”信息素等数据。所需要输入的参数包括：节点的数量n、起始节点的编号OriNode、目标节点的编号DesNode、最大循环次数MaxCount、蚂蚁的数量m、蒸发信息素的相对重要程度、每只蚂蚁所释放的信息素总量Q、信息素浓度的相对重要程度口、启发式信息的相对重要程。所需要初始化的参数包括：“巢穴”信息素和“食物”信息素等值，每条道路对应的“巢穴”信息素和“食物”信息素的值分别仞始化为1，这是为了在计算下一个节点的选择概率时，分母不为0。
在程序开始时，首先连接地图数据库，然后输入、初始化各个参数并开始进行循环。在每次循环中，每只蚂蚁依次进行寻食过程，如果有蚂蚁找到了食物即找到了一条寻食路径，将此路径与本次循环中其它蚂蚁找到的寻食路径进行比较，将最小的寻食路径更新为最优路径，并判断是否满足所给定的精度，如果满足则退出循环，否则进行下一次循环。当循环次数到达最大次数时，结束循环并判断是否找到了最优路径，如果找到了最优路径，则输出最优路径的路线及其权值，否则显示没有找到最优路径。最后，关闭地图数据库并结束程序。
在每只蚂蚁进行寻食的过程中，首先判断蚂蚁是否正在寻找食物，如果是则进行寻找食物的过程，否则进行寻找巢穴的过程。在进行寻找食物的过程中，首先从地图数据库的道路表中读取与当前节点所连接的节点数，以及每个节点的编号和权值。判断每个节点是否已经走过，如果此节点已经走过，则读取下一个节点。从地图数据库的信息素表中读取对应边的“食物”信息素值，从当前点到下一可行点的转移是由基于信息量的状态转移概率和和距离启发式信息概率综合决定的，而这里采用的综合决定方法是基于比例选择策略即“***赌”的方式。从地图数据库的道路表中读取对应边的权值，并计算所走过路径的权值。从地图数据库的信息素表中读取对应边的“巢穴”信息素值，并重新计算对应边的“巢穴”信息素值。当所得的值小于1时，将此值设置为1，这是为了保证下一回计算选择概率时分母不为0。将重新计算的“巢穴”信息素值更新到信息素表中。判断下一个目标节点是否为食物，如果是的话，则保存各个记录，如蚂蚁所走过的节点、此蚂蚁找到食物的次数以及整个路径的总权值等数据，并为寻找巢穴做准备，如清空内存中的历史数据，将食物作为起始节点等，否则设置下一个目标节点为当前节点。
在进行寻找巢穴的过程中，大部分的操作都跟上面蚂蚁进行寻找食物的过程一样，只不过将“食物”信息素和“巢穴”信息素进行对调，在判断下一个目标节点是否为巢穴的时候，不需要保存各个记录，只需为寻找食物做准备，如清空内存中的历史数据，将巢穴作为起始节点，并将此蚂蚁上次找到食物的路径记录。
程序流程图如下：
Matlab 仿真
地图数据库是从实际地图中抽象出来的城市道路网相关的数据信息，其中包括城市道路网的节点信息、道路信息和相应道路的信息素信息，每部分信息都各自形成一个数据表。在节点表中，包括了各个节点的编号、对应的地点名称和经纬度坐标等数据。在道路表中，包括了每条道路的起点和终点对应的编号、道路的长度、级别和所经过的路线等数据。在信息素表中，包括了对应道路上的“巢
穴”信息素和“食物”信息素等数据。本仿真系统的静态地图数据假设在机器人出发之前就已经得到，而动态地图数据假设按一定的频率可以得到。
在机器人整个仿真系统中所需要输入的参数包括：节点的数量栉、起始节点的编号OriNode、目标节点的编号DesNode、最大循环次数MaxCount、蚂蚁的数量m、蒸发信息素的相对重要程度、每只蚂蚁所释放的信息素总量Q、信息素浓度的
相对重要程度"、启发式信息的相对重要程。所需要初始化的参数包括：“巢穴”信息素和“食物”信息素等值，每条道路对应的“巢穴”信息素和“食物”信息素的值分别初始化为1，这是为了在计算下一个节点的选择概率时，分母不为0。

用于把障碍物分布图转化为图的赋权邻接矩阵，地形图矩阵是一个01矩阵，里面的所有元素要么为0，要么为1。为0即表示机器人可以到达的节点，为1即表示其对应的栅格是障碍物。
源程序如下：
function D=G2D(G)
a=1;
N=size(G,1);
D=inf*ones(N^2,N^2);