改进的蚁群算法及其应用.ppt

改进的蚁群算法及其应用 改进的蚁群算法 带精英策略的蚂蚁系统 带精英策略的蚂蚁系统（Ant System with elitist strategy, ASelite）是最早的改进蚂蚁系统 带精英策略的蚂蚁系统 信息素根据下式进行更新 带精英策略的蚂蚁系统 上式中 表示精英蚂蚁引起的路径(i, j)上的信息素量的增加 蚁群系统 蚁群系统(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的 蚁群系统状态转移规则 一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s 蚁群系统状态转移规则 q是在[0,1]区间均匀分布的随机数 q0的大小决定了利用先验知识与探索新路径之间的相对重要性。 上述状态转移规则被称为伪随机比例规则 特点：倾向于选择短的且有着大量信息素的边作为移动方向 蚁群系统全局更新规则 只有全局最优的蚂蚁才被允许释放信息素 目的：使蚂蚁的有哪些信誉好的足球投注网站主要集中在当前循环为止所找出的最好路径的领域内 全局更新在所有蚂蚁都完成它们的路径之后执行，使用下式对所建立的路径进行更新 蚁群系统全局更新规则 为信息素挥发参数，0 1 蚁群系统局部更新规则 类似于蚁密和蚁量模型中的更新规则 蚂蚁应用下列局部更新规则对它们所经过的边进行激素更新 最大-最小蚂蚁系统 蚁群算法将蚂蚁的有哪些信誉好的足球投注网站行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种有哪些信誉好的足球投注网站方式会使早熟收敛行为更容易发生 最大-最小蚂蚁系统 MMAS和AS主要有三个方面不同： 为了充分利用循环最优解和到目前为止找出的最优解，在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁 为避免有哪些信誉好的足球投注网站的停滞，在每个解的元素上的的信息素轨迹量的值域范围被限制在 区间内 将信息素轨迹初始化为 信息素轨迹更新 在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹 经修改的轨迹更新规则如下： 信息素轨迹的限制 不管是选择迭代最优还是全局最优蚂蚁来进行信息素更新，都可能导致有哪些信誉好的足球投注网站的停滞。 停滞现象发生的原因：在每个选择点上一个选择的信息素轨迹量明显高于其他的选择。 避免停滞状态发生的方法：影响用来选择下一解元素的概率，它直接依赖于信息素轨迹和启发信息。通过限制信息素轨迹的影响，可以很容易地避免各信息素轨迹之间的差异过大。 信息素轨迹的限制 MMAS对信息素轨迹的最小值和最大值分别施加了 和 的限制，从而使得对所有信息素轨迹 ，有 信息素轨迹的限制 的选取 信息素轨迹的限制 在一个选择点上选择相应解元素的概率Pdec直接取决于 和 信息素轨迹的初始化 在第一次循环后所有信息素轨迹与 相一致 信息素轨迹的平滑化 基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力 蚁群算法的应用 混流装配线调度 问题描述 以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为单级SMMAL调度问题。 问题描述 i表示车型数的标号 n表示需要装配的车型数 m表示装配线上需要的零部件种类总数 p表示生产调度中子装配的标号 表示零部件p的理想使用速率 j表示车型调度结果(即排序位置)的标号 D表示在一个生产循环中需要组装的各种车型的总和 问题描述 di表示在一个生产循环中车型i的数量 bip表示生产每辆i车型需要零部件p的数量 表示在组装线调度中前j-1台车消耗零部件p的数量和 蚁群算法在SMMAL中的应用 假设有3种车型A、B、C排序，每个生产循环需A型车3辆，B型车2辆，C型车1辆，则每个循环共需生产6辆车。采用下图的有哪些信誉好的足球投注网站空间定义，列表示6个排序阶段，行表示有3种车型可以选择。蚁群算法就是不断改变圆圈的大小，最终寻找到满意的可行解。 简单SMMAL排序的有哪些信誉好的足球投注网站空间举例 经过若干次迭代之后，有哪些信誉好的足球投注网站空间变化，此时最可能的可行解为B-A-C-A-B-A 局部有哪些信誉好的足球投注网站( )的计算 状态转移概率 状态转移概率公式如下 信息素更新规则 LB表示目标函数的下限值 表示当前目标函数的平均值 Zcutr表示当前的目标函数值 这种动态标记的方法可在有哪些信誉好的足球投注网站过程中加大可行解间信息素的差别，避免算法早熟 实验数据 实验参数设置 蚂蚁系统 蚂蚁数量N_ant = 5 最大循环周期Ncmax = 400 = 0.2 Q = 20000 = 0.9 LB = 0.0 实验参数设置 最大-最小蚂蚁系统 选取全局最优解 实验结果 实验结果