群智能算法【PPT课件】

东北大学信息学院陈东岳王晓哲,智能计算方法与应用,“群众的力量是伟大的”鸟群通过协作进行捕食鱼聚集成群可以有效的逃避捕食者房间偏僻角落里的蛋糕总会先被蚂蚁发现头脑简单的蜜蜂却能构造出世界上最完美的建筑物,6.1.1生物群体行为的启示,6.1群智能算法概述,生物群中的每个个体只有简单的信息处理能力和行为能力。鸟群：飞行，捕食，避碰昆虫：爬行，觅食，产生信息素群体中各个个体之间可以进行信息交互。鸟群：视觉，听觉，磁场昆虫：感知信息素群体的能力要远远超出个体能力的简单叠加信息感知能力分工协作能力适应生存能力,6.1.1生物群体行为的启示,6.1群智能算法概述,1.群智能(SwarmIntelligence，SI)的概念发展过程分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。byBeni，Hackwood任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。byBonabeau、Dorigo,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提出了收敛因子法其中，k0,1,=c1+c2,4，通常设=4.1，K0.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，121，211，312，132，222，313，133，223，31,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)适应值函数：需要该函数能够反映控制器的性能，常用的目标函数有：其中41，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粒子群算法应用,4.基于离散PSO的TSP问题求解粒子更新方法：每次更新中执行交换子操作的次数ns取决于粒子Xi和Xj之间的距离dfit(Xi,Xj),6.3.3PSO在TSP问题中的应用,6.3粒子群算法应用,4.基于离散PSO的TSP问题求解局部优化去交叉操作：“去交叉”操作即去掉路径中的交叉现象的过程。对一个粒子Xt设xti到xt(i+1)之间的连线记为linet,i;定义函数Corssover(linet,i,linet,j)是判断这两条线段是否有交叉的函数，有则返回True，否则返回False。去交叉操作伪代码如下：for(i=1;im-3;i+)for(j=i+2;jm;j+)if(crossover(linet,i,linet,j)isTrue)for(k=0;k=(j-i)/2;k+)exchange(xj-k,xi+k+1),6.3.3PSO在TSP问题中的应用,6.3粒子群算法应用,4.基于离散PSO的TSP问题求解算法步骤初始化粒子群计算适应度并搜索全局极值对每个粒子执行交换操作对全局极值执行去交叉操作如满足终止条件，结束