粒子群算法的实现..docx

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算法：max 其中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次实验结果次数最优极值最优极值位置X1最优极值位置X21719.52699-42057008271944446-421.05410371946710-420.999034837.96492-420.88716-420.887165837.96459-420.88821-420.91499671952774-420.948567837.96573-420.95130-420.962708837.96508-420.99897-421.036259837.96436-420.86644-420.9417110837.96570-420