粒子群优化算法与蚁群算法.ppt

人工智能 粒群优化算法蚁群算法理论蚁群算法的研究与应用 粒子群优化算法PSOParticleSwarmOptimization 背景 人工生命 研究具有某些生命基本特征的人工系统 包括两方面的内容 1 研究如何利用计算技术研究生物现象 2 研究如何利用生物技术研究计算问题 我们关注的是第二点 如何利用生物技术研究计算问题是人工生命研究的重要方向 现已有了很多源于生物现象的计算技巧 例如人工神经网络是简化的大脑模型 遗传算法是模拟基因进化过程的 背景 现在讨论另一种生物系统 社会系统 由简单个体组成的群落和环境及个体之间的相互行为 也可称为群智能 swarmintelligence 这些模拟系统利用局部信息从而可以产生不可预测的群行为 目前计算智能领域有 种基于群智能的算法 蚁群算法 antcolonyoptimization 和粒子群算法 particleswarmoptimization 背景 我们经常能够看到成群的鸟 鱼或者浮游生物 这些生物的聚集行为有利于它们觅食和逃避捕食者 它们的群落动辄以十 百 千甚至万计 并且经常不存在一个统一的指挥者 它们是如何完成聚集 移动这些功能呢 背景 对鸟群行为的模拟 Reynolds Heppner和Grenader提出鸟群行为的模拟 他们发现 鸟群在行进中会突然同步的改变方向 散开或者聚集等 那么一定有某种潜在的能力或规则保证了这些同步的行为 这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学 在这些早期的模型中仅仅依赖个体间距的操作 也就是说 这种同步是鸟群中个体之间努力保持最优的距离的结果 背景 对鱼群行为的研究 生物社会学家E O Wilson对鱼群进行了研究 提出 至少在理论上 鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验 这种受益超过了个体之间的竞争所带来的利益消耗 不管任何时候食物资源不可预知的分散 这说明 同种生物之间信息的社会共享能够带来好处 这是PSO的基础 算法介绍 粒子群优化算法 PSO 是一种进化计算技术 evolutionarycomputation 由Eberhart博士和kennedy博士于1995年提出 KennedyJ EberhartR Particleswarmoptimization ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks 1995 1942 1948 源于对鸟群捕食的行为研究 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解 算法介绍 设想这样一个场景 一群鸟在随机的搜索食物 在这个区域里只有一块食物 所有的鸟都不知道食物在那 但是它们知道自己当前的位置距离食物还有多远 那么找到食物的最优策略是什么 最简单有效的就是搜寻目前离食物最近的鸟的周围区域 算法介绍 抽象 鸟被抽象为没有质量和体积的微粒 点 并延伸到N维空间 粒子I在N维空间的位置表示为矢量Xi x1 x2 xn 飞行速度表示为矢量Vi v1 v2 vn 每个粒子都有一个由目标函数决定的适应值 fitnessvalue 并且知道自己到目前为止发现的最好位置 pbest 除此之外 每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置 gbest gbest是pbest中的最好值 粒子怎么样到达下一步的运动 算法介绍 PSO初始化为一群随机粒子 随机解 然后通过迭代找到最优解 在每一次的迭代中 粒子通过跟踪两个 极值 pbest gbest 来更新自己 在找到这两个最优值后 粒子通过下面的公式来更新自己的速度和位置 在式 1 2 中 i 1 2 M M是该群体中粒子的总数 2 式 算法介绍 Vi是粒子的速度 pbest和gbest如前定义 rand 是介于 0 1 之间的随机数 Xi是粒子的当前位置 c1和c2是学习因子 通常取c1 c2 2 在每一维 粒子都有一个最大限制速度Vmax 如果某一维的速度超过设定的值 那么这一维的速度就被限定为Vmax Vmax 0 算法介绍 算法介绍 从社会学的角度来看 公式 1 的第一部分称为记忆项 表示上次速度大小和方向的影响 公式第二部分称为自身认知项 是从当前点指向粒子自身最好点的一个矢量 表示粒子的动作来源于自己经验的分 公式的第三部分称为群体认知项 是一个从当前点指向种群最好点的矢量 反映了粒子间的协同合作和知识共享 粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动 以上面两个公式为基础 形成了后来PSO的标准形式 算法介绍 1998年shi等人在进化计算的国际会议上发表了一篇论文 Amodifiedparticleswarmoptimizer 对前面的公式 1 进行了修正 引入惯性权重因子 为非负数 称为惯性因子 公式 2 和 3 被视为标准pso算法 算法介绍 值较大 全局寻优能力强 局部寻优能力弱 值较小反之 初始时 shi将取为常数 后来实验发现 动态能够获得比固定值更好的寻优结果 动态可以在PSO搜索过程中线性变化 也可根据PSO性能的某个测度函数动态改变 目前 采用较多的是shi建议的线性递减权值 linearlydecreasingweight LDW 策略 算法介绍 通常由下式来确定 和是的最大最小值 和分别是当前叠代次数和最大叠代次数 的引入使PSO算法性能有了很大提高 针对不同的搜索问题 可以调整全局和局部搜索能力 也使得PSO算法能成功的应用于很多实际问题 典型取值 0 9 0 4 算法介绍 标准PSO算法的流程 Step1 初始化一群微粒 群体规模为M 包括随机位置和速度 Step2 评价每个微粒的适应度 Step3 对每个微粒 将其适应值与其经过的最好位置pbest作比较 如果较好 则将其作为当前的最好位置pbest Step4 对每个微粒 将其适应值与其经过的最好位置gbest作比较 如果较好 则将其作为当前的最好位置gbest Step5 根据 2 3 式调整微粒速度和位置 Step6 未达到结束条件则转Step2 算法介绍 迭代终止条件根据具体问题一般选为最大迭代次数或 和 微粒群迄今为止搜索到的最优位置满足预定最小适应阈值 全局和局部最优算法 权重因子 是调整粒子的自身经验与社会 群体 经验在其运动中所起的作用的权重 如果 0 则粒子没有自经验 只有 社会 social only 经验 它的收敛速度可能较快 但在处理较复杂的问题时 容易陷入局部最优点 如果 0 则粒子没有群体共享信息 只有 自身经验 因为个体间没有交互 一个规模为M的群体等价于运行了M个单个微粒 因而得到解的几率非常小 参数分析 参数有 群体规模M 惯性因子w 学习因子c1和c2最大速度Vmax 迭代次数iter 群体规模M 一般取20 40 对较难或特定类别的问题可以取到100 200 最大速度Vmax决定当前位置与最好位置之间的区域的分辨率 或精度 如果太快 则粒子有可能越过极小点 如果太慢 则粒子不能在局部极小点之外进行足够的探索 会陷入到局部极值区域内 这种限制可以达到防止计算溢出 决定问题空间搜索的粒度的目的 参数分析 权重因子包括惯性因子w和学习因子c1和c2 w使粒子保持着运动惯性 使其具有扩展搜索空间的趋势 有能力探索新的区域 c1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值 较低的值允许粒子在被拉回之前可以在目标区域外徘徊 较高的值导致粒子突然地冲向或越过目标区域 参数分析 参数设置 如果令c1 c2 0 粒子将一直以当前速度的飞行 直到边界 很难找到最优解 如果w 0 则速度只取决于当前位置和历史最好位置 速度本身没有记忆性 假设一个粒子处在全局最好位置 它将保持静止 其他粒子则飞向它的最好位置和全局最好位置的加权中心 粒子将收缩到当前全局最好位置 在加上第一部分后 粒子有扩展搜索空间的趋势 这也使得w的作用表现为针对不同的搜索问题 调整算法的全局和局部搜索能力的平衡 w较大时 具有较强的全局搜索能力 w较小时 具有较强的局部搜索能力 参数分析 通常设c1 c2 2 Suganthan的实验表明 c1和c2为常数时可以得到较好的解 但不一定必须等于2 Clerc引入收敛因子 constrictionfactor K来保证收敛性 其中 参数分析 通常取为4 1 则K 0 729 实验表明 与使用惯性权重的PSO算法相比 使用收敛因子的PSO有更快的收敛速度 其实只要恰当的选取和c1 c2 两种算法是一样的 因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例 恰当的选取算法的参数值可以改善算法的性能 蚁群算法理论 antcolonyoptimizationACO 小蚂蚁 大智慧 蚂蚁在8000玩年之间就建立了自己的社会 而我们人类只有5000余年的文明史 人类的许多城市都有不少都市问题 可是小小的蚂蚁却能建立起组织完好的复杂的 社会 有许多 蚂蚁城市 往往由5000万个成员组成 而在人口较为稠密的城市也不过1000多万人 蚂蚁有四种不同的蚁型 即蚁后 雄蚁 工蚁和兵蚁 不同的蚁型有不同的分工 蚁后称为 蚂蚁女王 主要职责是产卵 繁衍后代和管理蚂蚁家族 它可根据食物多少来决定是否生育 还可以根据筑巢和建立新群体所需的蚂蚁数量来调节人口结构 雄蚁负责交配 工蚁负责筑巢 采集食物 饲喂幼蚁和蚁后等 兵蚁负责保卫群体 尽管蚂蚁个体比较简单 但整个蚁群却表现为高度机构化的社会组织 在许多情况下能完成远远超过蚂蚁个体能力的复杂任务 这种能力来源于蚂蚁群体中的个体协作行为 其群体行为主要包括寻找食物 任务分配和构造墓地等三种 在现实生活中 我们总可以观察到大量蚂蚁在巢穴与食物源之间形式近乎直线的路径 而不是曲线或者圆等其他形状 蚂蚁群体不仅能完成复杂的任务 而且还能适应环境的变换 如在蚁群运动线路上加上障碍 一开始各只蚂蚁分布是均匀的 不管路径长短 蚂蚁总是按照同等概率选择各条路径 在蚂蚁运动的过程中 能够在其经过的路径上留下信息素 而且能够感知这种物质的强度及存在 并以此指导自己运动的方向 蚂蚁倾向于向信息素浓度高的方向移动 相等时间内较短路径上的信息素就遗留得较多 则选择的蚂蚁就变得多 由于蚁群集体行为表现出一种信息正反馈信息 即某一路径走过的蚂蚁越多 则后来者选择的概率就大得多 蚂蚁个体之间就是通过这种信息交流机制来搜索食物 并沿着最短的路径前进 迷人的蚂蚁 蚁群寻找食物的过程 蚁群觅食的双桥实验 蚁群算法的背景 蚁群算法 antcolonyoptimization ACO 又称蚂蚁算法 是一种用来在图中寻找优化路径的机率型算法 蚁群算法是一种模拟进化算法 初步的研究表明该算法具有许多优良的性质 针对PID控制器参数优化设计问题 将蚁群算法设计的结果与遗传算法设计的结果进行了比较 数值仿真结果表明 蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值 蚁群算法的由来 蚂蚁是地球上最常见 数量最多的昆虫种类之一 常常成群结队地出现在人类的日常生活环境中 这些昆虫的群体生物智能特征 引起了一些学者的注意 意大利学者M Dorigo V Maniezzo等人在观察蚂蚁的觅食习性时发现 蚂蚁总能找到巢穴与食物源之间的最短路径 经研究发现 蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素 Pheromone 的挥发性化学物质来进行通信和协调的 化学通信是蚂蚁采取的基本信息交流方式之一 在蚂蚁的生活习性中起着重要的作用 通过对蚂蚁觅食行为的研究 他们发现 整个蚁群就是通过这种信息素进行相互协作 形成正反馈 从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上 背景 这样 M Dorigo等人于1991年首先提出了蚁群算法 其主要特点就是 通过正反馈 分布式协作来寻找最优路径 这是一种基于种群寻优的启发式搜索算法 它充分利用了生物蚁群能通过个体间简单的信息传递 搜索从蚁巢至食物间最短路径的集体寻优特征 以及该过程与旅行商问题求解之间的相似性 得到了具有NP难度的旅行商问题的最优解答 同时 该算法还被用于求解Job Shop调度问题 二次指派问题以及多维背包问题等 显示了其适用于组合优化类问题求解的优越特征 34 自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题 可以构造人工蚁群 来解决最优化问题 如TSP问题 人工蚁群中把具有简单功能的工作单元看作蚂蚁 二者的相似之处在于都是优先选择信息素浓度大的路径 较短路径的信息素浓度高 所以能够最终被所有蚂蚁选择 也就是最终的优化结果 两者的区别在于人工蚁群有一定的记忆能力 能够记忆已经访问过的节点 同时 人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径 而不是盲目的 例如在TSP问题中 可以预先知道当前城市到下一个目的地的距离 35 蚁群算法与TSP问题1 3 TSP问题表示为一个N个城市的有向图G N A 其中城市之间距离目标函数为 其中为城市1 2 n的一个排列 36 蚁群算法与TSP问题2 3 TSP问题的人工蚁群算法中 假设m只蚂蚁在图的相邻节点间移动 从而协作异步地得到问题的解 每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定 1信息素值也称信息素痕迹 2可见度 即先验值 信息素的更新方式有2种 一是挥发 也就是所有路径上的信息素以一定的比率进行减少 模拟自然蚁群的信息素随时间挥发的过程 二是增强 给评价值 好 有蚂蚁走过 的边增加信息素 37 蚁群算法与TSP问题3 3 蚂蚁向下一个目标的运动是通过一个随机原则来实现的 也就是运用当前所在节点存储的信息 计算出下一步可达节点的概率 并按此概率实现一步移动 逐此往复 越来越接近最优解 蚂蚁在寻找过程中 或者找到一个解后 会评估该解或解的一部分的优化程度 并把评价信息保存在相关连接的信息素中 38 初始的蚁群优化算法 基于图的蚁群系统 GBAS 1 12 初始的蚁群算法是基于图的蚁群算法 graph basedantsystem 简称为GBAS 是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的 课本的参考文献2 算法步骤如下 STEP0对n个城市的TSP问题 城市间的距离矩阵为 给TSP图中的每一条弧赋信息素初值 假设m只蚂蚁在工作 所有蚂蚁都从同一城市出发 当前最好解是 39 初始的蚁群优化算法 基于图的蚁群系统 GBAS 2 12 STEP1 外循环 如果满足算法的停止规则 则停止计算并输出计算得到的最好解 否则使蚂蚁s从起点出发 用表示蚂蚁s行走的城市集合 初始为空集 STEP2 内循环 按蚂蚁的顺序分别计算 当蚂蚁在城市i 若完成第s只蚂蚁的计算 否则 若 则以概率 到达j 若则到达重复STEP2 40 初始的蚁群优化算法 基于图的蚁群系统 GBAS 3 12 STRP3对 若按中城市的顺序计算路径程度 若 路径长度置为一个无穷大值 即不可达 比较m只蚂蚁中的路径长度 记走最短路径的蚂蚁为t 若 则 用如下公式对W路径上的信息素痕迹加强 对其他路径上的信息素进行挥发 得到新的 重复步骤STEP1 41 初始的蚁群优化算法 基于图的蚁群系统 GBAS 4 12 在STEP3中 挥发因子对于一个固定的 满足并且经过k次挥发 非最优路径的信息素逐渐减少至消失 42 初始的蚁群优化算法 基于图的蚁群系统 GBAS 5 12 以上算法中 在蚂蚁的搜寻过程中 以信息素的概率分布来决定从城市i到城市j的转移 算法中包括信息素更新的过程1信息素挥发 evaporation 信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程 由表示 这个挥发过程主要用于避免算法过快地向局部最优区域集中 有助于搜索区域的扩展 2信息素增强 reinforcement 增强过程是蚁群优化算法中可选的部分 称为离线更新方式 还有在线更新方式 这种方式可以实现由单个蚂蚁无法实现的集中行动 也就是说 增强过程体现在观察蚁群 m只蚂蚁 中每只蚂蚁所找到的路径 并选择其中最优路径上的弧进行信息素的增强 挥发过程是所有弧都进行的 不于蚂蚁数量相关 这种增强过程中进行的信息素更新称为离线的信息素更新 在STEP3中 蚁群永远记忆到目前为止的最优解 43 图的蚁群系统 GBAS 6 12 可以验证 下式满足 即是一个随机矩阵 四个城市的非对称TSP问题 距离矩阵和城市图示如下 44 初始的蚁群优化算法 基于图的蚁群系统 GBAS 7 12 假设共4只蚂蚁 所有蚂蚁都从城市A出发 挥发因子 此时 观察GBAS的计算过程 矩阵共有12条弧 初始信息素记忆矩阵为 45 初始的蚁群优化算法 基于图的蚁群系统 GBAS 8 12 执行GBAS算法的步骤2 假设蚂蚁的行走路线分别为 当前最优解为 这个解是截止到当前的最优解 碰巧是实际最优解 46 初始的蚁群优化算法 基于图的蚁群系统 GBAS 9 12 按算法步骤3的信息素更新规则 得到更新矩阵这是第一次外循环结束的状态 47 初始的蚁群优化算法 基于图的蚁群系统 GBAS 10 12 重复外循环 由于上一次得到的W2已经是全局最优解 因此按算法步骤3的信息素更新规则 无论蚂蚁如何行走 都只是对W2路线上的城市信息素进行增强 其他的城市信息素进行挥发 得到更新矩阵这是第一次外循环结束的状态 48 初始的蚁群优化算法 基于图的蚁群系统 GBAS 11 12 重复外循环 由于W2全局最优解 GBAS只记录第一个最优解 因此一但得到了全局最优解 信息素的更新将不再依赖于以群的行走路线 而只是不断增强最优路线的信息素 同时进行挥发 第三次外循环后得到的信息素矩阵为 49 初始的蚁群优化算法 基于图的蚁群系统 GBAS 12 12 蚂蚁以一定的概率从城市i到城市j进行转移 信息素的更新在STEP3完成 并随K而变化 假设第K次外循环后得到信息素矩阵 得到当前最优解 第K次循环前的信息素和最优解为 经过第K次外循环后 得到 由于蚂蚁的一步转移概率是随机的 从到也是随机的 是一个马尔可夫过程