群智能算法 (1).ppt

东北大学信息学院陈东岳王晓哲 智能计算方法与应用 群众的力量是伟大的 鸟群通过协作进行捕食鱼聚集成群可以有效的逃避捕食者房间偏僻角落里的蛋糕总会先被蚂蚁发现头脑简单的蜜蜂却能构造出世界上最完美的建筑物 6 1 1生物群体行为的启示 6 1群智能算法概述 生物群中的每个个体只有简单的信息处理能力和行为能力 鸟群 飞行 捕食 避碰 昆虫 爬行 觅食 产生信息素 群体中各个个体之间可以进行信息交互 鸟群 视觉 听觉 磁场 昆虫 感知信息素 群体的能力要远远超出个体能力的简单叠加信息感知能力分工协作能力适应生存能力 6 1 1生物群体行为的启示 6 1群智能算法概述 1 群智能 SwarmIntelligence SI 的概念发展过程分子自动机系统中提出 分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用 从而实现自组织 byBeni Hackwood任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能 byBonabeau Dorigo Theraula无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性 byBonabeau 6 1 2群智能的概念 6 1群智能算法概述 2 定义SI的五条基本原则 byMarkMillonas1994 ProximityPrinciple 群内个体具有能执行简单的时间或空间上的评估和计算的能力 QualityPrinciple 群内个体能对环境 包括群内其它个体 的关键性因素的变化做出响应 PrincipleofDiverseResponse 群内不同个体对环境中的某一变化所表现出的响应行为具有多样性 StabilityPrinciple 不是每次环境的变化都会导致整个群体的行为模式的改变 AdaptabilityPrinciple 环境所发生的变化中 若出现群体值得付出代价的改变机遇 群体必须能够改变其行为模式 6 1 2群智能的概念 6 1群智能算法概述 3 SI的核心思路 Mindissocial 认为人的智能是源于社会性的相互作用 文化和认知是人类社会性不可分割的重要部分 这一观点成为了群智能发展的基石 4 SI的意义和发展前景群智能的思路 为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法 6 1 2群智能的概念 6 1群智能算法概述 广义的群智能算法包括 粒子群算法 模拟鸟群觅食行为蚁群算法 模拟蚁群觅食行为免疫算法 模拟生物免疫系统工作机理细菌觅食算法 模拟大肠杆菌觅食行为混合算法 多种群智能算法的结合 6 1 3群智能算法的分类 6 1群智能算法概述 SI与EC的相同点都研究个体与群体的关系都存在个体之间的信息传递都是为了解决实际问题 而非单纯的模拟自然现象都属于随机搜索算法SI与EC的不同点SI模拟的是个体之间的协同作用 而EC模拟的是适者生存的自然选择机制 6 1 4群智能算法与进化计算的异同 6 1群智能算法概述 1 粒子群算法的起源粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究 boids是一个复杂适应系统 在boids中 一群鸟在空中飞行 每个鸟遵守以下三条规则 1 避免与相邻的鸟发生碰撞冲突 2 尽量与自己周围的鸟在速度上保持协调一致 3 尽量试图向自己所认为的群体中靠近 仅通过使用这三条规则 boids系统就实现了非常逼真的群体聚集行为 鸟成群地在空中飞行 当遇到障碍时它们会分开绕行而过 随后又会重新形成群体 6 2 1粒子群算法概述 6 2粒子群优化算法 2 粒子群算法的提出粒子群算法最早是由美国的社会心理学家Kennedy和电气工程师Eberhart于1995年提出 他们在Reynolds的工作基础上引入了食物要素 进一步模拟了鸟群飞行觅食的行为 并发现该方法可以应用于复杂全局寻优问题的求解 粒子群优化算法的英文为 ParticleSwarmOptimization 通常缩写为PSO 6 2 1粒子群算法概述 6 2粒子群优化算法 3 粒子群算法的产生背景 一 复杂适应系统 CAS CAS是指其内部的成员 Agent 能够通过与其他成员以及外界环境的交流 并根据学习经验调整自身的结构和行为 进而实现整个系统的演变和进化的系统CAS的特点表现为 主体 AdaptiveAgent 是主动的 活的实体 个体与环境 包括其他个体之间 的相互影响 相互作用 是系统演变和进化的主要动力 宏观与微观有机结合引进随机因素的作用 具有更强的描述和表达能力 6 2 1粒子群算法概述 6 2粒子群优化算法 3 粒子群算法的产生背景 二 人工生命 AL 人工生命是对具有自然生命现象和行为特征的人造系统的研究 是一门涉及到生命科学 复杂性科学 人工智能 计算机科学 经济学 哲学和语言学等多学科的交叉学科 其研究模式主要体现为两类 如何利用计算技术研究生物现象 如何利用生物技术研究计算问题 人工生命的研究挑战主要为以下三类TheTransitionofLifeTheEvolutionaryPotentialofLifeTheRelationbetweenLifeandMindandCulture 6 2 1粒子群算法概述 6 2粒子群优化算法 4 粒子群算法的基本原则接近原则 粒子与群体应能够依照目标前进特性原则 群体应该能够反应环境的变化 当所处环境并非最佳解空间时 能够快速飞离该区域 不同响应原则 群体不会向不佳的解前进稳定原则 环境改变时 群体移动不会改变其运动模式适应原则 计算当下最佳解时 群体将会考量适当的参数变动 6 2 1粒子群算法概述 6 2粒子群优化算法 5 粒子群算法的基本概念 6 2 1粒子群算法概述 6 2粒子群优化算法 1 基本粒子群算法思想描述在PSO中 每个优化问题的潜在解被想象成d维空间上的一个点 我们称其为一个粒子 粒子在搜索空间中以一定的速度飞行 速度依据其本身和同伴的飞行经验进行动态调整 所有粒子都有一个被目标函数决定的适应值 并知道自己到目前为止发现的最好的位置 当前位置 以及目前为止整个群体所有粒子所发现的最好位置 粒子根据以下信息改变当前位置 当前位置 当前速度 当前位置与自己最好位置之间的距离 当前位置与群体最好位置之间的距离 6 2 2基本粒子群算法 6 2粒子群优化算法 2 基本粒子群算法数学描述已知优化问题为 第i个粒子表示为 粒子i速度记为 个体最好位置记为 也称为pbest群体最好位置记为Pg 也称为gbest 6 2 2基本粒子群算法 6 2粒子群优化算法 2 基本粒子群算法数学描述c1和c2为正常数 称为加速系数 r1和r2为 01 之间的随机数 上式中的速度和位置向量都被限制在有限区域内 一旦超出界限 则按照响应的最大最小界限计算 6 2 2基本粒子群算法 6 2粒子群优化算法 3 基本粒子群算法流程设定粒子群系统相关参数随机初始化粒子群 计算每个粒子的适应值统计个体极值pbest和群体极值gbest更新每个粒子的速度和位置判断是否满足停止条件 若满足则进行步骤6 若不满足则重复步骤3 5 返回当前群体极值gbest 6 2 2基本粒子群算法 6 2粒子群优化算法 1 粒子群算法主要研究方向算法分析 粒子群拓扑结构 参数选择与优化 社会行为与生物行为的模拟 与其他演化计算的融合 应用 6 2 3改进粒子群算法 6 2粒子群优化算法 2 几种常见的粒子群改进算法 线性递减惯性权重 收敛因子 最大速度 规范系数二进制PSO 离散PSO并行PSO 小生境PSO混合PSO 模糊PSO 混沌PSO HPSO 免疫PSO 6 2 3改进粒子群算法 6 2粒子群优化算法 3 标准粒子群算法 惯性权重法惯性权重概念是由Y Shi和Eberhart于1998年提出的其中的 称为惯性系数 通常随算法的搜索过程从0 9到0 4线性递减 合适的 取值能够提供算法局部探索与全局开发的平衡能力 同时也降低了算法对于每一回合的速度阈值设定的要求 较大的 使粒子具备较强的开发能力 较小的 使粒子具备探索能力 6 2 3改进粒子群算法 6 2粒子群优化算法 4 收敛 压缩 因子法在惯性权重法的基础上 1999年Clerc提出了收敛因子法其中 k 0 1 c1 c2 4 通常设 4 1 K 0 729 收敛因子法的有点在于能够在广度搜索的前提下保证算法的收敛 无需设定速度最大限制 6 2 3改进粒子群算法 6 2粒子群优化算法 5 模糊粒子群优化算法2001年 Y Shi和Eberhart提出了模糊粒子群算法 FuzzyPSO 用于解决自适应调整惯性权重递减问题 FuzzyPSO的基本思想是建立一个模糊推理系统 根据当前搜索的状态来判断下一回合应该使用怎样的惯性权重FuzzyPSO的惯性权重模糊推理系统的输入模糊量有 1 当前惯性权重 大 中 小2 规范化当前最优值性能评价 NCBPE 好 中 差FuzzyPSO的惯性权重模糊推理系统的输出模糊量为下一时刻应该使用的惯性权重 6 2 3改进粒子群算法 6 2粒子群优化算法 FuzzyPSO模糊推理系统界面双输入单输出 6 2 3改进粒子群算法 6 2粒子群优化算法 规范化当前最优性能评价 NCBPE 3个三角形模糊集 0 1 6 2 3改进粒子群算法 6 2粒子群优化算法 6 2 3改进粒子群算法 6 2粒子群优化算法 当前惯性权重3个三角形模糊集 0 2 1 1 6 2 3改进粒子群算法 6 2粒子群优化算法 下一时刻的惯性权重的调整量3个三角形模糊集 0 12 0 05 6 2 3改进粒子群算法 6 2粒子群优化算法 模糊推理规则共9条规则1 1 21 2 11 3 12 1 32 2 22 3 13 1 33 2 23 3 1 6 2 3改进粒子群算法 6 2粒子群优化算法 5 模糊粒子群优化算法模糊推理系统 响应曲面 6 2 3改进粒子群算法 6 2粒子群优化算法 5 模糊粒子群优化算法 优化性能比较测试目标函数 Rosenbrock函数 6 2 3改进粒子群算法 6 2粒子群优化算法 5 模糊粒子群优化算法 优化性能比较 6 3 1粒子群算法应用概述 6 3粒子群算法应用 1 粒子群算法的特点粒子群算法很好的模拟了社会行为和个体行为 在连续空间的多极值寻优问题中表现出了很好的性能 粒子群算法结构简单 易于实现粒子群算法经过改良 能够很好的跟其他智能优化方法相结合 同时也能扩展到动态规划 离散空间寻优等更具实用意义的领域粒子群算法在收敛速度和精度方面能够很好的取得平衡 并易于通过参数的改变来调整算法的倾向性 6 3 1粒子群算法应用概述 6 3粒子群算法应用 2 粒子群算法的应用领域控制领域模糊控制器 电机控制 机器人实时路径规划 优化领域无线路由协议 多目标优化 工作调度 识别决策领域语言分析 病症诊断 图像分割 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 1 PID控制问题描述 变量列表 u t 控制器输出e t 控制器输入Kp 比例放大器Ki 控制器积分系数Kd 控制器微分系数 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 1 PID控制问题描述PID控制问题的核心即选择三个合适的参数使得控制系统的性能达到最佳 通常 衡量一个控制系统的指标有三个方面 稳定性 准确性和快速性 具体的性能指标有 积分误差 上升时间 超调量等 常见的确定PID控制器参数的方法有 ZN动态特性法 CC响应曲线法 ISE整定法 极点配置法 根轨迹法 专家智能型PID整定技术 基于模糊推理的PID参数自整定技术以及基于其他智能优化方法 神经网络 遗传算法 免疫算法和蚁群算法等 的整定技术 基于PSO的PID参数整定属于智能优化PID参数方法的一种 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 2 PSO优化PID参数算法的模型初始化 1 粒子的设定 将PID控制器的一组参数 Kp Ki Kd 作为PSO算法中的一个粒子的位置 具体数值可随机选择 2 适应值函数 需要该函数能够反映控制器的性能 常用的目标函数有 其中 4 1 e t 为控制误差 u t 为控制量 ey为超调量 tu为上升时间 1至 4是各个评价量的系数 反映了控制系统对于不同性能的重视程度 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 3 PSO优化PID参数的仿真实验在Matlab Simulink平台下对控制对象进行PID控制 控制对象的二阶传递函数为 G S 400 S2 50 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 3 PSO优化PID参数的仿真实验用标准GA算法与PSO算法进行PID控制参数的优化 使用相同的目标函数 并比较两者的收敛性能 目标参数与算法参数设置如下 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 3 PSO优化PID参数的仿真实验目标函数收敛曲线如下 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 3 PSO优化PID参数的仿真实验收敛结果对应的响应曲线 6 3 2PSO在PID控制中的应用 6 3粒子群算法应用 3 PSO优化PID参数的仿真实验目标函数收敛结果如下表 结果分析 在PID控制参数优化问题上 PSO算法在收敛速度上明显优于GA算法 其收敛精度也略优于GA算法 6 3 3PSO在TSP问题中的应用 6 3粒子群算法应用 1 离散PSO算法标准的PSO算法只能应用于连续空间问题的优化 针对离散问题 Kennedy和Eberhart在1997年就提出了二进制离散PSO算法 将每个粒子的各个状态分量限定为0和1两种状态 并定义粒子的运行速度在各个分量上的投影S vid 为该粒子在此分量上取状态1的可能性 此后Hendlass 王康平等人通过对离散PSO算法的改进 将其成功地引入了TSP问题中 并取得了较好的结果 6 3 3PSO在TSP问题中的应用 6 3粒子群算法应用 2 离散PSO算法的核心问题如何定义不同粒子之间的距离 如何更新每个粒子的位置 3 TSP问题简述 狭义 地图上共有m个城市 任意两个城市之间的距离已知 推销员要遍历所有的城市回到出发点 每个城市只能去一次 求最短的遍历路径 6 3 3PSO在TSP问题中的应用 6 3粒子群算法应用 4 基于离散PSO的TSP问题求解粒子定义 粒子Xi是由1到m共m个数字随机排序组成的长度为m的向量 记为 距离定义 粒子Xi和Xj之间的距离定义为两者适应值函数的绝对差 6 3 3PSO在TSP问题中的应用 6 3粒子群算法应用 4 基于离散PSO的TSP问题求解粒子更新方法 基于 交换子 的粒子更新 交换子 记为 swap Xi Xj k 其中Xi为待更新粒子 Xj为个体极值或群体极值 1 记录Xi的第k位xik 并找到Xj中与xik相等的值所在的位置 记为xjl 即xjl xik 2 从xik xjl分别向后搜索 搜索到末尾则转至第一位 找到第一对不相等字节 分别记为xip xjq 3 在Xi中寻找等于xjq的字节 并将该字节与xip交换 即完成了一次交换子操作 4 如需完成多次 则接着重复步骤2 3 6 3 3PSO在TSP问题中的应用 6 3粒子群算法应用 4 基于离散PSO的TSP问题求解粒子更新方法 举例说明 m 7 k 2 6 3 3PSO在TSP问题中的应用 6 3粒子群