机器学习-第03讲-1-2-2-PSO

机器学习——

粒子群优化算法

ParticleSwarmOptimization-PSO

智能工程研究室计算机科学与技术学院2大纲一、算法概述二、产生基础三、算法内容四、和其它优化算法的比较五、应用举例3算法概述PSO是Kennedy&Eberhart于1995年提出的Kennedy博士心理学研究人员

/cathyk/jimk.htmlEberhart博士计算智能 /~eberhart/PSO是一种基于叠代的优化工具PSO概念简单容易实现KennedyJ.andEberhartR.C.,Particleswarmoptimization,ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks,1995，pp.1942–1948.4算法概述应用领域广发展很快系统设计、多目标优化、分类、模式识别、信号处理、机器人技术应用、决策制定、模拟和证明等目前被“国际进化计算会议”(IEEEInternationalConferencesonEvolutionaryComputation,CEC)列为一个讨论的专题。5背景对鸟群行为的模拟：Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现，鸟群在行进中会突然同步的改变方向，散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作，也就是说，这种同步是鸟群中个体之间努力保持最优的距离的结果。6背景对鱼群行为的研究：生物社会学家E.O.Wilson对鱼群进行了研究。提出：“至少在理论上，鱼群的个体成员能够受益于群体中其它个体在寻找食物的过程中的发现和以前的经验，这种受益超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散。”这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的基础。7设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一个放置食物的地方，所有的鸟都不知道食物在哪里。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。背景8PSO是对简化的社会系统的模拟源于对鸟群觅食行为的研究信息共享机制心理学假设在寻求一致的认知过程中，个体往往记住它们的信念，同时考虑其它个体的信念。当个体察觉其它个体的信念较好的时候，它将进行适应性地调整背景9算法内容概述粒子：优化问题的解粒子的适应度：评价解的质量，由优化问题决定粒子的速度：飞行方向和距离粒子的行为：追随当前的最优粒子，不断根据自身和同伴的经验来更新自己10粒子群原理示意图算法内容该粒子以前最优位置全局最优粒子当前飞行行为受以前最优位置影响受上一次飞行行为影响受全局最优粒子影响新的飞行食物源11算法内容形式(多维标准）假设搜索空间为D维，取N个粒子，第i个粒子表示为Xi=(xi1,xi2,…,xiD)Xi经历过的最好位置记为Pi=(pi1,pi2,…,piD)，它是粒子本身所找到的最优解，称为个体最优解，记为pBest所有粒子经历过的最好位置，是整个群体目前找到的最优解，称为群体最优解，记为gBest12算法内容核心公式惯性项个体经验群体经验13算法内容算法的实现步骤粒子表示：实数编码，整数编码适应度函数设计：非负，易于度量停止条件设置：最大更新代数，适应度函数增量群体规模设置：可参考粒子的维数群体初始化：在有效范围内随机产生群体更新：个体最佳位置，群体最佳位置个体速度，个体位置14算法内容参数分析粒子数一般取20–40.其实对于大部分的问题10个粒子已经足够可以取得好的结果粒子的维度由优化问题决定，每一维可以设定不同的范围最大速度(Vmax)决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度15算法内容参数分析学习因子C1=C2=2r1=r2

是随机量，为了避免一致性）惯性权重 V[]=W*V[]+C1*rand()*(pBest[]-present[])+C2*rand()*(gBest[]-present[])16初始化粒子群体是计算每个粒子的适应度值输出最终解速度(v)和位置(x)更新否更新个体最优解pBest更新群体最优解gBest满足停止条件？粒子群算法流程图在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：

v[]=w*v[]+c1*rand()*(pbest[]-present[])+c2*rand()*(gbest[]-present[])(a)

present[]=persent[]+v[](b)

v[]是粒子的速度,w是惯性权重,persent[]是当前粒子的位置.pbest[]andgbest[]如前定义rand()是介于（0，1）之间的随机数.c1,c2是学习因子.通常c1=c2=2.

程序的伪代码如下

Foreachparticle

____Initializeparticle

END

Do

____Foreachparticle

________Calculatefitnessvalue

________Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory

____________setcurrentvalueasthenewpBest

____End

____ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest

____Foreachparticle

________Calculateparticlevelocityaccordingequation(a)

________Updateparticlepositionaccordingequation(b)

____End

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax20应

用

举

例21应用举例粒子表示：2维实数向量X=(x,y)’速度表示：2维实数向量V=(vx,vy)’适应度函数：f(X)=f(x,y)停止条件设置：最大更新代数50群体规模：10群体初始化方法：随机产生0<x,y<8,0<v1，v2<8控制参数：C1=C2=2,w=122算法演示函数优化1（演示）f(x,y)=100*(x^2-y)^2+(1-x)^2,(-2.048<x,y<2.048)全局最小点（1，1），全局最小值0函数优化2f(x,y)=sin(x)*cos(y),(-pi/2<x,y<pi/2)全局最小点（-pi/2,0）,全局最小值-123函数优化3f(x,y)=(4-2.1x^2+x^4/3)x^2+xy+(-4+4y^2)y^2-10<x,y<10全局最小点(-0.0898,0.7126),(0.0898,-0.7126)，最小值-1.03162函数优化4f(x,y)=-0.5+(sin(sqrt(x^2+y^2))^2-0.5)/(1+0.001(x^2+y^2))^2,-100<x,y<100全局最小点(0,0),全局最小值-1算法演示24PSO算法已经用来应用于分析人的颤抖，对人的颤抖的诊断，包括帕金森(Parkinson)病和基本的颤抖一个电气设备的功率反馈和电压控制其它应用领域25解旅行商问题的离散粒子群优化算法如何把求解连续优化问题的PSO改造成能够求解离散优化问题的算法？设计粒子表示方法重新定义粒子速度重新定义粒子位移确定适应度函数形式26解旅行商问题的离散粒子群优化算法设计粒子表示方法采用整数形式的粒子表示方法152643727解旅行商问题的离散粒子群优化算法粒子速度定义粒子分量交换的次数适应度距离28解旅行商问题的离散粒子群优化算法粒子位移定义相对于个体最优位置和群体最优位置的变换SWAP(Xi,Xl,k):（l=pBest或者l=gBest,k=rand()(0<k<=n)）

Xi:Xj:

SWAP(Xi,Xj,5)12345673564127123756429粒子群算法求解旅行商问题的流程图解旅行商问题的离散粒子群优化算法数据结构（群体规模为m，粒子维数为n）X[m][n]:粒子位移V[m][n]:粒子速度YpBest[m][n]:个体最佳位置YgBest[n]:群体最佳位置30PSO和GA的比较GA选择操作交叉操作变异操作逆转操作需要把连续变量转化成二进制编码适应度影响个体遗传的概率PSO根据速度进行最优解搜索最适用于连续变量的优化问题适应度近供pBest和gBest的判定收敛速度快共同点：需要适应度函数评价个体的质量31补充阅读资料32离散PSO算法在广义TSP问题中的扩展广义TSP问题:把给定的n个城市分成m个组，旅行商要选择一条访问每个组中一个（或至少一个）城市的最短旅行回路应用领域:覆盖遍历问题、物流系统设计问题、邮箱收集问题以及随机车辆路由问题等33WuC.G.,LiangY.C.,LeeH.P.andLuC.Ageneralizedchromosomegeneticalgorithmforgeneralizedtravelingsalesmanproblemsanditsapplicationsformachining.PhysicalReviewE,2004,(70):016701-1-13.广义染色体

广义染色体的模式

广义染色体的一个例子

离散PSO算法在广义TSP问题中的扩展34与上图广义染色体对应的回路

35SWAP(Xi,Xj,k)XiXj离散PSO算法在广义TSP问题中的扩展36离散PSO算法在广义TSP问题中的扩展两种局部搜索技术头局部搜索在头部某一个节点，搜索最佳的城市号，并用它取代原来的城市号体局部搜索每次迭代的时候随机地交换两个广义顶点的顺序，如果适应度增大则保留交换，否则，保持原顺序不变

37初始化粒子群对每个粒子执行“交换子”操作执行头局部搜索结束是否执行体局部搜索是否满足终止条件？对每个粒子搜索Pi

以及Pg针对广义TSP问题的离散PSO算法流程图38一些标准测试问题的计算结果ProblemOptBestresultWorstresultAverageresultErr(%)11EIL51174176186180.213.5714ST70316315328317.110.3516EIL76209214232221.846.1416PR7664825649276784465670.741.3020KROA100971197