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算法。
改进的PSO算法的实现
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)