蚂蚁算法2015ppt课件

蚂蚁算法AntColonyOptimization 蚂蚁算法 蚂蚁算法的原理 特点蚂蚁算法的模型蚂蚁算法的研究进展蚂蚁算法求解TSP问题 蚂蚁的生物特征 用于优化领域的人工蚂蚁算法 其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征 1 察觉小范围区域内状况并判断出是否有食物或其他同类的信息素轨迹 2 释放自己的信息素 3 所遗留的信息素数量会随时间而逐步减少 图2 1蚂蚁从蚁穴 Nest 移至食物源 Food 图2 2在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程 蚂蚁算法的原理 蚂蚁在寻找食物源时 能在其走过的路上释放一种特殊的分泌物 信息素 随着时间的推移该物质会逐渐挥发 后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比 当一定路径上通过的蚂蚁越来越多时 其留下的信息素轨迹也越来越多 后来蚂蚁选择该路径的概率也越高 从而更增加了该路径的信息素强度 而强度大的信息素会吸引更多的蚂蚁 从而形成一种正反馈机制 通过这种正反馈机制 蚂蚁最终可以发现最短路径 特别地 当蚂蚁巢穴与食物源之间出现障碍物时 蚂蚁不仅可以绕过障碍物 而且通过蚁群信息素轨迹在不同路径上的变化 经过一段时间的正反馈 最终收敛到最短路径上 蚂蚁算法符号的定义 信息素轨迹的持久性 可理解为轨迹衰减度 evaporation 体现蚂蚁所留轨迹数量的一个常数 可行结点集合 为第k只蚂蚁在第结点i出发下一步的可行结点集 一个列表 用于记录第k只蚂蚁到目前为止已经访问的城市 蚂蚁算法求解的一般步骤 第1步 初始化 NC 0 将m只蚂蚁置于n个顶点上 第2步 将各蚂蚁的初始出发点置于当前解集中 对每一个蚂蚁k 按概率P选择移至下一顶点j上 将顶点j置于当前解集 第3步 计算各蚂蚁的目标函数值 记录当前的最好解 第4步 按更新方程修改信息素轨迹强度 第5步 对各边弧 NC NC 1 第6步 若搜索次数NC 预定迭代次数且无退化行为 即找到的都是相同解 则转第二步 第7步 输出目前的最好解 AS模型 AntSystem简称AS 蚂蚁系统 AS 是第一个蚁群优化算法 ACO 它是意大利科学家Dorigo在1991年最先提出 并成功地用于求解著名的组合爆炸问题TSP问题 后经他本人 1992 1996 2000 及学者Colorni Maniezzo 1997 1999 等进一步研究 将其系统化 其主要参数变量表达如下 选择概率 信息素更新方程为 按的不同取法 可形成三种类型的蚂蚁算法模型 1 蚂蚁密度模型 AntDensity 2 蚂蚁数量模型 AntQuantity 3 蚂蚁圈模型 AntCycle 其中 可行结点集合 具体应用中经常用表示 为第k只蚂蚁在第i结点出发下一步的可行结点集 TSP问题应去掉第k只蚂蚁已经过的结点 为第k只蚂蚁在本次循环中所走的路径的长度 上述三种模型中 蚂蚁密度模型和蚂蚁数量模型利用的是局部信息 而蚂蚁圈模型利用的是全局信息 对全局优化较好 Ant Q模型 Gambardella与Dorigo等学者在1995年 1996年运用Q leaning思想对AS算法进行了修改 其状态转移的规则如下 这里是均匀分布于 0 1 区间的一个随机变量 是个参数 V是按照下列三种规则决定的一个随机变量 1 Pseudo Random规则 V按照均匀分布选择 2 Pseudo Random Proportional规则 V按照下面概率选择 3 Random Proportional规则 设置为0 基于概率分布进行所有的决策 信息素轨迹更新方程为 这里 在初始化或求解最好结果路径上信息素增量 下一状态增加信息素相对最大值的比例是 ACS AntColonySystem 模型 Dorigo与Gambardella等学者在1997年在Ant Q算法的基础上进行修改 为了平衡寻找更好结果和寻找更大的搜索空间 Pseudo Random Proportionalrule下状态转移如下 V按照下面概率选择这里是将Ant Q模型中 更重要地是给出了局部在线和全局离线的两种信息素轨迹更新方式 LocalUpdating onlineupdating GlobalUpdating offlineupdating 这里的可以是 0 仅对最短路径的信息素增加量 局部更新用于每一时刻每一蚂蚁的每一步移动之中 而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果进行信息素轨迹更新 MMAS Max MinAntSystem 模型 为避免停滞和陷入局部 Stutzle和Hoos提出了MAX MINAntSystem 简称MMAS 模型 它对AS进行了三点改进 1 为了更加充分地寻优 各路径信息素初值设为最大值 2 一圈中只有最短路径的蚂蚁才进行信息素修改增加 这与AS蚂蚁圈模型调整方法相似 3 为了避免算法过早收敛非全局最优解 将各路经的信息素浓度限制在于之间 即 超出这个范围的值被强制设为或者 从实验结果看 MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进 ANTS模型 1998年Mainezzo提出求解QAP的改进蚂蚁算法 主要内容为 1 是具有下界的估计值 2 状态选择的规则是 3 信息素更新不用遗失因子 是第k只蚂蚁优化值 是蚂蚁的平均值 是最低值 下界 几种模型的评价 随着蚂蚁算法发展 蚂蚁算法的模型越来越丰富 人们针对不同的问题设计不同的参数 如求解TSP问题时 表示两个城市之间的距离 在求解QAP问题时 表示流程与距离的关系 在求解SMTT时 是可以得到的启发数据 如等参数的选择也要根据不同问题做出不同选择 同时 基于问题进行轨迹更新方程的修改及概率选择的定义也是必要的 在蚂蚁算法的几种模型中 AS ACS MMAS三种具有重要的作用 AS AntSystem 模型的优点 AS AntSystem 是最早的伴随蚁群这个概念提出来的算法 它首先被成功地运用于TSP问题 虽然与目前已经发展完备的一些算法 如GA等 比较起来 基本蚁群算法计算量比较大 而且效果也并不一定更好 但是它的成功运用激起了人们对蚁群算法的极大兴趣 并吸引了一批研究人员从事蚁群算法的研究 AS的优点在于 1 正反馈 从而能迅速找到好的解决方法 2 分布式计算可以避免过早地收敛 3 强启发能在早期的寻优中迅速找到合适的解决方案 4 AS算法被成功地运用于许多能被表达为在图表上寻找最佳路径的问题 ACS与AS的主要区别 1 ACS算法中 蚂蚁在寻找最佳路径的过程中使用局部信息 即采用局部信息对信息素浓度进行调整 2 在所有进行寻优的蚂蚁结束路径寻找后 信息素的浓度会再一次调整 这次采用的是全局信息 而且只对过程中发现的最好路径上的信息素浓度进行加强 3 有一个状态传递机制 用于指导蚂蚁最初的寻优过程 并通过信息素的积累反映问题的目前状态 MMAS模型特点 MMAS MAX MINAntSystem 是到目前为止解决TSP QAP等问题最好的ACO类算法 和其他寻优算法比较起来 它仍然属于最好的解决方案之一 其特点在于 1 只对最佳路径增加信息素的浓度 从而更好地利用了历史信息 这与ACS算法的调整方案有点类似 2 为了避免算法过早收敛于并非全局最优的解 将各条路径可能的信息素浓度限制于 超出这个范围的值被强制设为或者是 可以有效地避免某条路径上的信息量远大于其余路径 使得所有的蚂蚁都集中到同一条路径上 从而使算法不再扩散 3 将各条路径上信息素的起始浓度设为 这样便可以更加充分地进行寻优 表2蚂蚁算法及其应用 表2蚂蚁算法及其应用 续 蚂蚁算法可研究问题 蚂蚁算法的研究与发展历史毕竟较短 还存在诸多问题 1 它的发展远没有形成完整的理论体系 2 模型对问题具有依赖性 研究者必须根据问题的特点选择和修正模型 3 算法的参数选择更多的是依靠实验和经验 没有定理或公认的确定方法 4 由于初始信息素匮乏 计算时间偏长 对实时应用不利 这些都表明其理论和实践方面有许多问题尚需更深入的研究 举例1 遗传算法与蚂蚁算法的融合 遗传算法具有快速随机的全局搜索能力 但不能很好地利用系统的反馈信息 当求解到一定范围时往往作大量无为的冗余迭代 求精确解效率低 蚂蚁系统是一种并行的分布式正反馈系统 它是通过信息素的累积和更新收敛于最优路径上 但初期信息素匮乏 初始求解速度慢 遗传算法与蚂蚁算法的融合模型 采用遗传算法生成初始信息素分布 利用蚂蚁算法反复迭代求精确解 以期达到优势互补 遗传算法的基本原理 图3 1简单遗传算法进化过程示例 种群 位串适应值排序101101101138 33110001110043 72011101010154 51011001001034 64 交叉位11000111000111010101 变异位11000101010111011100 新后代11000101010111001100 选择 交叉 变异 新后代 遗传算法的特点 遗传算法具有进化计算的所有特征 其优点是 1 具有大范围全局搜索的能力 与问题领域无关 2 搜索从群体出发 具有潜在的并行性 3 可进行多值比较 鲁棒性强 4 搜索使用评价函数启发 过程简单 5 使用概率机制进行迭代 具有随机性 6 具有可扩展性 容易与其它算法结合 但遗传算法在编码表示 适应度函数 选择策略 控制参数等方面还存在诸多问题 特别是 对于系统中的反馈信息利用不够 当求解到一定范围时往往作大量无为的冗余迭代 求精确解效率低 遗传算法与蚂蚁算法的融合思想 遗传算法与蚂蚁算法的融合 GeneticAlgorithm AntAlgorithm简称GAAA 其基本思想是汲取两种算法的优点 克服各自的缺陷 优势互补 在时间效率上优于蚂蚁算法 在求精解效率上优于遗传算法 是时间效率和求解效率都比较好的一种新的启发式方法 其基本思路是算法前过程采用遗传算法 充分利用遗传算法的快速性 随机性 全局收敛性 其结果是产生有关问题的初始信息素分布 算法后过程采用蚂蚁算法 在有一定初始信息素分布的情况下 充分利用蚂蚁算法并行性 正反馈性 求精解效率高等特点 GAAA算法总体框架与流程 图3 2GAAA算法总体框架 定义目标函数生成若干组优化解定义适应值函数转化为初始信息素分布 问题 遗传算法 蚂蚁算法 最好解 图3 3GAAA算法详细流图 GAAA中遗传算法的模型选择定义 GAAA中的遗传算法是基于优胜选择遗传算法的原理与定义 编码与适应值函数 如TSP问题 以城市的遍历次序作为遗传算法的编码 适应度函数取为哈密顿圈的长度的倒数 种群生成与染色体选择 利用随机函数生成一定数量的十进制实数编码种群 根据适应值函数选择准备进行交配的一对染色体父串 交叉算子 采用Davis提出的顺序交叉方法 变异算子 采用逆转变异方法 交叉算子 采用Davis提出的顺序交叉方法 先进行常规的双点交叉 在进行维持原有相对访问顺序的巡回路线修改 具体交叉如下 1 随机在父串上选择一个交配区域 如两父串选定为 old1 12 3456 789 old2 98 7654 321 2 将old2的交配区域加到old1前面 将old1的交配区域加到old2的前面 old1 7654 123456789 old2 3456 987654321 3 依次删除old1 old2 中与交配区相同的数码 得到最终的两子串 new1 765412389 new2 345698721变异算子 采用逆转变异方法 所谓 逆转 如染色体 1 2 3 4 5 6 在区间2 3和区间5 6处发生断裂 断裂片段又以反向顺序插入 于是逆转后的染色体变为 1 2 5 4 3 6 这里的 进化 是指逆转算子的单方向性 只有经逆转后 适应值有提高的才接受下来 否则逆转无效 GAAA中蚂蚁算法模型选择 GAAA中蚂蚁算法选择基于蚂蚁圈模型 Ant Cycle 和MMAS MAX MINAntSystem 算法 在吸取其各自优点的基础上并进行改进 具体来说 信息素更新方程 选择概率 每一蚂蚁圈信息素增加 各路径设置信息素初值 GAAA中遗传算法与蚂蚁算法对接 两种算法对接的关键是如何把遗传算法的结果转化为蚂蚁算法的信息素 信息素的初值设置 MMAS是把各路径信息素初值设为最大值 max 这里我们通过遗传算法得到了一定的路径信息素 所以把信息素的初值设置为 S C G这里 C是一个根据具体求解问题规模给定的一个信息素常数 相当于MMAS算法中的 min G是遗传算法求解结果转换的信息素值 信息素更新模型 采用蚂蚁圈模型进行信息素更新 即一圈中只有最短路径的蚂蚁才进行信息素修改增加 仿真实验分析 我们采用GAAA算法分别对典型的NP hard问题30城市TSP问题和中国CHN144城市问题进行了实验 GAAA中遗传算法迭代次数分别选定为30代和144代 蚂蚁算法中各路径信息素初值 C分别设为60和600 遗传算法求解结果转换的信息素值是经过路径加2和20 轨迹更新分别取 0 8 Q 1000和 0 9 Q 100000 表3 1 表3 2 表3 3 表3 4 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 10 图3 11 图3 12 图3 13是仿真实验结果 表3 1GAAA算法优化解数据逼近过程 表3 2GAAA算法随机求解的30个优化解值分布 图3 4GAAA算法一次随机遗传变异后产生的信息素分布 TSP30 图3 5GAAA算法找到的最优路径 TSP30 d 423 74 图3 6GAAA算法一次随机迭代求得最好结果 TSP30 d 424 46 图3 7GAAA算法一次随机迭代求得最好结果 TSP30 d 424 67 图3 8GAAA算法一次随机迭代求得最好结果 TSP30 d 424 69 图3 9GAAA算法一次随机迭代求得最好结果 TSP30 d 424 90 图3 10GAAA算法找到的最优路径 CHN144 d 30351 图3 11GAAA算法一次随机迭代求得最好结果 CHN144 d 30354 表3 3 GAAA算法的实验结果表3 4 基本蚂蚁算法的实验结果 图3 12GAAA一次随机求解过程 TSP30 图3 13GAAA一次随机求解过程 CHN144 算法及实例仿真结论 1 算法无论是优化性能还是时间性能 都取得了非常好的效果 2 算法由于在遗传算法中使用随机生成种群 不仅加快了蚂蚁算法的速度而且避免求精确解阶段陷入局部最优 3 遗传算法与蚂蚁算法的融合 对于蚂蚁算法中的参数调整大大减低 减少了大量盲目的试验次数 4 算法对TSP问题进行了仿真应用 对于其它NP问题同样具有借鉴作用 举例2 K均值聚类与蚁群算法结合 对于组合爆炸的NP类大规模TSP问题 任何单一的算法都会面临优化性能与时间性能的双重挑战 混合算法体现 分而治之 的思想 首先采用动态K均值聚类快速邻域分解 其次应用蚁群算法同时对分区并行优化计算 最后基于分区重心进行邻域全局连接 得到大规模TSP问题的满意解 实际工程中需要满意解 许多实际工程问题往往属于大规模TSP 例如VLSI芯片加工问题 对应于1 2 106城市TSP Korte 1988 X ray 对应于14000城市的TSP Blandetal 1989 电路板设计中的钻孔问题 对应于17000城市TSP Litke 1984 以及对应于442城市TSP的著名PCB442问题 Grotscheletal 1991 鉴于TSP的复杂性 任何单一的算法在处理这类大规模问题时都会面临优化性能和时间性能的双重挑战 而实际工程中往往不一味追求最优解 切实可行的满意解更为重要 邻域搜索的空间分解体现了 分而治之 的思想 其基本思路是 把整个问题通过一定的分类方法分解成若干小规模子集 对每一小规模子集运用较好优化算法并行求解 然后结合一定的连接方式将各子集连接起来 从而快速得到大规模问题的一个满意解 利用分解策略降低问题的求解复杂性 如m n个城市分为m个区 则空间容量就由 m n 大大缩小为m n 如果m个区并行计算 则m n个城市问题即化为n个城市问题 其复杂度大大降低 邻域搜索的空间分解体现了 分而治之 的思想 聚类方法 聚类是将数据对象分组成为多个类或簇 在同一个簇中的对象之间具有较高的相似度 而不同的簇中的对象差别较大 即对象根据最大化类内的相似性 最小化类间的相似性的原则进行聚类或分组 常用的聚类方法有 基于划分的方法 K 均值聚类 k Means K 中心聚类 k Medians CLARNS 基于层次的方法 CURE Chameleon BIRCH 基于密度的方法 DBSCAN OPTICS DENCLUS 基于网格的方法 STING CLIQUE WaveCluster 基于模型的方法 COBWEB CLASSIT AutoClass K Means K 均值 算法 K 均值聚类是比较基本 也是目前聚类分析中最常用 最广泛应用的一种迭代的方法 其核心思想是一个中心点可以代表一个类 在每次迭代过程中将对象归入到相距中心最近的一类中 然后重新计算类的中心 自到中心不再变化 具体来说 k 平均法以k为参数 把n个对象分为k个簇 以使簇内有较高的相似度而簇间相似度较低 相似度的计算根据一个簇中对象的平均值 看作簇的重心 来进行 这种方法首先根据要生成的簇的数目创建一个初始划分 然后采用迭代的重定位技术 通过对象在划分之间移动来改进划分 图4 1K Means算法示意图 K Means算法的特点 算法优点 1 速度快 它是一种启发式的方法 用每类的平均值来表示该类 这就大大降低了计算的复杂性 提高了运算速度 2 适合大规模数据集 其时间复杂度为 n是所有对象的数目 k是簇的数目 t是迭代的次数 而且通常k n t n 此时算法以局部最优结束 对处理大数据集 该算法是相对可伸缩的和高效率的 3 簇与簇之间区别明显时 效果较好 算法缺点 该方法只有在簇的平均值有定义的情况下才能使用 要求用户必须预先给出分类的数目k 对 噪声 和孤立点数据敏感 动态聚类邻域分区并行蚁群优化算法的设计思想 动态聚类邻域分区并行蚁群算法的核心是对复杂大规模问题采用 分而治之 的思想 具体来说就是 K均值动态聚类快速邻域分区方法把大规模TSP分成K个分区子集 对K个分区利用网络互连群计算机或多处理器计算机进行并行计算 利用K重心邻接方法进行全局连接 其目标函数为 这里为各分区TSP最优值 为各分区连接时的断开链 为各分区之间连接链 K均值动态聚类快速邻域分区方法 算法的动态处理流程为 给定分区之数K 算法终止条件 值 初始化 随机地把所有对象分配到K个非空的簇中 计算每个簇的平均值 并用该平均值作为该簇的重心或聚核 将每个对象根据与各个簇重心距离重新分配到它最近的簇中 若每个簇的重心误差大于给定的 转 计算K个重心的之间的距离 输出最终结果 包括终值K个重心值 它们之间的距离 属于每个K重心的邻域点及数量 在这里 我们取TSP的规模整除100整数值为K 算法终止准则规定为 K重心邻域连接方法 重心邻域连接方法的基本思路是 根据K均值动态快速邻域分区方法K个重心以及它们之间的距离 确定K个邻域的连接方式 根据相邻区域的重心连线中点值 或坐标 确定相邻区域的可能连接点集 根据并行蚂蚁圈算法求解的区域最优解 在两两邻域连接的可能点集中选择邻域内TSP圈的断开链和邻域间的连接链 为保持整个邻域连接后TSP圈封闭 K重心距离最远的两个相邻邻域不进行连接 分别对分区TSP最优值 断开链 连接链求和 得大规模TSP满意解 实例分析 用上述方法对Grotschel 442城市TSP问题进行实例分析 根据442城市规模 设置分区数K 4 迭代终止条件重心误差 0 02 计算可得 K1 K2 K3 K4的重心值 坐标 它们之间的距离以所属分区中的城市个数及具体城市 坐标 如表4 1和表4 2所示 K均值动态聚类邻域分区TSP 表4 1 聚类重心及所属城市数表4 2 聚类重心之间的距离 表4 3 各聚类分区TSP蚂蚁优化结果表4 4 各聚类分区蚂蚁优化迭代时间 t 并行蚂蚁圈算法同时求各分区TSP 图4 2各类分区TSP蚁群优化性能图4 3各类分区TSP蚁群优化时间性能 根据上述动态聚类分区 利用网络多处理器同时并行对各分区TSP求解 在这里初值设为 1 2 0 8 Q 1000 经过多次迭代的结果见表4 3 表4 4所示 其优化性能与时间性能见图4 2和图4 3 K重心全局邻接得TSP满意解 图4 4442城市TSP邻域分区简图 图4 5442城市TSP邻域分区并行蚁群优化全局连接图 结论 1 通过对于大规模TSP问题实例分析 提出的方法无论是优化性能还是时间性能 都取得了较满意的结果 具有实际工程应用价值 2 K均值动态聚类速度非常之快 因而 在降低大规模TSP问题难度的同时 并未增加额外的运算负担 3 邻域分区多少 K 与分区规模 每个分区中城市数 是影响优化速度和优化效果的重要指标 分区太多影响全局解的质量 分区太少分区内优化速度太慢 从蚂蚁优化算法分区计算过程来看 如果分区规模度在100城市左右 迭代300次 整体效果最好 举例3 基于蚂蚁算法的动态路由选择 蚂蚁算法具有很强的自适应性 将自适应蚂蚁算法 网络的容量限制 流量变化和最短距离结合起来讨论 通过在找到的最短路径上设置障碍物来模拟网络拥塞 找到 源结点 目的结点 的多条最优路由序列 以便在实际中实时地 自适应地进行动态路由选择 网络拥塞主要表现 1 带宽设计太窄 不能满足日益增长的用户需要 形成千军万马过独木桥的局面 2 网络有一定的带宽 由于多条路由不能相互平衡 造成局部特别最优路径上拥塞 3 由于突发性事件 如美国911事件 造成网络局部信息急剧膨胀 使得网络拥塞 上述第一种情况属于无法软克服 只有增加网络带宽和提高网络速度 第三种情况可看作不可抗拒突发性意外事件 出现机率很小 而第二种情况是网络正常运转过程中最常见的现象 但时间的随机性和地点的随机性 现有的方法往往很难克服 蚂蚁算法对动态路由选择都具有很强的针对性 蚂蚁算法是一种随机的离散化的启发式的优化方法 尤其是在蚁群寻优的过程中遇到障碍物时 不仅能避开障碍物 而且能够利用其正反馈机制 或称增强型学习系统 自适应的重新寻找最优路径 并且其寻优过程就是蚁群移动过程中信息素的数量积聚过程 因而 无论从蚂蚁算法的过程 以及蚂蚁算法的所形成的机制和效果来看 用于处理当前网络的流量分配和拥塞控制以及动态路由选择都具有很强的针对性 动态最优路由选择 动态最优路由选择前提是 即针对不同的 源结点 目的结点 建立多目标路由表 路由表由最短路径的序列组成 当首选最短路径出现拥塞时 动态的自动选择次最短路径 以此类推 从而达到整个网络的正常运行和处于最佳状态 自适应蚂蚁算法构造思想 构造自适应蚂蚁算法思路是 在求解 源结点 目的结点 最短路径过程中 实时考虑网络每段路径上的容量限制和流量变化 即求解到的 源结点 目的结点 最短路径所有路段容量减去其最小路段容量 亦即最短路径上的瓶颈路段容量置0 即路段中断 其它路段减去瓶颈路段容量 而非最短路径的容量保持不变 因而利用蚂蚁算法的自适应性 可以求得 源结点 目的结点 次最短路径 如