蚁群算法最优路径.doc

(完整word)(完整word版)蚁群算法最优路径(完整word)(完整word版)蚁群算法最优路径(完整word)(完整word版)蚁群算法最优路径机器人的路径规划——-蚁群算法1.蚁群算法众所周知，蚁群算法是优化领域中新出现并逐渐引起重视的一种仿生进化算法它是群体智能的典型实现，是一种基于种群寻优的启发式搜索算法。自从M．Dorigo等意大利学者在1991年首先提出蚁群算法（AntColonySystem,ACS）以来,这种新型的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的应用。蚁群算法的特点主要表现在以下五个方面：(1)蚂蚁群体行为表现出正反馈过程。蚁群在寻优的过程中会释放一定量的信息素，蚁群的规模越大,释放的信息素的量也就越大，而寻优路径上存在的信息素浓度越高，就会吸引更多的蚂蚁,形成一种正反馈机制，然后通过反馈机制的调整,可对系统中的较优解起到一个自增强的作用，从而使问题的解向着全局最优的方向演变，最终能有效地获得全局相对较优解。(2）蚁群算法是一种本质并行的算法。个体之间不断进行信息交流和传递．有利于最优解的发现，并在很大程度上减少了陷于局部最优的可能。（3)蚁群算法易于与其他方法结合.蚁族算法通过与其他算法的结合，能够扬长避短，提高算法的性能。(4)蚁群算法提供的解具有全局性的特点。一群算法是一种群只能算法，每只蚂蚁巡游的过程相对独立，他们会在自己的活动空间进行搜索，蚂蚁在寻优过程中通过释放信息素，相互影响，互相通信,保证了解的全局性。（5）蚁群算法具有鲁棒性。蚁族算法的数学模型易于理解，可以广泛应用在很多复杂的优化问题中,蚁族算法区别于传统优化算法的一个特点在于该算法不依赖于初始点的选择，受初始点的影响相对较小，并且在整个算法过程中会自适应的调整寻优路径。由此可见，在机器人寻找最优路径的过程中,采用蚁群算法实现路径的规划问题，可以高效,准确的找到最优的路径。2.移动机器人的路径规划2.1环境信息处理假设机器人运行环境为边长分别为x和Y的矩形区域，在矩形区域内分布有n个异形障碍物，显然对于该获取的实际环境信息:首先,由于障碍物大小不一,而且形状也各不相同，为了减少机器人处理地图信息的负担，需要对工作环境行一些必要的预处理；其次，在后续章节中,描述机器人的路径规划方法是基于把障碍物近似成质点的基础上进行的，而要把障碍物近似成质点也同样需要对工作环境的信息进行适当预处理。环境信息预处理遵循以下原则：1）移动机器人作二维平面运动，障碍物不考虑高度信息；2)小问距障碍物作合并处理，即如果两个障碍物相距太近，障碍物之间距离小于机器人通过的最小安全距离。则将两个障碍物合并作为一个障碍物处理；3）作出障碍物的外接矩形，并对障碍物外接矩形进行径向扩张且对环境边界向内作径向扩张，因此可把移动机器人退化成运动质点处理。2.2环境建模设机器人工作空间为二维结构化空间记为RS，并且障碍物位置、大小已知。用尺寸相同的栅格对RS进行划分，栅格大小以机器人能在其内自由运动为限,设机器人能自由运动的范围为[0，R］.若某一栅格尺寸范围内不含任何障碍物,则称此栅格为自由栅格，反之称为障碍栅格。自由空间和障碍物均可表示成栅格块的集合,我们将障碍物栅格集记为OS。栅格标识可采用下述两种方法:（1）直角坐标法.以栅格阵左上角为坐标原点，水平向右为x轴正方向,竖直向下为Y轴正方向,每一栅格区间对应坐标轴上的一个单位长度。任一栅格均可用直角坐标（x，y）唯一标识。(2）序号法。按从左到右,从上到下的顺序,从栅格阵左上角第一个栅格开始,给每一个栅格一个序号n(从0开始计），则序号以与栅格块一一对应.2.3具体方法给定一个有弹个节点的城市道路网的路径规划问题,我们可以把指定的起始点s假设为人工蚁群(以下简称为蚁群)的巢穴，把目标点t假设为要寻找的食物，则此路径规划问题就可以转化为蚁群寻找食物的路径寻优问题。假定人工蚂蚁（以下简称为蚂蚁)的数量为m只，则每只蚂蚁的行为要符合以下的规则:(1）能够释放出两种类型的信息素：“食物”信息素和“巢穴”信息素；（2)根据与当前节点相连接的各个路径上的信息素浓度和路径长度,以相应的概率来随机选择下一个节点；（3)不再选择已经走过的节点为下一个节点,这可以通过一个结构数组来实现;（4）在寻找食物时，通过“食物”信息素寻找下一个节点，同时释放“巢穴"信息素;（5）在寻找巢穴时，通过“巢穴”信息素寻找下一个节点，同时释放“食物”信息素；(6）按一定的路径长度释放相应的信息素浓度，并且所释放的信息素浓度会随着时间的推移而逐步减少；3。程序设计流程在主程序流程中，地图数据库是从实际地图中抽象出来的城市道路网相关的数据信息，其中包括城市道路网的节点信息、道路信息和相应道路的信息素信息，每部分信息都各自形成一个数据表.在节点表中，包