群体智能第二讲幻灯片.ppt

《群体智能第二讲幻灯片.ppt》由会员分享，可在线阅读，更多相关《群体智能第二讲幻灯片.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、群体智能第二讲第1页，共46页，编辑于2022年，星期二粒子群优化粒子群优化 第2页，共46页，编辑于2022年，星期二粒子群优化粒子群优化（Particle Swarm Optimization,简称PSO）1，又称为微粒群算法，是由美国的心理学家J.Kennedy和电气工程师R.Eberhart于1995年提出的一种算法。1 J.Kennedy and R.Eberhart.“Particle Swarm Optimization,”Proceedings of IEEE International Conference on Neural Networks,Perth,WA,1995,p

2、p.1942-1948.PSO是模拟鸟群飞行觅食行为的一种随机优化算法。第3页，共46页，编辑于2022年，星期二Kennedy和Eberhart的初衷是研究鸟的觅食行为，建立一个模型来模拟鸟群寻找食源的现象。Kennedy和Eberhart在实验中发现，这个模型有很强的优化能力。第4页，共46页，编辑于2022年，星期二PSO原理将问题问题的搜索空的搜索空间间类比于鸟类鸟类的的飞飞行空行空间间。将每一只每一只鸟鸟抽象为一个无质量无体积的微粒（Particle)，用于表征每个候候选选解解。优优化化寻寻求最求最优优解解等同于鸟鸟群群寻寻找食物找食物。PSO为每个微粒制定了类似于鸟类运动的简单行为

3、规则，从而使整个微粒群的运动表现出与鸟类觅食类似的特性，用于求解复杂优化问题。第5页，共46页，编辑于2022年，星期二PSO原理单个微粒，代单个微粒，代表一个解表一个解微粒群体微粒群体微粒位置和速微粒位置和速度的更新策略度的更新策略PSO单个鸟单个鸟整个鸟群整个鸟群鸟群寻找食物鸟群寻找食物的飞行策的飞行策略略鸟群行为鸟群行为PSOPSO是对鸟群寻找食物这种群体行为的模拟是对鸟群寻找食物这种群体行为的模拟第6页，共46页，编辑于2022年，星期二PSO算法每个粒子有一个位置位置和一个速度速度。粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最粒子本身所找到的最优优解，即解，即pB

4、est；另一个是整个种群的最整个种群的最优优解，即解，即gBest。鸟群怎样尽量快的找到食物？鸟群怎样尽量快的找到食物？一个有效的方法就是搜寻目前离食物最近同伴的位置。一个有效的方法就是搜寻目前离食物最近同伴的位置。第7页，共46页，编辑于2022年，星期二PSO算法假设搜索空间为d维，群体（Swarm）中的粒子数为n。在第t次迭代中，群体中第i个粒子的位置表示为：第i个粒子在飞行中所经过的最佳位置为：群体中所有粒子的 中最佳位置为：第i个粒子的位置变化速度为：第8页，共46页，编辑于2022年，星期二PSO算法每个粒子的位置按如下公式变化：其中 和 为0,1间的随机数；和 为加速系数，用来控

5、制 和 对粒子飞行方向的影响。若粒子i的位置的第j维超过范围 ，则取边界值。若粒子i的速度的第j维超过范围 ，则取边界值。第9页，共46页，编辑于2022年，星期二PSO算法速度冲量认知项社会项微粒速度更新公式包括三项微粒速度更新公式包括三项:速度冲量：指引微粒继续飞行的先前微粒速度。认知项：微粒重新返回其所经过的最好位置的趋势，既微粒本身 记忆的影响。社会项：微粒被当前最好位置吸引的趋势，既群体信息的影响。在三部分的共同作用下，微粒根据历史经验并利用全局信息，不断调整自己的位置，以期找到最优解。第10页，共46页，编辑于2022年，星期二1.在搜索空在搜索空间间中随机生成中随机生成n个微粒，

6、个微粒，组组成微粒群成微粒群;2.重复下列步重复下列步骤骤：for(i=1 to n)计计算微粒算微粒i的适的适应值应值 ；if then for (j=1 to d)/d为为决策决策变变量量维维数数 按公式更新微粒按公式更新微粒i的第的第j个分量个分量；end end3.如果如果满满足足终终止条件，那么止条件，那么终终止算法，并止算法，并输输出出结结果果.取值为适应值最高的取值为适应值最高的 ;/更新微粒全局最优点更新微粒全局最优点PSO算法第11页，共46页，编辑于2022年，星期二PSO算法惯性权重惯性权重速度冲量导致微粒按照先前速度方向继续移动。Yuhui Shi1提出一个惯性权重w来

7、控制先前微粒速度的影响。1 Y.Shi,R.Eberhart.“A modified particle swarm optimizer,”Proceedings of IEEE World Congress on Computational Intelligence,Anchorage,AK,1998,pp.69-73.惯性权重第12页，共46页，编辑于2022年，星期二PSO算法通过调节通过调节w值，可以控制值，可以控制PSOPSO的全局探索和局部开发能力：的全局探索和局部开发能力：w1：微粒速度随迭代次数的增加而增加，微粒发散。0w1：微粒减速，算法的收敛性依靠惯性权重 和 。w0：微粒速

8、度随迭代次数的增加而减小，最后趋近0，算法收敛。实验实验表明，表明，w=0.7298和和 时算法具有较好的收敛性能。时算法具有较好的收敛性能。自适自适应或或动态惯性性权重重值：Eberhart和Shi：w的线性递减策略；Shi和Eberhart：以当前惯性权重值和当前算法最优值为模糊系统的 输入，给出一种惯性权重的模糊控制方法。第13页，共46页，编辑于2022年，星期二加速度系数加速度系数加速度系数，又称学习因子，用来控制加速度系数，又称学习因子，用来控制 和和 对微粒飞行方向对微粒飞行方向的影响。的影响。每个微粒执行局部搜索；微粒群转化为一个随机爬山法；微粒逐渐移向 和 的加权均值；算法比

9、较适合于单峰优化问题；算法比较适合于多峰优化问题。加速度系数加速度系数第14页，共46页，编辑于2022年，星期二PSO算法PSOPSO中粒子的位置更新中粒子的位置更新第15页，共46页，编辑于2022年，星期二压缩因子压缩因子Clerc和和Kennedy 1 建议把压缩因子引入微粒速度更新公式：建议把压缩因子引入微粒速度更新公式：压缩因子其中，通常，压缩因子 。1 M.Clerc and J.Kennedy,“The particle swarmexplosion,stability,andconvergence in a multidimensional complex space,”IE

10、EE Transactions on Evolutionary Computation,2002,vol.6,no.1,pp.58-73.第16页，共46页，编辑于2022年，星期二PSO的拓扑结构 全局全局PSO：群体中每个微粒跟踪的两个极值为自身最佳位置（pbest与群体最佳位置gbest。局部局部PSO：每个微粒跟踪自身最佳位置pbest，不跟踪群体的最佳位置，而是跟踪其拓扑其拓扑邻邻域中所有域中所有K个微粒的最佳位置个微粒的最佳位置lbest，其速度更新如下：为局部邻域最佳位置。有两类有两类PSO：第17页，共46页，编辑于2022年，星期二拓扑结构：拓扑结构：全连接拓扑，即受全连接拓

11、扑，即受gbest影响影响 环形拓扑，环形拓扑，K=2,=2,仅受与其紧邻的两个粒子的影响仅受与其紧邻的两个粒子的影响第18页，共46页，编辑于2022年，星期二拓扑结构：拓扑结构：星状拓扑星状拓扑(star)Von Neumann 拓扑拓扑锥形拓扑锥形拓扑(pyramid)四聚类拓扑四聚类拓扑(clusters)第19页，共46页，编辑于2022年，星期二 全连接拓扑信息传输速度快，相应地，全连接拓扑信息传输速度快，相应地，PSOPSO算法收敛速度快，算法收敛速度快，但是易于早熟收敛。但是易于早熟收敛。环形拓扑信息传输速度最慢，相应地，环形拓扑信息传输速度最慢，相应地，PSOPSO算法收敛速

12、度慢，但是微粒算法收敛速度慢，但是微粒有更多的机会发现最优解。有更多的机会发现最优解。Mendes Mendes和和Kennedy(2002)Kennedy(2002)在对比不同拓扑结构时发现：在对比不同拓扑结构时发现：Von Von Neumann Neumann拓扑优于其它拓扑。拓扑优于其它拓扑。Suganthan(1999)在在PSO算法初期采用局部算法初期采用局部PSO,后期采用后期采用 全局版全局版PSO;Hu和Eberhart(2002)提出了动态拓扑结构的概念。每次迭代时提出了动态拓扑结构的概念。每次迭代时 选择与当前微粒最近的选择与当前微粒最近的m个微粒作为它的新邻域。个微粒作

13、为它的新邻域。第20页，共46页，编辑于2022年，星期二PSO的收敛性 Van den Bergh(2002)、Trelea(2003)以及Bergh和Engelbrecht(2006)已经证明PSO能够收敛到一个平衡状态。那么，对于全局版PSO 算法，如果 这意味着随着迭代次数的增加所有微粒将收敛到一个点。但是，这不意味着微粒个体最优点和全局最优点的加权和就是问 题的最优解。第21页，共46页，编辑于2022年，星期二PSO的收敛性如果式中 ，那么，微粒仅依靠 更新其位置。进一步，如果上述状态持续足够代数后,那么 因此，有进一步解释：事实上，存在微粒群收敛到局部稳定点的可能。该局部稳定 点

14、不是问题的全局最优点，甚至不是问题的局部最优点。第22页，共46页，编辑于2022年，星期二PSO的收敛性部分典型方法:Dissipative PSO(Xie,et al.,2002)-增加微粒群的多样性;PSO with mutation(Stacey,et al.,2004)-重新初始化已经收敛的微粒;PSO with passive congregation(He et al.,2004)-提高微粒群的多样性;Speciation-based PSO(Li et al.,2006)-根据微粒之间相似程度，把整个微 粒群划分为若干类。Self-organizing PSO(Ratnawee

15、ra,et al.2004)-改进算法的控制参数;Multi-swarm parallel PSO,MPPSO(Belal M et al.,2004)-利用多种群思想。防止所有或者部分微粒长期接近微粒的全局最优点，即第23页，共46页，编辑于2022年，星期二PSO的收敛性一些方法：差分算法(Differential Evolution,DE)(Zhang and Xie,2003)遗传算法(Genetic algorithm,GA)(Matthew et al.,2005);爬山法;模拟退火(Simulated annealing,SA)(Nasser Sadati et al.,2006

16、);单纯形法(Simplex method,SM)(Fan S K et al.,2007).利用具有较强局部搜索能力的算法进一步细化/开发PSO所得结果。第24页，共46页，编辑于2022年，星期二二进制PSO最初的PSO算法是从处理连续优化问题中发展起来的。Kennedy和Eberhart1首次将实数PSO扩展为二进制PSO。微粒位置为二进制向量，微粒速度仍为浮点向量；微粒速度被逻辑函数s(v)转化为判断位置项选择0还是1的概率。1 J.Kennedy,R.C.Eberhart.“A discrete binary version of the particle swarm algorit

17、hm,”Proceedings of International Conference on System,Man,and Cybernetics,1997,Orlando,FL,pp.4104-4109.第25页，共46页，编辑于2022年，星期二二进制PSO为了防止s(v)饱和，Kennedy等建议将 限制在-4,4之间。其中 更新公式如下：第26页，共46页，编辑于2022年，星期二PSO与遗传算法的区别遗传算法强调“适者生存”，不好的个体在竞争中被淘汰；PSO强调“协同合作”，不好的个体通过学习向好的方向转变。遗传算法中最好的个体通过产生更多的后代来传播基因；PSO中的最好个体通过吸引

18、其它个体向它靠近来施加影响。遗传算法的选择概率只与上一代群体相关，而与历史无关，群体的信息变化过程是一个Markov链过程；而PSO中的个体除了有位置和速度外，还有着过去的历史信息（pBest、gBest）。第27页，共46页，编辑于2022年，星期二PSO的优点和缺点优点：优点：易于实现；可调参数较少；所需种群或微粒群规模较小；计算效率高，收敛速度快。缺点：缺点：基本PSO虽然收敛速度快，但有时会陷入局部最优。第28页，共46页，编辑于2022年，星期二PSO改进研究位置和速度更新公式多种群PSO种群拓扑结构与其他智能优化算法的混合拓展PSO算法用于：多目标优化 约束优化 离散优化 动态优化

19、第29页，共46页，编辑于2022年，星期二所用的测试函数（几个例子）SchafferGriewankAckleyRastrigin第30页，共46页，编辑于2022年，星期二函数优化函数优化数值函数优化，动态、多峰值、多目标优化数值函数优化，动态、多峰值、多目标优化 组合优化组合优化旅行商问题、车辆路由问题、布局优化问题等旅行商问题、车辆路由问题、布局优化问题等生产调度生产调度工件加工问题工件加工问题自动控制自动控制智能控制器优化、最优控制器的设计智能控制器优化、最优控制器的设计机器人学机器人学路径规划、协调控制路径规划、协调控制机器学习机器学习分类、聚类、数据挖掘分类、聚类、数据挖掘图像处

20、理图像处理图像识别、检测图像识别、检测机械设计机械设计形状、结构、参数的设计形状、结构、参数的设计神经网络训练神经网络训练系统参数辨识等系统参数辨识等PSO应用研究第31页，共46页，编辑于2022年，星期二PSO用于交通事故分析提出一种基于K-mean聚类全局引导的多目标PSO用于交通事故分析。用该PSO来发现关联规则，以此寻求与交通事故严重程度相关联的因素。文献：Chenye Qiu,Chunlu Wang,Binxing Fang,Xingquan Zuo.A multi-objective particle swarm optimization based partial classi

21、fication for accident severity analysis.Applied Artificial Intelligence,2014,28(6):555-576.第32页，共46页，编辑于2022年，星期二基于基于K-mean聚类的全局引导粒子选择方法聚类的全局引导粒子选择方法第33页，共46页，编辑于2022年，星期二交通事故数据交通事故数据第34页，共46页，编辑于2022年，星期二交通事故数据交通事故数据第35页，共46页，编辑于2022年，星期二获得的关联规则获得的关联规则第36页，共46页，编辑于2022年，星期二PSO用于云资源分配针对在需求峰值时云资源不足的问

22、题，提出一种基于基于PSO的资源分的资源分配方法配方法，将用户任务合理地分配给私有云和公有云。构造一种自适应自适应PSO来解决这一问题。文献：Xingquan Zuo,Guoxiang Zhang,Wei Tan.Self-adaptive Learning PSO based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud,IEEE Transactions on Automation Science and Engineering,2014,11(2):564-573.第37页，共46页，编辑于2022年，星期二云资源分配框架云资源分配框架第38页，共46页，编辑于2022年，星期二问题的定义问题的定义第39页，共46页，编辑于2022年，星期二第40页，共46页，编辑于2022年，星期二采用的算法采用的算法第41页，共46页，编辑于2022年，星期二采用的算法采用的算法第42页，共46页，编辑于2022年，星期二获得的结果获得的结果第43页，共46页，编辑于2022年，星期二获得的结果获得的结果第44页，共46页，编辑于2022年，星期二获得的结果获得的结果第45页，共46页，编辑于2022年，星期二获得的结果获得的结果第46页，共46页，编辑于2022年，星期二