粒子群算法

4.遗传算法和PSO的比较[编辑本段]大多数演化计算技术都是用同样的过程1.种群随机初始化2.对种群内的每一个个体计算适应值(fitnessvalue).适应值与最优解的距离直接有关3.种群根据适应值进行复制4.如果终止条件满足的话，就停止，否则转步骤2从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解但是，PSO没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较,PSO的信息共享机制是很不同的.在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动.在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优解的过程.与遗传算法比较,在大多数的情况下，所有的粒子可能更快的收敛于最优解5.人工神经网络和PSO[编辑本段]人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionarycomputation)技术来研究人工神经网络的各个方面。演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitnessfunction)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2.网络权重的编码而且遗传算子的选择有时比较麻烦最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmarkfunction)IRIS数据集。(Iris是一种鸢尾属植物)在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据.这样总共有150组数据或模式。我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100](这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。6.PSO的参数设置[编辑本段]从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤:问题解的编码和适应度函数PSO的一个优势就是采用实数编码,不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题f(x)=x1^2+x2^2+x3^2求解,粒子可以直接编码为(x1,x2,x3),而适应度函数就是f(x).接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程,中止条件一般为设置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置粒子数:一般取20–40.其实对于大部分的问题10个粒子已经足够可以取得好的结果,不过对于比较难的问题或者特定类别的问题,粒子数可以取到100或200粒子的长度:这是由优化问题决定,就是问题解的长度粒子的范围:由优化问题决定,每一维可是设定不同的范围Vmax:最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子(x1,x2,x3)x1属于[-10,10],那么Vmax的大小就是20学习因子:c1和c2通常等于2.不过在文献中也有其他的取值.但是一般c1等于c2并且范围在0和4之间中止条件:最大循环数以及最小错误要求.例如,在上面的神经网络训练例子中,最小错误可以设定为1个错误分类,最大循环设定为2000,这个中止条件由具体的问题确定.全局PSO和局部PSO:我们介绍了两种版本的粒子群优化算法:全局版和局部版.前者速度快不过有时会陷入局部最优.后者收敛速度慢一点不过很难陷入局部最优.在实际应用中,可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.另外的一个参数是惯性权重,Shi和Eberhart指出(Amodifiedparticleswarmoptimizer,1998)：当Vmax很小时（对schaffer的f6函数，Vmax=2),使用接近于1的惯性权重;当Vmax不是很小时（对schaffer的f6函数，Vmax=3),使用权重w=0.8较好.如果没有Vmax的信息,使用0.8作为权重也是一种很好的选择.另外,对于使用时变的权重,结果不清楚,但是预计结果应比较好.附上一个C++实现的C++代码：代码来自2008年数学建模东北赛区B题，原题描述=2;//加速因子intc2=2;//加速因子doublew=1;//惯性权重doubleWmax=1;//最大惯性权重doubleWmin=0.6;//最小惯性权重intKmax=110;//迭代次数intGdsCnt;//物资总数intconstDim=10;//粒子维数intconstPNum=50;//粒子个数intGBIndex=0;//最优粒子索引doublea=0.6;//适应度调整因子doubleb=0.5;//适应度调整因子intXup[Dim];//粒子位置上界数组intXdown[Dim]=;//粒子位置下界数组intValue[Dim];//初始急需度数组intVmax[Dim];//最大速度数组classPARTICLE;//申明粒子节点voidCheck(PARTICLE&,int);//约束函数voidInput(ifstream&);//输入变量voidInitial();//初始化相关变量doubleGetFit(PARTICLE&);//计算适应度voidCalculateFit();//计算适应度voidBirdsFly();//粒子飞翔voidRun(ofstream&,int=2000);//运行函数//微粒类classPARTICLE{public:intX[Dim];//微粒的坐标数组intXBest[Dim];//微粒的最好位置数组intV[Dim];//粒子速度数组doubleFit;//微粒适合度doubleFitBest;//微粒最好位置适合度};PARTICLEParr[PNum];//粒子数组intmain()//主函数{ofstreamoutf(out.txt);ifstreaminf(data.txt);//关联输入文件infGdsCnt;//输入物资总数Input(inf);Initial();Run(outf,100);system(pause);return0;}voidCheck(PARTICLE&p,intcount)//参数:p粒子对象,count物资数量{srand((unsigned)time(NULL));intsum=0;for(inti=0;iDim;i++){if(p.XXup){p.X=Xup;}elseif(p.XXdown){p.X=Xdown;}if(p.VVmax){p.V=Vmax;}elseif(p.V0){p.V=0;}sum+=p.X;}while(sumcount){p.X[rand()%Dim]--;sum=0;for(inti=0;iDim;i++){if(p.XXup){p.X=Xup;}elseif(p.XXdown){p.X=Xdown;}if(p.VVmax){p.V=Vmax;}elseif(p.V0){p.V=0;}sum+=p.X;}}}voidInput(ifstream&inf)//以inf为对象输入数据{for(inti=0;iDim;i++){infXup;}for(inti=0;iDim;i++){infValue;}}voidInitial()//初始化数据{GBIndex=0;srand((unsigned)time(NULL));//初始化随机函数发生器for(inti=0;iDim;i++){Vmax=(int)((Xup-Xdown)*0.035);}for(inti=0;i{for(intj=0;jDim;j++){Parr.X[j]=(int)(rand()/(double)RAND_MAX*(Xup[j]-Xdown[j])-Xdown[j]+0.5);Parr.XBest[j]=Parr.X[j];Parr.V[j]=(int)(rand()/(double)RAND_MAX*(Vmax[j]-Vmax[j]/2));}Parr.Fit=GetFit(Parr);Parr.FitBest=Parr.Fit;if(Parr.FitParr[GBIndex].Fit){GBIndex=i;}}}doubleGetFit(PARTICLE&p)//计算对象适应度{doublesum=0;for(inti=0;iDim;i++){for(intj=1;j=p.X;j++){sum+=(1-(j-1)*a/(Xup-b))*Value;}}returnsum;}voidCalculateFit()//计算数组内各粒子的适应度{for(inti=0;i{Parr.Fit=GetFit(Parr);}}voidBirdsFly()//粒子飞行寻找最优解{srand((unsigned)time(NULL));staticintk=10;w=Wmax-k*(Wmax-Wmin)/Kmax;k++;for(inti=0;i{for(intj=0;jDim;j++){Parr.V[j]=(int)(w*Parr.V[j])+(int)(c1*rand()/(double)RAND_MAX*(Parr.XBest[j]-Parr.X[j])+c2*rand()/(double)RAND_MAX*(Parr[GBIndex].XBest[j]-Parr.X[j]));}Check(Parr,GdsCnt);for(intj=0;jDim;j++){Parr.X[j]+=Parr.V[j];}Check(Parr,GdsCnt);}CalculateFit();for(inti=0;i{if(Parr.Fit=Parr.FitBest){Parr.FitBest=Parr.Fit;for(intj=0;jDim;j++){Parr.XBest[j]=Parr.X[j];}}}G