改进的PSO算法的实现

从20世纪90年代初,就产生了模拟自然生物群体(swarm)行为的优化技术。Dorigo等人从生物进化的机理中受到启发,通过模拟蚂蚁的寻径行为,提出了蚁群优化方法;美国学者Eberhart E C和Kennedy J于1995年提出的粒子群优化(particle swarm optimization)算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能(swarm intelligence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(PSO)最初是处理连续优化问题的,目前其应用已扩展到组合优化问题。

同遗传算法(genetic algorithm, GA)、蚁群优化等大多数进化计算方法一样,PSO也是一种基于群体的优化方法。但与其它进化计算方法相比,PSO的主要特点为:①每一个体(称为一个粒子)都被赋予了一个随机速度并在整个问题空间中流动;②个体具有记忆功能;③个体的进化主要是通过个体之间的合作与竞争来实现的。作为一种高效并行优化方法,PSO可用于求解大量非线性、不可微和多峰值的复杂优化问题,再加上PSO算法的程序实现异常简洁,需要调整的参数少,因而发展很快,出现了多种改进PSO算法,并已应用于许多科学和工程领域,得到了众多学者的重视和研究。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己，第一个就是粒子本身所找到的最优解.这个解叫做个体极值pb，另一个极值是整个种群目前找到的最优解,这个极值是全局极值gb。在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置：

vi(t+1)=wvi(t)+c1rand[pbi-xi(t)]+c2rand[gb-xi(t)] (1) xi(t+1)=xi(t)+vi(t+1) (2) 其中:

vi(t)是粒子i的t时刻的速度, w为惯性权重, xi(t)是当前粒子的位置, pbi和gb如前定义,

rand是介于(0,1)之间的随机数. c1,c2是学习因子.通常c1=c2=2.

PSO的算法流程如下:

Step 1: 初始化一群粒子(群体规模为m),包括随机位置和速度; Step 2: 评价每个粒子的适应度;

Step 3: 对每个粒子,将其适应值与其经历过的最好位置pbest作比较,如果较好,则将其作为当前的最好位置pbest;

Step 4: 对每个粒子,将其适应值与全局所经历的最好位置gbest作比较,如果较好,则重新设置gbest的索引号;

Step 5: 根据方程(1)变化粒子的速度和位置;

Step 6: 如未达到结束条件(通常为足够好的适应值或达到一个预设最大代数Gmax),则返回Step2.

在这里，采用java语言来实现这个PSO算法，通过优化下面的函数(求极大值)来演示PSO算法：

maxf(x)(x)sin(ii1nxi) 其中xi[-500,500].

该函数的图形如下(当n=2时):

从图中可以看出，这个函数有很多局部极大值点。

已知该函数的全局极值发生在xi= -420.9687， i=1:n, 其值为

f (x)=418.9829n

为了简化问题讨论，将w取为固定值0.8，c1和c2取为2。在这个程序中，粒子数PSONum和函数的维数funDim很容易实现调节。在这里将funDim取为2，考虑到该函数比较复杂，

所以将粒子数取的大一些，为100。通过实验发现PSO的收敛较快，所以将迭代次数searchTime取为1000是足够大的。

通过多次的实验发现，最大速度Vmax对于实验结果有很大的影响，当Vmax取值偏大时，粒子很容易“飞”出[-500，500]的范围，得不到满足要求的解，但是当Vmax取值偏小时，虽然能将粒子限定在[-500，500]的范围内，但是往往会陷入到局部极大值中。实验结果表明，在这个实验中，将Vmax取为105是比较合适的。下面的表格1中记录了14次实验的结果(除去了几个超出[-500，500]范围的结果)：

表1 14次实验结果

次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14

最优极值 719.52699 719.52570 719.52690 837.96492 837.96459 719.52738 837.96573 837.96508 837.96436 837.96570 837.96376 837.96568 719.52742 837.96476 最优极值位置X1 -420.93052 302.44446 302.46710 -420.88716 -420.88821 302.52774 -420.95130 -420.99897 -420.86644 -420.99166 -420.86609 -420.94311 -420.96432 -421.00490 最优极值位置X2 302.57008 -421.05410 -420.99903 -420.88716 -420.91499 -420.94856 -420.96270 -421.03625 -420.94171 -420.96471 -420.89517 -420.97755 302.53417 -420.88705 函数的最优值应该是837.9658，对应的位置应该是[-420.9687，-420.9687]，和上面的实验结果对比，发现粒子基本上能找到最优值，但有时候会陷入到局部极大值点[-420，302]和[302，-420]附近。为了减少粒子陷入到局部极大值的机会，我们可以通过添加入一些随机因素、增加种群的多样性、和其它算法相结合等手段去实现PSO算法。

附录（PSO Java源代码）

//自写的PSO程序by Java /*

* Created on 2008-6-21 *

* TODO To change the template for this generated file go to * Window - Preferences - Java - Code Style - Code Templates */ /**

* @author XiongRunqun *

* TODO To change the template for this generated type comment go to * Window - Preferences - Java - Code Style - Code Templates */

class Function {

private double asistFun(double x) { double abs = (x>=0 ? x : -x); double d = Math.sin(Math.sqrt(abs))*(-x); return d; }

private static final int dim = 2;//dim是优化函数的维数 public static int getDim() { return dim; } public double cumputeFitness(double position[]) { double sum = 0; for(int i=0;iclass Particle { static double Vmax = 105; static final double weight = 0.8; static final double c1 = 2.0; static final double c2 = 2.0; double velocity[]; double position[]; double bestPosition[]; double fitness; double bestFitness; int funDim; public Particle() { funDim = Function.getDim(); velocity = new double[funDim]; position = new double[funDim]; bestPosition = new double[funDim]; for(int i=0;i bestFitness)//因为求函数极大值 { bestFitness = fitness; for(int i=0;i{ for(int i=0;iVmax)velocity[i] = Vmax; if(velocity[i] < -Vmax)velocity[i] = -Vmax; position[i] += velocity[i]; } } }

class PSO { Particle particles[]; double globalBestPosition[]; double globalBestFitness; double tempBestFitness;//一次迭代中的最好值 int PSONum; int funDim; int tempBestIndex; int globalBestIndex; public PSO(int PSONum) { this.PSONum = PSONum; funDim = Function.getDim(); particles = new Particle[PSONum]; for(int i=0;i }

{ return globalBestFitness; }

public double[] getGlobalBestPosition() { return globalBestPosition; }

public void search() { for(int i=0;i globalBestFitness) { globalBestFitness = tempBestFitness; globalBestIndex = tempBestIndex; for(int i=0;ipublic class TestPSO { public static void main(String[]args) { double globalBestPosition[]; int PSONum = 100;//粒子数目 int searchTime = 1000;//迭代次数 PSO pso = new PSO(PSONum); int funDim = Function.getDim(); System.out.println(\"-------------------------------------------------\"); for(int i=1;i<=searchTime;i++) { pso.search(); if(i % 100== 0) { globalBestPosition = pso.getGlobalBestPosition(); System.out.println(\"目前的迭代次数是：\" + i + \ System.out.println(\"最好的适应值是：\" + pso.getGlobalBestFitness()); System.out.println(\"最好的位置是：\"); System.out.print(\"[\"); for(int j=0;j