蚂蚁寻路原理实例分析PPT课件

基于蚂蚁算法的实例分析 航空工程学院 吴鹏 Logo 蚂蚁寻径原理 目录 1 基于蚂蚁算法的中国邮路问题 2 基于蚂蚁寻径原理的最优路径选择算法 3 Logo 蚂蚁寻径原理 通过昆虫学家的研究和观察 蚂蚁在运动中 会在经过的路径上留下一种挥发性分泌物 信息素 这种分泌物随时间推移会逐渐挥发消失 周围蚂蚁能感知这种物质的存在及浓度 并倾向于朝信息素浓度高的方向移动 即选择该路径概率与当时这条路径上该物质的浓度成正比 信息素浓度越高的路径 选择它的蚂蚁就越多 在该路径上留下的信息素的浓度就更大 而浓度大的信息素又吸引更多的蚂蚁 从而形成一种正反馈 通过这种正反馈机制 蚂蚁最终可以发现最佳路径 蚂蚁寻径原理 图一蚂蚁寻径原理 基于蚂蚁算法的中国邮路问题 中国邮路问题 是由我国的管梅谷提出的一种图的极值问题 又被称为 中国邮递员问题 即一个邮递员负责某一个地区的信件投递 每天从邮局出发 走遍该地区所有的街道再返回邮局的最短路径 基于蚂蚁算法的中国邮路问题 算法描述 中国邮递员问题求解的关键是对图中奇数度结点进行匹配 使得图中不存在奇数度结点 匹配原则要保证所添加的边的权值之和最小 然后再寻找出以某个固定点为起始点和终点的一条最短路径 基于蚂蚁算法的中国邮路问题 选择概率 按照蚂蚁算法的思想 设邮局位于结点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 8s 实验图2平均耗时17 8s 总的来说 算法的效率是可以接受的 基于蚂蚁算法的中国邮路问题 结束语 基于蚂蚁算法的中国邮路问题介绍了一种智能求解中国邮路问题的算法 和其他算法相比 算法设计简单 易于实现 且能够在短时间内找到最优解 同时 算法中最优线路的构造方法也适合于其他求解最优路的问题 如机器人的路经规划问题 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 t ant t t U 进入下一步 否则 按公式 选择次最大概率的路段来选择下一查询节点U next 重复步骤 判断公式 4 是否满足 若满足 利用局部刷新公式 5 刷新所经路段上的信息素 以节点Unest为当前节点 转到步骤 否则 蚂蚁死亡 丢弃本次蚂蚁分组 并用公式 5 刷新路段信息素强度 判断k是否等于m 如果k m 算法结束 此时表明路网的交通状况比较差 否则 转到步骤 重复以上步骤 基于蚂蚁寻径原理的最优路径选择算法 算例 基于蚂蚁寻径原理的最优路径选择算法 结语 本文所提出的最优路径选择方法建立于蚂蚁寻径原理基础之上 因此承袭了