群智能算法-(1)

智能计算方法与应用东北大学2010年第六章群智能算法•6.1群智能算法概述•6.2粒子群优化算法•6.3粒子群算法应用智能计算方法与应用东北大学2010年6.1群智能算法概述•6.1.1生物群体行为的启示•6.1.2群智能的概念•6.1.3群智能算法的分类智能计算方法与应用东北大学2010年智能计算方法与应用东北大学2010年智能计算方法与应用东北大学2010年智能计算方法与应用东北大学2010年智能计算方法与应用东北大学2010年“群众的力量是伟大的”鸟群通过协作进行捕食鱼聚集成群可以有效的逃避捕食者房间偏僻角落里的蛋糕总会先被蚂蚁发现头脑简单的蜜蜂却能构造出世界上最完美的建筑物6.1.1生物群体行为的启示6.1群智能算法概述智能计算方法与应用东北大学2010年生物群中的每个个体只有简单的信息处理能力和行为能力。鸟群：飞行，捕食，避碰……昆虫：爬行，觅食，产生信息素……群体中各个个体之间可以进行信息交互。鸟群：视觉，听觉，磁场……昆虫：感知信息素……群体的能力要远远超出个体能力的简单叠加信息感知能力分工协作能力适应生存能力6.1.1生物群体行为的启示6.1群智能算法概述智能计算方法与应用东北大学2010年1.群智能(SwarmIntelligence，SI)的概念发展过程分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。——byBeni，Hackwood任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。——byBonabeau、Dorigo&Theraula无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。——byBonabeau6.1.2群智能的概念6.1群智能算法概述智能计算方法与应用东北大学2010年2.定义SI的五条基本原则（byMarkMillonas1994)ProximityPrinciple:群内个体具有能执行简单的时间或空间上的评估和计算的能力。QualityPrinciple:群内个体能对环境（包括群内其它个体）的关键性因素的变化做出响应。PrincipleofDiverseResponse:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。StabilityPrinciple:不是每次环境的变化都会导致整个群体的行为模式的改变。AdaptabilityPrinciple:环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。6.1.2群智能的概念6.1群智能算法概述智能计算方法与应用东北大学2010年3.SI的核心思路——“Mindissocial”认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。4.SI的意义和发展前景群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。6.1.2群智能的概念6.1群智能算法概述智能计算方法与应用东北大学2010年广义的群智能算法包括：粒子群算法：模拟鸟群觅食行为蚁群算法：模拟蚁群觅食行为免疫算法：模拟生物免疫系统工作机理细菌觅食算法：模拟大肠杆菌觅食行为混合算法：多种群智能算法的结合6.1.3群智能算法的分类6.1群智能算法概述智能计算方法与应用东北大学2010年SI与EC的相同点都研究个体与群体的关系都存在个体之间的信息传递都是为了解决实际问题，而非单纯的模拟自然现象都属于随机搜索算法SI与EC的不同点SI模拟的是个体之间的协同作用，而EC模拟的是适者生存的自然选择机制。6.1.4群智能算法与进化计算的异同6.1群智能算法概述智能计算方法与应用东北大学2010年6.2粒子群优化算法•6.2.1粒子群算法概述•6.2.2基本粒子群算法•6.2.3改进粒子群算法智能计算方法与应用东北大学2010年1.粒子群算法的起源粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个复杂适应系统。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：•1）避免与相邻的鸟发生碰撞冲突；•2）尽量与自己周围的鸟在速度上保持协调一致；•3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，boids系统就实现了非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体6.2.1粒子群算法概述6.2粒子群优化算法智能计算方法与应用东北大学2010年2.粒子群算法的提出粒子群算法最早是由美国的社会心理学家Kennedy和电气工程师Eberhart于1995年提出，他们在Reynolds的工作基础上引入了食物要素，进一步模拟了鸟群飞行觅食的行为，并发现该方法可以应用于复杂全局寻优问题的求解。粒子群优化算法的英文为“ParticleSwarmOptimization”，通常缩写为PSO6.2.1粒子群算法概述6.2粒子群优化算法智能计算方法与应用东北大学2010年3.粒子群算法的产生背景（一）：复杂适应系统（CAS）CAS是指其内部的成员(Agent)能够通过与其他成员以及外界环境的交流，并根据学习经验调整自身的结构和行为，进而实现整个系统的演变和进化的系统CAS的特点表现为：•主体(AdaptiveAgent)是主动的、活的实体；•个体与环境(包括其他个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；•宏观与微观有机结合•引进随机因素的作用，具有更强的描述和表达能力。6.2.1粒子群算法概述6.2粒子群优化算法智能计算方法与应用东北大学2010年3.粒子群算法的产生背景（二）：人工生命（AL）人工生命是对具有自然生命现象和行为特征的人造系统的研究，是一门涉及到生命科学，复杂性科学，人工智能，计算机科学，经济学，哲学和语言学等多学科的交叉学科，其研究模式主要体现为两类：•如何利用计算技术研究生物现象；•如何利用生物技术研究计算问题；人工生命的研究挑战主要为以下三类•TheTransitionofLife•TheEvolutionaryPotentialofLife•TheRelationbetweenLifeandMindandCulture6.2.1粒子群算法概述6.2粒子群优化算法智能计算方法与应用东北大学2010年4.粒子群算法的基本原则接近原则：粒子与群体应能够依照目标前进特性原则：群体应该能够反应环境的变化，当所处环境并非最佳解空间时，能够快速飞离该区域。不同响应原则：群体不会向不佳的解前进稳定原则：环境改变时，群体移动不会改变其运动模式适应原则：计算当下最佳解时，群体将会考量适当的参数变动。6.2.1粒子群算法概述6.2粒子群优化算法智能计算方法与应用东北大学2010年5.粒子群算法的基本概念6.2.1粒子群算法概述6.2粒子群优化算法最优化问题粒子群算法鸟群觅食行为解空间粒子可行空间天空候选解粒子鸟的位置候选解集粒子群鸟群解的搜索速度粒子速度鸟的速度目标函数适应度函数找到食物的可能性单个候选解搜索过程中的最优点个体极值某一只鸟记忆中最接近食物的位置所有候选解搜索过程中的最优点全局极值整个鸟群觅食过程中最接近食物的位置智能计算方法与应用东北大学2010年1.基本粒子群算法思想描述在PSO中，每个优化问题的潜在解被想象成d维空间上的一个点，我们称其为一个粒子。粒子在搜索空间中以一定的速度飞行，速度依据其本身和同伴的飞行经验进行动态调整。所有粒子都有一个被目标函数决定的适应值，并知道自己到目前为止发现的最好的位置，当前位置，以及目前为止整个群体所有粒子所发现的最好位置。粒子根据以下信息改变当前位置:①当前位置；②当前速度；③当前位置与自己最好位置之间的距离；④当前位置与群体最好位置之间的距离6.2.2基本粒子群算法6.2粒子群优化算法智能计算方法与应用东北大学2010年2.基本粒子群算法数学描述已知优化问题为：第i个粒子表示为：；粒子i速度记为：个体最好位置记为，也称为pbest群体最好位置记为Pg，也称为gbest;6.2.2基本粒子群算法6.2粒子群优化算法minf(x)=f(x1;x2;¢¢¢;xd);s.t.xi2[Li;Ui];i=1;2;¢¢¢;nminf(x)=f(x1;x2;¢¢¢;xd);s.t.xi2[Li;Ui];i=1;2;¢¢¢;nXi=(xi1;xi2;¢¢¢;xid)Xi=(xi1;xi2;¢¢¢;xid)Pi=(pi1;pi2;¢¢¢;pid)Pi=(pi1;pi2;¢¢¢;pid)Vi=(vi1;vi2;¢¢¢;vid)Vi=(vi1;vi2;¢¢¢;vid)智能计算方法与应用东北大学2010年2.基本粒子群算法数学描述c1和c2为正常数，称为加速系数；r1和r2为[01]之间的随机数。上式中的速度和位置向量都被限制在有限区域内，一旦超出界限，则按照响应的最大最小界限计算6.2.2基本粒子群算法6.2粒子群优化算法Vi(t+1)=Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡Xi(t))Xi(t+1)=Xi(t)+Vi(t+1)Vi(t+1)=Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡Xi(t))Xi(t+1)=Xi(t)+Vi(t+1)惯性认知社会智能计算方法与应用东北大学2010年3.基本粒子群算法流程①设定粒子群系统相关参数②随机初始化粒子群，③计算每个粒子的适应值④统计个体极值pbest和群体极值gbest⑤更新每个粒子的速度和位置⑥判断是否满足停止条件，若满足则进行步骤6);若不满足则重复步骤3)~5)⑦返回当前群体极值gbest，6.2.2基本粒子群算法6.2粒子群优化算法智能计算方法与应用东北大学2010年1.粒子群算法主要研究方向算法分析；粒子群拓扑结构；参数选择与优化；社会行为与生物行为的模拟；与其他演化计算的融合；应用。6.2.3改进粒子群算法6.2粒子群优化算法智能计算方法与应用东北大学2010年2.几种常见的粒子群改进算法：线性递减惯性权重，收敛因子，最大速度，规范系数二进制PSO，离散PSO并行PSO，小生境PSO混合PSO：模糊PSO、混沌PSO、HPSO、免疫PSO6.2.3改进粒子群算法6.2粒子群优化算法智能计算方法与应用东北大学2010年3.标准粒子群算法——惯性权重法惯性权重概念是由Y.Shi和Eberhart于1998年提出的其中的ω称为惯性系数，通常随算法的搜索过程从0.9到0.4线性递减；合适的ω取值能够提供算法局部探索与全局开发的平衡能力，同时也降低了算法对于每一回合的速度阈值设定的要求。较大的ω使粒子具备较强的开发能力，较小的ω使粒子具备探索能力6.2.3改进粒子群算法6.2粒子群优化算法Vi(t+1)=!Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡Xi(t))Xi(t+1)=Xi(t)+Vi(t+1)Vi(t+1)=!Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡Xi(t))Xi(t+1)=Xi(t)+Vi(t+1)智能计算方法与应用东北大学2010年4.收敛（压缩）因子法在惯性权重法的基础上，1999年Clerc提出了收敛因子法其中，k∈[0,1],φ=c1+c2,φ4，通常设φ=4.1，K≈0.729.收敛因子法的有点在于能够在广度搜索的前提下保证算法的收敛，无需设定速度最大限制。6.2.3改进粒子群算法6.2粒子群优化算法Vi(t+1)=K(Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡Xi(t)))Xi(t+1)=Xi(t)+Vi(t+1)K=2k=j2¡'¡p'2¡4'jVi(t+1)=K(Vi(t)+c1r1(t)(Pi(t)¡Xi(t))+c2r2(t)(Pg(t)¡X