《蚁群算法简述》PPT课件.ppt

蚁群算法简述 1 蚁群算法的提出2 蚁群算法的特征3 蚁群算法的数学模型4 蚁群算法的模型类型5 蚁群算法的优缺点6 蚁群算法所解决的问题7 蚁群算法的应用8 蚁群算法的研究方向 发展方向 1 蚁群算法的提出 算法的提出蚁群算法 AntColonyOptimization ACO 又称蚂蚁算法 一种用来在图中寻找优化路径的机率型算法 它由MarcoDorigo于1992年在他的博士论文 Antsystem optimizationbyacolonyofcooperatingagents 中提出 其灵感来源于蚂蚁在寻找食物过程中发现路径的行为 最早用于解决著名的旅行商问题 TSP travelingsalesmanproblem 1 蚁群算法的提出 概念原型各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物 当一只找到食物以后 它会向环境释放一种挥发性分泌物pheromone 称为信息素 该物质随着时间的推移会逐渐挥发消失 信息素浓度的大小表征路径的远近 来实现的 吸引其他的蚂蚁过来 这样越来越多的蚂蚁会找到食物 有些蚂蚁并没有象其它蚂蚁一样总重复同样的路 他们会另辟蹊径 如果另开辟的道路比原来的其他道路更短 那么 渐渐地 更多的蚂蚁被吸引到这条较短的路上来 最后 经过一段时间运行 就可能会出现一条最短的路径被大多数蚂蚁重复着 1 蚁群算法的提出 基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法 蚂蚁在运动过程中 能够在它所经过的路径上留下一种称之为外激素 pheromone 的物质进行信息传递 而且蚂蚁在运动过程中能够感知这种物质 并以此指导自己的运动方向 因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象 某一路径上走过的蚂蚁越多 则后来者选择该路径的概率就越大 1 蚁群算法的提出 简化的蚂蚁寻食过程蚂蚁从A点出发 速度相同 食物在D点 可能随机选择路线ABD或ACD 假设初始时每条分配路线一只蚂蚁 每个时间单位行走一步 本图为经过9个时间单位时的情形 走ABD的蚂蚁到达终点 而走ACD的蚂蚁刚好走到C点 为一半路程 1 蚁群算法的提出 本图为从开始算起 经过18个时间单位时的情形 走ABD的蚂蚁到达终点后得到食物又返回了起点A 而走ACD的蚂蚁刚好走到D点 1 蚁群算法的提出 假设蚂蚁每经过一处所留下的信息素为一个单位 则经过36个时间单位后 所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物 此时ABD的路线往返了2趟 每一处的信息素为4个单位 而ACD的路线往返了一趟 每一处的信息素为2个单位 其比值为2 1 寻找食物的过程继续进行 则按信息素的指导 蚁群在ABD路线上增派一只蚂蚁 共2只 而ACD路线上仍然为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素单位积累为12和4 比值为3 1 若按以上规则继续 蚁群在ABD路线上再增派一只蚂蚁 共3只 而ACD路线上仍然为一只蚂蚁 再经过36个时间单位后 两条线路上的信息素单位积累为24和6 比值为4 1 若继续进行 则按信息素的指导 最终所有的蚂蚁会放弃ACD路线 而都选择ABD路线 这也就是前面所提到的正反馈效应 1 蚁群算法的提出 人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题 可以构造人工蚁群 来解决最优化问题 如TSP问题 人工蚁群中把具有简单功能的工作单元看作蚂蚁 二者的相似之处在于都是优先选择信息素浓度大的路径 较短路径的信息素浓度高 所以能够最终被所有蚂蚁选择 也就是最终的优化结果 两者的区别在于人工蚁群有一定的记忆能力 能够记忆已经访问过的节点 同时 人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径 而不是盲目的 例如在TSP问题中 可以预先知道当前城市到下一个目的地的距离 1 蚁群算法的提出 1 标有距离的路径图2 在0时刻 路径上没有信息素累积 蚂蚁选择路径为任意3 在1时刻 路径上信息素堆积 短边信息素多与长边 所以蚂蚁更倾向于选择ABCDE 2 蚁群算法的特征 蚁群算法采用了分布式正反馈并行计算机制 易于与其他方法结合 并具有较强的鲁棒性 1 其原理是一种正反馈机制或称增强型学习系统 它通过信息素的不断更新达到最终收敛于最优路径上 2 它是一种通用型随机优化方法 但人工蚂蚁决不是对实际蚂蚁的一种简单模拟 它融进了人类的智能 3 它是一种分布式的优化方法 不仅适合目前的串行计算机 而且适合未来的并行计算机 4 它是一种全局优化的方法 不仅可用于求解单目标优化问题 而且可用于求解多目标优化问题 5 它是一种启发式算法 计算复杂性为O NC m n2 其中NC是迭代次数 m是蚂蚁数目 n是目的节点数目 2 蚁群算法的特征 下面是对蚁群算法的进行过程中采用的规则进行的一些说明 范围蚂蚁观察到的范围是一个方格世界 蚂蚁有一个参数为速度半径 一般是3 那么它能观察到的范围就是3 3个方格世界 并且能移动的距离也在这个范围之内 环境蚂蚁所在的环境是一个虚拟的世界 其中有障碍物 有别的蚂蚁 还有信息素 信息素有两种 一种是找到食物的蚂蚁洒下的食物信息素 一种是找到窝的蚂蚁洒下的窝的信息素 每个蚂蚁都仅仅能感知它范围内的环境信息 环境以一定的速率让信息素消失 觅食规则在每只蚂蚁能感知的范围内寻找是否有食物 如果有就直接过去 否则看是否有信息素 并且比较在能感知的范围内哪一点的信息素最多 这样 它就朝信息素多的地方走 并且每只蚂蚁都会以小概率犯错误 从而并不是往信息素最多的点移动 蚂蚁找窝的规则和上面一样 只不过它对窝的信息素做出反应 而对食物信息素没反应 2 蚁群算法的特征 移动规则每只蚂蚁都朝向信息素最多的方向移 并且 当周围没有信息素指引的时候 蚂蚁会按照自己原来运动的方向惯性的运动下去 并且 在运动的方向有一个随机的小的扰动 为了防止蚂蚁原地转圈 它会记住刚才走过了哪些点 如果发现要走的下一点已经在之前走过了 它就会尽量避开 避障规则如果蚂蚁要移动的方向有障碍物挡住 它会随机的选择另一个方向 并且有信息素指引的话 它会按照觅食的规则行为 信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多 并随着它走远的距离 播撒的信息素越来越少 根据这几条规则 蚂蚁之间并没有直接的关系 但是每只蚂蚁都和环境发生交互 而通过信息素这个纽带 实际上把各个蚂蚁之间关联起来了 比如 当一只蚂蚁找到了食物 它并没有直接告诉其它蚂蚁这儿有食物 而是向环境播撒信息素 当其它的蚂蚁经过它附近的时候 就会感觉到信息素的存在 进而根据信息素的指引找到了食物 2 蚁群算法的特征 基本蚁群算法流程图 详细 1 在初始状态下 一群蚂蚁外出 此时没有信息素 那么各自会随机的选择一条路径 2 在下一个状态 每只蚂蚁到达了不同的点 从初始点到这些点之间留下了信息素 蚂蚁继续走 已经到达目标的蚂蚁开始返回 与此同时 下一批蚂蚁出动 它们都会按照各条路径上信息素的多少选择路线 selection 更倾向于选择信息素多的路径走 当然也有随机性 3 又到了再下一个状态 刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了 evaporation 而刚刚经过了蚂蚁的路线信息素增强 reinforcement 然后又出动一批蚂蚁 重复第2个步骤 每个状态到下一个状态的变化称为一次迭代 在迭代多次过后 就会有某一条路径上的信息素明显多于其它路径 这通常就是一条最优路径 3 蚁群算法的数学模型 一般蚁群算法的框架主要有三个组成部分 蚁群的活动 信息素的挥发 信息素的增强 主要体现在转移概率公式和信息素更新公式 3 蚁群算法的数学模型 蚁群算法数学模型在路径搜索过程中 蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移 蚂蚁 在 时刻由节点 转移到节点 的状态转移概率如式所示 3 蚁群算法的数学模型 另外 为了避免残留信息素过多引起残留信息淹没启发信息 在每只蚂蚁走完一步或者完成对所有n个元素的遍历后 要对残留信息进行更新处理 由此 t n时刻在路径 i j 上的信息量可按如下规则进行调整其更新规则如下式所示 由于信息素更新策略的不同 以及城市规模取值在适当范围时 全局搜索能使之得到更优的解 因此采用全局信息素更新规则 形式如下 式中 Q表示蚂蚁循环一周 且在一定程度上影响算法收敛速度的信息素总量 Lk表示本次循环中 蚂蚁k所走路段的长度 3 蚁群算法的数学模型 蚁群的规模和停止规则蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数 终止条件 1给定一个外循环的最大数目 表明已经有足够的蚂蚁工作 2当前最优解连续K次相同而停止 其中K是一个给定的整数 表示算法已经收敛 不再需要继续 3目标值控制规则 给定优化问题 目标最小化 的一个下界和一个误差值 当算法得到的目标值同下界之差小于给定的误差值时 算法终止 4 蚁群算法的模型类型 根据信息素更新策略的不同 M Dorigo曾提出3种不同的基本蚁群算法模型 其差别在于 kij t 求法的不同 即 Ant Cycle模型Ant Quantity模型Ant Density模型其中Ant antity模型和Ant Density模型利用的是局部信息 而Ant Cycle模型利用的是整体信息 在求解TSP时性能较好 因此通常采用Ant Cycle模型作为蚁群算法的基本模型 4 蚁群算法的模型类型 Ant Cycle模型式中 Q表示信息素强度 它在一定程度上影响算法的收敛速度 Lk表示第k只蚂蚁在本次循环中所走路径的总长度 4 蚁群算法的模型类型 Ant Quantity模型Ant Density模型 4 蚁群算法的模型类型 区别后两个式子中利用的是局部信息 即蚂蚁完成一步后更新路径上的信息素 而第一个式中利用的是全局信息 即蚂蚁完成一个循环后更新所有路径上的信息素 在求解TSP时性能较好 因此通常采用第一个模型作为蚁群算法的基本模型 4 蚁群算法的模型类型 下面是一些最常用的变异蚁群算法1 精英蚂蚁系统全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素 2 最大最小蚂蚁系统 MMAS 添加的最大和最小的信息素量 max min 只有全局最佳或迭代最好的巡逻沉积的信息素 所有的边缘都被初始化为 max并且当接近停滞时重新初始化为 max 3 蚁群系统蚁群系统已被提出 4 基于排序的蚂蚁系统 ASrank 所有解决方案都根据其长度排名 然后为每个解决方案衡量信息素的沉积量 最短路径相比较长路径的解沉积了更多的信息素 5 连续正交蚁群 COAC COAC的信息素沉积机制能使蚂蚁协作而有效地寻解 利用正交设计方法 在可行域的蚂蚁可以使用增大的全局搜索能力和精度 快速 高效地探索他们选择的区域 正交设计方法和自适应半径调整方法也可推广到其他优化算法中 在解决实际问题施展更大的威力 5 蚁群算法的优缺点 蚁群算法的优点 蚁群算法与其他启发式算法相比 在求解性能上 具有很强的鲁棒性 对基本蚁群算法模型稍加修改 便可以应用于其他问题 和搜索较好解的能力 蚁群算法是一种基于种群的进化算法 具有本质并行性 易于并行实现 蚁群算法很容易与多种启发式算法结合 以改善算法性能 5 蚁群算法的优缺点 蚁群算法存在的问题 TSP问题是一类经典的组合优化问题 即在给定城市个数和各城市之间距离的条件下 找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线 蚁群算法在TSP问题应用中取得了良好的效果 但是也存在一些不足 1 如果参数设置不当 导致求解速度很慢且所得解的质量特别差 2 基本蚁群算法计算量大 求解所需时间较长 3 基本蚁群算法中理论上要求所有的蚂蚁选择同一路线 该线路即为所求的最优线路 但在实际计算中 在给定一定循环数的条件下很难达到这种情况 另一方面 在其它的实际应用中 如图像处理中寻求最优模板问题 我们并不要求所有的蚂蚁都找到最优模板 而只需要一只找到最优模板即可 如果要求所有的蚂蚁都找到最优模板 反而影响了计算效率 蚁群算法收敛速度慢 易陷入局部最优 蚁群算法中初始信息素匮乏 蚁群算法一般需要较长的搜索时间 其复杂度可以反映这一点 而且该方法容易出现停滞现象 即搜索进行到一定程度后 所有个体发现的解完全一致 不能对解空间进一步进行搜索 不利于发现更好的解 6 蚁群算法所解决的问题 调度问题车间作业调度问题 JSP 开放式车间调度问题 OSP 排列流水车间问题 PFSP 单机总延迟时间问题 SMTTP 单机总加权延迟问题 SMTWTP 资源受限项目调度问题 RCPSP 车间组调度问题 GSP 附带依赖安装时间顺序的单机总延迟问题 SMTTPDST 附带顺序相依设置 转换时间的多阶段流水车间调度问题 MFSP 车辆路径问题限量车辆路径问题 CVRP 多站车辆路径问题 MDVRP 周期车辆路径问题 PVRP 分批配送车辆路径问题 SDVRP 随机车辆路径问题 SVRP 装货配送的车辆路径问题 VRPPD 带有时间窗的车辆路径问题 VRPTW 依赖时间的时间窗车辆路径问题 TDVRPTW 带时间窗和复合服务员工的车辆路径问题 VRPTWMS 6 蚁群算法所解决的问题 分配问题二次分配问题 QAP 广义分配问题 GAP 频率分配问题 FAP 冗余分配问题 RAP 设置问题覆盖设置问题 SCP 分区设置问题 SPP 约束重量的树图划分问题 WCGTPP 加权弧L 基数树问题 AWlCTP 多背包问题 MKP 最大独立集问题 MIS 其他面向关系的网络路由无连接网络路由数据挖掘项目调度中的贴现现金流分布式信息检索网格工作流调度问题图像处理系统识别蛋白质折叠电子电路设计 6 蚁群算法所解决的问题 蚁群优化算法已应用于许多组合优化问题 包括蛋白质折叠或路由车辆的二次分配问题 很多派生的方法已经应用于实变量动力学问题 随机问题 多目标并行的实现 它也被用于产生货郎担问题的拟最优解 在图表动态变化的情况下解决相似问题时 他们相比模拟退火和遗传算法方法有优势 蚁群算法可以连续运行并适应实时变化 这在网络路由和城市交通系统中是有利的 第一蚁群优化算法被称为 蚂蚁系统 它旨在解决货郎担问题 其目标是要找到一系列城市的最短遍历路线 总体算法相对简单 它基于一组蚂蚁 每只完成一次城市间的遍历 在每个阶段 蚂蚁根据一些规则选择从一个城市移动到另一个 它必须访问每个城市一次 一个越远的城市被选中的机会越少 能见度更低 在两个城市边际的一边形成的信息素越浓烈 这边被选择的概率越大 如果路程短的话 已经完成旅程的蚂蚁会在所有走过的路径上沉积更多信息素 每次迭代后 信息素轨迹挥发 6 蚁群算法所解决的问题 在实验和应用中 蚁群算法有他的优势也有自己的劣势 但若与其他方法相结合 也能对解决问题的可行性和有效性有一定的帮助 下面列出与蚁群算法相关的方法遗传算法 GA 支持一系列的解决方案 解的合并或突变增加了解集 其中质量低劣的解被丢弃 寻找高级解决方案的过程模仿了这一演变 模拟退火 SA 是一个全局优化相关 的通过产生当前解的相邻解来遍历搜索空间的技术 高级的相邻解总是可接受的 低级的相邻解可能会根据基于质量和温度参数德差异的概率被接受 温度参数随着算法的进程被修改以改变搜索的性质 反作用搜索优化的重点在于将机器学习与优化的结合 加入内部反馈回路以根据问题 根据实例 根据当前解的附近情况的特点自动调整算法的自由参数 禁忌搜索 TS 类似于模拟退火 他们都是通过测试独立解的突变来遍历解空间的 而模拟退火算法对于一个独立解只生成一个突变 禁忌搜索会产生许多变异解并且移动到产生的解中的符合度最低的一个 为了防止循环并且促进在解空间中的更大进展 由部分或完整的解组建维系了一个禁忌列表 移动到元素包含于禁忌列表的解是禁止 禁忌列表随着解遍历解空间的过程而不断更新 人工免疫系统 AIS 算法仿照了脊椎动物的免疫系统 粒子群优化 PSO 群智能方法引力搜索算法 GSA 群智能方法蚁群聚类方法 ACCM中 这个方法利用了聚类方法扩展了蚁群优化 随机传播搜索 SDS 基于代理的概率全局搜索和优化技术 最适合于将目标函数分解成多个独立的分布函数的优化问题 7 蚁群算法的应用 应用领域蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题 现在其应用领域已扩展到多目标优化 数据分类 数据聚类 模式识别 电信QoS管理 生物系统建模 流程规划 信号处理 机器人控制 决策支持以及仿真和系统辩识等方面 群智能理论和方法为解决这类应用问题提供了新的途径 7 蚁群算法的应用 蚁群算法的模型改进及其应用近年来 国内外学者在蚁群算法的模型改进和应用方面做了大量的工作 其共同目的是在合理时间复杂度的限制条件下 尽可能提高蚁群算法在一定空间复杂度下的寻优能力 从而改善蚁群算法的全局收敛性 并拓宽蚁群算法的应用领域 部分的蚁群算法改进模型及其应用情况 附Pr 1 7 蚁群算法的应用 蚁群优化算法应用现状随着群智能理论和应用算法研究的不断发展 研究者已尝试着将其用于各种工程优化问题 并取得了意想不到的收获 多种研究表明 群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果 并在组合优化问题中表现突出 蚁群优化算法并不是旅行商问题的最佳解决方法 但是它却为解决组合优化问题提供了新思路 并很快被应用到其它组合优化问题中 比较典型的应用研究包括 网络路由优化 数据挖掘以及一些经典的组合优化问题 7 蚁群算法的应用 蚁群算法在电信路由优化中已取得了一定的应用成果 HP公司和英国电信公司在90年代中后期都开展了这方面的研究 设计了蚁群路由算法 AntColonyRouting ACR 每只蚂蚁就像蚁群优化算法中一样 根据它在网络上的经验与性能 动态更新路由表项 如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟 那么就对该表项做较大的增强 同时根据信息素挥发机制实现系统的信息更新 从而抛弃过期的路由信息 这样 在当前最优路由出现拥堵现象时 ACR算法就能迅速的搜寻另一条可替代的最优路径 从而提高网络的均衡性 负荷量和利用率 目前这方面的应用研究仍在升温 因为通信网络的分布式信息结构 非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似 7 蚁群算法的应用 基于群智能的聚类算法起源于对蚁群蚁卵的分类研究 Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据聚类分析 其基本思想是将待聚类数据随机地散布到一个二维平面内 然后将虚拟蚂蚁分布到这个空间内 并以随机方式移动 当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动 若运动