蚁群在嘉定校区的路线研究应用

蚁群在嘉定校区的路线研究应用汇报人：第12组

目录问题引入蚁群算法介绍简单Matlab仿真分析仿真过程01020304总结0501问题引入PARTONE1引例两只嘉定的小蚂蚁要去食堂吃饭、然后去1教上课、中午再去食堂吃饭……/aco//aco/1没事干找事蚁亲，我饿了，咱们该吃饭了，我们要怎么以最优的路径去食堂呢？2百事通智慧蚁哦，看看下边这种方案怎么样……1

引例1引例

虫洞，是宇宙中可能存在的连接两个不同时空的狭窄隧道。通过虫洞，可以大大缩短宇宙旅行的时间。因此，我们可以在教学楼和食堂之间建立一个虫洞，我们就可以快速地到达食堂喽！Goodidear当然，虫洞只是一个概念性方法，真正的最优路径还需要使用科学的方法来规划。1引例02蚁群算法简介PARTTWO2蚁群算法介绍定义AB特点D关键步骤C规则

自1991年由意大利学者M.Dorigo，V.Maniezzo和A.Colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。是一种用来寻找优化路径的概率型算法。

目前蚁群算法已经被广泛的应用于求解旅行商问题(travelingsalesmanproblem，TSP)、定量构效方法(QSAR)、网络路径最优问题、聚类、分类等领域。2.1定义

①其原理是一种正反馈机制或称增强型学习系统;它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上。②它是一种通用型随机优化方法,它吸收了蚂蚁的行为特(内在搜索机制),它是使用人工蚂蚁仿真(也称蚂蚁系统)来求解问题，但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能人工蚂蚁有一定的记忆;人工蚂蚁不完全是瞎的;人工蚂蚁生活的时空是离散的③它是一种分布式的优化方法,不仅适合目前的串行计算机,而且适合未来的并行计算机④它是一种全局优化的方法,不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题2.2特点123452.3规则感知范围蚂蚁观察到的范围是一个方格世界，相关参数为速度半径

移动规则蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。散发信息素规则

在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。

环境信息

蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中包括食物信息素、窝信息素，信息素以一定速率消失。移动规则

蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。231蚂蚁的移动操作释放自身的信息素信息素的更新操作2.4关键步骤03

简单Matlab仿真分析PARTTHREE4.1提出问题旅行商问题给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路？嘉定校区路线如果在嘉定校区主要建筑游览一圈，如何安排路线？4.2分析问题获取节点在二维平面坐标

节点标注

建立坐标1—一食堂2—体育馆3—悉尼工商4—综合楼5—宿舍区A6—图书馆7—快递点A

8—二教9—一教10—数码艺术11—二食堂12—澡堂13—大礼堂14—校医院15—保卫科16—教育超市17—小花坛18—篮球场19—快递点B20—足球场21—宿舍区B算法思想蚂蚁移动判定问题？信息素释放问题？信息素更新操作？构建节点矩阵C，分配蚂蚁，构建已访问和未访问矩阵；向未知节点移动的概率

计算每个蚂蚁移动路径长度，在其中寻找最小值并记录与之对应的路径；更新信息素

04

仿真过程PARTFOUR4具体程序4具体程序4具体程序4具体程序4具体程序4具体程序程序运行第一次结果：最短路径长路1934.7个单位长度。4结果分析程序运行第二次结果：最短路径长路1923.9个单位长度4.2结果分析程序运行第三次结果：最短路径长路1936.4个单位长度4.2结果分析05

总结PARTFIVE5.1蚁群算法的优缺点优点：

蚁群算法是一种正反馈的算法。蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。5.1蚁群算法的优缺点TSP问题是一类经典的组合优化问题，即在给定的城市个数和各个城市之间距离的条件下，找出一条遍历所有城市的最短路线，那么它在这类问题下的不足之处主要是：如果参数设置不当，会导致求解速度比较慢且所得的质量比较差。基本蚁群算法中，理论上要求所有的蚂蚁选择同一条线路，该线路即所求的最优路线。但是在给定的循环迭代的次数下，很难达到这种情况。蚁群算法收敛速度慢，容易陷入局部最优，即搜索到一定程度后，所有个体发现的解完全一致，不能对解的空间进行进一步的探索，导致最后迭代出来