《蚁群算法在路径规划策略中的应用.ppt》由会员分享，可在线阅读，更多相关《蚁群算法在路径规划策略中的应用.ppt（12页珍藏版）》请在三一文库上搜索。
1、蚁群算法在路径规划策略中的应用,摘要：本文提出了一种考虑交通负荷条件下的最优路径搜索算法。算法的主要目标就是在地图寻找出最优路径。本课题提出的路径搜索算法基于蚁群算法，搜索从地图给定起点到终点的最短路径。该算法由C+实现。该算法对于不同的地图表现出很好的鲁棒性，能快速计算出最短路径。,1.概述,性能良好的路径规划策略基于标准搜索算法，例如Dijkstra算法,该算法是通过不断地计算、比较和选择起始点到终点路径中的局部最优路径，从而达到整体最优的目标。这里选择局部最优路径的判断依据是路径最短或最快。本文讨论的是地图导航中的路径规划问题。 路径搜索算法已经在许多领域得到成功应用，例如网络路由策略、
2、驾驶导航系统。路径规划过程中，往往受一些限制，例如线路上的最大带宽容量，结点的最大传输速度等。这些限制经常影响优化结果。例如如果我们通过一个重负载结点来传送一个报文，因为总体的传送速度受到最大传送速度的限制，往往产生延迟。为了解决这个问题我们应该避免通过网络负载重的节点进行路由，本文在设计路由策略时候就把负载平衡问题考虑在内，实现平滑的报文传送。,本论文通过推导阐明了地图上的路径搜索问题是个寻找最短路径的最优化问题，并且提出了一种基于蚁群算法(ACO)的解决方法。蚁群算法是最近提出的一种基于种群的启发式仿生进化算法，被用来解决许多组合优化问题,例如旅行商问题,二次分配问题,图片着色问题, 抽水
3、蓄能电站排序优选问题。该算法与其他算法不同之处在于其实现比较简单、灵活，更重要的是该算法不易陷入局部解。为了适应一些像交通运输管理方面的应用，本论文采取路径最大负荷量来控制网络的流量。 论文的结构： 论文是包括以下章节:第二部分阐明了路径规划问题,第三部分介绍了蚁群算法。第四部分介绍了如何应用蚁群算法解决路径规划问题。第五部分介绍实验结果。,2.问题数学化,3.蚁群算法的基本原理,蚁群算法(ACO)是一种基于种群的启发式仿生进化算法。蚁群算法中人工蚂蚁的行为是模拟生物界中的蚂蚁的觅食行为。在生物界中，单只蚂蚁的行为也是非常简单的。当它们走过一个地方时，在路径上留下一种叫信息素的化学物质。而其他
4、蚂蚁的则根据路径上的信息素来选择觅食线路。蚂蚁会选择其中一条信息素浓度最大的线路。当然，人工蚂蚁有着生物界蚂蚁不具备的特性。其中很重要的一点就是人工蚂蚁工作在离散环境中，它们需要实现从节点到节点的转移。他们的行为往往和存储在内存特定数据结构有关。 信息素的更新值是发生在人工蚂蚁完成起点到终点的线路后，而不是在这个过程当中。每只人工蚂蚁都存有常量的信息素，当从起点到达终点后，信息素会被均匀地分配到线路上。如果该蚂蚁选择的是一条好的线路，分配的信息素就会多些。相反，如果该线路不好，则分配的信息素就会很少。线路质量的好坏就与信息素的多少联系起来。路线上的信息素随着时间逐渐减少，避免陷入局部最优解。,转移概率公式：,4.AOC算法的应用,5.仿真结果,表1为蚁群算法与其他算法的比较。从表中可以看出，给定一幅地图，节点数超过200后，蚁群算法明显更加高效。,6结论,本文讨论在给定地图或者网络中搜索最优路径的方法。路径规划问题可以看成是在考虑负载约束下查找最短路径的问题，本文在蚁群算法基础上提出了一种路径规划的新方法。该方法有以下优点：1）这种算法实现简单，可以用来解决许多最优化问题；2）算法灵活，鲁班性强；3）算法不易陷于局部最优解，能达到全局最优解。 最后，算法在几个网络上做了测试并取得了不错的效果。,