微粒群优化算法.ppt

《微粒群优化算法.ppt》由会员分享，可在线阅读，更多相关《微粒群优化算法.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、12023/4/2微粒群优化算22023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望32023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望42023/4/2群体智能群体智能(Swarm intelligence,SI)这个概念来自对

2、自然界中昆这个概念来自对自然界中昆虫群体的观察和模拟。一般群居性生物通过协作表现出的宏虫群体的观察和模拟。一般群居性生物通过协作表现出的宏观智能行为特征被称为群体智能。观智能行为特征被称为群体智能。一个群体智能系统通常包含多个简单的智能个体一个群体智能系统通常包含多个简单的智能个体(智能体智能体)，每个智能体与其它智能体以及环境之间存在相互作用。，每个智能体与其它智能体以及环境之间存在相互作用。所有智能体遵守着非常简单的规则，尽管没有中心控制结所有智能体遵守着非常简单的规则，尽管没有中心控制结构指导单个智能体的行为，但是，各智能体之间直接或间构指导单个智能体的行为，但是，各智能体之间直接或间接

3、的局部通信催生了系统复杂全局行为的产生。接的局部通信催生了系统复杂全局行为的产生。(来自来自 Wikipedia)群体智能的概念群体智能的概念52023/4/2n大自然中的智能群体：蚂蚁群、鸟类群体、细菌繁衍和鱼群等大自然中的智能群体：蚂蚁群、鸟类群体、细菌繁衍和鱼群等等。等。n典型的群体智能优化算法包括：蚁群优化算法、微粒群优化算法、典型的群体智能优化算法包括：蚁群优化算法、微粒群优化算法、菌群算法、鱼群算法和蛙跳算法等。菌群算法、鱼群算法和蛙跳算法等。62023/4/272023/4/2蚁群优化蚁群优化蚁群优化蚁群优化(Ant colony optimization,ACO)是是Dorig

4、o在在1992年提出年提出的一种快速随机优化技术，被用于处理那些可以归纳为发现图中的一种快速随机优化技术，被用于处理那些可以归纳为发现图中最短路径的计算问题。最短路径的计算问题。(Dorigo and Sttzle,2004)现实世界中，现实世界中，(初始状态初始状态)每个蚂蚁将在一定范围内随机游走，每个蚂蚁将在一定范围内随机游走，并通过在所经过路径上遗留信息素的方式，不断把相关的食物并通过在所经过路径上遗留信息素的方式，不断把相关的食物信息反馈给蚁群。如果其他蚂蚁发现了那条路径，那么这些蚂信息反馈给蚁群。如果其他蚂蚁发现了那条路径，那么这些蚂蚁很可能不再保持原来的随机游走，而跟随这条路径蚁很

5、可能不再保持原来的随机游走，而跟随这条路径(一条路一条路径上的信息素越多，其他蚂蚁选择这条路径的可能性越大径上的信息素越多，其他蚂蚁选择这条路径的可能性越大)。如果由该路径他们最终发现了食物，那么他们将在这条路径上如果由该路径他们最终发现了食物，那么他们将在这条路径上继续增加信息素。由于这条路径上信息素的不断增加，最终所继续增加信息素。由于这条路径上信息素的不断增加，最终所有蚂蚁将找到食物。有蚂蚁将找到食物。82023/4/2有兴趣的同学可以参考有兴趣的同学可以参考Marco Dorigo的的 Ant Colony Optimization 个人网址个人网址,或或者他的专著者他的专著“Ant

6、Colony Optimization”。(该图来自该图来自 Theresa Meggie et al.)(a)(b)(c)(d)92023/4/2 微粒群优化算法微粒群优化算法(Particle swarm optimization,PSO)是是Kennedy和和Eberhart在在1995年提出的。它的提出既有人工智能和社会心理学年提出的。它的提出既有人工智能和社会心理学的背景，又有工程和计算机科学的背景。的背景，又有工程和计算机科学的背景。微粒群优化算法微粒群优化算法正如提出者所说正如提出者所说“微粒群优化算法模拟了昆虫微粒群优化算法模拟了昆虫(或人类或人类)的社会行的社会行为。个体在学

7、习自身经验的同时相互交换信息，由此，种群成员为。个体在学习自身经验的同时相互交换信息，由此，种群成员将逐渐移到问题空间中较好的区域。将逐渐移到问题空间中较好的区域。”为什么取名“微粒”而不是“点“呢？Kennedy和和Eberhart都认为速度和都认为速度和加速度比较适合应用于微粒加速度比较适合应用于微粒。(X.Li and A.P.Engelbrecht)102023/4/2在某些方面在某些方面PSO与细胞自动机与细胞自动机(Cellular Automata,CA)是紧密联系的是紧密联系的 每一个细胞个体同时被更新；细胞状态的变化只受细胞自身和周遭细胞的影响；所有细胞均遵循同样的更新规则。

8、(Rucker,1999)微粒群中的个体(微粒)可理解为CA中的细胞，这些细胞在不同维上可以同时改变它的状态。细胞自动机细胞自动机由一些特定规则的格子所组成，每个格子看做是一个由一些特定规则的格子所组成，每个格子看做是一个细胞；每一个细胞可以具有一些状态，但是在某一时刻只能处一细胞；每一个细胞可以具有一些状态，但是在某一时刻只能处一种状态之中。随着时间的变化，格子上的每一个细胞根据周围细种状态之中。随着时间的变化，格子上的每一个细胞根据周围细胞的情形，按照相同的法则而改变状态。换句话说，一个细胞的胞的情形，按照相同的法则而改变状态。换句话说，一个细胞的状态由上一时刻所围绕细胞的状态所决定。状态

9、由上一时刻所围绕细胞的状态所决定。112023/4/2闪光灯闪光灯(blinker)在在MatlabMatlab中输入命令中输入命令lifelife，就可以进入简单的生命游戏仿真。，就可以进入简单的生命游戏仿真。滑翔机滑翔机(glider)(glider)两维细胞自动机两维细胞自动机生命游戏生命游戏(J.H.Conway)闪光灯：闪光灯：在叠代过程中，细胞群会在有限的叠代次数内周期循环其形状滑翔机：滑翔机：在有限的叠代次数内稳定地移动其形状当细胞自动机在电脑上模拟的时候，几乎可以复制出类似于自然界当中实际发生的动力系统122023/4/2PSO与遗传算法(GeneticAlgorithm,GA

10、)之间联系：uPSO和GA都是基于种群进行搜索的，具有本质并行性；u两种算法都是以目标函数值为搜索信息，适用于各类优化问题；u“适者生存”规则不适用于PSO。尽管PSO也利用适应值概念，但是适应值小的微粒不会灭亡；u没有交叉和变异等遗传操作算子；u每个微粒利用自身经验和邻域中其它微粒的经验更新位置。PSO自身具有的特点(RuiMendes,2004)：u易于理解和描述；u易于实现；u可调参数较少；u所需种群或微粒群规模较小；u计算效率高，收敛速度快。132023/4/2粒子群优化算法的发展粒子群优化算法的发展n 19971997年，年，EberhartEberhart首次提出了微粒群优化算法的

11、离散二进制版，首次提出了微粒群优化算法的离散二进制版，揭开了离散变量微粒群优化算法研究的序幕。揭开了离散变量微粒群优化算法研究的序幕。n 1998 1998年和年和19991999年，年，ShiShi和和ClercClerc等分别提出了基于惯性模型和压等分别提出了基于惯性模型和压缩因子的算法模型。缩因子的算法模型。n 2002 2002年年,Clerc,Clerc等给出了等给出了PSOPSO的稳定性和收敛性分析。的稳定性和收敛性分析。n 2002 2002年，年，CoelloCoello等把等把PSOPSO算法用于多目标优化问题，为算法研算法用于多目标优化问题，为算法研究注入了新的动力究注入了

12、新的动力。n 2004 2004年，年，KennedyKennedy和和MendesMendes研究微粒间拓扑结构，给出了一种研究微粒间拓扑结构，给出了一种全息微粒群优化算法全息微粒群优化算法。n 20062006年，年，Parrott Parrott 和和 LiLi 提出了用于动态多峰优化问题的提出了用于动态多峰优化问题的PSOPSO。142023/4/2微粒群优化算法的应用微粒群优化算法的应用 函数优化函数优化数值函数优化，动态、多峰值、多目标数值函数优化，动态、多峰值、多目标 组合优化组合优化旅行商问题、布局优化等问题旅行商问题、布局优化等问题生产调度生产调度工件加工问题工件加工问题自动

13、控制自动控制智能控制器优化、最优控制器设计智能控制器优化、最优控制器设计机器人学机器人学路径规划、协调控制路径规划、协调控制机器学习机器学习分类、数据挖掘分类、数据挖掘图像处理图像处理多边形近似问题多边形近似问题机械设计机械设计碳纤维强化塑料碳纤维强化塑料神经网络训练神经网络训练参数辨识等等参数辨识等等152023/4/2历年发表论文的数目历年发表论文的数目与微粒群优化相关论文的数目分布与微粒群优化相关论文的数目分布162023/4/2相关资源相关资源20012001年年,Kennedy,Kennedy等出版优秀著作等出版优秀著作Swarm IntelligenceSwarm Intellig

14、ence，对微粒群，对微粒群优化及其应用作了全面而系统的论述。优化及其应用作了全面而系统的论述。专著专著 19991999年首届进化计算会议上微粒群优化算法即被定为会议讨论议题。年首届进化计算会议上微粒群优化算法即被定为会议讨论议题。IEEE IEEE 群体智能研讨会群体智能研讨会 Genetic and Evolutionary Computation Genetic and Evolutionary Computation 国际会议国际会议会议及其杂志会议及其杂志网址网址 http:/，http:/icdweb.cc.purdue.edu/hux/pso.shtml.Evolutionar

15、y Computation(MIT press)Evolutionary Computation(MIT press)IEEE Transactions on Evolutionary ComputationIEEE Transactions on Evolutionary ComputationIEEE Transactions on Neural NetworkIEEE Transactions on Neural NetworkIEEE Transactions on Systems,Man,and Cybernetics Part:A,BIEEE Transactions on Sys

16、tems,Man,and Cybernetics Part:A,BSwarm IntelligenceSwarm Intelligence172023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望182023/4/2算法原理算法原理1 1）一个鸟群正在某一区域内随机寻找食物，在这一区域只有）一个鸟群正在某一区域内随机寻找食物，在这一区域只有一份食物；一份食物；2 2）鸟群不知道这份食物究竟在哪里，但是它们知道食物距

17、离）鸟群不知道这份食物究竟在哪里，但是它们知道食物距离它们有多远以及它们同伴的位置。它们有多远以及它们同伴的位置。首先给出两个假设：首先给出两个假设：鸟群怎样尽量快的找到食物？鸟群怎样尽量快的找到食物？一个最有效的方法就是搜寻目前离食物最近同伴的位置。一个最有效的方法就是搜寻目前离食物最近同伴的位置。192023/4/2单个鸟单个鸟整个鸟群整个鸟群鸟群寻找食鸟群寻找食物的飞行策物的飞行策略略单个微粒单个微粒由多个微粒组由多个微粒组成的微粒群成的微粒群微粒位置和速微粒位置和速度的更新策略度的更新策略PSO鸟群行为鸟群行为最大化问题最大化问题一个微粒代表问题一个微粒代表问题的一个解的一个解每个微粒

18、都有一个每个微粒都有一个由被优化函数值决由被优化函数值决定的适应值定的适应值 每个微粒通过跟踪每个微粒通过跟踪自身找到的最好位自身找到的最好位置以及邻域内其它置以及邻域内其它微粒找到的最好位微粒找到的最好位置，完成对整个搜置，完成对整个搜索空间的搜索索空间的搜索PSOPSO就是对鸟群或鱼群寻找食物这种群体行为的模拟。就是对鸟群或鱼群寻找食物这种群体行为的模拟。202023/4/2基本基本PSO ：t t次迭代后第次迭代后第i i个微粒的位置；个微粒的位置；：0,10,1之间服从均匀分布的两个随机数；之间服从均匀分布的两个随机数；：微粒微粒 从初始到目前迭代次数所得到的最好位置，通从初始到目前迭

19、代次数所得到的最好位置，通 常称为微粒个体最优点；常称为微粒个体最优点；：微粒微粒 邻域内所有微粒从开始到目前迭代次数所得邻域内所有微粒从开始到目前迭代次数所得 到的最优位置，通常称为微粒全局最优点；到的最优位置，通常称为微粒全局最优点；：两个：两个：两个：两个加速度系数，用来控制加速度系数，用来控制 和和 对微粒飞行方向的对微粒飞行方向的 影响。影响。212023/4/2基本基本PSO速度冲量认知项社会项微粒速度更新公式微粒速度更新公式(1a)包括三项包括三项:u速度冲量：指引微粒继续飞行的先前微粒速度；u认知项：当前微粒重新返回所经最好位置的趋势；u社会项：当前微粒被其邻域所找到的最好位置

20、吸引的趋势。邻域拓扑结构可以用来控制微粒之间信息的传播，即社会项的邻域拓扑结构可以用来控制微粒之间信息的传播，即社会项的影响，部分典型结构如全连接形、环形或星形等。影响，部分典型结构如全连接形、环形或星形等。全局版全局版PSO(gbest PSO)和局部版和局部版PSO(lbest PSO)。222023/4/2微粒速度限制微粒速度限制由式(1a)可知，微粒速度具有突增到一个大值的趋势。为防止发生上述现象，避免微粒进一步发散，利用参数 限制微粒的飞行速度。如果微粒的速度超过 ，则取相应微粒速度为。232023/4/2PSOPSO程序程序(最大化问题最大化问题)1.在搜索空间中随机生成在搜索空间

21、中随机生成N个微粒，组成微粒群个微粒，组成微粒群;2.重复下列步骤：重复下列步骤：for(i=1 to N)评价微粒适应值评价微粒适应值 ；if for (j=1 to D)/*D为决策变量维数为决策变量维数*/由式由式(1)更新当前微粒的第更新当前微粒的第j个分量；个分量；end end3.如果满足终止条件，那么终止算法，并输出结果如果满足终止条件，那么终止算法，并输出结果./*更新微粒全局最优点更新微粒全局最优点*/242023/4/2惯性权重惯性权重由于速度冲量容易导致微粒按照先前速度方向继续移动，因而，Shi提出个惯性权重 w，用来控制先前微粒速度所产生的影响。惯性权重在在没没有有 的

22、的特特定定情情况况下下，基基于于惯惯性性权权重重的的PSO也也能能收收敛敛。控制参数分析控制参数分析252023/4/2惯性权重惯性权重(续续)通过调节通过调节w值，可以控制值，可以控制PSOPSO的全局探索和局部开发能力：的全局探索和局部开发能力：w1：微粒速度随迭代次数的增加而增加，微粒发散。0w1：微粒减速，算法的收敛性依靠惯性权重和。w0：微粒速度随迭代次数的增加而减小，最后趋近0，算法收敛。实验表明，表明，w=0.7298和和 时算法具有较好的时算法具有较好的收敛性能。收敛性能。Eberhart和Shi：w的线性递减策略；陈贵敏等：开口向下抛物线、开口向上抛物线和指数曲线等3种非线性

23、权值递减策略；Shi和Eberhart：以当前惯性权重值和当前算法最优值为模糊系统的输入，给出一种惯性权重的模糊控制方法。自适应或动态惯性权重值：自适应或动态惯性权重值：262023/4/2惯性权重惯性权重(续续)272023/4/2加速度系数加速度系数(Accelerationcoefficients)：两个两个两个两个加速度系数，又称学习因子，用来控制加速度系数，又称学习因子，用来控制 和和 对微粒对微粒 飞行方向的影响。飞行方向的影响。每个微粒执行局部搜索；微粒群转化为一个随机爬山法；微粒逐渐移向 和 的加权均值；算法比较适合于单峰优化问题；算法比较适合于多峰优化问题。282023/4/

24、2自适应或动态加速度系数：自适应或动态加速度系数：实验建议：Ratnaweera等：基于迭代次数对两个加速度系数进行动态调节，其中，随进化代数增加而减小；相反，随进化代数增加而增大。292023/4/2压缩因子压缩因子(Constriction factor)Clerc和和Kennedy建议把一个压缩因子引入到微粒速度更新公式建议把一个压缩因子引入到微粒速度更新公式(1a)：压缩因子其中，如果设定，那么，公式(2a)等同于公式(3a)。(Shi,2004)通常，k取1，压缩因子。(Clerc and Kennedy,2002)302023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运

25、动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望312023/4/2微粒运动轨迹分析微粒运动轨迹分析l 微粒群中只有1个或2个微粒；l 微粒更新公式中没有随机元素；l 一维决策变量；l 事先指定微粒的初始位置及速度。考虑如下简化的考虑如下简化的PSOPSO算法：算法：下述仿真取下述仿真取，并且我们知道微粒的两个初始位置并且我们知道微粒的两个初始位置和和。要优化的函数是要优化的函数是，其中其中讨论如下两种情况：讨论如下两种情况：前两个位置位于问题最小值的同一侧(初始位置为)

26、。前两个位置位于问题最小值两侧(初始位置为)。322023/4/2因为微粒个体最优点始终等于因为微粒个体最优点始终等于x，因此，微粒未能收敛到问题最，因此，微粒未能收敛到问题最小值，即算法陷入早熟收敛。小值，即算法陷入早熟收敛。左图出示：微粒速度左图出示：微粒速度v过早趋近于过早趋近于0 0，从而导致算法早熟收敛。，从而导致算法早熟收敛。微粒轨迹微粒轨迹(单个微粒单个微粒)情况情况1：前两个位置位于问题最小值同一侧。：前两个位置位于问题最小值同一侧。332023/4/2微粒围绕问题最小值做震动，最终收敛到问题最小值。微粒围绕问题最小值做震动，最终收敛到问题最小值。左图出示：微粒速度时正时负，呈

27、螺旋状收敛到左图出示：微粒速度时正时负，呈螺旋状收敛到0。情况情况2：前两个位置位于问题最小值两侧。：前两个位置位于问题最小值两侧。342023/4/2微粒轨迹微粒轨迹(两个微粒两个微粒)该试验研究两个微粒，每个微粒具有一个个体最优点，并且可以该试验研究两个微粒，每个微粒具有一个个体最优点，并且可以随时获得另一个微粒的最优信息。每个微粒起始位置的设置与情随时获得另一个微粒的最优信息。每个微粒起始位置的设置与情况况1和和2相同。相同。每个微粒的移动时常受另一个微粒的最优信息的影响。尽管微粒每个微粒的移动时常受另一个微粒的最优信息的影响。尽管微粒收敛速度比较慢，但是算法极有可能收敛到问题的最小值。

28、收敛速度比较慢，但是算法极有可能收敛到问题的最小值。352023/4/2两个微粒相互帮助，保证了他们以螺旋状的形式收敛到问题两个微粒相互帮助，保证了他们以螺旋状的形式收敛到问题的最优点。的最优点。微粒轨迹微粒轨迹(两个微粒两个微粒)362023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望372023/4/2PSO算法的收敛性算法的收敛性u VandenBergh(2002)、Trelea(2003)以及Bergh

29、和Engelbrecht(2006)已经证明PSO能够收敛到一个平衡状态。那么，u 对于全局版PSO 算法，如果u 这意味着随着迭代次数的增加所有微粒将收敛到一个点。u 但是，这不意味着微粒个体最优点和全局最优点的加权和就是问 题的最优解。382023/4/2如何防止上述问题的发生呢？如何防止上述问题的发生呢？如果式(2)中 ，那么，微粒仅依靠 更新其位置。进一步，如果上述状态持续足够代数后,那么 因此，有进一步解释：进一步解释：u 事实上，存在微粒群收敛到局部稳定点的可能。该局部稳定 点不是问题的全局最优点，甚至不是问题的局部最优点。392023/4/2部分典型方法部分典型方法:l Diss

30、ipativePSO(Xie,et al.,2002)-增加微粒群的多样性;lPSOwithmutation(Stacey,et al.,2004)-重新初始化已经收敛的微粒;lPSOwithpassivecongregation(He et al.,2004)-提高微粒群的多样性;lSpeciation-basedPSO(Li et al.,2006)-根据微粒之间相似程度，把整个微粒群划分为若干类。lSelf-organizingPSO(Ratnaweera,et al.2004)-改进算法的控制参数;lMulti-swarmparallelPSO,MPPSO(Belal M et al.

31、,2004)-利用多种群思想。方法一：方法一：防止所有或者部分微粒长期接近微粒的全局最优点，即，防止所有或者部分微粒长期接近微粒的全局最优点，即，满足满足402023/4/2部分典型方法：部分典型方法：l差分算法(Differential Evolution,DE)(Zhang and Xie,2003)l遗传算法(Genetic algorithm,GA)(Matthew et al.,2005);l爬山法;l模拟退火(Simulatedannealing,SA)(Nasser Sadati et al.,2006);l单纯形法(Simplexmethod,SM)(FanSKetal.,20

32、07).方法二：方法二：利用具有较强局部搜索能力的算法进一步细化利用具有较强局部搜索能力的算法进一步细化/开发开发PSOPSO所得结果。所得结果。412023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望422023/4/2微粒群拓扑结构微粒群拓扑结构每个微粒的行为受到邻域微粒的影响，该邻域可以看做微粒群拓每个微粒的行为受到邻域微粒的影响，该邻域可以看做微粒群拓扑中的一个子区域。微粒群拓扑中所有子区域通过一定方式相

33、互扑中的一个子区域。微粒群拓扑中所有子区域通过一定方式相互关联，共同对问题空间进行协同搜索。关联，共同对问题空间进行协同搜索。全局版全局版PSOPSO：每个微粒受整个微粒群所发现最好位置的影响，：每个微粒受整个微粒群所发现最好位置的影响，即每个微粒的邻域是整个微粒群；即每个微粒的邻域是整个微粒群；局部版局部版PSOPSO：每个微粒受所定义的局部邻域中微粒的影响，而：每个微粒受所定义的局部邻域中微粒的影响，而 微粒的邻域由拓扑图中每条边上距离它最近的微粒组成。微粒的邻域由拓扑图中每条边上距离它最近的微粒组成。常用的两类常用的两类PSO算法：算法：432023/4/2几种拓扑结构：几种拓扑结构：全

34、连接拓扑全连接拓扑(all)环形拓扑环形拓扑(ring)Von Neumann 拓扑拓扑星状拓扑星状拓扑(star)锥形拓扑锥形拓扑(pyramid)四聚类拓扑四聚类拓扑(clusters)全连接拓扑为全局拓扑，其余都为邻域规模不同的局部拓扑。全连接拓扑为全局拓扑，其余都为邻域规模不同的局部拓扑。部分图来自 Mendes 和Kennedy(2004).442023/4/2我们应该选择那种拓扑结构？我们应该选择那种拓扑结构？u 全连接拓扑信息传输速度快，相应地，全连接拓扑信息传输速度快，相应地，PSOPSO算法收敛速度快，算法收敛速度快，但是易于早熟收敛；环形拓扑信息传输速度最慢，相应地，但是易

35、于早熟收敛；环形拓扑信息传输速度最慢，相应地，PSO PSO算法收敛速度慢，但是微粒有更多的机会发现最优解。算法收敛速度慢，但是微粒有更多的机会发现最优解。u Kennedy(1999)Kennedy(1999)指出：在处理简单问题时，采用较小邻域的指出：在处理简单问题时，采用较小邻域的PSOPSO 算法性能较好；在处理复杂问题时，采用较大邻域的算法性能较好；在处理复杂问题时，采用较大邻域的PSOPSO算法性算法性 能较好。能较好。u Mendes Mendes和和Kennedy(2002)Kennedy(2002)在对比不同拓扑结构时发现：在对比不同拓扑结构时发现：Von Von Neuma

36、nn Neumann拓扑优于其它拓扑。拓扑优于其它拓扑。u Suganthan(1999)，在在PSO算法初期采用局部版算法初期采用局部版PSO,后期采用后期采用 全局版全局版PSO;u Hu和Eberhart(2002),提出了动态拓扑结构的概念。每次迭代时提出了动态拓扑结构的概念。每次迭代时 选择与当前微粒最近的选择与当前微粒最近的m个微粒作为它的新邻域。个微粒作为它的新邻域。452023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的

37、协同机器人搜索n研究展望462023/4/2并行微粒群优化算法并行微粒群优化算法 面对复杂优化问题,PSO在优化速度上显得“力不从心”。为求得满意的优化结果，常需要计算相当多次的函数值；对于一些实际问题，计算单个函数值就可能需要付出昂贵代价。并行算法具有如下优点(Jaimes,2007)：提高计算速度，减少优化时间；为问题提供更多的存储空间；提高种群的多样性；易于与其它算法并行。并行PSO的分类：主从式模式 细粒度模式 粗粒度模式 472023/4/2主从式模式，又称全局式PSO主处理器主处理器：执行微粒全局最优点的选择、微粒位置更新等算子；从处理器从处理器：并行计算多个微粒的函数值。算法每次

38、迭代时，算法每次迭代时，主处理器分配新生微粒到各从处理器；从处理器计算所接受微粒的函数值，并将其返回给主处理器；主处理器利用从处理器返回的微粒 函数值，首先更新微粒的个体最优 点和全局最优点，接着，更新微粒 的速度和位置。返回。缺点：由于未对PSO算法框架进行改动，所以该模式存在主从节点负荷忙闲 不均衡的问题482023/4/2细粒度模式，又称扩散式PSOl赋予每个微粒一个处理器。l对每个微粒，微粒全局最优点的选择和微粒位置更新皆在其所处处理器及其邻域(红色图标)中进行。l该模型可以最大限度的发挥算法的并行潜力l但算法的实现对处理器数量要求很高，其应用范围受到了很大限制。优缺点：优缺点：492

39、023/4/2粗粒度模式，又称迁移式PSOl 将随机生成的初始种群依处理器个数分割成若干个子种群，各 个子种群在不同的处理器上并行进化。l 每经过一定进化代数，各子群间交换若干最优信息。该模型不仅通信代价较小该模型不仅通信代价较小,而且非而且非常适合在通信带宽较低的集群上运常适合在通信带宽较低的集群上运行行,是适应性强且应用范围广的并是适应性强且应用范围广的并行模型。行模型。可以提高种群多样性，防止未成熟可以提高种群多样性，防止未成熟收敛的发生。收敛的发生。优点：优点：502023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微

40、粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望512023/4/2n 最初的PSO算法是从处理连续优化问题中发展起来的。n Kennedy和Eberhart首次将实数版PSO扩展为二进制 PSO。n 微粒位置为二进制向量，微粒速度仍为浮点向量；n 然而，微粒速度将被逻辑函数s(v)转化为判断位置项 选择0还是1的概率。二进制二进制PSO(Binary PSO)522023/4/2为了防止s(v)饱和，Kennedy等还建议将 限制在-4,4之间。其中，n具体更新公式如下：532023/4/2角度调节角度调节PSO(AngleM

41、odulatedPSO,AMPSO)n AMPSO算法是由Pampara、Engelbrecht和Franken提出的。n 取代进化二进制位串，算法利用PSO优化实参数(a,b,c,d)。PSO迭代后，把所得参数(a,b,c,d)值带入g(x)；在每个区间x上随机对g(x)值进行采样，产生一个0,1位值；所有位值组成优化问题的一个二进制解.其中，x为集合S中元素，S中元素为均匀分割的区间，其元素个数由需要产生的位的个数决定。例如，S 可以为0到10之间的10个区间(0,1,(1,2,(9,10。n 通过进化下述位串产生函数，求解具有二进制变量的优化问题。542023/4/2二进制位串的产生对于

42、一个区间x，随机对它所对应的g(x)值进行采样，如果采样值为正位值为1；否则，位值为0.a=d=0,b=c=1时g(x)曲线552023/4/2简洁简洁PSO(BareBonesPSO)u 简洁微粒群优化算法是Kennedy在2003年提出的。u 删除了传统的微粒速度更新公式。u 利用一个基于微粒全局最优点和个体最优点的高斯采样公 式，更新微粒位置：如果固定 和 不变，PSO将以中心在 和 之间的钟形分布对搜索空间进行采样。562023/4/2全息全息PSO(FullyInformedPSO)先前微粒更新公式：令，得由上式可见，微粒趋向于收敛到一个确定点，该点是微粒和全局最优点的加权和。个体最

43、优点572023/4/2进一步，可把 扩展为关于多个邻域微粒信息的加权和：其中，NB为当前微粒的邻域，为NB中第k个微粒的个体最优点。n 如果|NB|=2，和 ，那么上式退化为传统PSO。n 除 和 之外，上式允许我们自由利用更多的邻域信息。582023/4/2其它其它本态性PSO算法(Essential particle swarm)(Kennedy,2006)部落PSO(Tribes particle swarm)(Clerc,2006)自适应地调整微粒群的规模，因此不需要人为设置。自适应PSO(Adaptive PSO)(Zhan 等,2009)把PSO的整个搜索过程划分为全局探索、局部

44、开发、收敛和跳离等4个进化状态。根据状态的不同，动态调整惯性权重和学习因子等参数。小生境PSO(Niche PSO)(Brits 等,2007)把种群划分为若干子种群，每个子种群代表一个不同的解或小生境。592023/4/2测试函数测试函数SchafferGriewankAckleyRastrigin602023/4/2目目 录录n群体智能n基本微粒群优化算法n微粒运动轨迹分析n微粒群优化算法的收敛性n微粒群拓扑结构n并行微粒群优化算法n微粒群优化算法的改进或变形n用于多目标优化的微粒群优化算法n基于微粒群优化的协同机器人搜索n研究展望612023/4/2问题描述问题描述在日常生活、管理以及工

45、程等领域，存在着诸多需要使多个目标函数(可能相互冲突的)在给定区域上同时最优的问题，这类问题称为多目标或多准则优化问题(Multi-objectiveoptimizationproblems，MOP)。处理该类问题的目的是找到满足所有目标函数的最优解。图图5 5(Graphics from Li Xiaodong)622023/4/2多目标优化问题多目标优化问题:Pareto支配支配(Pareto dominance):对于给定解对于给定解 ，我们说它支配解，我们说它支配解 ，当且仅当，当且仅当 相关概念相关概念记为：记为：632023/4/2进一步解释：进一步解释：解2和3,解1和2,解1和

46、3是互不支配的；解3支配解5和6；解2支配解4、5和6。642023/4/2多目标微粒群优化算法多目标微粒群优化算法 包含足够多的包含足够多的ParetoPareto最优解，通过这些解可以近似给出真实最优解，通过这些解可以近似给出真实 Pareto Pareto前端的形状；前端的形状；无限接近或者已经包含在真正无限接近或者已经包含在真正ParetoPareto最优解集中；最优解集中；所对应所对应ParetoPareto前端应该具有尽可能好的均匀分布性和延展性。前端应该具有尽可能好的均匀分布性和延展性。MOPMOP的目标是，寻找满足如下条件的最优解集：的目标是，寻找满足如下条件的最优解集：利用利

47、用PSOPSO处理处理MOP,MOP,必须考虑如下方面：必须考虑如下方面：如何存储算法搜索过程中得到的如何存储算法搜索过程中得到的ParetoPareto最优解？通常问题的最优解？通常问题的ParetoPareto前前端是一个曲线或曲面，因而保存所得所有端是一个曲线或曲面，因而保存所得所有ParetoPareto最优解是不可能。这最优解是不可能。这需要需要PSOPSO保存一些典型解。保存一些典型解。如何为每个微粒选择它的如何为每个微粒选择它的？PSO需要发现需要发现Pareto前端上多种多样的最前端上多种多样的最优解，而不是单一解。这需要为不同微粒分配不同的优解，而不是单一解。这需要为不同微粒

48、分配不同的 。652023/4/2部分典型多目标微粒群优化算法：部分典型多目标微粒群优化算法：Fieldsend and Sigh(2002)-指出应该保存进化过程中所得所有非劣个体，并称这样指出应该保存进化过程中所得所有非劣个体，并称这样可以提高算法的收敛性。为保存所有非劣解，提出了一种数据结构可以提高算法的收敛性。为保存所有非劣解，提出了一种数据结构-即支配树。即支配树。MOPSO(Coello et al.,2002)-利用自适应划分网格的方法更新储备集；基于储备集利用自适应划分网格的方法更新储备集；基于储备集中元素在网格中的分布密度，选择微粒的全局最优点中元素在网格中的分布密度，选择微

49、粒的全局最优点.Mostaghim and Teich(2003)-利用微粒和储备集元素之间利用微粒和储备集元素之间Sigma 值的相似程度，选值的相似程度，选择微粒的全局最优点；通过小生境技术更新储备集。择微粒的全局最优点；通过小生境技术更新储备集。Non-dominated Sorting PSO(Li,2003)-首先利用首先利用N个当前微粒及个当前微粒及N个微粒个体最优个微粒个体最优点组成一个临时种群，接着采用点组成一个临时种群，接着采用NSGA-II中所提分等级方法从中选择中所提分等级方法从中选择N个微粒。个微粒。Maximino and Jonathan E.(2005)-利用适应

50、值共享技术维护微粒的多样性。利用适应值共享技术维护微粒的多样性。Mario and Kaori(2007)-利用利用“渐进渐进Pareto支配关系支配关系”选择微粒的全局最优点。选择微粒的全局最优点。Mostaghim and Teich(2003)-采用采用-支配方法控制外部储备集的规模。支配方法控制外部储备集的规模。Agrawal等等(2008)-在所提算法中，用一种聚类技术更新外部储备集。在所提算法中，用一种聚类技术更新外部储备集。Wang 和和Yang(2009)-提出了一种基于偏好顺序机制提出了一种基于偏好顺序机制(Preference order scheme)的最优性测度，评价储