粒子群算法优化不同维数的连续函数以及离散函数的最小值问题

1、引言2、问题描述31.1 函数优化问题31.2 粒子群算法根本原理3二、算法设计52.1 算法流程框图52.2 算法实现52.3 算法的构成要素62.4 算法的改良7三、算例设计83.1 测试函数介绍83.2 优化函数特点8四、仿真实验设计104.1 实验参数设计104.2 根本粒子群算法在测试函数中应用11五、仿真实验结果分析125.1 实验结果汇总125.2 实验结果分析13六、总结与展望146.1 总结146.2 展望14附录一15附录二17引言本文主要利用粒子群算法解决连续函数以及离散函数的最小值问题,粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法,粒子群优化算法通过粒子间的竞

2、争和协作以实现在复杂搜索空间中寻找全局最优点.它具有易理解、易实现、全局搜索水平强等特点,倍受科学与工程领域的广泛关注,已经成为开展最快的智能优化算法之一.惯性权重是PSO标准版本中非常重要的参数,可以用来限制算法的开发(exptation)和探索(exploration)水平.惯性权重的大小决定了对粒子当前速度继承的多少.较大的惯性权重将使粒子具有较大的速度,从而有较强的探索水平；较小的惯性权重将使粒子具有较强的开发水平.关于惯性权重的选择一般有常数和时变两种.算法的执行效果很大程度上取决于惯性权重的选取.本文介绍了粒子群优化算法的根本原理,分析了其特点,并将其应用于函数优化问题求解.止匕外

3、,本文根据惯性权重对粒子群优化算法性能影响的研究,提出了三种不同的惯性权重.通过仿真实验,验证了各自的收敛性.同时也说明了惯性权重在粒子群优化算法中有很大的自由度.、问题描述1.1 函数优化问题目标优化问题可以描述为：maxf(x)(1)xS或：mif(x)(2)xS这里S-Rn称为搜索空间,f(x):S-Rn称为目标函数.(1)式描述的优化问题称为极大化问题,(2)式描述的称为极小化问题.当把f(x)看成是一序列的函数时,上述的问题就转变为多目标优化问题.对很多实际问题进行数学建模后,可将其抽象为一个数值函数的优化问题.由于问题种类的繁多、影响因素的复杂,这些数学函数会呈现出不同的数学特征,

4、比如连续的、离散的、凸的、凹的、单峰值的、多峰值的函数等等,经常遇到的函数还有这些不同数学特征的组合,除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外,大局部情况需要通过数值计算方法来进行近似优化计算.尽管人们对这个问题研究了很多年,但至今仍无一种既能处理各种不同的复杂函数、又具有良好求解结果的数值计算方法.特别是当问题的规模比拟大时,优化计算时的搜索空间急剧扩大,人们熟悉到要严格地求出其最优解不太现实.所以需要研究出一种能够在可接受的时间和可接受的精度范围内求出数值函数近似最优解的方法或通用算法.粒子群优化由于其算法的简单,易于实现,无需梯度信息,参数少等特点在连续优化问题和

5、离散优化问题中都表现出了良好的效果,特别是由于其天然的实数编码特点适合于处理实优化问题.近年来成为国际上智能优化领域研究的热门.1.2 粒子群算法根本原理粒子群优化算法PSO(ParticleSwarmOptimization)是一种基于群体的自适应的搜索优化方法.是由JamesKenned评口Eberhart在1995年提出的.PSO中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子.所有的粒子都有一个由被优化的函数决定的适值(fitnessvalue),每个粒子还有一个速度决定它们飞翔的方向和距离.然后粒子们就追随当前的最优粒子在解空间中搜索.PSO初始化为一群随机粒子(随机解),

6、然后通过迭代找到最优解.在每一次迭代中,粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解,这个解称为个体极值；另一个极值是整个种群目前找到的最优解,这个极值是全局极值.另外也可以不用整个种群而只是用其中一局部作为粒子的邻居,那么在所有邻居中的极值就是局部极值o假设在一个D维的目标搜索空间中,有N个粒子组成一个群落,其中第i个粒子表示为一个D维的向量Xi(xi1>xi2>>xiD)i=1,2,N)0第i个粒子的飞行速度也是一个D维的向量,记为Vi=(Vi1,Vi2,Md)i=1,2,3,0第i个粒子迄今为止搜索到的最优位置称为个体极值,记为Pbest=(Pi1,

7、Pi2,PiD),i=12,No整个粒子群迄今为止搜索到的最优位置为全局极值,记为gbest-(pg1,pg2,pgD)在找到这两个最优值时,粒子根据如下的公式(1.1)和(1.2)来更新自己的速度和位置：vid=w"vid+c1r1(RdXid)+c2r2(pgd-Xid)(11)Xid=Xid+Md(1.2)其中：勒和白为学习因子,也称加速常数(accelerationconstant)r1和r2为0,1范围内的均匀随机数.式(1.1)右边由三局部组成,第一局部为惯性(inertia)或动量(momentum)局部,反映了粒子的运动习惯(habit)代表粒子有维持自己先前速度的趋

8、势；第二局部为认知(cognition)局部,反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)代表粒子有向自身历史最正确位置逼近的趋势；第三局部为社会(social)局部,反映了粒子间协同合作与知识共享的群体历史经验.算法设计这局部内容主要是针对本文主要研究问题的类型确定粒子群算法具体实现过程和一些参数的选择.2.1 算法流程框图开始初始化每个粒子的速度和位置r计算每个粒子的适应值1求出每个粒子的个体最优1r求出整个群体的全局最优值1根据方程(1.1)行4对粒子的速度进二化V1:束条件是f输出结果2.2 算法实现算法的流程如下:初始化粒子群,包括群体规模N,每个粒

9、子的位置Xi和速度Vi计算每个粒子的适应度值FJi;对每个粒子,用它的适应度值FJi和个体极值&s/i)比拟,如果Fiti>Pbest(i),那么用Fiti替换掉Pbest；对每个粒子,用它的适应度值Fiti和全局极值gbest比拟,如果FitiAPbes(i)那么用Fiti替gbest；根据公式(1.1),(1.2)更新粒子的速度Vi和位置Xi;如果满足结束条件(误差足够好或到达最大循环次数)退出,否那么返回.2.3算法的构成要素对于构成粒子群算法的各个参数进行设定.本算法中主要的参数变量为惯性权值w,学习因子c1,c2,群体的大小N,迭代次数M,粒子维数Do(1)群体大小通常

10、,群体太小那么不能提供足够的采样点,以致算法性能很差,容易陷入局部最优；群体太大尽管可以增加优化信息,阻止早熟收敛的发生,但无疑会增加计算量,造成收敛时间太长,表现为收敛速度缓慢.本文对函数的优化选择种群规模为500.(2)最大迭代次数迭代次数越多能保证解的收敛性,但是影响运算速度,本文对函数的优化选最大迭代次数为100畋.(3)惯性权值惯性权重w表示在多大程度上保存原来的速度.w较大,全局收敛水平强,局部收敛水平弱；w较小,局部收敛水平强,全局收敛水平弱.(4)学习因子加速常数Ci和c2分别用于限制粒子指向自身或邻域最正确位置的运动.建议4=c+c2三4.0,并通常取G=c2=2.本文中取G

11、=c2=2.(5)粒子维数粒子维数取决于待优化函数的维数,例如本文主要有三个函数主要：第一个函数是2维的,第二个函数是10维的,第三个函数是30维的.(6)粒子空间的初始化较好的选择粒子初始化空间,将大大缩短收敛的时间.在本文中我们主要是选用随机对粒子进行初始化.2.4算法的改良对于函数的优化我们主要选择的是对于惯性权重的优化.惯性权重是粒子优化算法的重要参数,算法的成败很大程度上就取决于参数的选取和调节,本文采用固定权重、时变权重和随机权重三种权重.(1)固定权重即赋予惯性权重以一个常数值,一般来说,该值在0和1之间.固定的惯性权重使粒子在飞行中始终具有相同的探索和开发水平.显然对于不同的问

12、题,获得最好优化效果的常数是不同的,要找到这个值需要大量的实验.通过实验发现：种群规模越小,需要的惯性权重越大,由于此时种群需要更好的探索水平来弥补粒子数量的缺乏,否那么粒子极易收敛；种群规模越大,需要的惯性权重越小,由于每个例子可以更专注于搜索自己附近的区域.(2)时变权重希望粒子群在飞行开始的时候具有较好的探索水平,随着迭代次数的增加,特别是在飞行后期,希望有较好的开发水平.所以使用动态调节惯性权重.可以通过时变的惯性权重来实现.设惯性权重的取值范围为：仲min©max,最大迭代次数为Iter_max,那么第i次迭代时的惯性权重可以为："max-"min.二-

13、iimaxItermax(3)随机权重随机权重是在一定范围内随机取值,在本文中我们采用的是：入Random=0.5其中Random为0-1之间的随机数.这样惯性指数将在0.5-1之间随机变化.均值为0.75.对于动态优化问题来说,不能够预测在给定的时间粒子群于要更好的探索水平还是更好的开发水平.所以,可以使惯性权重在一定范围内随机变化.需要说明的是,本文的程序允许改变除惯性权重以外的其他参数,由于本文编写的程序参照MATLAB工具箱,留给用户解决这类问题一个接口函数,上述的各个参数正是接口函数的参数,因此允许改变.另外对于也可采用变参数法,即随迭代次数增加,利用经验公式使它们动态调整,本文采用

14、固定值.三、算例设计3.1测试函数介绍本文主要选取三个函数：一个2维连续函数、一个10离散函数、一个30维离散函数,利用MATLAB编写粒子群算法程序来优化它们.本文选取了三个函数,分别如下:sinx2x1-0.5f1二0.5r10.001x2x210_-2f2='(xi-10cos(2-xi)10)i1(30301-2xixi-JIIcos()14000i1i1i其中f1求最大值,f2和f3为求最小值.3.2优化函数特点Schaffer函数:f1=0.5-sin.Xi2x；-0.5(1+0.001(x2+x；求其最大值.目标函数的效果图如图3.1下:10.80.60.40.2055图

15、3.1Schaffer函数的效果图由图知此函数是个二维函数,常用于测试粒子群算法性能的测试函数,全局在(0,0)处取得最大值,具有强烈震荡的状态,而在Xi(-3.14,3.14)范围内,有无限个次全局最大点.10(2) Rastrigrin函数：f2=£(x2-10cos(2nxi)+10)i1目标函数的效果图如图3.2所示：1008060402005A：.<0050-5-5图3.2Rastrigrin函数的效果图由图知此函数是10维多峰值函数,存在大量按正弦拐点排列的、很深的局部最优点.其在(0,0,0)处取得全局最小值,在Xiw(-5.12,5.12)范围内大约有10个局部

16、极小点,不难优化查找到全局最优值.130230Xi(3) Girewank函数：f3=、xi-cos()14000yy.i目标函数的效果图如图3.3所示：图3.3Girewank函数的效果图由图知此函数为一个多峰值函数,为30维函数,变量之间有相互关系,该函数有很多局部最优点,其全局最优点全局最小值在(Xi,X2,Xn)=(0,0,0)取得,目标函数最优为00四、仿真实验设计4.1 实验参数设计(1)权重参数设计本文对每个测试函数将使用三种不同的惯性权重策略进行实验,分别为固定权重：«=.6.随机权重：金=0.5+Random1；时变权重：飒二.max-'侬"min

17、引,其中缶max=0.9,min=0.2.Itermax2其他参数设计对于Schaffer函数,种群规模N=500,最大迭代次数M=1000,学习因子G=.2=2,f1函数是2维的,粒子维数取Di=2.对于Rastrigrin函数种群规模N=500,最大迭代次数M=1000,学习因子Cl=C2=2,f2函数是10维的,粒子维数D2=10.对于Girewank函数,种群规模N=500,最大迭代次数M=1000,学习因子G=c2=2,f3函数是30维,粒子维数D3=30.4.2 根本粒子群算法在测试函数中应用以Schaffer函数、Rastrigrin函数、Girewank函数为例来说明根本粒子群

18、算法在函数优化中问题中的效果.步骤1:首先依据根本粒子群算法的流程图编写粒子群算法的MATLAB程序见附录一；步骤2:分别编写各个函数的适应值函数程序见附录二；步骤3:在MATLAB环境中用根本粒子群算法分别调用三个函数的适应值程序,得到收敛效果图.Schaffe幅数、Rastrigrin函数、Girewank函数的收敛效果图分别如图4.1、4.2、4.3所示：1,11p1p0.99980.9996-0.9994-0.9992-0.999-°.9988010020.30040.50.60.70.s0°1000图4.1Schaffer函数收敛效果图图4.2Rastrigrin

19、函数收敛效果图0.070.060.050.040.030.020.01001002003004005006007008009001000图4.3Girewank函数收敛效果图五、仿真实验结果分析5.1 实验结果汇总表1统计了固定迭代次数为1000次时,三个测试函数分别在固定权重、随机权重和时变权重三种惯性权重策略下求解的平均值和最差的的一次求解结果.惯性权重SchafferGriewank平均值最差值平均值最差值固定权重.=0.6118.2616.91随机权重入Random=0.52时变权重116.2115.92表1算法运行100次搜索到的解的平均值和最差值Rastrigrin平均值最差值1.

20、82e-0062.04e-0052.14e-0061.74e-0051coigmemaxmin"i='max-i17.72Itermax18.93.20e-0092.16e-0085.2 实验结果分析惯性权重是粒子群优化算法标准版本的重要参数,算法的成败很大程度上取决于该参数的选取和调节.本文重点研究了惯性权重对优化效果的影响.从表1可以看出,1在其他参数选择适当的条件下,利用三种不同惯性权重策略的PSO算法得到的平均值和最差值相差不太,较为稳定.2固定权重、随机权重以及时变权重对Schaffer函数都具有较好的优化效果,并能较快地迭代到最优值.2对于Rastrigrin函数

21、,三种惯性权重策略下都未能搜索到目标函数的理想最优点,但相比之下利用随机权重进行函数优化具有较好的效果,时变权重并未取得比固定权重好的优化效果.3对于多峰函数Girewank函数,惯性权重采用时变权重优化效果明显比固定权重、时变权重好,取得了不错的收敛结果.六、总结与展望6.1 总结本文主要用粒子群算法优化不同维数的连续函数以及离散函数的最小值问题,主要有以下几个方面：首先介绍了粒子群的算法在智能优化中的地位,也介绍了粒子群算法的主要特点,并通过对粒子群算法的学习和了解为下面粒子群改良算法在对不同维数的函数优化问题打下了很好的根底.其次对粒子群算法解决最优化问题的统一框架进行了分析,在此根底上

22、提出了粒子群优化算法的设计步骤；又对粒子群优化算法的原理进行了分析,从而对粒子群算法有了更深刻的了解.最后将根本的粒子群算法与改良的粒子群算法分别对函数的优化问题在MATLAB中进行了仿真,从而将根本算法和改良算法在函数优化问题中的仿真结果进行了比照,从而验证了改良算法的相对优越性,并且验证了改良算法的实际可行性.6.2 展望本文中主要利用改变权重的方法来对函数进行优化,实际用粒子群算法对函数进行优化还有很多方法：改变邻域拓扑结构、改变学习因子,对于离散函数的优化可以采用二进制编码和顺序编码来实现同时也可以使用基于遗传策略和梯度信息的集中改良方法例如：基于选择的改良算法.基于交叉的改良算法、基

23、于变异的改良算法、带有梯度加速的的改良算法,同时智能优化方法处理约束的一般性策略都可以借鉴到粒子群算法中,也可以根据粒子群优化的特性来设计专门的约束处理方式,可以通过以上的优化方法来解决函数优化问题.附录一主函数%fitness-是要优化的目标函数,N-种群数,c1,c2-学习因子,w-惯性权重,M-迭代次数,D-粒子维数.formatlong;%初始化种群%c1=2;%c2=2;%N=500;%w=0.6;%M=1000;c1=2;c2=2;N=500;%w=0.6;M=1000;D=30;x=randn(N,D);%B机初始化位子y=randn(N,D);v=randn(N,D);%随机初始化速度p=rand(N,1);%先计算各个粒子的适应度,并初始化pi-粒子个体极值和pg-全局极值fori=1:Np(i