人工智能07蚁群算法及其应用PPT学习课件

第七章蚁群算法及其应用 1 2 蚁群算法的背景 20世纪50年代中期创立了仿生学 人们从生物进化的机理中受到启发 提出了许多用以解决复杂优化问题的新方法 如进化规划 进化策略 遗传算法等 这些算法成功地解决了一些实际问题 蚁群算法从蚂蚁觅食得到启发 2 2020 4 19 蚁群算法的背景 仿生算法集群智能算法概率型算法遗传算法 进化算法粒子群算法 课程论文2 蚁群算法用来解决众多NP hard问题 3 2020 4 19 蚁群算法的背景 自然蚁群的自组织行为特征高度结构化的组织 虽然蚂蚁的个体行为极其简单 但由个体组成的蚁群却构成高度结构化的社会组织 蚂蚁社会的成员有分工 有相互的通信和信息传递 自然优化 蚁群在觅食过程中 在没有任何提示下总能找到从蚁巢到食物源之间的最短路径 当经过的路线上出现障碍物时 还能迅速找到新的最优路径 信息正反馈 蚂蚁在寻找食物时 在其经过的路径上释放信息素 外激素 蚂蚁基本没有视觉 但能在小范围内察觉同类散发的信息素的轨迹 由此来决定何去何从 并倾向于朝着信息素强度高的方向移动 自催化行为 某条路径上走过的蚂蚁越多 留下的信息素也越多 随时间蒸发一部分 后来蚂蚁选择该路径的概率也越高 4 2020 4 19 蚁群算法的背景 概念原型各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物 当一只找到食物以后 它会向环境释放一种挥发性分泌物pheromone 称为信息素 该物质随着时间的推移会逐渐挥发消失 信息素浓度的大小表征路径的远近 来实现的 吸引其他的蚂蚁过来 这样越来越多的蚂蚁会找到食物 有些蚂蚁并没有像其它蚂蚁一样总重复同样的路 他们会另辟蹊径 如果另开辟的道路比原来的其他道路更短 那么 渐渐地 更多的蚂蚁被吸引到这条较短的路上来 最后 经过一段时间运行 就可能会出现一条最短的路径被大多数蚂蚁重复着 5 2020 4 19 蚁群算法的提出 算法的提出蚁群算法 AntColonyOptimization ACO 又称蚂蚁算法 一种用来在图中寻找优化路径的机率型算法 它由MarcoDorigo于1992年在他的博士论文 Antsystem optimizationbyacolonyofcooperatingagents 中提出 其灵感来源于蚂蚁在寻找食物过程中发现路径的行为 最早用于解决著名的旅行商问题 TSP travelingsalesmanproblem 6 2020 4 19 蚁群算法的提出 基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法 蚂蚁在运动过程中 能够在它所经过的路径上留下一种称之为信息素 pheromone 的物质进行信息传递 而且蚂蚁在运动过程中能够感知这种物质 并以此指导自己的运动方向 因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象 某一路径上走过的蚂蚁越多 则后来者选择该路径的概率就越大 7 2020 4 19 蚁群算法的提出 简化的蚂蚁寻食正反馈过程蚂蚁从A点出发 速度相同 食物在D点 可能随机选择路线ABD或ACD 假设初始时每条路线分配一只蚂蚁 每个时间单位行走一步 本图为经过9个时间单位时的情形 走ABD的蚂蚁到达终点 而走ACD的蚂蚁刚好走到C点 为一半路程 8 2020 4 19 蚁群算法的提出 本图为从开始算起 经过18个时间单位时的情形 走ABD的蚂蚁到达终点后得到食物又返回了起点A 而走ACD的蚂蚁刚好走到D点 9 2020 4 19 蚁群算法的提出 假设蚂蚁每经过一处所留下的信息素为一个单位 则经过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路线 这也就是前面所提到的正反馈效应 10 2020 4 19 蚁群算法的提出 人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题 可以构造人工蚁群 来解决最优化问题 如TSP问题 人工蚁群中把具有简单功能的工作单元看作蚂蚁 二者的相似之处在于都是优先选择信息素浓度大的路径 较短路径的信息素浓度高 所以能够最终被所有蚂蚁选择 也就是最终的优化结果 两者的区别在于人工蚁群有一定的记忆能力 能够记忆已经访问过的节点 同时 人工蚁群在选择下一条路径的时候是按一定算法规律有意识地寻找最短路径 而不是盲目的 例如在TSP问题中 可以预先知道当前城市到下一个目的地的距离 人工蚁群VS自然蚁群 11 2020 4 19 蚁群算法的特征 蚁群算法采用了分布式正反馈并行计算机制 易于与其他方法结合 并具有较强的鲁棒性 1 其原理是一种正反馈机制或称增强型学习系统 它通过信息素的不断更新达到最终收敛于近似最优路径上 2 它是一种通用型随机优化方法 但人工蚂蚁决不是对实际蚂蚁的一种简单模拟 它融进了人类的智能 3 它是一种分布式的优化方法 不仅适合目前的串行计算机 而且适合未来的并行计算机 4 它是一种全局优化的方法 不仅可用于求解单目标优化问题 而且可用于求解多目标优化问题 5 它是一种启发式算法 计算复杂性为O NC m n2 其中NC是迭代次数 m是蚂蚁数目 n是目的节点数目 12 2020 4 19 蚁群算法的特征 算法优点 1 求解问题的快速性 由正反馈机制决定 2 全局优化性 由分布式计算决定 避免蚁群在寻优空间中过早收敛 3 有限时间内答案的合理性 由贪婪式搜索模式决定 使能在搜索过程的早期就找到可以接受的较好解 13 2020 4 19 蚁群算法的基本思想 算法流程图 14 2020 4 19 蚁群算法的基本思想 以TSP问题为例 1 根据具体问题设置多只蚂蚁 分头并行搜索 2 每只蚂蚁完成一次周游后 在行进的路上释放信息素 信息素量与解的质量成正比 3 蚂蚁路径的选择根据信息素强度大小 初始信息素量设为相等 同时考虑两点之间的距离 采用随机的局部搜索策略 这使得距离较短的边 其上的信息素量较大 后来的蚂蚁选择该边的概率也较大 15 2020 4 19 蚁群算法的基本思想 4 每只蚂蚁只能走合法路线 经过每个城市1次且仅1次 为此设置禁忌表来控制 5 所有蚂蚁都搜索完一次就是迭代一次 每迭代一次就对所有的边做一次信息素更新 原来的蚂蚁死掉 新的蚂蚁进行新一轮搜索 6 更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加 7 达到预定的迭代步数 或出现停滞现象 所有蚂蚁都选择同样的路径 解不再变化 则算法结束 以当前最优解作为问题的解输出 16 2020 4 19 蚁群算法的数学模型 TSP算例分析 旅行商问题 TSP 给定n个城市和两个两个城市之间的距离 要求确定一条经过所有城市仅一次的最短路径 第一步 初始化将m只蚂蚁随机放到n个城市 每只蚂蚁的禁忌表为蚂蚁当前所在城市 各边信息素初始化为c 禁忌表体现了人工蚂蚁的记忆性 使得蚂蚁不会走重复道路 提高了效率 17 2020 4 19 蚁群算法的数学模型 第二步 选择路径路径在t时刻 蚂蚁k从城市i转移到城市j的概率为 18 2020 4 19 蚁群算法的数学模型 19 2020 4 19 蚁群算法的数学模型 蚁群的规模和停止规则蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数 终止条件 1给定一个外循环的最大数目 表明已经有足够的蚂蚁工作 2当前最优解连续K次相同而停止 其中K是一个给定的整数 表示算法已经收敛 不再需要继续 3目标值控制规则 给定优化问题 目标最小化 的一个下界和一个误差值 当算法得到的目标值同下界之差小于给定的误差值时 算法终止 第四步 输出结果若未达到终止条件则转步骤二 否则 输出目前的最优解 20 2020 4 19 TSP应用举例 21 2020 4 19 TSP应用举例 22 2020 4 19 TSP应用举例 23 2020 4 19 TSP应用举例 24 2020 4 19 TSP应用举例 25 2020 4 19 TSP应用举例 26 2020 4 19 改进的蚁群优化算法 27 2020 4 19 一般蚁群算法的框架主要有三个组成部分 蚁群的活动 信息素的挥发 信息素的增强 主要体现在转移概率公式和信息素更新公式 28 2020 4 19 一 带精英策略的蚂蚁系统 特点 在信息素更新时给予当前最优解以额外的信息素量 使最优解得到更好的利用 找到全局最优解的蚂蚁称为 精英蚂蚁 29 2020 4 19 二 蚁群系统 规则 和 都是为了使搜索过程更具有指导性 即使蚂蚁的搜索主要集中在当前找出的最好解邻域内 规则 则是为了使已选的边对后来的蚂蚁具有较小的影响力 以避免蚂蚁收敛到同一路径 30 2020 4 19 三 最大最小蚂蚁系统 关于的取值 没有确定的方法 有的书例子中取为0 01 10 有的书提出一个在最大值给定的情况下计算最小值的公式 四 基于优化排序的蚂蚁系统 特点 每次迭代完成后 蚂蚁所经路径由小到大排序 并根据路径长度赋予不同的权重 路径越短权重越大 信息素更新时对考虑权重的影响 31 2020 4 19 六 一种新的自适应蚁群算法 特点 将ACS中的状态转移规则改为自适应伪随机比率规则 动态调整转移概率 以避免出现停滞现象 说明 在ACS的状态转移公式中 是给定的常数 在AACA中 是随平均节点分支数ANB而变化的变量 ANB较大 意味着下一步可选的城市较多 也变大 表示选择信息素和距离最好的边的可能性增大 反之减小 32 2020 4 19 七 基于混合行为的蚁群算法 特点 按蚂蚁的行为特征将蚂蚁分成4类 称为4个子蚁群 各子蚁群按各自的转移规则行动 搜索路径 每迭代一次 更新当前最优解 按最优路径长度更新各条边上的信息素 如此直至算法结束 蚂蚁行为 蚂蚁在前进过程中 用以决定其下一步移动到哪个状态的规则集合 33 2020 4 19 蚁群算法与遗传 模拟退火算法的比较 实验结果表明 1 蚁群算法所找出的解的质量最高 遗传算法次之 模拟退火算法最低 2 蚁群算法的收敛速度最快 遗传算法次之 模拟退火算法最慢 蚁群算法之所以能够快速收敛到全局最优解 是因为该算法的个体之间不断进行信息交流和传递 单个个体容易收敛于局部最优 多个个体通过合作可以很快地收敛于解空间的最优解的附近 34 2020 4 19 蚁群算法的应用 应用领域蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题 现在其应用领域已扩展到多目标优化 数据分类 数据聚类 模式识别 电信QoS管理 生物系统建模 流程规划 信号处理 机器人控制 决策支持以及仿真和系统辩识等方面 群智能理论和方法为解决这类应用问题提供了新的途径 35 2020 4 19 蚁群算法的应用 蚁群算法在电信路由优化中已取得了一定的应用成果 HP公司和英国电信公司在90年代中后期都开展了这方面的研究 设计了蚁群路由算法 AntColonyRouting ACR 每只蚂蚁就像蚁群优化算法中一样 根据它在网络上的经验与性能 动态更新路由表项 如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟 那么就对该表项做较大的增强 同时根据信息素挥发机制实现系统的信息更新 从而抛弃过期的路由信息 这样 在当前最优路由出现拥堵现象时 ACR算法就能迅速的搜寻另一条可替代的最优路径 从而提高网络的均衡性 负荷量和利用率 目前这方面的应用研究仍在升温 因为通信网络的分布式信息结构 非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似 36 2020 4 19 蚁群算法的应用 基于群智能的聚类算法起源于对蚁群蚁卵的分类研究 Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据聚类分析 其基本思想是将待聚类数据随机地散布到一个二维平面内 然后将虚拟蚂蚁分布到这个空间内 并以随机方式移动 当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动 若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置 然后继续移动 重复上述数据搬运过程 按照这样的方法可实现对相似数据的聚类 37 2020 4 19 蚁群算法的应用 ACO还在许多经典组合优化问题中获得了成功的应用 如二次规划问题 QAP 机器人路径规划 作业流程规划 图着色 GraphColoring 等问题 经过多年的发展 ACO已成为能够有效解决实际二次规划问题的几种重要算法之一 AS在作业流程计划 Job shopScheduling 问题中的应用实例已经出现 这说明了AS在此领域的应用潜力 利用MAX MINAS解决PAQ也取得了比较理想的效果 并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好 且与禁忌搜索算法性能相当 利用ACO实现对生产流程和特料管理的综合优化 并通过与遗传 模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值 38 2020 4 19 蚁群算法的应