粒子群优化算法研究

粒子群优化算法研究（精选11篇）

粒子群优化算法研究 第1篇

关键词：粒群优化,早熟因子,逆反粒子,变异策略,协同机制

1 引言

当前, 通过模拟生物群体的行为来解决计算问题已经成为新的研究热点, 形成了以群体智能 (Swarm Intelligence) 为核心的理论体系。研究表明, 生物群体中的信息共享会产生进化优势。基于这种思想, 美国的Eberhart 博士和Kennedy 博士受鸟群觅食行为的启发于1995 年提出了粒子群优化算法 (Particle Swarm Optim ization, PSO) , 并逐步演化为一种简单而有效的优化计算技术。同遗传算法比较, 粒子群算法的收敛速度快, 更加简单, 容易实现并且无需调整很多参数。目前已被广泛应用于函数优化, 神经网络训练, 模糊系统控制以及其他遗传算法的应用领域。

但与其它全局优化算法一样, PSO算法同样存在早熟收敛现象[2], 尤其是在比较复杂的多峰值搜索问题中。为此, 本文在PSO算法迭代过程中不是简单地选取适应度最大的粒子作为最优粒子, 而是采用轮盘赌的方法, 从若干个适应度最大的粒子中选取一个作为最优粒子, 这样可以避免所有粒子迅速朝一个可能的局部最优粒子靠拢, 从而降低了算法过早收敛于局部最优解的几率[10]。为避免过于早熟, 考虑在算法搜索过程中引入一些干扰因素[11], 从而使粒子在新的位置以新的速度开始搜索, 跳出了原早熟区域, 避免了局部最优解, 能够更好地找到全局最小。

2 粒子群算法

PSO算法是通过模拟鸟群的捕食行为来达到优化问题的求解.首先在解空间内随机初始化鸟群, 鸟群中的每一只鸟称为“粒子”, 这些“粒子”在解空间内以某种规律移动, 经过若干次迭代后找到最优解。

在每一次迭代中, 粒子通过跟踪 2个“极值 ”来更新自己.第 1个是粒子本身的最优解 pbest, 第 2个是整个微粒群目前找到的最优解g.best, 找到这 2个极值后, 每个粒子根据自己的飞行速度决定自身的走向及飞行距离。

PSO的速度位置算式如下[1]:

v (i+1) =ωv (i) =c1r1 (pbest-x (i) ) +c2r2 (gbest-x (i) ) (1)

x (i+1) =x (i) +v (i+1) (2)

式 (1) 中的pbest表示该粒子从开始到现在搜索产生的最优解, gbest表示粒子群目前找到的最优解, 即运行到当前代为止所找到的全局最优。ω∈[0, 1], 被称作惯性因子, 用于根据上一次迭代得到的速度调节本次迭代过程上粒子的运动速度。c1和c2是加速系数, 分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长, 若太小, 则粒子可能远离目标区域, 若太大则可能会导致飞过目标区域。r1和r2是 (0, 1) 之间的随机数。根据目标函数计算的适应度值用来衡量搜索空间内哪个位置更好。适应度值驱使各粒子朝着搜索空间内个体最优和到目前为止发现的全局最优方向移动。

粒子群算法的步骤如下:

Step1: 对粒子群的随机位置和速度进行初始设定, 同时设定迭代次数;

Step2: 计算每个粒子的适应值;

Step3: 对于每个粒子, 将其适应值与所经历的最好位置Pi 的适应值进行比较, 若较好, 则将其作为当前的个体最优位置;

Step4: 对每个粒子, 将其适应值与全局所经历的最好位置Pg 的适应值进行比较, 若较好, 则将其作为当前的全局最优位置;

Step5: 根 据 式 (1) 、式 (2) 对粒子的速度和位置进行优化, 从而产生新的粒子 (即新解) ;

Step6: 如未达到结束条件通常为最大循环数或最小错误要求, 则返回Step2。

从式 (1) 可以看出:当一个粒子的当前位置接近但并未到达全局最优位置时, 如果该粒子的上一次迭代中的运动速度达全局最优位置时, 如果该粒子的上一次迭代中的运动速度和惯性权值非零, 则该粒子将渐渐运动远离该位置。另外, 一旦所有粒子追赶上当前全局最优粒子, 则这些粒子将停止移动。该现象称为早熟, 即算法过早收敛。

在基本PSO算法中, 粒子的飞行速度是一个很重要的因素, 它取决于粒子当前的位置, 个体最好位置以及群体最优位置, 而且它还不能超过算法设置的最大速度vmax。设置较大的vmax就可能使粒子拥有较大的活动范围, 有可能摆脱局部极值的束缚;但是这样却造成局部寻优能力下降, 往往很难获得高精度的解。vmax设置得较小, 则会使粒子易于陷入局部极值, 无法找到全局最优解。为此, 对粒子群算法做出改进。

3 PSO算法的优化策略

3.1 早熟因子的引入

为避免早熟, 考虑在算法搜索过程中引入一些干扰因素, 描述如下:

v (i) =v (i) +random (3)

x (i) =x (i) +2v (i) (4)

当早熟发生时, 式 (3) 为速度增加一个随机数, 从而改变了该粒子的运动速度, 式 (4) 将粒子移动到一个新的位置, 改变搜索方向。式 (3) 适合单模函数, 式 (4) 适合多模函数。 式 (3) 和式 (4) 描述的干扰使得粒子在新的位置以新的速度开始搜索, 跳出了原早熟区域, 避免了局部最优解, 能够更好地找到全局最小。

当过早收敛发生时, 干扰被引入。在搜索过程中引入搜索因子来发现早熟发生的时机, 该因子被定义为fm。迭代搜索过程中记录下每一个有效搜索步骤, 每一有效搜索步骤的输出记为fg。当迭代过程中某一步的输出大于早熟因子时, 式 (3) 和式 (4) 描述的干扰产生作用, 破坏过早收敛的条件。早熟因子fm根据目标函数的不同取不同值。

3.2 逆反粒子的引入

为避免陷入局部极值, 无法找到全局最优解。提出逆向思维粒子的概念[9]。一个群体中, 具有逆向思维的个体往往会在一个群体中表现突出, 他们往往能够取得意想不到的成功, 使得整个群体受益。

逆向思维粒子的特点是不朝当前粒子的最优结果和当前全局最优结果的加权方向移动。它们随机在粒子群中选取, 其位移公式为:

x (i+1) =x (i) -c3randomv (i) (5)

其中:c3逆向思维因子, random为 (0, 1) 区间的随机数。

在运行过程中总有粒子朝着和大家认定的最优方向相反的方向进行搜索, 由于逆向思维粒子的选择是随机的, 因此其运动的方向也是随机的, 这就保持了群体的活力, 增强了全局寻优的能力。

3.3 变异策略的引入

以往试验表明, 式 (1) 中惯性因子ω将影响PSO的全局与局部搜索能力。ω值较大, 全局搜优能力增强, 局部搜优能力弱;反之, 则全局搜优能力弱, 局部搜优能力强。因此, 采用线性递减权策略[8], 调节PSO算法的全局与局部搜索能力, 即:

ω (t) =ωmax-t (ωmax-ωmin) /nmax (6)

式中: t为当前进化代数, nmax为最大进化代数。这样, 随着迭代进行, 加权因子ω由最大的ωmax线性减小到最小加权因子ωmin。使PSO 在开始时探索较大的区域, 快的定位最优解的大致位置, 着ω逐渐减小, 粒子速度减慢, 开始精细的局部搜索。

3.4 协同机制的引入

可以将协同机制引入PSO算法中[7], 该方法是将n维向量分到n个粒子群中, 每个粒子群优化一维向量, 评价适应值时将分量合成一个完整向量。例如针对第 j 个粒子群, 除第 j 个分量外, 其他n-1个分量都设为最好值, 不断用第j个粒子群中的粒子替换第j个分量, 得到第j维的最好值, 其他维相同。为将有联系的分量划分在一个群, 可将n维向量分到k个粒子群来优化, 则前n mod k 个粒子群是n/ k维 的, 后 k - ( n mod k) 个 粒 子 群是n/ k维的。称这种算法为CPSO – Sk, 它在某些问题上有更快的收敛速度, 但该算法容易被欺骗。

3.5 进化多样性思想的引入

从上面的分析, 为保证收敛到理论全局最优解, 在算法过程中应尽量保证粒子多样性的全局运动。在这思想的指导下, 同时为了保证算法的收敛性, 在进化方程中迭加了多个当前个体最优值。方法是在方程中用到了两个当前个体最优值[12,13]。

引入两个当前个体最优值的具体做法比较简单, 即在每一个粒子的进化方程中, 除了原来自身的当前个体最优值之外, 再另外迭加一个邻近粒子的当前个体最优值。这里所谓的邻近是指粒子编号上的临近。即, 粒子的进化方程描述为:

Vi (t+1) =ῶVi (t) +c1, 1r1, 2 (Lbesti-Xi) +c1, 2r1, 2 (Lbesti+1-Xi) +c2r2 (Gbest-Xi)

Xi (t+1) =Xi (t) +Vi (t+1) (7)

这里, Lbesti粒子i本身的当前个体最优位置, 另外加入了邻近粒子i+1的当前个体最优位置Lbesti+1, 取c1, 1=c1, 2。通过函数的优化测试, 结果显示有较明显的效果。

4 结束语

PSO算法是根据鸟群觅食过程中的迁徙和群集模型[14,15]而提出的用于解决优化问题的一类新兴的随机优化算法, 其最具吸引力的特征就是简单、易实现, 没有很多参数需要调整和很强的全局优化能力. PSO是解决非线性连续优化问题、组合优化问题和混合整数非线性优化问题时的有效优化工具, 目前对粒子群优化算法的研究尚处于初期, 最成功地应用是在进化神经网络方面, 但对其他的研究才刚刚起步, 相对于其他比较成熟的进化算法, 还没有形成系统的分析方法和一定的数学基础, 且应用范围较小, 还有许多问题有待解决。

具体有以下几点:

(1) 算法理论

虽然PSO在实际应用中被证明是有效的, 但其理论基础较弱, 目前还没有给出收敛性、收敛速度估计等方面的数学证明, 即 PSO 中位置和速度的构造以及参数的设计理论不成熟, 对 PSO 中的参数分析没有实质性的认识, 还处于试验分析阶段。

(2) 粒子群的拓扑结构

不同的粒子群邻居的拓扑结构是对不同类型社会的模拟, 如何选择拓扑结构以使 PSO有最佳的性能, 也是需要进一步研究的问题。

(3) 算法应用

粒子群优化算法研究 第2篇

基于粒子群优化算法的无人机航迹规划

提出一种基于粒子群优化算法的无人机路径规划方法,利用粒子群优化算法,将约束条件和搜索算法相结合,从而有效减小搜索空间,得到一条全局最优路径.仿真结果表明:该方法能够快速有效地完成规划任务,获得满意的三维航迹.

作 者：陈冬 周德云 冯琦 CHEN Dong ZHOU De-yun FENG Qi 作者单位：西北工业大学电子信息学院,西安,710072刊 名：弹箭与制导学报 PKU英文刊名：JOURNAL OF PROJECTILES, ROCKETS, MISSILES AND GUIDANCE年，卷(期)：27(4)分类号：V279关键词：无人机 航迹规划 粒子群优化

粒子群优化算法研究 第3篇

摘要：供热管网优化设计一直是多年来城市地下管网工程中的研究热点。通过分析供热管网的优化模型，建立关于供热管网的目标函数即供热管网投资费用，根据供热管网的目标函数及约束条件建立适应度函数。利用粒子群优化算法对该非线性模型进行求解，借鉴遗传算法中变异操作的思想，设计基于遗传算法的混合粒子群算法，寻求在水力约束条件下目标函数的最小值。实例结果表明，将粒子群优化算法应用于供热管网优化设计可以取得较好的优化结果，并且充分的体现出粒子群算法的寻优能力。

关键词：供热管网；目标函数；粒子群优化算法；遗传算法；水力约束条件

中图分类号：TP311文献标识码：A

Abstract：By analyzing the optimization model of heat supply network， a heat supply network objective function， i.e.， the heat supply network investment cost， was established， then the fitness function was established on the basis of the objective function and constraint conditions of heat supply network. To solve this nonlinear model with the particle swarm optimization algorithm， by using the idea of the mutation operation of genetic algorithm， a hybrid particle swarm algorithm based on genetic algorithm was designed， and the minimum of objective function with the hydraulic constraint was sought. The results show that the application of the particle swarm optimization algorithm in the optimization design of heat supply network can achieve better optimization results， and the searching capability of the particle swarm algorithm can be fully embodied.

Key words：heat supply network；objective function； particle swarm optimization algorithm；genetic algorithm；hydraulic constraints

1引言

取暖是保证我国寒冷区域基本生活必要条件之一。随着我国城市供热管网建设的快速发展，原有的供热管网已不能完全满足城市建设的需求，这就需要准确地把握城市供热管网的现状，包括旧管线的维护管理、新管线的设计建设和新小区的管网规划等[1]。目前，对于供热管网的需求，我国已经不满足于规模的逐渐扩大，对于供热管网的适用性、合理性以及热能的有效以及充分的利用率也有了更高的需求。

对于传统的供热管网设计，设计者一般是根据经验进行设计，并且优化设计方案也仅仅是考虑几种不同的布置形式方案比较，并未考虑到同一种布置形式的不同设计的参数组合方案比较[2]。随着优化方法的不断完善，如何使用优化设计优化水力参数，已经成为供热管网设计中非常重要的课题。

粒子群算法由于有精度高、容易实现、收敛速度快等优点，引起学术界的重视，并且在应用于实际的问题中展示了优越性[3]。通过研究粒子群优化算法及遗传算法，以供热管网投资费用作为目标函数，建立供热管网数学优化设计模型，并把粒子群算法应用于这一模型。

2供热管网优化模型

2.1目标函数

管线是供热系统的主要组成部分，供热管材的选择关系到整个供热系统的可靠性和安全性[4]。在供热管网优化设计中，主要设计目标就是在满足管网设计约束条件情况下，使供热管网投资费用即目标函数C最小，以保证经济性。考虑到管径、施工环境、地下水位以及地下及地上构筑物等因素，需要考虑各节点的用水量及水压，来确定根据管线上各管段的设计流量及水压来确定管线干路和支路上流量及水压[5]。供热管网投资费用由供热管线造价、实施费用、年折损值、水电的运行费用四部分组成。本文主要考虑粒子群优化算法在供热管线中的应用，目标函数包括管线造价和管线运行费用两部分。

目标函数如下：

2.2约束条件

通常的情况下，在供热管网中默认水为不可压缩的流体，密度恒定不变[6]。为了解决供热管网优化模型的目标函数，即使供热管网投资费用在一定约束条件下获得最优解，需要在目标函数基础上加上约束条件[7]。

1）管段流速的约束条件

在供热管网设计中，管段流速理应在管段设计最小流速与管段设计最大流速之间，即：

3粒子群优化算法基本理论

粒子群优化算法（particle swarm optimization，PSO）是一种基于种群的智能算法[9]。是20世纪90年代由作者J.Kenndy和R.C.Eberhart等提出一种基于启发式的优化算法。PSO算法起源于对鱼群和鸟群等运动轨迹的观察[10]。此算法中，个体仅仅是通过对同伴的行为追踪以及自身简单的行为，就可以让整个群体的运动达到一种和谐的状态。

其中，每个个体抽象成一个“粒子”，它不具有体积，仅仅包含速度和位置的信息，所有的粒子都有适应度值（fitness），且fitness=1/C。粒子根据不断地向自身经历过的最优的位置和当前种群的最优位置学习，向解空间中更好位置进行搜索，直到搜索到全局最优解[11]。

图1为第t代和第t+1代的粒子位置和速度调整示意图。其中，v1为迭代时刻t粒子通过对“社会部分”的学习使粒子向群体位置最优值（gbest）方向不断靠近的速度；v2为迭代时刻t+1粒子通过对“自知部分”的学习使粒子向群体位置最优值（pbest）方向不断靠近的速度；v3表示粒子自身具有的速度。在速度v1，v2和v3的共同作用下，粒子在迭代时刻t+1以速度vt+1到达位置xt+1，在下一个迭代时刻，粒子以同样模式的位移和速度组成方式继续向最优位置靠近，从位置xt+1如此继续迭代下去。

粒子群优化算法的基本数学模型如下：假设问题求解于D维的搜索空间，每个粒子作为一个可能解，所有的粒子形成一个群体（Swarm）。Swarm={x（k）1，x（k）2，…，x（k）m}，其中，m为粒子个数。在D维搜索空间中，k时刻第i个粒子当前的位置向量为x（k）i=（x（k）i1，x（k）i2，…，x（k）id），i=1，2，…，m，这是目前为止个体在搜索空间内的极好位置，即个体极值[12]。其中，下标d表示为粒子第d维（d=1，2，…，D）。与该个体的位置向量对应的该个体速度向量是v（k）i=（v（k）i1，v（k）i2，…，v（k）id）。在k时刻第i个粒子的第d维领域计算公式如下：

v（k）id=w·v（k-1）id+c1·r1·（p（k-1）id-x（k-1）id）+

c2·r2·（p（k-1）ld-x（k-1）id）（13）

x（k）id=x（k-1）id+v（k）id（14）

式中：w为惯性权重[13]，用来表示粒子的惯性对于速度的影响程度；c1，c2为粒子加速因子，用来影响粒子速度，一般c1=3，c2=2；r1，r2为（0，1）之间的随机数；k为迭代次数；p（k-1）id，p（k-1）ld分别为粒子个体位置最优解与粒子群体位置最优解。

粒子更新机制是在搜索空间中随机的初始每个粒子的初始速度和粒子群的初始速度，通过粒子的不断迭代从初始粒子群开始搜索粒子的适应度函数最优解[14]。每次迭代过程中，粒子通过跟踪个体位置最优解与粒子群体位置最优解不断调整自己的方向和速度，用来更新粒子位置。

4PSO算法在供热管网优化设计中的应用

由于粒子群优化算法容易陷入局部最优解，所以通过对照遗传算法中变异操作的思想，使用变异算子对粒子进行变异操作，设计基于遗传算法的混合粒子群算法。对操作算子的引进进行解析：

首先，对于算子选择方案，按照一定比例选择进行选择，按照实际问题采用相应的比例度。本文根据适应度函数选取前半部分较好的粒子直接进入下一代，使粒子的优良基因一直地传递下去，有利于找到更优解。

杂交算子操作的设定，采用遗传算法中杂交操作的概念，提出杂交粒子群算法思想。在每一次的迭代过程中，选择适量的粒子放入一组中，并赋予粒子一个与适应度函数无关的随机的概率，即杂交概率ρn*。首先，凭借ρn*对选取的粒子进行杂交的操作计算，并且把上一代个体替换成新产生同等数量的个体。其次，在整体数量不变的基础上，凭借原来粒子位置加权来计算新粒子的位置。然后，根据类似交叉的思想，选择已经根据适应度值排序完毕的前半部分粒子进行两两交叉操作运算，赋予与适应度不相关的一个随机的ρn*，产生同等数量的粒子安置到下一代的粒子群的后半部分替换原来粒子群[15]。按照下列式子进行位置交叉：

是两个即将进行杂交操作的粒子速度，采用杂交之后的粒子速度用来替换上一代粒子速度，这样粒子就完成了对于位移和速度的杂交方案。

变异操作是在随机初始化整个粒子群的基础上，设定一个变异概率ρn*，与随机产生的变异概率进行对比，若满足了相应的条件，即随机生成的变异概率小于ρn*，那么就进行对粒子得变异操作。ρn*表达式如下：

ρn*=0.10-m·（0.10）/n（19）

其中，m表示粒子当前的序数，通过粒子的变异操作可以有效的防止PSO算法陷入收敛或局部早熟。

基于PSO算法的供热管网优化设计步骤如下：

1）确定供热管网数学模型，初始化粒子群的个体位置与速度，输入原始数据；

2）根据初始的粒子位置和速度计算粒子的适应度值；

3）初始化粒子的个体最优值pbest和群体最优值gbest；

4）计算惯性权重w值，更新粒子速度和位置；

5）计算当前粒子适应度值，按照适应度值排序；

6）按照改进的选择交叉变异算子进行操作；

7）重新计算粒子的适应度值，更新粒子个体最优值pbest；

8）判断全部粒子是否计算完毕，未完成粒子数加1，转步骤4），若完成则更新群体最优值gbest；

9）判断是否达到迭代次数n，未达到迭代次数则n+1，转步骤4），达到则输出结果，运行结束。流程图如下；5实例分析

实例：图3为某小区供热管网示意图，进行管段优化设计计算。小区的供热管网共有一个热源和17个热源连接节点，热源节点为1，设计流量300 t/h（吨/时），管线压力为0.4 MPa，热源连接节点分别为2～18。由于此小区管线管线敷设方式为直埋，故β=0.15。

6结论

供热管网的优化设计一直是多年来城市地下管网系统中的研究热点[16]。针对供热管网管径的选择问题，本文通过借鉴遗传算法中变异操作的思想，使用变异算子对粒子进行变异操作，设计基于遗传算法的混合粒子群算法。通过粒子的速度与位置的寻优寻找最优解，即最优供热管线管径组合。实例结果表明，优化后年运行费用比优化前年运行费用节省约61万元。理论上年运行费用节约7%，管线年基础费用节约5%。故粒子群优化算法在供热管网优化设计中取得了满意的效果，同时也证明了该粒子群算法在供热管网优化中的可行性。此外，PSO算法最终的解还需要更进一步的验证，优化算法的效率也有待更进一步的提高。

参考文献

[1]孙巍.供热管网的建模分析及水力平衡调节[D].北京：北京化工大学硕士学位论文.2008.

[2]任伟建，黄晶，杨有为，等.基于改进粒子群算法的油田注水管网优化设计[J]. 给水排水.2009，9（11）：2929-2933.

[3]杨亚红，王瑛，曹辉.基于粒子群优化算法的环状管网优化设计[J].兰州理工大学学报.2007，33（1）：136-138.

[4]孙明月，许文斌，邹彬，等.基于整数编码粒子群算法的树状供水管网优化[J].水资源与水工程学报.2012，23（6）：168-171.

[5]殷方康.基于蚁群粒子群混合算法的多目标优化在供水管网优化设计中的应用[J].山东商业职业技术学院学报.2014，14（4）：102-105.

[6]ZHOU Y，CHEN Y，XU G，et al.Home energy management with PSO in smart grid[C]//Industrial Electronics（ISIE），2014 IEEE 23rd International Symposium on.IEEE，2014：1666-1670.

[7]薛英文，文倩倩.基于粒子群算法的污水管网优化设计[J].中国农村水利水电.2010，（8）：40-42.

[8]YANG J，HE L，FU S.An improved PSO-based charging strategy of electric vehicles in electrical distribution grid[J].Applied Energy，2014，128：82-92.

[9]刘孟军，邹平华.供热管网经济性分析软件的研究[J].暖通空调，2005，35（10）：12-16.

[10]秦芳芳.供热管网水力计算模型研究[D].北京：华北电力大学硕士学位论文，2008.

[11]张保花.关于供热管网敷设分析的设计探讨[J].山西建筑.2015，41（24）：127-128.

[12]QIAN L，WEN Y L，GUOHUA G.OCCI And PSO-based Optimization And Management System for Grid Maintenance Scheduling[J].2013.

[13]THEOBALD D M.GIS concepts and ArcGIS methods[M].Conservation Planning Technologies，2007.

[14]李祥立，邹平华.基于模拟退火算法的供热管网优化设计[J].2005，35（4）：77-81.

[15]谢元平.改进粒子群优化算法的研究及其在控制系统设计中的应用[D].北京：北京化工大学硕士学位论文，2011.

粒子群优化算法的发展研究 第4篇

0引言

优化概念反映人类实践活动中十分普遍的现象, 即要在其他各方面的前提下, 争取获得可能范围内的最佳效果, 其应用已涉及多种学科的各种不同领域。因此, 一些新颖的解决优化问题的优化算法得到迅速发展。从20世纪90年代初, 已存在模拟自然界生物的群行为来构造随机优化算法的思想, 即群智能算法。典型的方法有Dorigo提出的蚁群算法和Eberhart和Kennedy[1]提出的粒子群算法。

粒子群算法 (PSO) 根源于人工生命的研究, 特别是对鸟群、鱼群等群体行为机制的模仿, 并借鉴生物学家Hepper提出的生物体模型, 同时也融入进化计算的思想。该算法概念简单、易理解, 参数少容易编程实现, 且对计算机的硬件的速度和存储要求不高, 对非线性、多峰值问题具有较强的全局搜索能力, 在科学研究和工程实践中得到广泛关注。

1基本粒子群算法

1.1原始粒子群算法

PSO模拟鸟群的捕食行为, 设想这样一个场景:一群鸟在随机搜索食物, 在这个区域里只有一块食物, 所有的鸟都不知道食物在那里, 但是他们知道当前的位置离食物还有多远, 那么找到食物的最优策略是什么呢, 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题, 每个优化问题的解都是搜索空间中的一只鸟, 我们称之为“粒子”。设zi= (zi1, zi2, , zi D) 为第i个粒子 (i=1, 2, , m) 的D维位置矢量, 根据事先设定的适应值函数 (与要解决的问题有关) 计算zi的当前的适应值, 即可衡量粒子位置的优劣;vi= (vi1, vi2, , vid, , vi D) 为粒子i的飞行速度, 即粒子移动的距离;pi= (pi1, pi2, , pid, , pi D) 为粒子迄今为止搜索到的最优位置;pg= (pg1, pg2, , pgd, , pg D) 为整个粒子群迄今为止搜索到的最优位置。

在每次迭代中, 粒子速度和位置迭代公式分别为:

其中, i=1, 2, , m, d=1, 2, , D, k是迭代次数, r1和r2为[0, 1]之间的随机数, 这两个参数是用为保持群体的多样性。c1和c2为学习因子, 也称加速因子, 其使粒子具有自我总结和向群体中优秀个体学习的能力, 从而向自己的最优点以及群体内历史最优点靠近。由于粒子群算法中没有实际的机制来控制粒子速度, 所以有必要对粒子的最大值进行限制, 当速度超过这个阈值时, 设其为vmax, 这个参数被证明是非常重要的, 因为值太大会导致粒子跳过最好解, 但太小的话又会导致对搜索空间的不充分搜索。

式 (2-1) 的第二项是“认知”部分, 代表粒子对自身的学习。而公式的第三项是“社会”部分, 代表粒子间的协作。式 (2-1) 正是粒子根据它上一次迭代的速度、它当前的位置和自身最好经验与群体最好经验之间的距离来更新速度, 然后粒子根据式 (2-2) 飞向新的位置。

1.2带惯性权重的粒子群算法

为了改善上述粒子群算法的收敛恨性能, Shi和Eberhart[2]在1998年提出了一种改进算法, 在速度更新公式中引入惯性权重w, 速度迭代公式变为:

为了使改进的算法更好的提高算法性能, 他们不是把惯性权重设置为定值, 而是一个随时间线性减小的函数。针对惯性权值线性递减粒子群算法不能适应复杂的非线性优化搜索过程的问题, shi和Eberhart[3]则用模糊系统来控制粒子群算法中的惯性权重, 达到动态地调整搜索能力。zhang等[4]人提出了一种动态改变惯性权的自适应粒子群算法, 该算法引入了参数粒子群进化速度因子和聚集度因子, 使算法具有动态适应性, 收敛速度和收敛精度都有所提高。

1.3带收缩因子的粒子群算法

Clerc[5]的研究表明使用收缩因子可以保证粒子群算法收敛。收缩因子定义为:

Clerc的带收缩因子的方法中设l为4.1, 故收缩因子χ为0.729。实验证明, 该收缩因子导致粒子随时间快速收敛, 即当粒子在局部和邻域的先前最好点时, 粒子振荡幅度减小了。

1.4与其他算法的异同

1、与传统的基于梯度的优化算法相比:

粒子群算法对优化目标函数及问题定义的连续性没有特殊要求, 使得算法应用更广泛;没有中心控制约束, 更有鲁棒性;采用非直接的信息共享方式实现合作, 更具有扩充性;随机搜索本质, 使它更不容易陷入局部最优。因此, 粒子群算法对于复杂, 特别是多峰高维的优化计算问题具有很强的优越性。

2、与进化计算技术 (如遗传算法) 相比:

粒子群算法没有直接使用组合算子、单向的信息流动、没有“适者生存”的概念、没有直接利用选择函数。所有粒子在大多数情况下可能更快地收敛于最优值, 就算低适应值的粒子在优化过程中也能生存, 且可能搜索到解空间的任何一个领域。

3、与蚁群算法相比:

两者提出的年代相似, 且基本思想都是模拟自然界生物群体行为来构造随机优化算法的。都是不确定的概率型的全局优化算法, 都不依赖优化问题本身的严格数学性质, 都是基于多个智能体且并行性的仿生优化算法。不同点在于粒子群算法所需的代码和参数较少、算法受问题维数的影响较小, 并且数学基础相对薄弱, 在收敛性方面研究还需进一步深入。

2改进的粒子群算法

基本粒子群算法存在很多缺陷, 如对环境的变化不敏感, 常常会受pbest和gbest的影响而陷入非最优区域, 算法经常发生早熟收敛等现象。所以很多学者在基本粒子群的基础上, 提出了很多类型的改进算法, 下面介绍一些有代表性的改进, 并讨论这些算法的优缺点及主要应用范围。

2.1离散粒子群优化算法

2.1.1二进制离散粒子群优化算法

由于基本粒子群优化算法主要针对连续函数进行搜索运算, 但许多实际工程问题都描述为离散的组合优化问题, 典型的例子包括调度问题或路由问题。为此, Kennedy和Eberhart提出离散二进制版本的PSO算法[6]。粒子使用二进制字符串进行编码, 通过使用sigmoid函数, 速度被限制在[0, 1]区间之内, 并被解释为“概率的变化”。

2.1.2改进的二值离散粒子优化算法

为提高算法的运算效率, 防止早熟收敛, 杨红孺等[7]提出改进的二进制离散粒子群优化算法, 该算法利用基本粒子群算法中“粒子依赖自身经验及粒子群全体经验, 同时克服自身飞行惰性”的思想, 改进了粒子的更新运动公式, 并采用怀疑策略将离散的二进制值由0、1改为-1、1。Shen等[8]则在研究了Kennedy的离散版本的PSO后提出了一种更为简单与有效的粒子群优化算法, 该算法通过采用强制10%的粒子做随机运动来避免算法陷入局部最优。Yang[9]等对该方法在量子空间进行了扩展。

2.1.3离散粒子群优化算法应用

CHEN等[10]将离散量子粒子群算法应用到车辆排程调度问题 (CVRP) 上, 并与遗传算法、模拟退火算法在同一问题上的运算结果作比较, 得出在该问题中离散量子粒子群算法的搜索效果是最优秀的。为了解决旅行商问题, 庞巍等[11]提出了模糊离散粒子群优化算法, 该算法使用模糊矩阵表示粒子位置和速度, 迭代过程中加入归一化和解模糊化运算, 并证明了该算法在求解旅行商问题上有较为优越的性能;余玲俐等[12]同样针对旅行商问题, 根据组合优化问题和离散量的特点, 对离散粒子群算法加入逆转变异优化策略、受蚁群启示的变异优化策略和邻近搜索变异优化策略3种优化变异优化策略, 使其成为新的混合离散粒子群算法。於世为, 诸克军[13]提出了一种基于离散粒子群的自适应RBF网络模型, 该模型采用二进制编码的PSO, 通过改进最邻近聚类选择中心向量的方法, 在神经网络建模与控制中, 被证明具有实用价值。于化龙等[14]在shen的基础上, 通过增加一条新规则对算法进行改进, 使其不但可以有效的克服局部最优, 而且可以获得一个尽可能小的特征子集, 同时具有更高的分类性能。

2.2小生境粒子群优化算法

Brits等[15]将小生境技术引入粒子群算法中, 提出了小生境粒子群算法 (Niche PSO) , 实验表明, 小生境粒子群优化算法在求解多峰函数的问题上搜索效果优秀。Niche PSO同时使用多个子种群来定位和跟踪多个最优解[16,17]。Brits还研究了一种通过调整适应值计算方式的方法来同时找到多个最优解[18]。王俊年等[19]基于Niche PSO算法提出了基于聚类的小生境粒子群算法 (CBNPSO) , 该算法采用聚类算法区分粒子群不同的子粒子群, 并采用多种策略实现全局和各子粒子群按不同的粒子群进化, 虽然算法与标准PSO相差不多, 但小生境的收敛情况明显好于标准的PSO。王俊年等[20]又提出了一种新的多种群并行进化的种群小生境粒子群优化算法 (SNPSO) , 该算法在神经网络训练上效率最高, 适合解决前向神经网络结构和权值的设计问题。

2.3混合粒子群优化算法

由于单个算法总有其优势, 也有其缺陷, 因此, 很多学者通过对多个算法的混合, 发挥各自的优势, 并应用于相应的领域。实验证明, 混合算法确实能出高效果。

1、基于遗传思想改进粒子群算法

Angeline[21]提出了混合群体, 其结合了类似于传统进化计算中的选择机制, 此选择过程在粒子修改群体前执行, 使得在每一代中, 一半的个体将会被移动到比当前位置具有相对优势的位置上, 因此, 带有选择机制的混合群体比粒子群具有更多开发能力。Lovbjerg[22]则提出了繁殖粒子群算法, 即给粒子群中的粒子赋予一个杂交概率, 在每次迭代中, 根据杂交概率选择一定数量的粒子进入一个池中, 池中的粒子随机两两杂交, 产生相同的子代, 并用子代取代父代粒子, 以保证种群的粒子数目不变。崔光照等[23]则将引进扰动策略的改进粒子群算法再与遗传算法相结合, 提出了改进的粒子群遗传算法 (MPSO/GA) , 该算法以基本遗传算法为基础, 同时将改进的粒子群算法作为遗传算法的一个重要因子, 并将该算法对DNA计算中编码序列实现了优化, 得到比较好的DNA序列。

2、混沌粒子群优化算法

高鹰等[24]提出混沌粒子群优化算法 (CPSO) , 该算法为防止在迭代中出现停滞, 利用混沌变量的遍历性, 以粒子群当前搜索到的全局最优位置为基础迭代产生一个混沌序列, 然后将序列中的最优粒子位置替代当前粒子群中的某一粒子的位置并进行迭代。实验证明, 该算法运行稳定并具有较好的鲁棒性和适应性。郏宣耀等[25]在CPSO基础上提出一种自动调整邻域搜索范围和方向的自适应变邻域混沌搜索微粒群算法 (AVNC-PSO) , 该算法在种群收敛于局部最优时, 选择飞行停滞且聚集程度高的粒子向不同邻域内进行混沌搜索, 搜索方向和粒子偏移量根据粒子与收敛中心的距离和混沌变量的值共同确定, 实验表明, 该算法能够使局部搜索更精确, 提高优化精度。

3、基于模拟退火的粒子群优化算法

2004年高鹰等[26]提出了以基本粒子群优化算法作为主体运算流程, 引入模拟退火机制, 并混合了基于遗传思想的粒子群优化算法中的杂交运算和带高斯变异的粒子群优化运算的模拟退火粒子群优化算法 (SA-PSO) 。该算法首先随机产生一个初始粒子群, 然后通过基本粒子群优化算法对初始粒子群进行搜索, 产生一个较优的新粒子群。再应用杂交算法和带高斯变异算法在模拟退火操作下对这个较优的粒子群进行寻优运算, 最终得到算法结果。理论实验证明, 只要迭代次数足够多, 模拟退火粒子群算法将以概率收敛于函数最优值。

2.4其他粒子群改进算法

纪震等[27]基于传统粒子群算法, 提出了智能单粒子算法 (ISPO) 。在ISPO算法的优化过程中, 算法不是对整个速度矢量或位置矢量同时进行更新, 而是先把整个矢量分成若干个子矢量, 并按顺序循环更新每个子矢量。在子矢量的更新过程中, 此算法通过引入一种新的学习策略, 使得粒子在更新过程中能够分析之前的速度更新情况, 并决定子矢量在下一次迭代中的速度。实验结果表明, 此算法在优化复杂具有大量局部最优点的高维多峰函数具有一定优势, 且其解非常接近全局最优点。

3粒子群算法的应用

粒子群算法作为一种新兴的群体智能算法, 自从提出之后, 由于其概念简明、实现方便, 在短期内迅速得到国际演化计算领域的认可, 并且由于其在解决复杂的组合优化类问题方面所具有的优越性能, 被广泛应用于工程设计与优化[28,29,30,31,32,33]、电力系统[34,35,36,37,38,39]、机器人控制[40,41]、交通运输[42,43,44,45,46]、通信[47,48]、计算机[49,50,51,52]、工业生产优化以及生物医学[53]和电磁学[54,55]等领域。

4结论与展望

本文对PSO的基本原理, 算法改进的研究发展和应用进行了全面综述, 不仅可以让初学者了解PSO, 也为资深学者提供一定的参考价值。

粒子群优化算法研究 第5篇

一种改进粒子群优化算法及其在投资规划中的应用

粒子群优化算法(PSO)是模拟生物群体智能的优化算法,具有良好的`优化性能.但是群体收缩过快和群体多样性降低导致早熟收敛.本文引入了多样性指标和收敛因子模型来改进PSO算法,形成多样性收敛因子PSO算法(DCPSO),并且对现代资产投资的多目标规划问题进行了优化,简化了多目标规划的问题,并且表现出了比传统PSO算法更好性能.

作 者：刘羿 陈增强 袁著址 LIU Yi CHEN Zeng-qiang YUAN Zhu-Zhi 作者单位：南开大学,自动化系,天津,300071刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：200737(11)分类号：O1关键词：PSO算法(Particle Swarm Optimization) 现代资产投资 多样性 收敛因子模型 多目标优化

基于粒子群遗传算法的配电网络重构 第6篇

关键词：网络重构；粒子群遗传算法；多目标优化；配电网

中图分类号：TM727 文献标识码：A 文章编号：1674-1161（2014）02-0044-03

配电网连接输电网和用户网两部分，从输电网或地区发电厂接受电能，通过配电设施就地分配（或按电压逐级分配）给各类用户网，是电力系统中线路最紧密的地方。由于配电网中的电压等级相对较低，因此会消耗大量的有功功率。相关数据显示，配电网上损耗的有功功率约占全部线路损耗的60%。通过配网重构方式降低配电系统的有功损耗，对减少全网网损有重要意义。

传统意义上的配电网网络重构是使配电网一直保持在辐射状运行状态，在满足馈线热容、电压降落和变压器容量等约束条件的情况下，通过改变网络中分段开关与联络开关的开闭状态组合重构、优化现存网络拓扑，使配电系统内某一项或者多项目标达到最优状态，改善配电网的潮流分布，从而达到降低系统网损、均衡系统负荷和改善电压质量的目的。

1 配电网网络重构问题描述

1.1 目标函数

配网重构的优化目标函数有很多种，常见的有以下3种：

1）以系统有功网损最小作为目标的函数表达式为：

f1=minRi （1）

式中：Ui，Qi，Pi，Ri分别为配电网中第i条支路的母线电压、无功功率、有功功率、电阻阻值。

2） 以均衡负荷分布及供电质量为目标的函数表达式：

f2=minLB （2）

式中：nB为系统总支路数，Si，Simax分别为流过支路的功率和支路容量。

3） 以提高供电可靠性、平均用电无效度最小目标的函数表达式为：

f3= （3）

式中：Np为配电系统中负荷数；Ni为负荷点i的用户数；Ui为负荷点i的年停运时间；NT为总用户数。

配网重构问题其实是多个单一目标的组合问题，单一目标函数仅仅能使系统中一项指标达到最佳，忽视了配电网中的其他重要指标，实现不了配电网重构的全部目的，因此有必要引入多目标函数优化理论。采用线性加权法，根据各个目标在问题中的重要程度，分别赋予事先给定的相应权值λ，作为各目标系数，且系统之和为1，然后把带系数的目标函数相加来构造评价函数，即：

minh（X）=λ1f1+λ2f2+λ3f3 （4）

1.2 约束条件

配电网网络重构需要满足以下约束条件：1） 潮流方程约束，即重构必须建立在满足潮流方程的基础上；2） 供电约束，即网络拓扑约束，包括辐射状运行约束（开关的操作必然是成对的，即每闭合一开关，必然要打开另一个开关）和无网络“孤岛”；3） 线路容量约束；4） 节点电压约束。

2 粒子群遗传算法

遗传算法（GA）和粒子群算法（PSO）的进化（或迭代）都是在上一次计算结果基础上进行的，两种算法都采用多点搜索策略，且都以适应值作为搜索依据。GA具有较好的全局收敛性，缺点是没有记忆性，即随着新一代个体的出现，会自然抛弃很多上一代有价值的信息。相比之下，PSO优点在于简单、灵活且具有记忆性，但在全局收敛性上表现不佳。

基于GA和PSO的相同之处，并结合各自的优点，提出粒子群遗传混合算法。该算法的基本思想为：在寻优过程中，对部分个体应用粒子群优化的搜索策略进行寻优，另一部分个体则以遗传操作进化，挑选适应值较高的个体进行下一代寻优，共享整个群体的进化信息；同时，为确保算法的收敛性，采用最佳个体保留策略（即在进化过程中，当前最优的个体不进行进化操作而是直接进入下一代），既能提高粒子群算法的全局收敛性和搜索效率，又能保证遗传到有价值的信息。

2.1 粒子群算法

将粒子群搜索空间设为B维，粒子总数为M。第i个粒子的位置表示为Li=（li1，li2，...，liB），“飞行”历史中最优位置为Xi=（xi1，xi2，...，xiB），速度为向量Vi=（vi1，vi2，...，viB）。每个粒子的位置按下列公式进行变化：

viBt+1=w×vidt+c1×rand×（liBt-xiBt）+c2×rand×（pgBt-xiBt） （5）

xiBt+1=xiBt+vidt+1 （6）

式中：c1，c2為正常数，粒子的加速因子；rand为[0，1]之间随机数；w为惯性因子。

首先通过随机方式产生粒子群的初始位置和速度，然后按上述公式（5）和（6）进行迭代运算。如果迭代超出了边界值，则取边界值，直至求出满意解。

2.2 遗传算法

2.2.1 编码和初始化 GA的一个显著特点是既能在编码空间对染色体进行遗传运算，又能在解空间对解进行评估选择，交替工作于编码空间与解空间。解和编码规则是密不可分的。二进制编码方式会产生大量不可行解。由于环网判断较复杂，如果采用十进制编码会使程序解码困难，影响求解速度，因此引入混合编码，将联络开关闭合时形成的环网组成编码组，格式为K1，T1；K2，T2；...；Ki，Ti。其中：Ki为联络开关的开闭状态，用二进制编码方式编码；Ti为联络开关闭合状态下该环网应打开的分段开关，用十进制编码方式编码。

遗传算法的初始化，就是根据编码规则随机产生编码向量，然后根据编码向量确定的网络拓扑计算网络潮流，判断节点电压是否满足配电网节点电压要求的约束条件。若满足要求，将其选为染色体的初始种群；否则重复上述步骤，直至产生满足要求的初始种群数量Q。

nlc202309021044

2.2.2 适应度函数 适应度函数是在初始种群中选择染色体进行相应遗传操作和用来评价染色体质量的前提。适应度函数的适应值可指导遗传算法的搜索方向，因此对配电网络重构求解问题构造合适的适应度函数非常重要。适应度函数的值应为正数，且优化方向应与对应适应值增加方向一致。配网重构的优化问题属于最小值优化问题。现应用的适应度函数为：

F=Amax-f f

0 其他 （7）

式中：Amax 为给定的常量；F为适应度函数；函数表达式f为综合考虑网络和约束条件的罚函数。

2.2.3 遗传操作 遗传操作包括选择复制、交叉和变异。选择复制通常采用数学轮盘赌法按照每个染色体适应度进行选择复制，并加入最优保留策略。这既能使染色体被选择的概率与其适应值成正比，又能保证种群多样性和最优个体不被破坏。

由于采用混合编码策略，所以要对染色体中不同的編码序列进行交叉和变异操作。对于二进制编码序列进行交叉操作时，采用双电切法；进行变异操作时，对二进制编码按变异概率任选若干基因位，以实现反转其位值的变异。对十进制编码序列进行交叉操作时，采用基于次序的杂交法，变异操作采用倒位操作的变异算子进行。与传统方法相比，混合交叉方法和变异操作可以更有效地防止GA过早收敛。

根据上述步骤给出粒子群遗传算法流程图，如图1所示。

3 算例分析

利用提出的粒子群遗传算法对IEEE69节点测试系统进行网络重构计算。该测试系统拥有69个节点、73条线路，5个联络开关分别为S69，S70，S71，S72，S73，总负荷为3 802.2 kW+j2 694.6 kVar。设置种群数量50（其中GA种群25，PSO数量为25），染色体长度为5，最大进化代数为100。测试系统的结构如图2所示。

应用算法程序所得的计算结果以及粒子群遗传算法同粒子群算法、遗传算法的寻优性能对比结果如表1所示。

4 结论

针对GA算法的无记忆性以及PSO算法较差的全局收敛能力，提出粒子群遗传算法。其结合GA的进化思想和PSO的记忆性，无论是算法效率上还是全局收敛性上，都具有比单一GA算法和PSO算法更好的性能。通过对IEEE69节点测试系统进行计算和分析，验证了算法的有效性和可行性。

粒子群算法优化神经网络结构的研究 第7篇

基于粒子群和神经网络[6,7,8]的特点,本文选取两个隐含层的BP神经网络,通过用粒子群算法来确定神经网络的初始权阈值和结构,主要表现在BP神经网络的初始权阈值和隐含层节点数的确定上,将该模型应用到函数拟合数值实验上,取得了良好的效果。

1 粒子群优化算法

粒子群优化算法来自对鸟群的捕食行为的模拟。设想这样一个场景:一群鸟在搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在那里,但是它们知道当前的位置离食物还有多远,那么找到食物的最优策略是寻找目前距离食物最近的鸟的周围区域。

粒子群优化算法是一种基于群体智能的进化计算技术,粒子群优化算法的数学描述为:假设在一个n维的搜索空间中,由m个粒子组成的种群x=(x1,x2,,xm)T,其中,第i个粒子位置为xi=(xi,1,xi,2,,xi,n)T,其速度为vi=(vi,1,vi,2,,vi,n)T。它的个体极值pI=(pI,1,pI,2,,pI,n)T,种群的全局极值pG=(pG,1,pG,2,,pG,n)T。粒子根据下面公式(1)和(2)来更新自己的速度与位置。

式中:c1和c2为学习因子;rand()为介于(0,1)间产生的随机数;vik,d和xik,d分别为粒子i在第k次迭代中第d维的速度和位置;pIk,d和pkG,d分别为粒子i在第d维的个体极值和全局极值的位置。

本文针对粒子群算法易陷入局部极值的问题,在PSO进化过程中加入了混沌的思想,混沌具有随机性,遍历性,规律性等特点,相对于一般的随机搜索方法,混沌搜索在小空间具有较强的局部搜索能力,细致搜索的有效性更强。最为重要的是,混沌运动是在一定的范围内可以按其自身的规律不重复遍历所有状态。利用混沌变量的这些特征进行优化搜索,能使算法跳出局部最优,可保持群体多样性,进一步改善算法的全局寻优能力。本文取一个典型的混沌系统即Logisitc映射作为混沌信号发生器[9],迭代公式如下:

式中:μ为控制参量,当μ=4,0x01时,Logisitc完全处于混沌状态。

混沌粒子群更新公式为:

式中:chaos=4rand()(1-rand())。

一般的PSO算法只能应用于连续空间,为解决离散优化问题,Kennedy等人提出了二进制PSO算法,其中,粒子位置的每一维只有0和1两种状态,速度更新的方法与连续PSO相同,位置的更新则取决于由粒子速度决定的状态转移概率,速度大于一定的数值时,粒子取1的可能性大,反之越小。迭代公式如式(6),式(7)所示:

式(7)中:ρik+,d1∈[0,1]是一随机数;sig()为sigmoid函数,为速度转换函数,在本文中,选取logsig()函数。

2 粒子群优化神经网络

2.1 编码方法

本文通过十进制粒子群算法来优化网络的权阈值,同时用二进制粒子群算法来优化网络的结构。优化网络结构主要表现在是通过二进制粒子群算法来确定网络各个隐含层的节点是否存在。

根据式(7),若该位置变量等于1,则其对应的隐含层节点存在,其对应的网络的权阈值存在。否则,若该位置变量等于0,则其对应的隐含层节点不存在,其对应的网络的权阈值不存在。然后根据网络的结构和权阈值来计算适应度。适应度评价函数为:

式中:T为网络期望输出;T′为网络实际输出;N为训练样本的个数;S2为输出层节点个数。

2.2 粒子群优化神经网络的流程

(1)分别初始化设置十进制粒子群算法(DePSO)和二进制粒子群算法中BiPSO的基本参数。种群的大小为M,惯性权重为w,学习因子为c1和c2,粒子群算法的最大迭代次数为Tmax,令当前迭代次数为t=1,在可行域内分别产生DePSO和BiPSO初始粒子的初始位置和初始速度。设定BP算法的最大训练次数为TBP。根据经验初始化各个隐含层节点的个数。

(2)根据初始化的网络结构和权阈值,评价每个粒子的初始适应度值,pbesti和pbestdi分别设置为当前粒子权阈值和结构的位置,gbest和gbestd分别设置为初始化粒子中最好粒子权阈值和结构的位置。

(3)根据式(4)、式(5)更新所有粒子权阈值变量的速度和位置,产生一组新的粒子。

(4)根据式(6)、式(7)更新所有粒子结构的速度和位置,产生一组新的粒子。

(5)根据当前网络的结构和权阈值来评价每个粒子的适应度值,如果第i个粒子的适应度值比更新前的适应度值高,则更新pbesti和pbestdi的值及对应的位置;如果所有粒子中最好的适应值优于gbest和gbestd,则更新gbest和gbestd对应的位置,t=t+1,如果t>Tmax,转到步骤(6),否则转到步骤(3);

(6)将通过粒子群优化确定的权阈值和结构作为BP算法的初始权阈值和网络结构,然后用BP算法进行训练,若达到最大的训练次数TBP,则训练结束,结果存盘。

2.3 算法参数设置

粒子种群规模为200个,十进制粒子群算法中,初始位置在[-10,+10]范围内随机产生,初始速度在[-5,+5]间随机产生,学习因子c1=2.8,c2=1.3。惯性权重从0.9~0.4线性递减。二进制粒子群算法中,初始位置在[-1,+1]间随机产生,初始速度在[-0.5,+0.5]间随机产生,学习因子c1=c2=2。惯性权重w=1。

3 函数拟合数值实验

下面通过2个函数对本文所建立的粒子群神经网络的模型进行测试,按照下面式(9)计算函数误差:

(1)函数1:

根据经验,初始的2个隐含层的节点数均取为10个。粒子群算法中最大迭代次数Tmax为200次,之后BP算法再对神经网络训练10 000次。在[-1,+1]之间总共选取512个样本,其中训练样本250个,测试样本262个。为消除算法的随机性,通过5次仿真实验,结果如表1所示。

(2)函数2:

式中:xi∈[0,1],误差按式(9)计算,根据经验,初始的2个隐含层的节点数均取为15个。粒子群最大迭代次数Tmax为200次,之后BP算法再对神经网络训练10 000次。在[0,1]之间随机产生2 200个样本,其中200个作为训练样本,2 000个作为测试样本。为消除算法的随机性,通过5次仿真实验,结果如表2所示。

通过表1和表2的结果,可以看到该算法在训练权阈值的同时可以确定出网络的结构,即确定出网络的隐含层的节点数,避免了重复性的来试凑隐含层的节点数,节省了大量的实验时间,同时训练误差和测试误差都可以达到较高的精度,与参考文献[10]相比,本文预测的结果较好。

4 结语

本文通过十进制粒子群优化算法(DePSO)和二进制粒子群优化算法(BiPSO)同时来优化神经网络的权阈值和结构,并通过函数拟合数值实验来进行验证,结果较好。这一方法避免了重复性的试凑隐含层节点数,为隐含层节点数的确定给出了一种可行的优化方法,时间短、精度高。

摘要：针对BP神经网络初始权阈值确定的随机性和隐含层节点数的不确定性,通过利用十进制粒子群优化算法(DePSO)和二进制粒子群优化算法(BiPSO),同时优化神经网络的初始权阈值和结构。通过粒子群优化算法首先确定一个较好的搜索空间,然后在这个解空间里利用BP算法对网络进行训练和学习,搜索出最优解。通过函数拟合数值实验对该模型来进行训练和测试,相比其他算法,该模型可以获得较高的预测精度,结果表明该方法是可行的。

关键词：粒子群,神经网络,隐含层节点数,函数拟合

参考文献

[1]田旭光,宋彤,刘宇新.结合遗传算法优化BP神经网络的结构和参数[J].计算机应用与软件,2004,21(6):69-71.

[2]魏志成,杨联祥,周激流.遗传算法优化神经网络拓扑结构和权值[J].广西师范大学学报,2003,21(1):62-65.

[3]周辉仁,郑丕谔,牛D,等.基于递阶算法和BP网络的模式分类方法[J].系统仿真学报,2009,21(8):2243-2247.

[4]宁东方,章卫国,田娜.基于改进粒子群优化算法的神经网络设计[J].计算机应用研究,2008,25(11):3343-3345.

[5]王慧,刘希玉.基于最具影响粒子群优化的BP神经网络训练[J].计算机工程与应用,2007,43(18):69-71.

[6]唐贤伦,庄陵,李银国,等.混合粒子群优化算法优化前向神经网络结构和参数[J].计算机应用研究,2007,24(12):91-93.

[7]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008.

[8]SESTITO S,DILLON T.Knowledge acquisition of conjunctiverules using multilayered neural networks[J].InternationalJournal of Intelligent Systems,1993,8(7):779-805.

[9]高鹰,谢胜利.混沌粒子群优化算法[J].计算机科学,2004,31(8):13-15.

粒子群优化算法研究 第8篇

无线传感器定位可分为基于测距的定位算法和无需测距的定位算法,其主要区别在于是否需要距离信息。基于测距的定位算法中节点需使用测距技术获得距离信息,优点是定位精度高但需要额外的硬件设备,常用的测距技术有接收信号强度RSSI、信号到达时间TOA、信号到达时间差TDOA及信号到达角度AOA等; 无需测距的定位算法仅依靠相邻节点间的连通关系进行定位,无需基础网络设施的支持,但定位精度较低［4］。

传统的节点定位算法常采用最小二乘法求解非线性方程组,很容易受到测距误差的影响。为了进一步提高定位精度,笔者将自适应策略引入到粒子群优化节点定位算法中,有效地克服了粒子群优化( Particle Swarm Optimization,PSO) 算法容易产生种群的趋同效应,出现早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题。

1 粒子群优化算法

粒子群优化( Particle Swarm Optimization,PSO) 算法是由Kennedy和Eberhart在1995 年提出的。PSO算法是一种模拟鸟群迁徙和觅食行为的群体智能全局随机优化计算方法,通过种群中个体间的竞争与协调,搜索复杂空间的最优解。PSO算法将种群中的每个个体看成一个质量和体积都为零的粒子,粒子根据自身历史最优位置和种群历史最优位置不断更新自身的速度和位置,从而实现进化［5］。

在PSO算法中,种群中共有N个粒子,每个粒子可以看成优化问题在D维搜索空间的一个潜在解。每一个粒子都有一个由目标函数决定的适应度值,该值的大小决定了粒子的优劣程度。通过所有粒子的适应度值可以判定出每个粒子的自身最佳位置和全局最佳位置,同时每个粒子还有一个决定其飞行方向和距离的速度。所有的粒子以一定的规则在搜索空间中搜索最优解。每次迭代时,粒子通过局部极值和全局极值来更新自己的信息。局部极值就是粒子本身到目前为止所找到的最优位置,而全局极值就是整个种群到目前为止所找到的最优位置。假设一个种群有N个粒子随机地分布在D维搜索空间中,其中第i个粒子在搜索空间中的位置向量可表示为:

第i个粒子的飞行速度向量可表示为:

第i个粒子到目前为止搜索的局部极值表示为:

整个种群的全局极值可表示为:

每个粒子按如下公式更新自己的速度向量和位置向量:

式中c1、c2———加速因子,根据经验通常都取2;

k ———迭代次数;

rand( ) ———在( 0,1) 范围内的随机数;

ω ———惯性权重。

式( 5) 右边可分为3 个部分,第一部分称为“惯性部分”,反映粒子维持先前速度的程度; 第二部称为“认知部分”,反映粒子本身历史最佳位置对现在的影响; 第三部分称为“社会部分”,反映种群对粒子的影响,粒子有向全局最佳位置靠拢的趋势。为了防止粒子飞出搜索空间,通常对粒子的速度进行一定的限制。

在PSO算法中存在粒子向种群全局历史最佳位置和自身局部历史最佳位置聚集时容易产生种群趋同效应的现象,并导致早熟收敛、易陷入局部极值、在搜索后期停滞不前而导致种群的优化性能不佳的问题,同时,PSO算法的优化性能还依赖于参数的取值情况。为克服这些不足,文献[6]提出了用指数变化的惯性权重取值方法来优化复杂的非线性方程组,笔者在此基础上进一步简化算法,提出了一种基于自适应策略的粒子群优化节点定位算法,该算法从惯性权重和全局最优位置两个方面对原有的PSO算法进行改进,实现了在不增加额外硬件的条件下对无线传感器网络节点定位在定位精度和计算耗时上的进一步优化。

2 自适应策略

笔者提出的基于自适应策略的改进算法主要包括两个方面: 一是惯性权重的自适应取值方法;二是从适应度值进行改进的全局最优位置的自适应变异操作。

2. 1 惯性权重的自适应取值方法

惯性权重 ω 是PSO算法中最重要的改进参数,其反映了粒子先前的飞行速度对现在值的影响。当其取值较大时,全局搜索能力强,收敛速度快,但缺点是得到的解精度不够; 当取值较小时,局部搜索能力强、得到的解的精度高,但存在收敛速度较慢且可能陷入局部极值的缺点。合适的 ω值能够平衡算法的全局搜索能力和局部搜索能力,从而得到最佳的优化解。

笔者提出的自适应的惯性权重取值方法,其设计思想主要有两个过程: 在定位算法迭代前期ω 取较大值,实现快速收敛到最优解附近,后期则取较小值求高精度解; 同时该算法在适应度值越大时全局搜索能力越高,从而加快向全局最优位置的聚集速度,粒子适应度值较小时局部搜索能力越高,从而得到高精度的解。笔者提出的惯性权重的自适应取值公式如下:

其中当 ω2> ω1时,一般取 ω1= 0. 3、ω2=0. 8,T为当前迭代次数,Tmax为最大迭代次数。为了防止 ω( i) 在迭代后期取值过小,笔者对 ω( i)的值设置了下限0. 2,当 ω ( i) 低于下限值时ω( i) = 0. 2。f( i) 为第i个粒子的适应度值,fmax、fmin为所有种群中粒子适应度值的最大值和最小值,相应的粒子速度更新公式变为下式:

2. 2 全局最优位置的自适应变异操作

粒子的适应度值可以反映粒子当前位置的优劣程度,把种群所有粒子的当前适应度值看作一个样本,这个样本的方差就可以用来定量描述整个种群的聚集程度。种群越密集,表明整个种群的群居搜索能力变差,此时就需要对全局最优位置进行变异操作,保证整个种群能跳出当前的搜索区域。粒子群的种群适应度值方差 δ2的计算公式为:

其中favg为种群中所有粒子适应度值的平均值; F为归一化因子,通常F = max ( 1,| f( i) -favg| ) 。其全局最优位置发生变异的概率计算公式如下:

其中pmax、pmin分别为gbest进行变异操作概率的最大值和最小值,通常取pmax= 0. 4,pmin= 0. 3。全局最优位置变异操作的公式为:

通过增加一个随机扰动来对gbest进行变异操作,其中gbest_k是gbest的第k维分量。

2. 3 基于自适应策略的节点定位流程

假设未知节点K( x,y) 有3 个以上的邻居连通锚节点Ki( xi,yi) ,其中i = 1,2,…,n。采用RS-SI测距方法测得未知节点到锚节点的距离为di。另,距离其中( x',y') 为未知节点的估计位置。定义适应度值函数为:

其值越小,对该点的定位就越精确。节点定位的具体流程如下:

a. 在搜索空间( 目标区域) 随机部署一定数目的锚节点和未知节点,节点启动后锚节点以周期T向相邻节点发送自己的信息( 主要包括节点ID、位置信息) ;

b. 未知节点根据邻居连通锚节点的相关信息和RSSI模型公式计算出自身到锚节点间的距离;

c. 存在邻居连通锚节点的未知节点在自身处运行笔者改进后的PSO算法,计算自身定位结果。

3 实验仿真

在MATLAB R2008a中对基于自适应策略的粒子群优化节点定位算法的性能进行验证,并与常用的极大似然估计( Maximum Likelihood,ML)进行对比分析。

在本实验中,假设无线传感器节点部署在100m × 100m的二维平面区域中,在此区域内随机分布5 个传感器节点,其中4 个为锚节点,其坐标分别为A ( 22. 23,48. 64) 、B ( 62. 48,2. 46) 、C( 44. 60,80. 42) 、D( 85. 22,70. 48 ) ,未知节点的实际坐标为E( 82. 24,46. 32) 。

基于自适应策略的粒子群优化定位算法中的参数设置为: ω1= 0. 3、ω2= 0. 8,pmax= 0. 4,pmin=0. 3,ω ( i)min= 0. 2,c1= c2= 2。种群粒子总数大小N = 30,总的迭代次数T = 100,粒子每维最大位置为100m,最大速度为10m/s。为了减少实验中随机误差的干扰,进行100 次定位实验得到最终的实验数据。在无线传感器节点定位过程中,测距误差直接决定着定位的进度和稳定度。因此,本实验以测距误差作为实验的前提条件,在不同测距误差的条件下比较ML算法和笔者算法的性能优劣。在引入相同测距误差的条件下,分别对两种算法做100 次的定位运算,并在不同测距误差的情况下,重复进行上述定位运算。两种算法定位结果分别见表1、2。

图1、2 分别反映了测距误差对平均定位误差和定位方差的影响,图3 为适应度值与迭代次数的关系。

通过实验数据可以得到:

a. 从图1 可看出,在给定的5 种测距误差条件下,笔者算法的平均定位误差要比ML算法小,说明该算法的定位精度要高于ML算法的。从图2 可以看出,笔者算法的定位方差要比ML算法小,说明该算法的稳定性要高于ML算法的。

b. 从图1、2 可以进一步发现,当系统测距误差较小时,两种定位算法的性能相差无几,但随着距离误差变大,笔者算法的优良定位性能就凸显出来,说明该算法在一定程度上可以减轻测距误差对定位精度的影响。

c. 图3 是笔者算法在测距误差为5% 时的一次定位过程,从图中可以看出算法在迭代不到10 次时就可以收敛到一个精度较高的优化解,收敛速度较快,能耗较低,适合应用在对能耗有较高要求的无线定位系统中。

4 结束语

粒子群优化算法研究 第9篇

针对上述问题,提出了基于粒子群改进的WCPSO算法。通过将惯性权重线性递减策略与动态加速常数自适应策略加入到PSO算法中,有效地提高了算法的寻优精度和收敛速度,对三维空间传感器的优化部署问题具有重要意义。

1 WCPSO算法的数学模型和改进策略

1.1 WCPSO算法的数学模型

在WCPSO算法中,将个体粒子视为n维空间中无体积和重量的粒子,并以一定的速度飞行在空间中[7,8],粒子的飞行速度可根据群体经验和自身经验进行更新。以Xi=(xi1,xi2,⋯,xin)表示粒子的当前位置,以Vi=(vi1,vi2,⋯,vin)表示粒子当前的飞行速度,以Pi=(pi1,pi2,⋯,pin)表示粒子i的历史最优位置,以Pg=(pg1,pg2,⋯,pgn)表示群体的历史最优位置,以pbest表示粒子在所有搜索过程中能够达到的最优解,以gbest表示全部粒子在所有搜索过程中能够达到的最优解。各个粒子可根据群体历史最优位置和自身的历史最优位置更新自身的位置和速度,则带惯性权重的WCPSO优化算法的进化方程如式(1),式(2)所示:

式中:i代表第i个粒子;j代表粒子的第j维;t代表第t次迭代;w代表惯性权重;c1和c2代表加速常数,一般在0~2区间内取值;r1和r2表示[0,1]区间内两个相互独立的随机数。从式(1),式(2)中可以看出,惯性权重w,加速常数c1和c2会对WCPSO算法的性能产生主要影响。其中,惯性权重w使粒子维持运动惯性,以便粒子能够探索新区域;加速常数c1改变粒子飞向自身最优位置的步长,加速常数c2改变粒子飞向全局最优位置的步长。在各步迭代过程中,全部粒子都依据进化方程式(1)和式(2)更新自身的位置和速度。为了抑制粒子无规律的跳动,将vij限定在-vmax和vmax之间,若整个探测空间为[-xmax,xmax],则vmax=k·xmax,。

对于来袭路径未知和来袭路径能够预估的最大化问题,粒子i当前最优位置的确定如式(3)所示:

设粒子的总数量为m,在第t次迭代过程中,全部粒子所经过的最优位置Pg(t)如下:

从式(3),式(4)中可以看出,在整个求解过程中,惯性权重w、加速常数c1和c2共同平衡粒子对局部和全局的搜索能力。

1.2 WCPSO算法的改进策略

1.2.1 惯性权重线性递减策略

为了平衡算法局部和全局的寻优能力,并保证算法的收敛速度,通过使用惯性权重线性递减策略来改变惯性权重w对速度的影响。该策略能够确保算法开始时,粒子可以在全局搜索范围内以比较大的步长搜索到较好的位置,然后各粒子在极点四周范围内进行较为精细的搜索,从而保证算法能够以比较大的概率收敛于全局最优解处,具体策略如下:

式中:wmin和wmax分别表示惯性权重的最小值和最大值;t表示目前进化代数;tmax表示最大进化代数。此处选择惯性权重w从0.9逐步线性递减至0.4。

1.2.2 动态加速常数自适应策略

固定的加速常数不利于粒子指向自身或邻域最优位置运动的控制,通过使用动态加速常数自适应策略来提高算法的性能。在优化前期,该策略使粒子在整个搜索空间内移动,而在优化后期,可以增强粒子收敛于最优解的概率。该改进策略加速常数c1和c2随进化代数进行调整,具体如下:

式中:R1,R2,R3和R4表示初始设定的常数;t表示当前进化代数;tmax表示最大进化代数。通过改变初始常数R1,R2,R3和R4的值能够对c1和c2进行调节。此处c1随着进化代数t从R1线性增加至R1+R2,c1随着进化代数t从R3线性增加至R3-R4,从而保证算法具有较好的寻优精度和效率。

2 WCPSO算法设计

2.1 粒子位置生成

空间中的一个粒子就能够代表一种传感器位置的布置方案,所以各粒子的位置向量X可由全部传感器的位置(一组三维位置坐标)表示,具体如下:

式中:{xi,yi,zi}(i=1,2,⋯,N)表示第i个传感器的位置坐标,具体取值范围由传感器网络布置空间的大小和约束条件确定。

2.2 优化目标函数

对于确定的探测空间,在传感器数量给定的情况下,传感器的三维部署优化问题共分为两种情况,具体如下:

来袭路径未知,覆盖范围最大:优化的目标要求F(X)最大,F(X)的具体表达式如下所示:

式中:H为探测空间高度的分层数量;wl为各高度层权重系数;λl,σl,θl和ρl分别为第l个高度层上探测网络的资源利用系数、空间重叠覆盖系数、探测区域覆盖系数和高探测概率覆盖系数。此处K1,K2,K3和K4均为0.25。

来袭路径能够预估,探测概率最大:优化目标要求F(X)最大,F(X)的具体形式如下:

式中:M为目标可能来袭的的路径数目;j为目标各袭击路径的权重系数,各袭击路径的权重系数βj的总和为1。

2.3 粒子种群初始化

取WCPSO算法的粒子总数为m,对种群中的粒子i(i=1,2,…,m)随机初始其位置和速度,然后计算各粒子的适应度并将粒子的初始适应度值设置为最优适应度值pbest,同时将粒子初始位置设置为粒子的最优位置。最后将粒子适应度的最优值作为粒子群体的最优适应度gbest,最优适应度值粒子位置设置为群体最优位置。

2.4 单次优化准则

对于上述的两种最大化问题,粒子I的最优位置由式(10)确定,具体如下:

在第t次迭代过程中,全局最优位置Pg(t)由式(11)确定,具体如下:

2.5 参数更新策略

WCPSO算法使用惯性权重线性递减策略和动态加速常数自适应策略。在优化之前,首先设定好wmax,wmin,R1,R2,R3和R4的值。在第t次迭代过程中,按照式(5),式(6)更新各粒子的惯性权重和加速常数,从而完成对粒子位置和速度的更新。

2.6 粒子速度和位置更新

各粒子依据群体历史最优位置和自身的历史最优位置更新自身的位置和速度,具体如下:

式中:I为第I(I=1,2,⋯,m)个粒子;J为第J(J=1,2,⋯,n)维;为迭代次数;r1J和r2J为[0,1]区间内相互独立的随机数。

2.7 算法执行流程

WCPSO算法优化三维空间传感器网络的部署问题的具体步骤如下:

(1)各粒子位置和速度的初始化,各粒子的位置为一组传感器的三维坐标序列;

(2)依据式(10)确定各粒子的最优位置PI,根据式(11)确定当前的群体最优位置Pg;

(3)将各粒子的最优位置pbest值与全局最优位置gbest值比较,若pbest好于gbest,令Pg=PI;

(4)执行参数更新策略,按照式(5),式(6)计算各粒子的惯性权重w、加速常数c1和c2;

(5)按照式(10),式(11)对各粒子的速度Vi和位置Xi进行更新,同时对各粒子的位置和速度进行检查,防止其越界;

(6)判断是否达到最大迭代次数tmax,若达到最大值,则迭代完成,转入步骤(7),否则继续执行步骤(2);

(7)输出探测能力函数和传感器网络优化后的部署方案。

算法的具体流程如图1所示。

3 实验仿真

根据如图1所示的WCPSO算法的流程图,使用Matlab按照算法功能划分为主控模块、初始化模块、优化计算模块和方案生成模块四个模块,各模块的功能如下:

主控模块:用于整个仿真程序的开始、运行、暂停和终止,该模块使用Matlab的Command Window进行人机交互。

初始化模块:处于主控模块的控制下,帮助实验用户完成数学模型和计算参数的设定,同时将各参数传送到优化计算模块。

优化计算模块:处于主控模块的控制下,接收初始化模块传送来的模型和参数,然后根据设计的动态加速常数协同惯性权重的粒子群优化算法WCPSO进行迭代计算,直到完成迭代将优化方案发送至方案生成模块。

方案生成模块:处于主控模块的控制下,将接收到的优化计算模块传送来的结果生成传感器优化部署方案,并通过三维效果图来完成方案的分析和展现。

3.1 实验仿真一

针对来袭路径未知,覆盖范围最大的空间传感器布置优化问题,假设传感器的探测范围为空间中的球,球体内各点处的探测概率相等、球体外探测概率为0。

实验共设置6个传感器,其探测半径分别设置为20 km,25 km,25 km,35 km,35 km和40 km。传感器网络的探测空间设为100 km×100 km×100 km,高度方向共划分为20 km,50 km和80 km三个高度层,各层权重大小为0.35,0.45和0.20。实验中取λl,σl,θl和ρl系数的初始大小依次为0.20,0.20,0.20和0.40。种群规模大小为5,粒子的维数为22,粒子的位置、速度在1~100范围内取值,最大迭代次数tmax设置为1 200并作为迭代终止条件。

对随机初始状态、PSO优化和WCPSO优化的目标函数值结果如表1所示。

从表1中可以看出,使用WCPSO算法优化传感器部署能显著提高传感器网络探测性能,综合加权指标值由0.671 4增大到0.770 4,且大于PSO算法的优化结果0.754 1。说明本文所提出的基于粒子群的WCPSO优化算法较PSO算法部署的传感器网络的探测性能有了较大的提高。

不同高度层上传感器网络的截面图如图2~图4所示。

从图4中可以看出,使用本文WCPSO算法进行优化的传感器网络的探测范围更大,传感器的利用率也更高,覆盖重叠区域也更加合理。

3.2 实验仿真二

针对来袭路径可预估,综合探测概率最大的空间传感器布置优化问题,实验共设置6个传感器,其探测半径分别设置为20 km,25 km,25 km,30 km,30 km和40 km。其中,前3个传感器探测范围为圆锥形,探测半径表示的是底面圆半径,而探测圆锥的高度均取40 km,传感器网络的探测空间设为100 km×100 km×100 km。预估的来袭路径共有3条,在3条来袭路径上分别取5个点进行离散化处理,处理结果如图5所示。

Path 1,Path 2和Path 3三条路径的权重分别设置为0.4,0.3和0.3。各路径上5个离散点的权重分别设为0.15,0.1,0.3,0.25和0.2。种群规模大小设为5,粒子的维数为22,粒子的位置和速度可在约束范围内随机取值,最大迭代次数tmax设置为3 000并作为迭代终止条件。

对随机初始状态、PSO优化和WCPSO优化的目标函数值结果如表2所示。

从表2中可以看出,使用WCPSO算法对传感器网络部署优化后,明显提高了传感器网络对三条预估路径的整体探测概率,由随机初始状态下的0.512 0增加到了0.724 3,且好于PSO优化算法的结果0.572 7。因此对于来袭路径可预估,综合探测概率最大的传感器网络部署优化问题,WCPSO算法的优化部署方案明显优于PSO算法的方案,对传感器网络目标探测系统的整体性能有较大的提升。

3.3 实验结论

从实验一和实验二的结果可以看出,本文对PSO算法进行改进后的基于粒子群的WCPSO算法,对三维空间传感器网络的部署优化的效果和算法效率均优于改进前的PSO算法,证明了本文算法改进的有效性。

4 结论

针对三维空间传感器网络的优化部署问题,本文提出了通过使用惯性权重线性递减策略与动态加速常数自适应策略的基于粒子群优化的WCPSO算法,有效地提高了PSO算法的寻优精度和收敛速度。并给出WCP-SO算法的设计方案和执行流程,最后对两种典型问题进行了仿真,证明了所提出算法的有效性,对今后三维空间传感器网络的优化部署具有重要意义。

摘要：针对目前三维空间传感器部署算法PSO算法存在寻优精度、全局收敛性和收敛速度不能保证的问题,提出了通过惯性权重线性递减策略与动态加速常数自适应策略改进的基于粒子群的WCPSO优化算法,有效地提高了算法的寻优精度和收敛速度。给出了算法的设计方案并进行了来袭路径未知和来袭路径预估情况下的仿真实验,仿真实验结果表明WCPSO算法的优化效果和效率都要优于改进前的PSO算法。

关键词：粒子群优化算法,部署优化,传感器网络,WCPSO算法

参考文献

[1]POLI R,KENNEDY J,BLACKWELL T.Particle swarm optimization:an overview[J].Swarm intelligence,2013,1(1):33-57.

[2]HUANG Husheng,XIONG Jiajun,YANG Longpo.Optimized disposition of radar netting based on genetic algorithm[J].Journal of air force radar academy,2008,22(4):250-252.

[3]唐志华.基于临近空间的目标探测及宽带通信[J].无线电工程,2007(11):28-30.

[4]白雁.基于线性递减系数粒子群优化算法的组卷实现[J].现代电子技术,2014,37(24):41-44.

[5]尚学刚,戴幻尧,李永祯,等.探测临近空间飞行器的天基雷达系统设计[J].舰船电子对抗,2011,34(2):55-59.

[6]PERRY R P,DIPIETRO R C,FANTE R L.SAR imaging of moving targets[J].IEEE transactions on aerospace and electronic systems,1999,35(1):188-200.

[7]袁浩.基于改进蜂群算法无线传感器感知节点部署优化[J].计算机应用研究,2010(7):2704-2705.

粒子群优化算法研究 第10篇

随着电力体制改革的不断深入和电力市场的逐步开放,电力系统的安全性和经济性越来越受到人们的重视。在电力系统中,无功功率对电压损失影响较大,无功功率的合理分布可以有效改善电压质量,降低网损,提高电网的安全性和经济性。电力系统无功优化就是在当前电网运行状况下,在满足各种安全约束的前提下,确定一种最优的无功功率分布方案,使得电网的1个或多个指标性能达到最优。

传统的无功优化大多只考虑有功网损最小、电压偏移量最小或是将二者结合起来。这些模型均欠缺对电压稳定性以及无功投资成本的考虑。另外,传统的无功优化方法在考虑多个目标时均会通过加权等手段将其处理成单目标优化问题,具有很大的局限性。本文针对传统无功优化的不足,将电压稳定性和无功投资成本也加入了优化目标函数的行列,建立了以电网有功损耗最小、节点电压偏移最小、静态电压稳定性最好和无功成本最小的多目标无功优化模型。在求解模型中,本文应用基于Pareto解的多目标混沌粒子群算法将这4个目标同时进行优化,得到1组Pareto支配概念下的最优解。应用该方法对IEEE30节点系统进行了仿真分析,得到了良好的结果。

1 多目标无功优化模型

电力系统无功优化[1,2,3]中的控制变量主要有发电机的机端电压幅值、可调变压器的变比和各种无功补偿设备的补偿容量。而状态变量则有可调发电机的无功出力和系统内各母线电压的幅值。

1.1 目标函数

电力系统无功优化的目标函数有很多,主要有以下几种:1)系统的有功网损最小;2)系统的节点电压总偏移最小;3)无功补偿成本最小;4)静态电压稳定性最好;5)系统总的费用最小;6)补偿设备[4]的动作次数最少。

本文在综合考虑上述几个指标的基础上,结合电力系统目前的实际情况,在电力系统有功调度一定的情况下,建立以系统的有功损耗最小、电压质量最好、静态电压稳定性最好和无功补偿成本[5,6,7]最小的多目标函数。其表达式为:

其中各个子目标函数的具体表达式如下:

(1)有功网损最小

式中:Pg是系统内处于运行状态发电机发出的总的有功功率;pd是系统内所有负荷的总有功功率。其中f1>0。

(2)节点电压偏移最小

式中:Vi为负荷节点i的实际电压:为期望电压值,且;为最大电压偏差,其中;n为系统负荷节点数。

(3)无功成本最小[8]

式中:Bi为母线节点i的补偿容量,MVar;Bm为补偿容量的最大值,MVar;α为并联电容器的单位补偿成本;β为电抗器的单位补偿成本;n为系统内需要加装补偿设备的节点数。

(4)电压稳定性最好(FVSI指标和最小)

本文的静态电压稳定性采用的是快速电压稳定指标,即FVSI指标[9]。当系统内所有的FVSI指标和最小时,系统的电压稳定性最好。

式中:NL为系统内支路数;Vi为第k条支路的首端节点电压;Vj为第k条支路的末端节点电压。

1.2 约束条件

在本文的无功优化模型中,节点的有功和无功约束如下:

式中:PGi、QGi分别为发电机节点的有功功率和无功功率;PDi、PGi、QGi分别为负荷节点的有功负荷、无功负荷和无功补偿的功率;Cij、Bij分别为节点i和j之间的电导和电纳。

无功优化模型的不等式约束可分为状态变量的约束和控制变量的约束。其中,发电机的无功出力和各节点的母线电压的约束视为状态变量的约束;而发电机的机端电压、无功补偿设备的补偿容量以及可调变压器的变比等的约束则为控制变量的约束。其具体表达式为:

式中:NPV为可调发电机的节点个数;VG为可调无功出力的发电机个数;VT为可调分接头的变压器个数;NL无功补偿点的个数;NPQ为PQ节点的个数。

2 基于Pareto解的混沌粒子群算法

2.1 改进的混沌粒子群算法

基本粒子群算法[10]在进化后期极易陷入局部最优解而过早收敛,所以本文引入了一种新的学习策略,即全面学习策略[11]。该策略利用所有粒子的历史最好信息来更新粒子的速度,即粒子群向全局最好位置gbest、粒子群的自身最好位置pbest和其他粒子的pbest学习。假设粒子的位置和速度是n维向量,其中m维向gbest习,剩下的n-m维要么向随机选择的粒子的pbest学习,要么向粒子本身的pbest学习。则全面学习粒子群算法公式如下:

式中:vid表示第i个粒子速度的第d维分量;wk表示第k次迭代的惯性权重;rand 0表示1个0到1间的随机数;xid示第i个粒子位置的第d维分量;gbestd表示全局最优位置的第d维分量;pbestfd表示第fi个粒子个体最优位置的第d维分量;pbestid表示第i个粒子个体最优位置的第d维分量。

混沌具有随机性和遍历性,将其用于优化具有天然的优势。本文应用混沌初始化粒子群算法中的初始种群。其中用到的是Logistic混沌系统[12],其方程为:

式中:zn为买值序列;μ为参数,当μ=3.571 448时,Logistic映射开始进入混沌状态,研究表明,当3.571 448μ4时,该混沌映射处于混沌状态,将3.571 448μ4定义为混沌区域,给定1个初值z0,由Logistic映射生成序列为{zk|k=0,1,2,3,},其具有混沌序列特性。

采用混沌系统初始化粒子的位置和速度,既没有改变粒子群优化算法初始化粒子群时的随机化本质,又利用混沌提高了粒子群的多样性和搜索的遍历性[13]。由混沌产生大量初始群体的样本后,根据适应度最优的原则择优选出初始群体。

2.2 多目标优化问题

多目标优化是科学研究和工程应用上十分重要的研究课题,多目标优化问题的最优解不同于单目标的优化,它们一般均有多个最优解。如何从多个最优解中找出人们需要的解,怎样构造1个多目标优化问题的最优解集,如何评价各种构造最优解集方法的好坏等问题均需要人们进行更为深入的研究。

多目标优化问题[14,15](Multi-objective Optimization Problem,MOP)可以定义如下。

定义1:一般MOP由n个决策变量、M个目标函数和K种约束条件组成,最优化目标如下:

其中:x=(x1,x2,,xn)∈D为决策变量;y=(f1,f2,,fM)∈Y表示目标向量;D为决策向量形成的决策空间;Y表示目标向量形成的目标空间。

定义2:Pareto支配相关概念

(1)Pareto支配

解x0支配x1(x0>x1)当且仅当fi(x0)fi(x1),i=1,2,M,fi(x0)

(2)Pareto最优

如果解x0是Pareto最优的当且仅当。

(3)Pareto最优集

所有Pareto最优解的集合。

(4)Pareto最优前端或均衡面或Pareto前端

所有Pareto最优解对应的目标函数值所形成的区域:

2.3 多目标混沌粒子群算法

本文在基本粒子群算法中引入了全面学习策略和混沌优化,然后将其应用到多目标优化问题的求解中,得到了基于Pareto最优概念的多目标混沌粒子群算法(MOCPSO)。其主要思想是:构造非支配集,维护外部精英档案,使得档案中的非支配解不断逼近Pareto最优集,最终达到优化目的。其具体方法如下:

(1)用擂台赛算法构造非支解集

当用擂台赛算法[14]构造1个进化群体的Pareto最优解集时,每次搜索新的非支配个体时不需要与已有的非支配个体进行比较,每一轮比较时在构造集中选出1个个体出任擂台主(一般为当前构造集的第一个个体),由擂台主与构造集中的其它个体进行比较,将被该擂台主所支配的个体删除,将支配该擂台主的个体作为新的擂台主,并继续该轮比较;一轮比较结束后,最后的擂台主个体就是非支配个体。按照这种办法进行下一轮的比较,直至构造集中的个体为零。

擂台赛算法的具体构造方法为:设P为1进化群体,Q为构造集,初始时Q=P;NDSet为非支配集,初始时为空集。从Q中任取1个个体x,依次与Q中的所有其它个体y进行比较,如果x支配y,则将个体y从Q中删除;如果y支配x,此时y成了新的擂台主,并继续该轮比较。一轮比较结束后,将最终的擂台主加入到NDSet中。继续进行下一轮比较,真至构造集Q为空集。

(2)用拥挤距离法维护精英档案[15]

精英档案用来保留算法在进化过程获得的非劣解,其更新策略为:对于每个新解,如果该解被某个档案成员所支配,则拒绝该解存入档案中;如果该解支配了某些档案成员,则删除那些被支配的成员,同时将该解存入档案中;如果该解和档案中的所有成员彼此不受支配,则将该解存入档案中。当档案大小超过或达到规定的最大规模时,计算所在档案成员的拥挤距离,并从大到小排序,保留其中拥挤距离最大的个档案成员,其他成员从档案中剔除[7]。

1个个体的拥挤距离是通过计算与其相邻的2个个体在每个子目标上的距离差之和求得的。如图1所示,设有2个子目标f1和f2,个体i的拥挤距离是图1中实线矩形的长与宽之和。设P[i]distance为个体i的拥挤距离,P[i].m为个体i在子目标m上的函数值,则图1中个体i的拥挤距离为:

P[i]distance=(P[i+1]:f1-P[i-1]:f1)+(P[i+1]:f2-P[i-1]:f2)(11)

在一般情况下,当有r个子目标时个体的拥挤距离为:

计算种群中每一个体的拥挤距离时,需要对该群体按每个子目标的函数值进行排序,排序后第一个个体和最后1个个体的拥挤距离均为无穷大。

3 MOCPSO算法在无功优化中的应用

3.1 粒子的编码

无功优化模型中的控制变量有可调发电机的机端电压、可调变压器的变比、无功补偿设备的补偿容量。其中可调发电机的机端电压用实数编码,而可调变压器的变比、无功补偿设备的补偿容量是离散变量,用整数编码[16]。

对于可调变压器变比Ti,其对应的变压器分接头档位为Bi。则可调变压器的变比Ti与分接头档位Bi的关系为Ti=1+ΔTiBi,其中ΔTi为级电压。对于无功补偿设备的补偿容量Qc,定义1个与之对应的补偿设备投切组数Dc,其为一连续整型变量。则补偿容量与投切组数的关系为Qc=Dcab,其中,a为无功补偿装置单组的容量,如前述的2 Mvar;b为补偿设备性质判别,b=1时为电容器补偿,b=-1时为电抗器补偿。通过上述公式,离散的可调变压器变比Ti可以转化为连续的整型变量分接头档位Bi;离散的无功补偿容量Qc转化为连续的整型变量投切组数Dc。

按上述方法,在本文提出的MOCPSO算法粒子编码中,将可调发电机的机端电压VG、可调节变压器的变比Ti和无功补偿设备容量Qc等这3种控制变量作为1个粒子的片段,每一种控制变量均限制在其取值范围之内。其中VG用实数进行编码,则变比Ti和Qc通过前述的映射采用整数进行编码。则粒子x的编码格式如下式:

与粒子的位置相对应的是粒子速度Vid,粒子的速度编码格式与粒子的位置相同,所不同的是要对其速度大小进行限制,则粒子的最大速度为:

由式(13)则可求出粒子的最大限速,其中a为比例因子。粒子的每一维速度范围为[-Vmax,Vmax]。

3.2 约束条件的处理

对于潮流平衡的等式约束式,在计算中,如果潮流收敛,则此等式自然满足,所以不用单独考虑。对于控制变量约束,只需要将其限制在取值范围内即可,因此也能满足。真正需要考虑的是状态变量的约束条件,本文将状态变量的约束转化为1个罚函数,并将其作为1个目标加入到无功优化的目标函数中。

式中:λ1和λ2为节点电压越限罚因子和无功越限罚因子;Uilim和Qilim分别定义为:

则本文最终的多目标无功优化模型为:

3.3 计算流程

(1)读入算法所必须的原始数据。包括电力系统的所有原始数据、粒子群算法的学习因子、惯性因子、最大迭代次数、外部档案规模、粒子个数、粒子维数及惩罚因子等。

(2)混沌初始化粒子群个体。即先利用Logistic方程产生N个n维的粒子位置xi,然后再将其载波到各个优化变量的取值范围之内,同时产生粒子的速

(3)计算各个粒子的每个目标的适应度值,择优选择M个粒子作为初始粒子群体,M为种群粒子个数。由于多个目标有多种适应度值,所以本文以有功网损为参考标准,选出M个有功网损较优的个体作为初始粒子群体。

(4)初始群体确定后,应用牛顿拉夫逊法进行电力系统潮流计算得出各个目标适应度值,然后根据Pareto支配关系,应用擂台赛算法找出这些适应度值非支配个体,形成初始外部档案,同时从外部档案中选出当前粒子群的全局最优位置gbest,接着选出每个粒子的个体最优位置pbest。

(5)更新每个粒子的速度vi和位置xi。其中每隔10代,粒子群采用全面学习策略,若不足10代则根据常规策略进行更新。在粒子速度和位置的更新过程中,若xi>ximax,则xi=ximax,vi=-vi;若xi

(6)若满足迭代终止条件,则停止迭代,输出最终结果;否则返回步骤(4),即更新外部档案,若更新后外部档案规模大于最大外部档案规模,则应用拥挤距离法进行档案维护,然后选出粒子群新的全局最优位置gbest和个体最优位置pbest,继续进行迭代计算,直到满足终止条件。

4 算例仿真

IEEE-30标准系统接线图见图2,其中包括6台发电机、4台可调变压器、2个无功补偿点。节点1是平衡节点,节点2、8、11、13为PV节点,线路6-9、6-10、4-12、27-28为变压器支路,节点10、24为无功补偿点。系统控制变量和状态变量的约束条件[17,18]见表1和表2。

计算所涉及到的量均为标幺值,功率的基准值为100 Mvar;种群规模为100,外部档案规模为20,加速因子c1和c2均取2,惯性权重的最大值和最小值分别为0.9和0.4;算法中的学习概率为0.4,精英概率为0.7,算法的最大迭代次数为100次;电压和无功越限罚因子分别为2和5,粒子的每维最大速度取其位置取值范围的30%。重复实验20次,最终得出1组Pareto最优解,从20次实验中选出3个出现最频繁的解,分别对应3种优化方案。然后统计其结果并与优化前进行比较。

优化前有9个节点的电压越下限,其中节点26的电压最低,仅为0.939 5 p.u.。节点8的发电机无功越限。同时有功网损和电压偏移均较大,电压稳定性较差。

经过优化后,各个节点的电压均恢复到合格范围之内,发电机的无功越限情况得到了很好的纠正。与此同时,系统的有功网损、电压偏移和电压稳定指标均下降。从表3中可知,3种方案的无功成本与初始状态相比均有所增加,这表明,当优化到一定程度时,必须加装一定的无功补偿设备才能使得网损进一步下降。总的来说,优化后的多个指标均比优化前更优。另外从表3中还可知,算法在进化初期,各个子目标均优于初始状态,但是当到了进化后期时,即当有功网损或是电压偏移降低到一定程度时,网损或电压偏移会随着另一目标的减小而增大,同理电压稳定性指标和无功成本也会出现类似情况。也就是说,当优化到一定程度时,这几个目标变成了相互矛盾的目标。这个现象充分说明了以前无功优化方法的局限性。

在无功优化中,不能只考虑有功网损这1个目标,还需要关注其它目标,如电压偏移、电压稳定、无功成本等、而当考虑多个目标时,传统的方法均是通过加权的方法将多目标转化成单目标进行优化,实际上这种单目标优化的结果仅仅是Pareto边界前沿上的1个运行状态,并不能得到其它的运行状态。而应用本文的方法得到的是Pareto边界上的很多个解,即求出了很多个可行的运行状态,从而给了决策者多样化的选择。如果决策者比较在乎无功投资成本,可以选择方案1;如果决策者更在意电压偏移,可以选择方案2;当然如果决策者更看重系统的电压稳定,可以选择方案3。也就是说,本文的方法给了决策者更多的选择,而不是唯一的选择,决策者可以根据自己经验和偏好或是实际情况做出选择,这正是本文提出的方法的优越性。

4 结论

无功优化在电力系统经济运行中占有十分重要的地位,研究电力系统无功优化问题时还应将电压稳定、无功成本等指标考虑进去。要同时考虑多个目标的无功优化问题时,传统的处理成单目标优化的方法往往具有很大的局限性。本文应用提出的基于Pareto解的多目标混沌粒子群算法对多个目标同时进行优化,最后得到了目标空间的1组Pareto最优解。以IEEE30节点系统作为算例,计算结果表明,基于本文模型的无功优化结果可以降低系统有功网损,提高系统静态电压稳定性并改善电压水平,同时得到的Pareto最优解可以给决策者以多元化的选择参考。

摘要：针对传统无功优化的不足,建立了以电网有功损耗最小、节点电压偏移最小、静态电压稳定性最好和无功成本最小的多目标无功优化模型。为了将这4个目标同时进行优化,提出了基于Pareto解的混沌粒子群算法多目标无功优化方法,求出该多目标优化问题的Pareto最优解集,供决策者根据实际情况进行科学决策选择。为证明提出方法的有效性,对IEEE30节点系统进行了多目标无功优化分析,结果表明本文提出的方法能够得到良好的无功优化结果。

粒子群优化算法研究 第11篇

关键词：粒子群优化算法,量子行为,惯性权重,递减策略,0-1背包问题

粒子群优化(PSO)算法是一种群智能优化算法,最早由Kennedy和Eberhart于1995年共同提出,其基本思想是对鸟群捕食行为的仿生模拟[1],通过鸟群之间的集体协作,快速搜寻并找到最优解。其基本的进化方程如下:

vt+1=vt+c1r1(Pt-xt)+c2r2(Pg-xt) (1)

xt+1=xt+vt+1 (2)

其中,r1,r2∈[0,1]为均匀分布的随机数;C1,C2均是正常数;t表示进化代数;Vt,Xt分别表示每个粒子的速度和位置;Pg,Pt分别是粒子群的全局最优和个体最优。

为了改善基本PSO算法的收敛性能,YShi等人提出了惯性权重的方法[2]和用模糊控制器来动态自适应地改变惯性权重的技术[3]。之后Jun Sun等人提出的具有δ函数形式的粒子群算法[4](QDPSO) 使粒子群算法的计算更加简单容易。最近一种新的QDPSO 算法[5] 考虑了速度对位置的影响,通过速度的更新选择位置的更新方程。在经典粒子群算法的可调整参数中,惯性权重是非常重要的参数,较大的权重有利于提高算法的全局搜索能力,而较小的权重会增强算法的局部搜索能力。因此,对这种新的QDPSO算法的速度项引用惯性权重ω,通过研究4种方案,发现惯性权重ω的变化对具有量子行为的粒子群算法的收敛性具有很大改善。可以说惯性权重的适当设置对新的QDPSO算法性能也起着重要的作用。

1 量子行为的粒子群优化算法及其改进

1.1 QDPSO算法

文献[4]的作者认为,若是在PSO系统下的个体粒子具有量子行为,则该粒子将会以与基本PSO算法中的粒子不同的方式运动。在量子空间,粒子的速度和位置不能再依据“不确定原理”被同时确定,所以提出了QDPSO算法。该算法改变了基本PSO算法的粒子更新策略,只用了粒子的位置向量。QDPSO算法的粒子进化方程如下:

undefined

其中,a,b,u∈[0,1]为均匀分布的随机数;pid是第i个粒子在第d维空间找到的局部最优解,pgd是群体在第d维空间找到的全局最优解;xid表示第i个粒子在第d维空间找到的当前值;而g必须满足条件:undefined,才能保证算法的收敛。

1.2 改进的粒子群算法

新的QDPSO算法利用个体粒子的速度产生一个介于[0,1]之间的数来代替原算法中的由计算机随机产生的数,用以选择该粒子的位置更新方程。更新方程和参数设定参考文献[5]。

本文考虑到惯性权重随粒子的迭代次数变化影响个体粒子的速度引导该粒子向最优解靠拢,所以采用4种方案对该改进算法进行研究。通过使惯性权重随粒子的迭代次数变化,从而影响速度的更新方程:

vt+1=ωvt+c1r1(pt-xt)+c2r2(pg-xt) (6)

其中,采用4种惯性权重ω方案来影响速度的更新,然后与QDPSO算法进行性能比较:

方案1 ω为从(1,0.875)递减的函数ω=1-k0.125/genmax。采用这种方案的QDPSO算法称为w1-QDPSO;

方案2 ω为从(0.9,0.4)递减的函数ω=0.9-k0.5/genmax[6]。采用这种方案的QDPSO算法称为w2-QDPSO;

方案3 ω为一定值0.729 8[7],采用这种方案的QDPSO算法称为w3-QDPSO;

方案4 ω为一凹函数[8]( ωstart-ωend)(t/tmax)2+(ωstart-ωend) (2t/tmax)+ωstart,其中ωstart=0.95,ωend=0.4,tmax为最大的迭代次数。采用这种方案的QDPSO算法称为w4-QDPOS。

综上所述,选择测试函数F1(x)和F2(x)分别为Sphere和Rastrigin(参数设置见文献[4]),改进后的算法流程如下:

Step 1 初始化种群粒子的速度和位置;

Step 2 通过对两个测试函数进行初始化计算,得到每个粒子的当前位置为粒子最佳位置pbest,初始群体粒子位置的最优值为群体最佳位置gbest;

Step 3 重新把粒子的位置代入测试函数进行计算,得到每个粒子新的适应值,将其与pbest比较,若较好,则将pbest设置为新位置;并将其与gbest比较,若较好,则将gbest设置为新位置;

Step 4 根据公式(6)更新粒子的速度;

Step 5 用个体粒子的速度产生用以选择该粒子位置的更新方程的数据:

rand-q=1/(1+|(vmax-vid)/(vid-vmin)|) (7)

Step 6 由Step 5 产生的数据选择更新粒子位置的方程:

if rand-q>0.5

xid=p+L(ln(1/u))

else xid=p-L(ln(1/u))

Step 7 若未达到终止条件(足够小的适应值或预设的最大迭代次数),则返回Step 3。

更新粒子速度时需要注意:如果粒子的速度超出预设的范围,则采取使粒子反向运动的策略,从而保证算法有效进行。

1.3 算法的结果及数据分析

目标函数为F1(x)和F2(x),基本参数是:c1=c2=2.05,g=0.968 5,每种算法都在同一台计算机,同一环境下用Matlab 7.1.0软件运行。结果如表1所示。

表1的数值是对每个函数在粒子数为20个的条件下,测试50次,然后取平均得到的结果。从表中可以看出,对于函数F1(x),比较结果可以明显得知:在随粒子群维数增加的情况下,ω1-QDPSO是比QDPSO得到更好的解,其他几种改进方案的解都比较差;函数F2(x)在随粒子群维数增加的情况下,4种改进方案和QDPSO都能得出比较好的解。

通过实验,可以看出:对于单峰函数F1(x),ω的递减不能太小,从方案ω1-QDPSO和ω2-QDPSO的结果就可以比较出来,而方案ω3-QDPSO和ω4-QDPSO的结果不好,可能是因为它们搜索的区域太小,从而陷入局部最优解。

对于多峰函数F2(x),ω的变化对测试函数的解的精确度没有太大影响,说明了改进方案在此方面没有明显提高。接下来,我们还对算法的收敛速度进行了比较。结果如表2所示。

注:表2中“”表示函数测试50次没有收敛。

表2是对函数测试50次后取得平均值的结果。可见对于函数F1(x),ω1-QDPSO和QDPSO都在10维的情况下收敛,而20维时只有ω1-QDPSO收敛,其他函数都没有收敛,导致这种结果的原因有2种:

(1) 各种方案随ω的变化,削弱或失去了调节能力,在达到最大迭代次数时也未收敛;

(2) 即使在算法已搜索到最优解附近时,由于局部搜索能力太差,跳过了最优解。对于函数F2(x),ω3-QDPSO,ω4-QDPSO,QDPSO收敛速度都比较快,ω1-QDPSO和ω2-QDPSO的收敛速度就相对较慢一些。这是由于对多峰函数测试时,各种方案的初始化范围附近可能存在最优解,所以减少了迭代次数,加快了算法速度。

通过对4种方案的研究,这里选取方案1应用于0-1背包问题,并得到理想的结果。

2 对改进算法应用到0-1背包问题

2.1 0-1背包问题的数学描述

0-1背包问题是一种典型的组合优化问题。0-1背包问题的描述如下:假设有n个物品,其大小和价值分别为wi和ci (其中wi>0,ci >0,i=1,2,,n),背包的容量假设为V(V>0)。要求在背包的容量限制内,使所装物品的总价值最大。该问题的数学模型可表示为:

undefined

其中,当将物品i装入背包时xi=1;否则xi=0。

2.2 0-1背包问题的改进粒子群算法

改进粒子群算法应用到0-1背包问题的思想:粒子群中粒子的个数与每个粒子的维数相等。先定义二进制数x,x只能取0和1。再把粒子的种群数看作背包的个数n,对于每个粒子xi(其中i=1,2,,n表示粒子个数)有n个维数,即1个粒子有n个位置。然后初始化每个粒子的速度vij,(其中j=1,2,,n表示每个粒子位置的维数),每个粒子的每一维都对应一个初始化了的速度。对公式(8)进行变化:

undefined

解决背包问题的步骤:

(1) 初始化粒子的速度和位置;

(2) 将初始化的位置向量代入式(9),在所得每个粒子的解中找到最优解pbest,并令pbest=gbest;

(3) 通过式(6)更新粒子的速度,对所得最优解进行修正,然后再次代入函数方程中继续寻找新的最优解;

(4) 若达到终止条件,则结束迭代,输出到存储向量,即为所求结果;否则,k=k+1,转步骤(3)。

2.3 实验仿真

为了验证ω1-QDPSO求解0/1背包问题的可行性及有效性,这里进行了2组实验,每组实验用ω1-QDPSO算法进行测试,每组算法运行50次。

实验一:取参数popsize=10,dimsize=10,c1=c2=2.05,genmax=1 000,g=0.968 5;N=10,V=269,W={95,4,60,32,23,72,80,62,65,46},C={55,10,47,5,4,50,8,61,85,87},得到实验结果是max f=295,收敛平均迭代次数11。

实验二:取参数popsize=20,dimsize=20,c1=c2=2.05,genmax=1 000,g=0.968 5;N=20,V=878,W={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58},C={44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63},得到实验结果是max f=1 024,收敛平均迭代次数23。

ω1-QDPSO算法求解0-1背包问题,与文献[9]中提出的用带有死亡罚函数的粒子群优化算法求解0-1背包问题相比,其运行速度明显提高。

3 结 语

本文通过采用4种方案对具有量子行为的粒子群优化算法的惯性权重研究分析表明,QDPSO改进算法中惯性权重的改变对性能的影响与经典PSO算法相比既具继承性又具发展性,在算法精度上ω1-QDPSO的结果比较优,而在计算速度上ω3-QDPSO和ω4-QDPSO的结果更优。选择其中算法性能相对较好的ω1-QDPSO算法应用于0-1背包问题,可以看出改进算法性能的改善在应用中得到更好的体现。

参考文献

[1]Kennedy J,Eberhart R C.Particle Swarm Optimization[C].Proc.IEEE International Conference on Neural Networks USA,IEEE Press.,1995(4):1 942-1 948.

[2]Shi Y,Eberhart R C.A Modified Particle Swarm Optimizer[C].IEEE International Conference of Evolutionary Compu-tation,Anchorage,Alaska,1998.

[3]Shi Y,Elberhart R C.Fuzzy Adaptive Particle Swarm Opti-mization[A].Proceeding of Congress on Evolutionary Com-putation[C].Seoul,Korea,2001.

[4]Sun Jun,Feng Bin,Xu Wenbo.Particle Swarm Optimizationwith Particles Having Quantum Behavior[A].Proc.2004Congress on Evolutionary Computation[C].2004:325-331.

[5]马金玲,唐普英.一种基于量子行为的改进粒子群算法[J].计算机应用研究,2007,43(36):89-90,180.

[6]Shi Y,Elberhart R C.Empirical Study of Partical SwarmOptimization[J].Proceeding of 1999 Congress on Evolution-ary Computation.Piscataway,NJ,IEEE Service Centerm,1999:1 945-1 950.

[7]曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004.

[8]陈贵敏,贾建援,韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报,2006,40(1):53-56,61.