智能算法AntAlgorithm

改进的蚁群算法及其应用 改进的蚁群算法 Macro Dorigo Gambardella 带精英策略的蚂蚁系统 带精英策略的蚂蚁系统（ Ant System with elitist strategy, ASelite）是最早的改进蚂蚁系统 遗传算法中的精英策略 传统的遗传算法可能会导致最适应个体的遗传信息丢失 精英策略的思想是保留住一代中的最适应个体 蚂蚁系统中的精英策略 每次循环之后给予最优解以额外的信息素量 这样的解被称为 全局最优解 （ global-best solution） 找出这个解的蚂蚁被称为 精英蚂蚁 (elitist ants) 带精英策略的蚂蚁系统 信息素根据下式进行更新 *( 1 ) ( )ij ij ij ijtt 1 m k ij ij k 其中 , 0, k kij Q k L 如 果 蚂 蚁 在 本 次 循 环 中 经 过 路 径 (i,j) 否 则 * * , 0, ij Q L 如 果 边 (i,j) 是 所 找 出 的 最 优 解 的 一 部 分 否 则 带精英策略的蚂蚁系统 上式中 表示精英蚂蚁引起的路径 (i, j)上的信息素量 的增加 * *L 特点： 可以使蚂蚁系统找出更优的解 找到这些解的时间更短 精英蚂蚁过多会导致搜索早熟收敛 是精英蚂蚁的个数 是所找出的最优解的路径长度 蚁群系统 蚁群系统 (Ant Colony System, ACS)是由 Dorigo和 Gambardella在 1996年提出的 蚁群系统做了三个方面的改进： 状态转移规则为更好更合理地利用新路径和利用关于问 题的先验知识提供了方法 全局更新规则只应用于最优的蚂蚁路径上 在建立问题解决方案的过程中，应用局部信息素更新规 则 蚁群系统状态转移规则 一只位于节点 r的蚂蚁通过应用下式给出的规则选 择下一个将要移动到的城市 s 0a r g m a x ( , ) ( , ) , , ku allowe d r u r u q q s S 如 果 按 先 验 知 识 选 择 路 径 否 则 其中， S根据下列公式得到 ( ) ( ) , ( ) ( )() 0, k ij ij k k is is ij s all ow e d tt j al l ow e d ttPt ot he rw i se 蚁群系统状态转移规则 q是在 0,1区间均匀分布的随机数 q0的大小决定了利用先验知识与探索新路径 之间的相对重要性。 上述状态转移规则被称为 伪随机比例规则 特点： 倾向于选择短的且有着大量信息素的 边作为移动方向 蚁群系统全局更新规则 只有全局最优的蚂蚁才被允许释放信息素 目的：使蚂蚁的搜索主要集中在当前循环为止所找 出的最好路径的领域内 全局更新在所有蚂蚁都完成它们的路径之后执行， 使用下式对所建立的路径进行更新 ( , ) ( 1 ) ( , ) ( , )r s r s r s 1 , ( , ) 0, gbLrs 如 果 (r,s) 全 局 最 优 路 径 否 则 蚁群系统全局更新规则 为信息素挥发参数， 0 1 为到目前为止找出的全局最优路径 gbL 全局更新规则的另一个类型称为迭代最优 区别 :使用 代替 ， 为当前迭代 (循环 )中的最优路径 长度 这两种类型对蚁群系统性能的影响差别很小，全局最优 的性能要稍微好一些 gbL ibLibL 蚁群系统局部更新规则 类似于蚁密和蚁量模型中的更新规则 蚂蚁应用下列局部更新规则对它们所经过的边进行 激素更新 ( , ) ( 1 ) ( , ) ( , ) 01 r s r s r s 其 中 , 为 一 个 参 数 , 0 1 nnnL 实验发现， 可以产生好的结果，其中 n是城 市的数量， 是由最近的邻域启发产生的一个路径 长度 nnL 局部更新规则可以有效地避免蚂蚁收敛到同一路径 最大 -最小蚂蚁系统 蚁群算法将蚂蚁的搜索行为集中到最优解的 附近可以提高解的质量和收敛速度，从而改 进算法的性能。但这种搜索方式会使 早熟收 敛 行为更容易发生 最大 -最小蚂蚁系统 (Max-Min Ant System, MMAS)能将这种搜索方式和一种能够 有效避 免早熟收敛 的机制结合在一起，从而使算法 获得最优的性能 最大 -最小蚂蚁系统 MMAS和 AS主要有三个方面不同： 为了充分利用循环最优解和到目前为止找出的最优 解，在每次循环之后，只有一只蚂蚁进行信息素更 新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁， 也可能是找出从实验开始以来最优解的蚂蚁 为避免搜索的停滞，在每个解的元素上的的信息素 轨迹量的值域范围被限制在 区间内 将信息素轨迹初始化为 max min max , 信息素轨迹更新 在 MMAS中，只有一只蚂蚁用于在每次循环后更新 信息轨迹 经修改的轨迹更新规则如下： ( 1 ) ( ) ijb e s tij ijtt 1 ( )ijb e s t b e s tfs 表示迭代最优解或全局最优解的值 在蚁群算法中主要使用全局最优解，而在 MMAS中 则主要使用迭代最优解 ()bestfs 信息素轨迹的限制 不管是选择迭代最优还是全局最优蚂蚁来进 行信息素更新，都可能导致搜索的停滞。 停滞现象发生的原因 ：在每个选择点上一个 选择的信息素轨迹量明显高于其他的选择。 避免停滞状态发生的方法 ：影响用来选择下 一解元素的概率，它直接依赖于信息素轨迹 和启发信息。通过限制信息素轨迹的影响， 可以很容易地避免各信息素轨迹之间的差异 过大。 信息素轨迹的限制 MMAS对信息素轨迹的最小值和最大值分别施加 了 和 的限制，从而使得对所有信息素轨 迹 ，有 min max ()ij t m in m a x()ij t MMAS收敛 ：在每个选择点上，其中一个解元素 上的轨迹量为 ，而所有其他可选择的解元素上 的轨迹量为 。 min max 若 MMAS收敛，通过始终选择信息素量最大的解 元素所构造的解将与算法找出的最优解相一致 信息素轨迹的限制 的选取 max m a x 1 1() ()ij t ti opt i t fs opt其 中 , f ( s ) 为 对 于 一 个 具 体 问 题 的 最 优 解 g b o p t渐 进 的 最 大 值 估 计 通 过 使 用 f ( s ) 代 替 f ( s ) 来 实 现 的选取要基于 两点假设 最优解在搜索停滞发生之前不久被找出 对解构造的主要影响是由信息素轨迹的上限与下限之间 的相对差异决定 min 信息素轨迹的限制 在一个选择点上选择相应解元素的概率 Pdec直接取 决于 和 min max 在每个选择点上蚂蚁需在 avg=n/2个解元素中选择 m a x m a x m in( 1 ) de cP av g 蚂蚁构造最优解，需作 n次正确的决策 de c n be stPP m a xm a x m in ( 1 )( 1 ) ( 1 ) ( 1 ) n b e s td e c nd e c b e s t PP a v g P a v g P 信息素轨迹的初始化 在第一次循环后所有信息素轨迹与 相一致 max(1) 通过选择对这种类型的轨迹初始化来增加在算法的 第一次循环期间对新解的探索 当将信息素轨迹初始化为 时，选择概率将增加 得更加缓慢 实验表明，将初始值设为 可以改善最大 - 最小蚂蚁系统的性能 max m ax(1) 信息素轨迹的平滑化 基本思想 ：通过增加选择有着低强度信息素轨迹量 解元素的概率以提高探索新解的能力 * m a x( ) ( ) ( ( ) ( ) )ij ij ijt t t t *( ) ( ) ij ijtt 其 中 , 0 1 , 和 分 别 为 平 滑 化 之 前 和 之 后 的 信 息 素 轨 迹 量 平滑机制有助于对搜索空间进行更有效的探索 蚁群算法的应用 混流装配线调度 混流装配线 (sequencing mixed models on an assembly line, SMMAL)是指一定时间内，在一 条生产线上生产出多种不同型号的产品，产品的品 种可以随顾客需求的变化而变化。 SMMAL是车间 作业调度问题 (job-shop scheduling problem, JSP)的具体应用之一。 问题描述 以汽车组装为例，即在组装所有车辆的过程中，所 确定的组装顺序应使各零部件的使用速率均匀化。 如果不同型号的汽车消耗零部件的种类大致相同， 那么原问题可简化为单级 SMMAL调度问题。 2 1, 1 1 1 m in ( ) D n m p ip j p ji j i p j b x 1, 0,ji ijx 如 果 车 型 在 调 度 中 的 位 置 否 则 i ip i p db D 问题描述 i表示车型数的标号 n表示需要装配的车型数 m表示装配线上需要的零部件种类总数 p表示生产调度中子装配的标号 表示零部件 p的理想使用速率 j表示车型调度结果 (即排序位置 )的标号 D表示在一个生产循环中需要组装的各种车型的 总和 p 问题描述 di表示在一个生产循环中车型 i的数量 bip表示生产每辆 i车型需要零部件 p的数量 表示在组装线调度中前 j-1台车消耗零部件 p的 数量和 1 , 0 ,0j p j p j i i p pxb 且 1,jp 蚁群算法在 SMMAL中的应用 假设有 3种车型 A、 B、 C排序，每个生产循环需 A型车 3 辆， B型车 2辆， C型车 1辆，则每个循环共需生产 6辆 车。采用下图的搜索空间定义，列表示 6个排序阶段， 行表示有 3种车型可以选择。蚁群算法就是不断改变圆 圈的大小，最终寻找到满意的可行解。 搜索的初始状态 简单 SMMAL排序的搜索空间举例 经过若干次迭代之后，搜索空间变化，此时 最可能的可行解为 B-A-C-A-B-A 若干次迭代后的状态 局部搜索 ( )的计算 ij 2 1, 1 () ij m p ip k p p Q jb 局部搜索 采用的是贪心策略 ij 基本思路：每一步均从当前可选择策略中选 取，使目标函数值增加最少的策略，即在确 定第 j个位置组装的车型时，如果有多种车 型可供选择，则从中选择一种车型 i，使第 j 个位置组装车型 i时各零部件的使用速率最 为均匀。 状态转移概率 状态转移概率公式如下 ( 1 ) , ( 1 )() 0, k ij ij k k ij ij ij j tabu i tabu pt 若 否 则 信息素更新规则 LB表示目标函数的下限值 表示当前目标函数的平均值 Zcutr表示当前的目标函数值 这种动态标记的方法可在搜索过程中加大可行解间信息素的 差别，避免算法早熟 Z 0 ( 1 ) , 0, c utr k ij Z L B ij Z L B 如 果 车 型 在 调 度 中 的 位 置 否 则 _ 1 n an t k ij ij k ( ) ( 1 ) ( )ij ij ijt n t 实验数据 实验参数设置 蚂蚁系统 蚂蚁数量 N_ant = 5 最大循环周期 Ncmax = 400 = 0.2 Q = 20000 = 0.9 LB = 0.0 蚁群系统 q0 = 0.5 全局更新规则中的 和局部更新规则中的 均取 0.1 实验参数设置 最大 -最小蚂蚁系统 选取全局最优解 ()bestfs m in 0 m a x 0 0 , 1 , L DL 是 利 用 贪 心 策 略 算 得 的 目 标 函 数 值 带有精英策略的蚂蚁系统 精英蚂蚁数量 :1只 实验结果 实验结果分析 直接用贪心策略求解结果： 3293.4375 蚂蚁系统求解 SMMAL问题的性能较差 对于这个具体的问题，带精英策略的蚂蚁系 统的求解性能并 不好于 蚂蚁系统 蚁群系统的性能相对于前两者而言，有了很 大幅度的提高 最大 -最小蚂蚁系统的性能最好，大多数情 况下的求解结果已达到实际的最优解 实验界面 实验界面 蚁群系统在 TSP问题中的应用 10城市 TSP问题 20城市 TSP问题 蚁群系统在 TSP问题中的应用 30城市 TSP问题 48城市 TSP问题 Questions