蚂蚁寻路原理实例分析.ppt

LogoLogo基于基于蚂蚁算法的算法的实例分析例分析航空工程学院：吴航空工程学院：吴鹏Logo 蚂蚁寻径原理目目录1 基于蚂蚁算法的中国邮路问题2基于蚂蚁寻径原理的最优路径选择算法3Logo蚂蚁寻径原理径原理 通通过过昆虫学家的研究和昆虫学家的研究和观观察，察，蚂蚁蚂蚁在运在运动动中，会在中，会在经过经过的路径上留下一种的路径上留下一种挥发挥发性分泌物性分泌物(信息素信息素)，这这种分泌物随种分泌物随时间时间推移会逐推移会逐渐挥发渐挥发消失。周消失。周围蚂蚁围蚂蚁能能感知感知这这种物种物质质的存在及的存在及浓浓度，并度，并倾倾向于朝信息素向于朝信息素浓浓度高的方向移度高的方向移动动。即。即选择该选择该路径概率与当路径概率与当时这时这条路条路径上径上该该物物质质的的浓浓度成正比。信息素度成正比。信息素浓浓度越高的路径，度越高的路径，选择选择它的它的蚂蚁蚂蚁就越多，在就越多，在该该路径上留下的信息素的路径上留下的信息素的浓浓度就更大，而度就更大，而浓浓度大的信息素又吸引更多的度大的信息素又吸引更多的蚂蚁蚂蚁，从而形成一种从而形成一种正正反反馈馈。通。通过这过这种正反种正反馈馈机制，机制，蚂蚁蚂蚁最最终终可以可以发现发现最佳路径。最佳路径。蚂蚁寻径原理径原理图一一 蚂蚁寻径原理径原理基于基于蚂蚁算法的中国算法的中国邮路路问题 “中国中国邮邮路路问题问题”是由我国的管梅谷提出的一种是由我国的管梅谷提出的一种图图的极的极值问题值问题，又被称，又被称为为“中国中国邮递员问题邮递员问题”，即一，即一个个邮递员负责邮递员负责某一个地区的信件投某一个地区的信件投递递，每天从，每天从邮邮局局出出发发，走遍，走遍该该地区所有的街道再返回地区所有的街道再返回邮邮局的最短路局的最短路径径.基于基于蚂蚁算法的中国算法的中国邮路路问题算法描述算法描述：中国：中国邮递员问题求解的关求解的关键是是对图中奇数度中奇数度结点点进行匹配，使得行匹配，使得图中不存在中不存在奇数度奇数度结点，匹配原点，匹配原则要保要保证所添加的所添加的边的的权值之和最小，然后再之和最小，然后再寻找出以某个固定点找出以某个固定点为起始点和起始点和终点的一条最短路径点的一条最短路径.基于基于蚂蚁算法的中国算法的中国邮路路问题选择选择概率概率：按照按照蚂蚁算法的思想，算法的思想，设邮局位于局位于结点点u0,m个个邮递员服服务于同一地区，每个于同一地区，每个邮递员初始初始时刻随机刻随机选择出行方向，不妨出行方向，不妨设各个方向的各个方向的选择几率几率相同，即相同，即:ij（0）=C为常数常数.每个每个邮递员完成一次投完成一次投递任任务后，都要后，都要计算各自行走的算各自行走的总距离，并根据最短距离，并根据最短距离更新各个地点的距离更新各个地点的选择概率概率.设t时刻刻邮递员位于地位于地点点i，按，按(1)式式计算其未去算其未去过的下一地区的概率的下一地区的概率ij（t）表示表示t时刻在刻在ij连线上相上相应地区所占比率地区所占比率(对应于于蚂蚁算法中当前算法中当前积累的信息素累的信息素).基于基于蚂蚁算法的中国算法的中国邮路路问题（1)式中此式中此 表示在表示在t时时刻刻邮递员邮递员k由地点由地点i移移动动到地点到地点j的的选选择择概率：概率：基于基于蚂蚁算法的中国算法的中国邮路路问题信息素信息素调调整方法整方法：随着：随着时间的推移，以前留下的信息素的推移，以前留下的信息素逐逐渐消逝，用参数消逝，用参数1-p表示信息素消逝程度，表示信息素消逝程度，经过n个个时刻刻邮递员完成一次循完成一次循环回到起点，各路径上信息素要根回到起点，各路径上信息素要根据据(2)式作式作调整整 基于基于蚂蚁算法的中国算法的中国邮路路问题路径最路径最优优化和多化和多样样性的保性的保证证方法方法：对于于图G中任意的中任意的结Vi,Vj，设起点起点为Vi，终点点为Vj，按照，按照(1)式式计算它的每一个算它的每一个结点的点的选择概率，概率，产生下一生下一结点，重复点，重复执行直到行直到选择出出终点点为止止.路路线上通上通过的的结点点的的权重之和即重之和即为路路线长度度.根据路根据路线经过的的结点点Vi和其和其邻接点接点Vk，则按按(2)和和(3)式式调整整ij。但是修改但是修改ij的的时机也是必机也是必须注意的一个地方，假注意的一个地方，假设每每产生一条起生一条起点到点到终点的路点的路线都修改都修改ij的的话，那么由于，那么由于结点点选择的随机性，当的随机性，当前前单次次产生的路生的路线不一定是全局中的最短路不一定是全局中的最短路线，这种随机路种随机路线上上信息素的信息素的调整可能使得某些不佳路整可能使得某些不佳路线上上结点的点的选择概率增大，概率增大，为了避免了避免这种情况，可以种情况，可以让蚂蚁从起点到从起点到终点多点多产生几条路生几条路线，然，然后从多条路后从多条路线中中选出当前最出当前最优路路线再再对结点加以激励，即通点加以激励，即通过适适当增加当增加结点之点之间的的权重来提高重来提高这些些结点的点的选择概率概率.同同时为了保了保证路径的多路径的多样性，性，应该在多次在多次调整之后随机的降低信息素的整之后随机的降低信息素的值，以，以便小概率便小概率结点被点被蚂蚁选中而中而产生新的路径生新的路径.可以按下式可以按下式调整整:ij=ij-，为一个正常量，具体一个正常量，具体值可根据当前可根据当前图的的权重情况决定，重情况决定，为了保了保证路路线的多的多样性，性，值不易不易过大大.基于基于蚂蚁算法的中国算法的中国邮路路问题算法流程算法流程：(1)存存储图G的的邻接接权重矩重矩阵，初始化算法控制参数，初始化算法控制参数;(2)计算算图G中的每个中的每个结点的点的邻接接结点和点和结点度数，如果存在点度数，如果存在奇数度奇数度结点点则转(3)，否，否则算法算法结束束;(3)以某个以某个结点点为起点，按起点，按(2)式式计算其算其邻接接结点的点的选择概率，概率，直到直到图中所有中所有结点都被遍点都被遍历且最且最终回到起点回到起点为止止.为了保了保证路路线的多的多样性，可以多重复几次本步性，可以多重复几次本步(本文中本文中记为5次次)，保留本，保留本步步结束束时的当前最的当前最优路路线;(4)根据当前的最根据当前的最优路路线按照按照(2)和和(3)a式修改式修改图中中结点之点之间的概率的概率;(5)重复重复执行行(3),(4)(本文本文设定定为100次次)，并随机按，并随机按(4)式适式适当降低当降低结点之点之间的的权重以保重以保证路径的多路径的多样性性;(6)保留最保留最终的最的最优路路线和路和路线长度，算法度，算法结束束.基于基于蚂蚁算法的中国算法的中国邮路路问题仿真仿真实验：图1和和图2表示某个区域的表示某个区域的邮局分布情况，其中局分布情况，其中圆圈表示圈表示邮局的位置，局的位置，实线表示道路，表示道路，实线边上的数字是道路的上的数字是道路的长度，道路度，道路长度与度与结点位置无关点位置无关.按照本文的算法通按照本文的算法通过MATLAB对图1和和图2中的中的实例例进行了行了检验，算法都在，算法都在较短的短的时间内找出了最内找出了最优解，其中，粗解，其中，粗实线表示表示邮递员需要重复行走的道路需要重复行走的道路.同同时时，经过经过多次重复多次重复实验计实验计算得到算得到:实验图实验图1平均耗平均耗时时3.8 s，实验图实验图2平均耗平均耗时时17.8 s，总总的来的来说说，算法的效率是可以接受的。，算法的效率是可以接受的。基于基于蚂蚁算法的中国算法的中国邮路路问题结结束束语语：基于：基于蚂蚁算法的中国算法的中国邮路路问题介介绍了一种智能求解中国了一种智能求解中国邮路路问题的算法，和其的算法，和其他算法相比，算法他算法相比，算法设计简单，易于，易于实现，且，且能能够在短在短时间内找到最内找到最优解解.同同时，算法中，算法中最最优线路的构造方法也适合于其他求解最路的构造方法也适合于其他求解最优路的路的问题，如机器人的路，如机器人的路经规划划问题,TSP问题等等.基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法驾驶员驾驶员偏好性分析偏好性分析：通常，通常，驾驶员在出行前最在出行前最优路径路径选择方面会表方面会表现出多出多样性，会根据个人的偏好和出行的目的性，会根据个人的偏好和出行的目的选择性性质和功能不同的和功能不同的路径。吉林大学路径。吉林大学对长春市各春市各类驾驶员进行了行了驾驶员路径路径选择偏好抽偏好抽样问卷卷调查，得出，得出驾驶员对不同路不同路线类型的偏好程度如型的偏好程度如图2所示所示:基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法从从图图中看出中看出驾驶员驾驶员在路径在路径选择时选择时比比较较看重看重时间时间、距离、距离、费费用、用、道路等道路等级级和和拥挤拥挤程度。在所有程度。在所有这这些可供些可供选择选择因素中可以分因素中可以分为为优优性服性服务务因素因素(指数指数值值越大或越多，出行者的越大或越多，出行者的满满意程度就越高意程度就越高的因素，如路段速度、道路等的因素，如路段速度、道路等级级、路面、路面质质量、熟悉程度等量、熟悉程度等)和和劣性服劣性服务务因素因素(指数指数值值越小或越少，出行者的越小或越少，出行者的满满意程度就越高意程度就越高的因素，如的因素，如时间时间、距离，、距离，费费用等用等)。为为便于便于讨论讨论，本文，本文选选取其中取其中驾驶员驾驶员最最为为关心的关心的几几类类因素，由因素，由于耗油、收于耗油、收费费以及以及拥挤拥挤程度等可以通程度等可以通过时过时间变变相的反相的反应应出来，出来，故本文故本文仅仅从从优优性服性服务务因素中因素中选选取道路等取道路等级级，劣性服，劣性服务务因素中因素中选选取取时问时问和距离来构造路径和距离来构造路径选择选择模型。模型。基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法驾驶员驾驶员路径路径选择选择模型模型:如果将如果将现实现实城市交通网城市交通网络络中的中的驾驶员对应驾驶员对应成一成一只只的只只的“蚂蚁蚂蚁”，那么我，那么我们们就可以把交通路网就可以把交通路网络的的动态动态路径路径选择问题选择问题同同蚂蚂蚁寻蚁寻径原理径原理联联系起来。其中出行起点代表系起来。其中出行起点代表蚁蚁穴，穴，终终点代表食物源。通点代表食物源。通过过释释放放“人工人工蚂蚁蚂蚁群群”创创建基于建基于蚂蚁蚂蚁方法的路径方法的路径选择选择模型。式模型。式(1)给给出了在出了在节节点点u中的中的“蚂蚁蚂蚁”k选择选择相相邻节邻节点点v的概率。的概率。基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法模型模型约约束条件束条件:驾驶员在在选择路径路径时，不但考，不但考虑备选路径的功能路径的功能性性质要要满足自己的个性偏好，通常足自己的个性偏好，通常还会会对备选路径提出一种硬性路径提出一种硬性要求，要求，这种要求往往是根据种要求往往是根据驾驶员本人的本人的经验积累而得的。累而得的。设l表表示路径示路径p上的路段，上的路段，dl表示路段表示路段l的的长度，度，fl表示路段表示路段l的道路等的道路等级，tl表示路段表示路段l的行的行驶时间。如果。如果驾驶员对路径路径p的期望的期望长度是度是d,期期望最差道路等望最差道路等级是是f,期望期望时间是是t，则有以下有以下约束条件束条件:基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法算法算法设计设计:(1)信息素初始化信息素初始化:“蚂蚁”在初始在初始选择出行路径出行路径时，对于每个于每个节点，点，选择各个相各个相邻节点的概率是相等的。因此，在初始化点的概率是相等的。因此，在初始化时，将，将路网的各路段信息素均路网的各路段信息素均赋值为T(为方便方便计算一般可取整数算一般可取整数)。(2)信息素刷新信息素刷新规则:2.1局部刷新局部刷新:当当“蚂蚁”经过路段路段(u、v)后，路段后，路段(u、v)上的信上的信息素按下列息素按下列规则刷新刷新:基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法2.2全局刷新全局刷新:当当“蚂蚁”到达目的到达目的节点后，从源点后，从源节点到目的点到目的节点点路网上各路段的信息素按下列路网上各路段的信息素按下列规则刷新刷新:基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法算法步算法步骤骤:当当驾驶员进行路径行路径选择时，会提出路径，会提出路径“请求求”，即即对上述模型中的上述模型中的、,d,t、f进行个性偏好行个性偏好设定。定。为了了记录蚂蚁行行驶的的时间、距离和、距离和经过各路段的道路等各路段的道路等级，分，分别设定一定一个个时间域域ant.t,一个距离域一个距离域ant.d和一个常数域和一个常数域ant.f。我我们假假设源源节点点为S，目的，目的节点点为D，在接到，在接到驾驶员路径清求之路径清求之后，后，对每条路段的信息素按初始化的信息素每条路段的信息素按初始化的信息素值进行初始化，然后行初始化，然后按以下步按以下步骤进行。行。选取取m只只蚂蚁进行分行分组。在源。在源节点点S以周期以周期(t)周期性周期性的的发送送蚂蚁，每只，每只蚂蚁从源点开始从源点开始寻找找觅食的下一食的下一节点点U，按公，按公式式(1)选取最大概率的路段作取最大概率的路段作为蚂蚁前前进的路段的路段;判断判断U是否等于是否等于D，如果，如果U不等于不等于D，则按式按式(1)选取最大概率取最大概率的路段来的路段来选择下一下一查询节点点Unect，进入下一步。否入下一步。否则顺序的序的提取提取蚂蚁所所经过的路径，并按全局刷新公式的路径，并按全局刷新公式(6)对路径的每一路路径的每一路段段进行刷新，算法行刷新，算法结束束;基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法判断公式判断公式(2),(3)是否是否满满足，若都足，若都满满足，将足，将蚂蚁发蚂蚁发送到送到节节点点队队。，同，同时时更新距离域更新距离域ant.d ant.d+d(U、Unext)、常数域、常数域aht.f min(aht.f,f(U,Unext)，并，并记录记录ant.tant.t+t(U,)，进进入下一步。否入下一步。否则则，按公式，按公式()选择选择次最大概率的次最大概率的路段来路段来选择选择下一下一查询节查询节点点Unext，重复步，重复步骤骤;判断公式判断公式(4是否是否满满足，若足，若满满足，利用局部刷新公式足，利用局部刷新公式(5刷新刷新所所经经路段上的信息素，以路段上的信息素，以节节点点Unest为为当前当前节节点，点，转转到步到步骤骤。否否则则，蚂蚁蚂蚁死亡死亡(丢丢弃本次弃本次蚂蚁蚂蚁分分组组)，并用公式，并用公式(5)刷新路段信息刷新路段信息素素强强度。度。判断判断k是否等于是否等于m，如果，如果km，算法，算法结结束，此束，此时时表明路网的交表明路网的交通状况比通状况比较较差。否差。否则则，转转到步到步骤骤，重复以上步，重复以上步骤骤。基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法算例算例:基于基于蚂蚁寻径原理的最径原理的最优路径路径选择算法算法结语：本文所提出的最本文所提出的最优路径路径选择方法建立于方法建立于蚂蚁寻径原理径原理基基础之上，因此承之上，因此承袭了了蚂蚁算法的算法的许多多优点。另外，点。另外，论文提文提出的模型能出的模型能够反映反映驾驶员的偏好，而且考的偏好，而且考虑了了驾驶员对路径路径选择的的“硬性要求硬性要求”，以此，以此为模型添加了相关模型添加了相关约束条件，更束条件，更符合符合驾驶员的心理特性和个性要求。的心理特性和个性要求。本文所提模型和方法有待本文所提模型和方法有待进进一步完善，可以考一步完善，可以考虑为虑为模型添模型添加更多更加更多更细细化的化的驾驶员驾驶员偏好因素或添加更多的偏好因素或添加更多的约约束条件以更束条件以更大范大范围围的的满满足不同足不同驾驶员驾驶员的个性偏好。此外，至于基于的个性偏好。此外，至于基于论论文文所述的路径所述的路径诱导诱导方式的仿真方式的仿真软软件有待件有待进进一步研究。一步研究。LogoLogoThank you谢谢观赏