改进的PSO算法的实现

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。在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置：

vixi

(t+1)

=w′vi+c1′rand′[pbi-xi]+c2′rand′[gb-xi] (1) =xi+vi

(t)

(t+1)

(t)(t)(t)

(t+1)

(2)

其中:

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

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

(t)(t)

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算法。