离散粒子群优化算法

离散粒子群优化算法（精选10篇）

离散粒子群优化算法 篇1

摘要：储粮害虫特征选择是粮虫自动检测系统的一个关键环节。为此, 提出了把离散粒子群优化算法应用到粮虫的特征选择。该算法从粮虫的17维形态学特征中自动选择出面积、周长等7个特征的最优特征子空间, 采用参数优化后的SVM分类器对90个粮虫样本进行分类, 识别率达到95%以上, 证实了基于离散粒子群优化算法的粮虫特征选择是可行的。

关键词：储粮害虫,离散粒子群优化算法,特征选择,支持向量机

0 引言

快速准确地判别粮仓中是否存在害虫, 并检测出储粮害虫 (以下简称粮虫) 的种类和数量是粮食储藏中需要解决的关键问题。近10年多来, 图像识别法一直是粮虫检测领域的研究热点[1,2]。

提取粮虫的最优特征子空间可缩短粮虫分类的时间, 并提高识别的精度, 因此粮虫的特征选择是粮虫图像识别中一个关键的预处理环节。穷举法和启发法是经典的特征选择方法, 通过遍历或按照设定的方向重复迭代来选择最优或次优特征组合, 但这两类方法的计算量太大, 或者优化程度比较低。实质上粮虫特征选择是一个组合优化问题, 可以采用一些启发式的搜索算法如遗传算法、离散粒子群算法来选择特征子集。2002年, 张红涛提出了用遗传算法进行粮虫的特征选择, 但最优特征子空间的维数是事先指定的[3]。粒子群优化算法 (Particle swarm optimization, PSO) 是模拟鸟群捕食行为而提出的一种新的智能仿生算法, 它是一种现代启发式随机搜索算法, 该算法计算简单、鲁棒性好, 并能够快速地收敛到全局最优解, 近年来得到了广泛的应用。为此, 本文提出应用离散PSO对粮虫特征进行最优特征子集的选择, 实验结果验证了离散PSO算法用于特征选择的可行性和有效性。

1 PSO原理及实现步骤

PSO算法源于对鸟类捕食行为的研究, 一群鸟在随机搜寻食物, 如果这个区域里只有一块食物, 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域, PSO算法就是从这种模型中得到启示而产生的, 并用于解决优化问题[4]。

PSO求解优化问题时, 问题的解对应于搜索空间中一只鸟 (被称为“粒子”) 的位置, 每个粒子都有自己的位置和速度, 以决定飞行的方向。对于D维空间由M个粒子组成的群落, 其第i个粒子的位置和速度分别为xi= (xi1, xi2, …, xiD) T和vi= (vi1, vi2, …, viD) T, i=1, 2, …, M, 并通过其适应度函数值来衡量xi的优劣。在每一次迭代中, 粒子通过跟踪本身最优值pid和全局最优值pgd来更新自己的位置和速度, pid就是粒子本身所找到的最好解, pgd是整个种群目前找到的最好解。在找到这两个最好解后, 粒子根据式 (1) 和式 (2) 来更新自己的速度和位置, 即

vundefined=ωvundefined+c1rundefined (pundefined-xundefined) +c2rundefined (pundefined-xundefined) (1)

xundefined=xundefined+vundefined (2)

其中, ω为惯性权重;c1, c2为加速系数 (又称学习因子) ;rundefined, rundefined都属于[0, 1]区间服从均匀分布的随机数;xundefined, vundefined分别为粒子i在第k次迭代中第d维的当前位置和当前速度, d=1, 2, …, D。

PSO算法的一般步骤如下:

1) 初始化粒子群位置和速度, 每个粒子的个体极值点设置为当前位置, 并将全局极值点设置为个体极值中最好粒子的当前位置。

2) 计算粒子的适应度值, 对粒子群粒子进行性能评价, 如果好于该粒子当前的个体极值, 则更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值, 则更新全局极值。

3) 由式 (1) 和式 (2) 更新粒子的速度和位置。

4) 判断是否达到一定的迭代次数, 若达到则停止迭代, 输出最优解, 否则转向步骤2) 。

2 粮虫特征选择中的离散PSO实现

粮虫特征选择的任务就是从面积、周长、延伸率、复杂度等17个形态学归一化特征中选出d (d<17) 个特征的最优组合, 使性能评价准则达到最大[3]。这里xid的每一维的值用二进制表示, 选中的特征取为1, 否则为0, 种群规模M=50, D=17, 算法的终止条件是达到最大迭代次数20。另外, 还涉及到以下几个关键参数和问题。

1) 适应度函数。

适应度函数F是粒子位置的评价依据, 定义为

F=psvm×100-d/L (3)

其中, psvm为v折交叉验证训练模型的识别率, d为所选特征子集的特征个数, L为提取的粮虫原始特征的个数[5]。这里采用支持向量机 (Support vector machine, SVM) 分类器, 径向基核函数参数g=10/d, 惩罚因子C=20。可见, F越大表明选择的特征子集性能越好, 即利用较少的特征获得了较高的分类正确率。

2) 惯性权重ω。

它用来控制上一步速度对当前速度的影响, 通常取值在0.4～0.9, 且有较快的收敛速度。较大的ω可以加强PSO的全局搜索能力, 而较小的ω能加强局部搜索能力。因此, 可使ω随迭代次数k的增加而线性下降, 这样可使开始优化时搜索较大的解空间, 得到合适的种子, 在后期逐渐收缩到较好的区域进行更精细的搜索以加快收敛速度。

3) 学习因子c1和c2。

它们分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长, 若太小, 粒子可能远离目标区域, 若太大则会导致突然向目标区域飞去, 或越过目标区域。合适的c1, c2可以加快收敛且不易陷入局部最优, 这里取c1=c2=2。

4) 速度vd的钳位。

为防止粒子远离搜索空间, 粒子的每一维速度rd都会被钳位在[-vdmax, +vdmax]之间, Vdmax太大, 粒子将飞离最好解, 太小将会陷入局部最优, 这里取vdmax=4。

5) 离散PSO的位置更新方式。

对于离散PSO问题, Kennedy J 等学者提出将xid的每一维都限制为1或者0, 而速度不作这种限制[6]。则有

sig (vundefined) =1/[1+exp (-vundefined) ] (4)

其中, ρundefined是[0, 1]之间的随机数, sig () 为Sigmoid函数。若vid高一些, 粒子的位置xid更有可能选1, 否则选0。因此, 离散PSO与连续PSO的重要区别在于是按式 (4) 和 (5) 来更新粒子的位置。

6) 粒子变异。

为了避免算法过早地陷入局部最优解, 这里引入遗传算法中的变异算子, 即对粒子群中选取除最优个体外的部分个体进行变异操作。这里选择每次平均一个粒子只有1维数据发生变异, 变异概率为0.3。

3 实验结果及其分析

米象、大谷盗、谷蠹等是粮仓中最常见的、危害最大的9类粮虫, 本文从每类粮虫中随机选取15个样本进行训练, 从每类中随机选取10个样本进行识别检验。选用上述参数设置, 离散PSO算法优化10次的特征选择和分类实验结果如表1所示。

由表1可以得出, 运行10次之后, 适应度最高为96.254 9, 验证集的识别率91.111 1%也同时达到了最高, 则此时选择的面积、周长、占空比、等效圆半径、球形性、不变矩2和不变矩3等7个特征即为离散PSO法优化结果。

由表1可以看出, 在10次实验中, 有3次成功将17维特征压缩至7维, 与原始特征相比, 最少降低了8维, 大大地压缩了特征空间, 除1次之外, 其余9次都能够保持高于运用全部17维特征的正确识别率 (83.333 3%) 。这说明离散PSO法能够成功提取出特征空间中较优的特征子集。

在参数设置方法相同的情况下, 利用文献[7]的方法对同样的数据进行分析, 结果表明, 比离散PSO法多选择了3个特征, 识别率还降低了4.444 4%。这说明, 利用离散PSO法所选择的特征子集进行分类提高了识别的正确率。这是由于离散PSO法在寻优的过程中抛弃了对分类识别起干扰作用的不良特征以及冗余特征, 保留了对分类贡献较大的特征。

在采用SVM分类器识别的过程中, 惩罚因子C和径向基核函数参数g两个参数的选择对识别率有较大的影响。若采用离散PSO法选择出的7维特征子集, 并按照文献[7]方法对这两个参数进行优化, 当psvm达到最高96.666 7%时, C=20.244 3, g=1.343 8, 检验集的识别率为95.555 6%, 可见取得了较好的分类效果。

4 结论

1) 提出将离散PSO应用到粮虫的特征选择, 该方法自动提取出面积、周长等7个特征为最佳特征子空间。

2) 采用同样的数据进行分析, 离散PSO法比文献[7]法少选择3个特征, 识别率提高了4.444 4%, 表明离散PSO法可进一步压缩特征空间, 并提高了正确识别率。

3) 利用离散PSO法所提取的特征子集, 运用优化之后的SVM分类器进行识别分类, 识别率可以达到95.555 6%, 从而证实了基于离散PSO的粮虫特征的有效性。

参考文献

[1]毛罕平, 张红涛.储粮害虫图像识别中的研究进展及展望[J].农业机械学报, 2008, 39 (4) :175-179.

[2]Neethirajan S, Karunakaran C, Jayas D S, et al.Detectiontechniques for stored-product insects in grain[J].FoodControl, 2007, 18 (2) :157-162.

[3]张红涛.储粮害虫图像识别中的特征提取研究[D].郑州:郑州大学, 2002.

[4]杨维, 李歧强.粒子群优化算法综述[J].中国工程科学, 2004, 6 (5) :87-94.

[5]张红涛, 胡玉霞, 毛罕平.基于SVM的储粮害虫图像识别分类[J].农机化研究, 2008 (8) :36-38.

[6]Kennedy J, Eberhart R C.A discrete binary version of theparticle swarm algorithm[C]//Proceedings of the WorldMulticonference on Systemics, man and Cybernetics:Volume5.Piscataway, NJ:IEEE Service Center, 1997:4104-4109.

[7]胡玉霞, 张红涛.基于模拟退火算法—支持向量机的储粮害虫识别分类[J].农业机械学报, 2008, 39 (9) :108-111.

离散粒子群优化算法 篇2

基于粒子群算法的并联机构结构参数优化设计

介绍了粒子群优化算法的原理和实现方法,分析了该算法的主要参数对搜索性能的`影响,并把粒子群算法用于六自由度的并联机构的参数优化设计中,取得了较好的效果,试验证明,粒子群算法是一种有效的优化方法,适用于大型复杂结构的优化设计.

作 者：孙凡国 黄伟 KONG Fan-guo HUANG Wei 作者单位：五邑大学,机电工程系,广东,江门,529020刊 名：机械设计与研究 ISTIC PKU英文刊名：MACHINE DESIGN AND RESEARCH年，卷(期)：22(3)分类号：V221.6关键词：粒子群优化算法 进化计算 优化设计

离散粒子群优化算法 篇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

关键词：点协同通信,离散粒子群优化,功率分配

LTE-A中为解决小区间干扰问题和增强小区边缘用户的服务质量, 提出了协作式多点传输 (Coordinated Multipoint, Co MP) 技术[1,2]。邻近的几个基站协同为小区边缘的用户提供服务, 避免了OFDMA系统中小区间同频干扰, 同时也提升了小区边缘用户的服务质量[3]。与传统的无线蜂窝小区相比, 由于不同基站的信道不相同, Co MP的功率分配将更具挑战。相应的一系列针对Co MP的功率分配算法被提出来。

文献[4]提出联合注水算法 (Joint Water-filling, JoWF) 并证明其为理论最优, 但需要多次迭代才能得到最优解。为简化复杂度, 现在的系统中大量采用等功率分配算法 (Equal Power Allocation, EPA) , 但都不同程度地存在不足[5,6,7,8,9,10,11,12]。

粒子群优化算法 (Particle Swarm Optimization, PSO) 是James Kennedy和Russ Eberhart通过模拟鸟群觅食行为而提出的一种基于群体协作的随机搜索算法[13]。PSO算法最初应用于连续空间的优化, 如何应用PSO算法解决离散优化问题引起了人们的注意, 出现了一系列的离散PSO (Discrete Particle Swarm Optimization, DPSO) 算法, 针对0-1规划问题通过将速度作为位置变化的概率, 提出了二进制粒子群优化算法 (Binary PSO, BPSO) [14]。文献[15]以直觉模糊熵作为粒子群状态测度和速度变异的基本参数, 同时加入了位置变异策略。DPSO算法在电力系统、典型组合优化难题等领域中得到应用研究[16,17,18,19]。

本文针对下行Co MP系统的单用户功率分配问题, 通过把其转换成0-1规划问题, 采用DPSO搜索等功率分配的最优解。结果表明本文所提算法逼近理论最优的Jo-WF, 在吞吐量和迭代次数上具有显著优势。

1 系统模型

1.1 下行Co MP系统模型

Co MP系统通过多个协同基站 (Cooperative Base Stations, CBS) 向在小区边缘的用户 (User Equipment, UE) 提供服务, 如图1所示。每个用户向所在的小区基站反馈信道状态信息 (Channel State Information, CSI) , 假设所有基站通过有线方式快速获得瞬时CSI, 从而根据各自不同的CSI在相同的频带B上分配功率, 同时发送相同的数据。由于Co MP的下行采用OFDMA, 不同用户的带宽和总功率分配由用户间的Qo S和公平性确定, 当各个用户的子载波数和可用功率确定后, 多用户资源分配问题就变成如何让单用户获得最大的吞吐量。对于单用户UE一共有K个协同基站为其提供服务, 各个协同基站CBSi的功率限制为Pi, i∈{1, 2, …, K}。CBSi和UE的信道响应为Hi (f) , 假设有N个子载波, 每个子载波带宽为ΔB=B/N。

由于Co MP的下行采用OFDMA, 当小区边缘用户UE分配了N个子载波, 有K个协同基站为其提供服务, 该用户的吞吐量为各子载波吞吐量之和, 则用户吞吐量为

式中:B为用户分配的总带宽;N为子载波总数;Pi, j和Hi, j分别为第i个协同基站CBSi在第j个子载波上的发射功率和信道响应;N0为加性高斯白噪声 (AWGN) 功率谱。

由于每个CBS的总功率确定, 在各个子载波上分配的功率之和等于相应的总功率Pi。因此使用每个子载波分配到的功率比例xi, j来代替绝对功率值Pi, j, 即xi, j=Pi, j/Pi。使用γi, j= (Pi|Hi, j|2) / (N0B/N) 来表示当第i个CBS在第j个子载波上分配全部功率Pi时的信噪比。

在各个CBS总功率约束条件下, 以小区边缘用户吞吐量最大为目标的功率分配优化问题如下

1.2 联合注水功率分配

文献[4]通过分析吞吐量的海森矩阵, 证明式 (2) 最大值在可行域的边界上取得, Co MP最优的功率分配如图2所示。一共有N个子载波要分配功率, 只有1个子载波 (序号为n) 是K个CBS都分配功率的, 剩下的子载波被分成K份, 分别被各个CBS使用, 比如第1个CBS1使用K1个子载波, 其他的CBS不在这K1个子载波分配功率;第k个CBSk使用Kk个子载波, 其他的CBS不在这Kk个子载波分配功率。

其中, N=K1+K2+...+Kk+1。从而式 (2) 转变为求解下面的凸优化问题

通过拉格朗日对偶的方法, 可以获得各个CBS的注水水位λi为

可以看到λi由各个CBS在公用子载波n上的信噪比γi, n以及每个CBS所使用的子载波γi, n倒数之和确定。当获得λi后, 相应的各个子载波分配的功率比例xi, j为

最优的功率分配如式 (6) 所示, 需要迭代找到每个CBS使用的子载波和公用的n子载波, 保证每个P都大于零, 即

2 DPSO等功率分配算法 (DPSO-EPA)

2.1 经典DPSO算法

离散粒子群算法 (DPSO) 中针对解决0-1规划问题的BPSO, 每个粒子用一个二进制变量来表示, 每个取值在{0, 1}的粒子在解空间中移动。粒子的速度则用二进制变量的翻转概率来表示, t时刻, 种群中第i个粒子的速度和位置更新公式分别为

式中:xid和vid分别为种群中第i个粒子的位置和变化率;φ为常数, 称为学习因子;pbest和pgbest分别表示种群中第i个粒子找到的的最优位置和全局最优位置。xid, pbest和pgbest都只能是0或1, vid因为表示的是概率, 则限制在[0, 1]之间。函数sig (vid) 是一个转换限制函数, 能够保证xid的每一个分量都限制在[0, 1], 而rand () 则表示一个[0, 1]之间的随机数。vid值越大, 粒子的位置xid选1的概率越大, vid值越小, xid选0的概率则越大。BPSO算法各参数的分析和算法具体步骤见文献[18]。

2.2 DPSO等功率分配算法

联合注水算法需要不断地迭代来获得最优的功率分配。确定每个CBSi对应使用子载波Ki和公用子载波n将非常复杂。并且每当计算出注水水位λi后, 如果xi, j<0都需要重新迭代, 当可用子载波总数N和CBS数目K增大时, 由于需要确定每个CBS分配的子载波数目和公用子载波, 迭代次数也会大幅递增。根据文献[5-6]只要分配好子信道, 平均功率分配和注水算法的差别将很小, 同时为简化系统实现的复杂度, 本文考虑使用平均分配功率的算法来逼近最优解。

采用功率平均分配后, 将消除式 (2) 的每个CBSi总功率Pi的约束条件使得易于计算。原先每个子载波的各个不相同的功率比率xi, j, 简化成该子载波分配或者不分配功率两种情况, 用ri, j∈{0, 1}表示。xi, j由ri, j的总和来确定。这样原先的连续凸优化问题转变为确定ri, j的0-1规划问题。从而下行Co MP的功率分配优化问题可描述为

传统求解0-1规划问题有枚举法、分支定界法和动态规划法等, 但当问题规模扩大时, 其计算量呈指数级增加。大量快速算法被提出, 比如遗传算法、模拟退火算法、粒子群算法等。相对遗传算法DPSO简单容易实现并且没有太多参数需要调整, 尤其在问题的维数增加时, DPSO算法比遗传算法速度快[18,19]。本文采用DPSO来逼近最优解, 以式 (10) 为适应度函数。

3 实验结果及分析

通过蒙特-卡罗来分析各种功率算法的性能。取1 000次独立的频率选择性衰落信道下, 各个不同功率分配算法下的用户吞吐量的平均值, 信道由6路随机瑞利多径组成。假定下行Co MP在每个子信道的噪声N0ΔB都相同为-105 d Bm。其他具体参数参见表1[2]。

3.1 DPSO-EPA算法性能比较

仿真选择K个CBS进行仿真, 每个CBS的发射功率限制都一样为P, 其中一个CBS与用户的距离d为1.0 km, 其他CBS的距离d为0.6 km。当K=2时, d1=1.0, d2=0.6;K=3时, d1=1.0, d2=d3=0.6;K=4时, d1=1.0, d2=d3=d4=0.6。

选取文献[4]中的联合注水算法 (Jo-WF) , 传统分立注水算法 (SP-WF) 和本文提出的DPSO-EPA进行吞吐量的比较, 仿真结果如图3所示。图4给出了当P=40 d Bm, K=2时3种算法的吞吐量细节图。表2给出在不同发射功率限制下的DPSO-EPA, SP-WF分别和JoWF吞吐量的相对误差。

由仿真结果可以看到, DPSO-EPA算法的吞吐量逼近理论最优的Jo-WF, 且随着发射功率和CBS数目K的增加, 其差别逐渐变小。当两个CBS同时工作, 发射功率为40 d Bm时, 差别只有0.8%。DPSO-EPA算法在发射功率较高时优于SP-WF, 这是因为SP-WF没有利用联合信道的信息, 所以SP-WF得到的功率分配算法仅仅是局部最优;当发射功率较低时, 由于使用等功率分配没有利用不同信噪比子载波的分集效应, 故低于传统注水。

3.2 DPSO-EPA算法收敛速度

图5给出不同CBS数目K下的DPSO-EPA算法和Jo-WF吞吐量的相对误差随迭代次数变化的曲线。结果表明, 相对误差在迭代开始迅速减少, 接下来经过几次迭代搜索, 结果收敛。同时由于K的增加, 算法需要搜索的空间也相应增大, 所以K=4结果收敛需要100次迭代, 而K=2只需要40次。因此随着更多的子载波数和CBS数可用时, DPSO-EPA算法需要更多的粒子数目和迭代次数。

4 小结

离散粒子群优化算法 篇5

蚁群算法(ACO)是受自然界中蚂蚁搜索食物行为的启发，是一种群智能优化算法。它基于对自然界真实蚁群的集体觅食行为的研究，模拟真实的蚁群协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。蚁群算法作为通用随机优化方法，已经成功的应用于TSP等一系列组合优化问题中，并取得了较好的结果。但由于该算法是典型的概率算法，算法中的参数设定通常由实验方法确定，导致方法的优化性能与人的经验密切相关，很难使算法性能最优化。

蚁群算法中每只蚂蚁要选择下一步所要走的地方，在选路过程中，蚂蚁依据概率函数选择将要去的地方，这个概率取决于地点间距离和信息素的强度。

(ｔ+ｎ)=(t)+ Δ(ｔ+ｎ)上述方程 表示信息素的保留率，1－ 表示信息素的挥发率，为了防止信息的无限积累，取值范围限定在0～1。Δ ij 表示蚂蚁k在时间段t到(t +n)的过程中，在i到j的路径上留下的残留信息浓度。

在上述概率方程中，参数α和β:是通过实验确定的。它们对算法性能同样有很大的影响。α值的大小表明留在每个节点上信息量受重视的程度，其值越大，蚂蚁选择被选过的地点的可能性越大。β值的大小表明启发式信息受重视的程度。这两个参数对蚁群算法性能的影响和作用是相互配合，密切相关的。但是这两个参数只能依靠经验或重复调试来选择。

在采用蚁群－粒子群混合算法时，我们可以利用PSO对蚁群系统参数α和β的进行训练。具体训练过程：假设有n个粒子组成一个群落，其中第i个粒子表示为一个二维的向量 xi =(xi1 , xi2), i = 1, 2, ⋯,n，即第i个粒子在搜索空间的中的位置是xi。换言之，每个粒子的位置就是一个潜在的解。将xi带入反馈到蚁群系统并按目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。

蚁群算法的优点：

蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。

蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。蚁群算法很容易与多种启发式算法结合，以改善算法性能。

蚁群算法存在的问题：

TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足：（1），如果参数α和β设置不当，导致求解速度很慢且所得解的质量特别差。（2），基本蚁群算法计算量大，求解所需时间较长。（3），基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。

另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。

蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。

粒子群优化具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化。粒子群算法的本质是利用当前位置、全局极值和个体极值3个信息，指导粒子下一步迭代位置。其个体充分利用自身经验和群体经验调整自身的状态是粒子群算法具有优异特性的关键。PSO算法的优势在于求解一些连续函数的优化问题。

PSO算法存在的问题：

问题最主要的是它容易产生早熟收敛（尤其是在处理复杂的多峰搜索问题中）、局部寻优能力较差等。PSO算法陷入局部最小，主要归咎于种群在搜索空间中多样性的丢失。

不同算法的混合模型主要分为两类：（1）全局优化算法与局部优化算法混合；（2）全局优化算法与全局优化算法混合。纵观各种与PSO算法相关的混合算法，大多数基本上采用一种策略对其改进，要么与其他算法，要么加入变异操作，同时采用两种策略的混合算法较少。

上述策略中，两者之间有一定的矛盾性，全局算法与局部算法相混合，尽管可以提高局部收敛速度，但也加剧了陷入局部极小的可能；全局算法与全局算法的混合，算法的局部细化能力仍然没有改善。但如果只加入变异操作，则算法的探测能力得到提高，但也损害了其局部开发能力。

因此如果将局部搜索和变异操作同时混合到PSO算法中，通过适当的调节，发挥各自的优点，提高算法的开发能力，增加变异操作防止算法早熟，来共同提高PSO算法的全局寻优能力。

融合策略：

（1）针对蚁群算法初始信息素匮乏的缺点，采用其他算法生成初始信息素分布，利用蚁群算法求精确解，从而提高时间效率和求解精度。（使用的其他算法的求解结果以什么规则转换成蚁群算法的信息素初值，需要通过多次实验）

（2）将其他算法（如遗传算法）引入到蚁群算法系统的每次迭代过程中。以蚁群系统每一代形成的解作为其他算法的初始种群，然后经过其他算法的多次迭代，试图寻找更好的解，从而加快蚁群系统的收敛速度，提高求解速率。

（3）蚁群算法中α，β的选取往往是通过经验来取得的，而选取不当时会造成算法的性能大大降低，因此可以利用其他算法对蚁群系统参数α，β进行训练。

（4）对于蚁群算法出现过早收敛于非全局最优解以及时间过长的缺点，可以通过使用蚁群算法进行搜索，然后用其他算法对蚁群算法得到的有效路由路径，通过选择、交叉、变异等优化过程，产生性能更优的下一代群体。

离散粒子群优化算法 篇6

为了降低配电网网损,提高电网经济效益,要对配电网络进行优化。配电网重构在配电网络优化中具有降低网损、提高供电电压质量、消除过载等作用。中国配电网络馈线负荷分布很不均匀,电压质量不高,因此配电网重构目标函数不能是单一的,需要将降低配电网网损、提高供电电压质量以及负荷分布均衡化等目标函数综合起来考虑,建立多目标函数模型。配电网重构的研究目标大部分以降低网络损耗为主要目标函数,部分文献将几个目标函数综合起来研究。但这些多目标函数优化算法不能找到较好的全局最优解,计算速度慢,受参数影响较大。如遗传算法、蚁群算法、禁忌搜索性法、模拟退火算法等人工智能算法[1,2,3,4,5,6]都存在这些缺点。本文提出采用二进制粒子群算法(Binary Particle Swarm Optimization,BPSO)[7]对网络进行优化,将量子计算编码[8,9,10]应用到离散粒子群算法中,用量子比特概率表示离散粒子的状态,能够保证粒子的多样性和全局搜索能力。通过算例仿真,证明该算法比二进制粒子群算法全局搜索性好,相对其它算法收敛速度快。

1配电网重构数学模型

配电网络重构是非线性、多目标的组合优化问题,以往的目标函数都以降低网络损耗为目标函数,本文提出将降低配电网网损和提高电压质量共同作为目标函数,采用线性加权法对两目标进行处理,数学模型为

undefined

式中Ri为网络线路i的电阻;Pi和Qi为流过支路i的有功功率和无功功率;Ui为支路i的末端电压值;Ni为网络支路总数。

提高电压质量指提高网络各个节点电压幅值,使实际电压幅值和标准电压幅值偏差最小,该目标函数为

undefined

式中Ut为标准电压幅值;Ui为节点i的电压幅值;△U为节点电压幅值偏差;N为网络的节点数。

本文最终的目标函数为

min F″=min [λ1F+λ2F′], (3)

式中λ1、λ2为目标函数中的权系数,有λ1+λ2=1。

配电网重构目标函数有潮流方程约束、节点电压约束、支路容量约束、网络辐射状约束等约束条件,表达式为

undefined

式中Pi、Qi分别为节点i的有功和无功功率;Pli、Qli分别为节点i负荷的有功和无功功率;Vi、Vimin、Vimax分别为节点i处的电压幅值、最小和最大电压幅值,重构后的网络应满足辐射状网络结构。

2 BPSO和量子编码的基本理论

2.1二进制粒子群算法

粒子群算法由Eberhart和Kennedy博士第一次提出生物群体智能演化算法,这主要是用来处理连续性优化目标函数。粒子群算法开始是用来解决连续优化问题的,为了完善粒子群算法,Eberhart博士提出了二进制粒子群算法,即离散粒子群算法。在二进制粒子群算法中,xid表示第i个粒子d维向量的位置,vid表示第i个粒子d维向量的速度,则位置和速度的更新过程为

vundefined=wvundefined+c1r1(pundefined+xundefined)+c2r2(pundefinedxundefined) , (7)

式中xundefined为粒子i在第k-1次迭代时d维的取值;vundefined表示第k次迭代的速度;pundefined为k-1次迭代个体粒子最优解;pundefined为k-1次迭代整个粒子群全局最优解;w为惯性权重系数;c1、c2为加速因子;r1、r2为在[0,1]之间变化的随机数;xid为优化函数状态解,其取值限制为1或0 两种状态。速度vid的大小决定xid的取值,若vid的取值较大时,xid很可能为1;若vid更新值较小时,xid取值为0的概率比较大。利用Sigmoid函数来判定xid的取值主要公式为

S(x)=1/(1+e-x), (8)

undefined

式中rand的取值为[0,1]之间的随机数;vid的大小限制在[vmin,vmax]之间。

2.2量子编码的基本理论

1982年Feynman第一次提出了量子计算的概念,量子计算具有并行性以及指数级的存储容量,表明其具有很快的计算能力。量子计算的基本概念如下。

2.2.1 量子比特

量子计算中最小的信息量为单个量子位,即量子比特。量子比特的状态可以取“0” 状态和“1”状态,用公式表示为

|ψ>=α|0>+β|1>, (10)

式中α、β表示量子比特出现“0”、“1”状态的概率复数;|α|2、|β|2分别表示量子比特位是状态“0”、状态“1”的概率,有

|α|2+|β|2=1。 (11)

2.2.2 量子编码方式

离散粒子群算法采用二进制编码,在基本的量子计算中用α、β概率复数表示1个量子比特位的状态值,可以表征多个状态组合的叠加,这样使群体具有很好的多样性,扩展了种群的数量。具有M个量子比特位的表示方法为

undefined

式中undefined;qj为第j个量子个体,这样能表征2M个状态组合。要确定量子比特位的状态值,先在[0,1]区间随机产生1个随机数,若该随机数大于undefined,则取1,否则为0。

3基于量子粒子群算法配电网重构的研究

用量子编码表示粒子群的新算法称作量子粒子群算(Quantum Particle Swarm Optimization ,QPSO),其基本过程是根据配电网络开关状态初始化二进制粒子群个体并保存当前状态;用量子比特概率表示粒子状态的取值;更新种群的量子比特概率并转化为二进制粒子状态值;根据评估函数评价此时状态解。1997年Eberhart博士提出了离散粒子群算法,即二进制粒子群算法,其参数少、容易控制、收敛速度快,具有并行处理的优化特点,适合于多目标函数优化,但容易陷入局部最优解。离散粒子群算法经过多次迭代后,其多样性逐渐降低,而量子计算的编码方式能表征2M个状态组合,扩展了种群的数量和多样性,量子编码的方式具有并行性,适合于多目标组合优化问题。每个粒子向量用量子比特状态表示,其表示形式为

undefined, (13)

undefined, (14)

式中Q(t)为量子编码表示的粒子向量;qundefined(t)表示第j个粒子向量的第i位状态取值的概率,j=1,2...,n,i=1,2...,m;n为粒子种群数目。量子编码形式的粒子向量转变为二进制粒子,需要先在[0,1]区间产生1个随机数,若该随机数大于qundefined(t)中undefined,则该粒子的状态值为1,否则就为0。

根据二进制粒子群算法中位置和速度的更新公式,可以得出量子粒子向量种群Q(t)的更新公式为

Q(t+1)=d1Q(t)+d2Qselfbest(t)+d3Qglobebest(t), (16)

Qselfbest(t)=a×pselfbest(t)+b×(1-pselfbest(t)), (17)

Qglobebest(t)=a×pglobebest(t)+b×(1-pglobebest(t)), (18)

式中a、b为控制系数,a+b=1,且有0

根据配电网络的结构特点,配电网重构的过程就是改变配电网络开关的组合状态,量子粒子群算法在配电网重构中的应用流程如下:

a.初始化量子粒子向量种群Q(t),设种群数目为n,最大迭代次数为kmax,设定d1、d2、d3学习系数及控制系数为a、b。

b. 写出与量子粒子向量种群相对应的离散粒子群P(t),改变开关位置状态,然后判断网络是否为辐射状网络,若是则对配电网进行潮流计算,计算此时网损,保存最优解。

c. 根据量子粒子群算法中式(15)、(16)、(17)和(18)对量子粒子向量种群Q(t)进行更新,得到下一代的种群Q(t+1)。将Q(t+1)转变为离散粒子群P(t+1),根据在[0,1]之间产生随机数,若随机数大于qundefined(t)中undefined的值,则该离散粒子的状态值为1,否则就为0;判断更新后的网络是否为辐射状,若是则进行潮流计算,并计算网损,保存局部最优解和全局最优解。

d. 若达到最大迭代次数kmax,则停止计算,否则返回第c步。

4算例分析

本文采用2个算例验证了量子粒子群算法的可行性。算例1是IEEE单馈线33节点配电系统,来自文献[11],其额定电压为12.66 kV,网络中有37条支路,其中5条支路上有联络开关,该网络的总负荷为3 715 kW+j 2 300 kVA。设定离散粒子种群数量为50,最大迭代次数为100,控制系数a、b分别为0.4、0.6,本文算法与其它算法仿真结果比较如表1所示。

从表1网络重构结果可以看出,经过本文算法重构后的网损比改进后BPSO、改进遗传禁忌算法要低很多,跳出了局部最优点,网络中最低节点电压比重构前有所提高,达到了多目标优化的目的,验证了本文算法的可行性。网损收敛曲线如图1所示。

算例2来自文献[12],该配电网包含69个节点和74条支路,5个常开联络开关分别位于支路10-65、12-20、14-68、26-53、38-47上,额定电压为12.66 kV,总负荷为3 802+j 2 694 kVA,参数设置与算例1相同。网络重构前,该配电网网损为225.53 kW,经过本文算法重构后,网损降为94.2 kW;改进BPSO重构后,网损为106.4 kW。

由上述2个算例验证可知,量子粒子群算法跳出了局部最优点,能够快速地收敛到最优解。

5结论

本文提出将离散粒子群算法和量子编码计算结合起来应用到配电网重构中,通过2个算例验证,该算法可行,并在一定程度上跳出了局部最优,收敛速度相对离散粒子群算法比较快。

摘要：阐述了配电网重构数学模型、二进制粒子群算法、量子编码的基本理论,对量子粒子群算法配电网重构进行了研究,将量子编码应用到离散粒子群算法中,用量子比特概率表示离散粒子的状态,根据二进制粒子群速度更新公式更新粒子的状态,改变开关开合状态进行网络重构。量子比特概率能够表征丰富的信息量,保证粒子的多样性和全局搜索能力。通过2个算例验证,表明量子粒子群算法满足了实际运行要求。

关键词：配电网重构,配电网网损,电压质量,二进制粒子群算法,量子编码

参考文献

[1]Nara K,Shiose A,Kitagawa.Implementation of genetic algorithmfor distribution systems loss minimum reconfiguration[J].IEEETrans.On Power system,1992,7(3):1044-1051.

[2]Srinivas M,Pattnaik L.M.Adaptive probalities of crossoverandmutation in genetic algorithms[J].IEEE Trans.On Sys-tems,Man and Cybernetics.1994,24(4):656-667.

[3]刘莉,陈学允.基于模糊遗传算法的配电网络重构[J].中国电机工程学报,2000,20(2):66-69.

[4]Ching-Tzong Su,Chung-Fu Chang,Ji-Pyng Chiou.Distribu-tion Network Reconfiguration for loss reduction by Ant ColonySearch Algorithm[J].On Electric Power Systems Research,2005,190-199.

[5]Young-Jae Jeon.Jae-chul Kim.An efficient simulated annealingalgorithm for network reconfiguration in large-scale distributionsystems[J].IEEE Transactions on Power Delivery,2002,17(4):1070-1077.

[6]胡敏羡,陈元.配电系统最优网络重构的模拟退火算法[J].电力系统自动化,1994,18(2):24-28.

[7]Kennedy J,Eberhart R C.A discrete binary version of the particleswarm algorithm[C].International Conference on System,ManandCybernetics.Orlando.USA,1997:4104-4108.

[8]Kuk-HyunHan,Jong-HwanKim.Quantum-Inspired Evolution-ary Algorithm for a class of Combinatorial OPtimization[J].IEEETransaction on Evolutinary Computation,2002,16(6):580-592.

[9]侯云鹤,鲁丽娟.量子进化算法在输电网扩展规划中的应用[J].电网技术,2004,28(17):19-23.

[10]李斌,谭立湘.量子概率编码遗传算法及其应用[J].电子与信息学报,2005,27(5):805-810.

[11]ME Baran,F F Wu.Network reconfiguration in distribution sys-tems for loss reduction and load balancing[J].IEEE Trans onPower Delivery,1989,4(2):1401-1407.

离散粒子群优化算法 篇7

空间遥感技术自1962年诞生以来,全球已发射了500余颗对地观测卫星,是目前世界上发射数目最多、应用范围最广、最具代表性的一类卫星。我国的卫星对地观测事业历经30余年的发展,取得了长足的进步。目前,我国已发射的对地观测卫星超过50颗,形成了气象、资源、海洋和环境减灾四大民用系列对地观测卫星体系,可以覆盖我国的陆地和海域的全部,以及周边国家和地区,总面积超过1 500万平方千米。

在2006年公布的《中华人民共和国国民经济和社会发展第十一个五年规划纲要》中将“高分辨率对地观测系统”列为16个重大科技专项与重大科技基础设施之一。预计在2020年,我国将形成全天候、全天时、全球覆盖的对地观测能力。

随着成像任务需求的快速增长、任务类型的复杂化和多样化,以及对地观测卫星的数量及种类的逐步增加,任务规划的复杂度大大增加,早期的卫星独立管控模式已经无法满足未来的需要,必须将多颗成像卫星进行综合规划调度。

因此,如何在多星多任务的情况下,充分利用对地观测卫星、合理规划和调度卫星资源、优化卫星任务配置,是一个重要而迫切需要解决的问题。

多星任务规划问题是NP-hard问题[1],其求解空间随着任务数和资源数量的增加而迅速增加,针对大规模的任务规划问题,无法在合理的时间内计算最优解。而针对多星任务规划这类时效性较强的问题,在合理时间内得到问题的近似最优解更有实际意义。

群智能算法是一类卓有成效的求解最优化问题的搜索算法,借助评价函数对解的优劣进行判定,对目标函数和约束的要求更为宽松。相比传统算法,群智能算法的效率更高,每个群个体的能力十分简单,执行时间也比较短,算法实现简单,鲁棒性更强。群智能算法包括蚁群算法和粒子群算法等,在各个领域具有广泛应用[2,3,4,5,6]。

本文主要研究利用离散粒子群算法解决多星任务调度优化问题,提出了一种基于离散粒子群算法的多星任务规划算法。通过实验仿真表明,本文算法简单、灵活、易于扩展,能够有效地对问题实行求解。

1 对地观测任务规划模型

1. 1 对地观测任务描述

对地观测卫星多以近地轨道绕地球运转,每天可绕地球运行多圈。单颗卫星可以对指定区域进行周期性观测,通过组网工作,多颗卫星可以持续观测指定区域。

为了增加单颗卫星的检测范围,很多对地观测卫星都搭载具有侧视功能的载荷,能够沿垂直于运行轨道的方向进行摆动,实现偏离星下线的目标的观测,因此,在指定时刻内,卫星的观测范围是一个以星下线为圆心的圆形区域。

由此可见,卫星的成像任务主要有点目标成像任务和区域目标成像任务2种。为简便起见,一般的处理方式是将区域成像任务进行分解成多个点任务,统称为单元任务,统一进行处理。

1. 2 数学模型

从约束规划的角度来看,多星任务规划问题实际上就是将有限的系统资源分配给要求完成的任务的过程。

多星任务规划问题主要涉及2个集合: 卫星集合S和任务集合T。其中卫星集合S表示为S ={ s1,s2,…,sk} ,单元任务集合T表示为T = { t1,t2,…,tm} 。

由于卫星可以执行多种观测任务,不同的任务有不同的优先级,通过将优先级转换为任务的权值,作为任务收益的重要参数。任务i的权值表示为tqi,其中tqi> 0,且i∈T。

由于对地观测任务的特性,任务只有在特定的时间窗口之内才能进行,因此其所对应的资源其实是卫星的时间窗口。TWk,i为卫星k执行单元任务i时可以使用的时间窗口集合,表示为:

虽然对于特定任务,在多个时间窗口都可以进行观测,但是其观测质量可能并不一样,通过将该因素量化,作为时间窗口的权值。对于任务i可见的时间窗口j的权值表 示为wqi,j,其中wqi,j> 0,且i∈T,j∈TWk,i。

根据不同的优化策略可以构建不同的优化目标函数。对于多星任务规划系统,常见的优化策略主要是在满足容量和波段等约束条件下得到最大化任务完成收益( 包括任务权值和窗口权值) ,即

式中,xi,j为决策变量,如果单元任务i执行任务时占用的时间窗口为j,则xi,j= 1; 否则,xi,j= 0。

2 面向任务规划的离散粒子群算法

2. 1 基本粒子群算法

粒子群优化( Particle Swarm Optimization) 算法最早于1995年由James Kennedy和Russell Eberhart提出,是一种基于群智能的随机搜索算法[2]。

基本粒子群算法基于位置—速度模型,粒子在飞行过程中,通过调整自身的飞行轨迹,并借助于以前自身的最佳位置和整个粒子群曾经的最佳位置的最佳经验,不断调整自身的位置。因此,群中的每个粒子都要有记忆能力,并且可以对自身的最佳位置进行调整,整个粒子群可以对群体的最佳位置进行调整。对于一个最大化问题,较佳位置是指解空间中对应目标函数的值较大的一个点。

2. 2 离散粒子群算法设计

基本粒子群算法及其改进算法[8,9]主要被用于在连续论域中搜索函数的最优值,其模型直观简单、参数较少、效率高、执行速度快。但是由于标准粒子群算法所描述的粒子状态和运动方式都是基于连续变量的,在针对建模在离散空间中的问题,如任务调度和路径规划等,粒子的速度和位置变化难以使用基本粒子群方程表示,因此基本粒子群算法完全不适合求解离散空间中的问题。为了解决在离散空间中求解问题,需要将粒子群算法离散化[10,11]。本文提出一种适合多星任务规划的离散粒子群算法。

2. 2. 1 离散编码方式

在离散粒子群算法中,每个粒子代表一个可行解。针对任务分配问题,每个粒子就代表将任务分配给相应的资源的一种方式。通过自然数对任务进行编码,对于n个任务,其编码为1 ~ n,对于m个资源,其编码为1 ~ m,粒子的长度等于任务的个数。如图1所示,假定任务的个数为5,任务的编码为1、2、3、4、5; 资源的个数是1、2、3、4。按照图1的方式为任务指派相应资源,如为任务1指派资源2,任务5指派资源4等,得到一个相应的解为( 2,3,2,1,4) ,因此该粒子就为( 2,3,2,1,4) 。

2. 2. 2 粒子位置变化公式

粒子群的位置是粒子的速度、粒子的个体最优值和全局最优值相互作用的结果,粒子根据自己的飞行经验不断调整自身位置和速度,向最优位置飞行。根据资源分配的特点,对粒子群方程进行重新定义:

由此可以看出,离散粒子群和基本粒子群类似,其粒子位置的更新也受3个方面因素的影响: 粒子的当前状态、粒子的最优历史记录和群的历史最优记录,离散粒子群方程也分为3个部分。对于资源分配问题,粒子的速度由粒子内部的置换操作和粒子之间的替换操作表示。

首先,离散粒子群公式的第1部分是粒子的“惯性”操作,当粒子处于某一状态时,通过调整粒子内部的结构,得到粒子的位置更新,该操作表示为:

式( 4) 是式( 2) 的一部分。其计算过程如下: 假设粒子的维度为n,生成一个位于区间[1,n]的随机数i,然后依据任务约束条件,从时间窗口集合TW中查询计算i可以置换到的位置集合,从中随机选择一个元素j进行置换,符号“”表示2个粒子之间的置换操作,如图2所示。计算置换以后的粒子适应度,如果该适应度更接近最优值,称该置换为优势置换,记做dom( ) = 1,否则称该置换为劣势置换,记做dom( ) = 0。如果该置换是个优势置换,则执行i和j的置换。如果该置换是个劣势置换,按照一定的概 率进行劣 势替换,劣势替换 规则为rand( 0) < α* w,其中函数rand ( ) 生成[0,1]之间的随机数,α为门限值,w为惯性权重,在此采用线性递降权重策略,惯性权重的计算方式为:

式中,Tmax为最大进化代数,即设定的算法迭代次数; wmax为初始惯性权重,取值0. 9; wmin为进化到最大代数的惯性权重,取值为0. 4。

离散粒子群公式的第2部分是粒子的“自我认知”,除了自身的位置调整以外,粒子还可以根据历史上的最优记录调整自身位置,该操作在粒子“惯性”操作的基础之上执行,其表示形式如下:

从式( 6) 可以看出,该公式叠加到粒子的“惯性”操作之上。“”表示2个粒子之间的替换操作,假设粒子的维度为n,生成2个位于区间[1,n]的随机数i和j,不失一般性,设i < j,如图3所示,得到一个替换区间[i,j],利用历史最优粒子位于区间[i,j]的部分替换掉当前粒子位于该区间的内容。首先判断该替换是否满足性能约束条件,如果不满足,则设置j = j - 1,直到满足约束,或者到达i < j,如果替换满足约束条件,计算替换以后的粒子适应度,如果该适应度大于当前的适应度,称该替换为优势替换,记做dom( ) = 1,否则称该 置换为劣 势替换,记做dom( ) = 0。如果该替换是个优势替换,则执行该区间的替换。如果该置换是个劣势替换,按照一定的概率进行劣势替换,劣势替换规则为rand( ) < β,其中函数rand( ) 生成[0,1]之间的随机数,β为门限值,如果生成的随机数小于门限值,则执行该替换。

离散粒子群公式的第3部分粒子的“社会认知”,除了前面2步,粒子还可以根据整个粒子群的最优记录调整自身位置,该操作在粒子“自我认知”操作的基础之上执行,其表示形式为:

式( 7) 也是离散粒子群公式的一部分,叠加到粒子的“惯性”操作和“自我认知”操作之上。“”表示2个粒子之间的替换操作,假设粒子的维度为n,生成2个位于区间[1,n]的随机数i和j,不失一般性,设i < j,如图4所示,得到一个替换区间[i,j],利用群最优粒子位于区间[i,j]的部分替换掉当前粒子位于该区间的内容。首先判断该替换是否满足约束条件,如果不满足,则设置j = j - 1,直到满足约束,或者到达i < j,如果该替换满足约束条件,接下来计算替换以后的粒子适应度,若该适应度更接近最优值,称该替换为优势替换,记做dom( ) = 1,执行该替换操作; 否则称该置换为劣势替换,记做dom( ) = 0,按照一定的概率执行该替换,其替换按照规则rand( ) < γ进行,其中函数rand( ) 生成[0,1]之间的随机数,γ为门限值,如果生成的随机数小于门限值,则执行该替换。

上述3步过程完成以后,当前粒子的位置调整也已经结束,得到了一个新的解。通过计算该粒子的适应度,如果该适应度优于个体历史最优记录,将其记做个体最优历史记录; 如果该适应度优于群最优历史记录,将其标记为粒子群最优历史记录。

2. 3 离散粒子群算法流程

离散粒子群由多个粒子组成,其核心通过粒子之间的协作,获得所求解问题的可接受解。其算法流程如下:

1设定粒子群的规模N,最大进化代数Tmax,惯性参数wmax和wmin,劣势置换门限值α、β、γ。

2生成N个初始粒子。计算每个粒子的适应度,将初始解作为局部最优值,从中选择最优值作为全局最优值。

3判定算法是否达到终止条件( 达到最大进化代数或者满足算法的收敛准则) ,如果满足,算法终止,否则进入步骤4。

4更新步长,计算惯性权重w。

5对每个粒子执行粒子位置变化公式,更新粒子的位置,计算粒子的适应度。如果该适应度优于个体历史最优记录,将其记做个体最优历史记录; 如果该适应度优于群最优历史记录,将其标记为粒子群最优历史记录。转入步骤3。

3 模拟仿真结果

本文研究设计了一个仿真算例: 通过离散粒子群算法和数学编程语言 ( A Mathematical Programming Language,AMPL) 的线性规划算法对比,以验证离散粒子群算法在解决多星任务规划问题中的能力。

在对地观测卫星任务规划领域内,并没有标准的测试数据集对不同的调度方法进行验证和对比。本文中,实验数据利用卫星仿真工具包 ( SatelliteTool Kit,STK) 仿真生成,根据对地观测任务的特点,在一定的场景和地面站中添加卫星对象,任务的可视窗口由待观测任务的地理位置和遥感天线的物理特性决定,并设置任务与时间窗的权值对应关系; 任务的权值由任务的类型决定。为了验证模型的可行性,假设调度目标在限定的范围内均匀分布。

假定分解后的待执行任务纬度为 - 60° ~ 60°,经度0° ~ 180°均匀分布,且任务的优先级为正整数,卫星和任务的可见性由卫星模拟软件仿真生成。

仿真实验中分别将卫星数目设定为: 10、20、30、40、50、80、100,对每组卫星数根据指定的任务数和窗口数随机生成测试样例。对同一组数据分别利用AMPL线性规划工具包和离散粒子群算法实现 ( 由Java语言实现第2节的算法) 进行求解。离散粒子群算法的粒子数设为1 000,迭代次数设为10 000,惯性权重设为0. 9,3个置换门限值都设为0. 000 5。实验结果如表1所示,AMPL列和DPSO列分别表示2种算法的执行时间。

由表1中的数据得到AMPL和DPSO两种算法的执行时间曲线图如图5所示。

由图5可以看出,当任务数增大时,AMPL执行时间曲线近似呈指数增长。因为多星任务规划问题本质上是个约束规划问题,而约束规划是NP问题,因此,当问题规模很大时,AMPL的效率就非常低。而离散粒子群算法的执行时间基本上随着问题规模的增长而线性增长,显示了该算法具有良好的可扩展性,能够有效处理较大规模的多星任务规划问题。

4 结束语

依据构建的多星任务规划模型,在上述模型的基础之上,利用离散粒子群算法完成对多星任务规划的求解。通过仿真实验表明,离散粒子群算法能够有效解决多星任务规划问题,特别是在任务规模较大的情况下展现了良好的可扩展性。综上所述,建立的多星任务规划模型是合理的,而算法能够对不同尺度的多星任务规划问题进行有效求解。

摘要：对地观测卫星的任务规划是卫星管控中的关键内容,其本质是一个优化决策的过程。面向多对地观测卫星任务规划的问题特点,建立了问题的数学模型,提出了一种基于离散粒子群的优化算法,设计了离散粒子群的位置变化公式。仿真结果表明,离散粒子群算法具有收敛速度快、寻优能力强等优点,能够有效地解决多约束条件下的多星任务规划问题。

关键词：任务规划,多星,离散粒子群

参考文献

[1]胡海洋,张学庆,刘喆,等.基于AMPL的多成像卫星任务调度与规划[J].系统工程与电子技术,2012 34(3):517-522.

[2]邢旭东,周旭,米健.基于改进的人工蚁群的图像分割算法[J].无线电通信技术,2013,39(6):71-73,81.

[3]席斌,李帅,侯媛媛.基于多目标粒子群算法的异构网接入控制[J].无线电通信技术,2012,38(4):42-44,50.

[4]卢文清,何加铭,曾兴斌,等.基于多特征提取和粒子群算法的图像分类[J].无线电通信技术,2014,40(2):90-93.

[5]高明哲,祝明波,邹建武.基于改进粒子群算法的单脉冲雷达多目标分辨[J].无线电工程,2014,44(6):25-28.

[6]张旺,王黎莉,伍洋.基于遗传算法的阵列天线综合及分析[J].无线电通信技术,2011,37(4):28-30.

[7]KENNEDY J,Eberhart R.Particle Swarm Optimization[C]∥Proceeding of IEEE International Conference on Neural Networks.Piscataway,NJ:IEEE Service Center,1995:1942-1948.

[8]SHI Y,Eberhart R.A Modified Particle Swarm Optimizer[C]∥Proceedingof IEEE International Conference on Evolutionary Computation,1998:69-73.

[9]CLERCM,KENNEDY J.The Particle Swarm:Explosion,Stability,and Convergence in a Multidimensional Complex Space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[10]KENNEDYJ,Eberhart R,SHI Y.Swarm intelligence[M].San Francisco:Morgan Kaufman Publishers,2001.

[11]KENNEDY J,Eberhart R.Discrete Binary Version of the Particle Swarm Algorithm[M].CSMC,1997.

离散粒子群优化算法 篇8

基于模型诊断MBD (Model-Based Diagnosis) 是为了克服传统专家系统诊断方法的不足而提出的一种推理方法, 它对人工智能领域的研究具有重大意义[1,2,3]。MBD把诊断推理过程与系统模型分开, 具有很好的移植性, 已经广泛应用于工程、航天、电路诊断等领域[4,5,6]。

MBD方法一般先根据系统的描述和观测, 得到极小冲突集, 然后通过计算最小冲突集MCS (Minimal Conflict Set) 的最小碰集, 得到系统的极小诊断。许多学者对计算最小碰集算法进行了深入研究, 文献[7-9]中提出的HS-Tree、HST-Tree、BHS-Tree等树形搜索算法, 需要建立树或者图, 而且可能因为剪枝问题而丢失正确解, 算法实现比较繁琐并且计算效率较低。文献[10-11]中提出的布尔代数、逻辑数组方法则需先存储所有碰集, 通过化简才能得到所有的最小碰集集合。文献[12]中提出的遗传算法 (GA) 只能快速计算出95%的最小碰集, 并不能保证所有输出结果都为最小碰集。

离散二进制粒子群优化 (BPSO) 算法由Kennedy和Eberhart在1997年首次提出[13]。BPSO算法本质上是属于迭代的随机搜索算法, 具有并行处理特征, 鲁棒性好, 易于实现, 原理上可以以较大的概率找到优化问题的全局最优解, 并且具有较快的收敛速度和较高的计算效率, 在许多领域得到广泛应用。基于此, 本文在基于模型的配电网诊断实例中, 将计算最小碰集问题转化为0、1表示的二值空间问题, 并且引入离散BPSO算法用于求解冲突集的最小碰集, 取得了很好的效果。

1 MBD的基本概念

MBD的目的是辨识出故障部件, 所以模型必须清楚地表示设备的部件和行为模式。1987年Reiter首次将MBD原理用一阶逻辑表示出来[14,15]。在诊断的逻辑表示中, 系统可以用一个三元组 (SD, OBS, COMP) 来表示, 其中SD为系统的模型描述一阶语句, OBS为系统的观测值一阶语句, COMP为组成系统的元件集合。MBD领域中的常用基本概念介绍如下。

冲突集:元件集C是系统 (SD, OBS, COMP) 的一个冲突集 (CSC) , C必须满足2个条件:

a.C={c1, c2, …, cn}⊆COMP;

b.不一致。

如果C的任一真子集都不是冲突集, 则称C是最小冲突集。

在冲突集中至少有一个元件存在故障, 这样才能解释系统模型预期和实际观测差异存在的原因。

碰集:设CS是一个冲突集簇 (即由集合组成的集合) , H是CS的一个碰集, H必须满足2个条件:。如果H的任一真子集都不是碰集, 则称H是最小碰集。

定理1 Δ是 (SD, OBS, COMP) 的一个极小诊断, 当且仅当Δ是 (SD, OBS, COMP) 的最小冲突集的最小碰集。

由定理1可知, 如果知道了系统所有的最小冲突集, 可以通过计算最小冲突集的最小碰集, 得到极小诊断结果。

2 基于BPSO算法的最小碰集搜索算法

2.1 标准BPSO算法

为解决离散或二进制变量的优化问题, 文献[16]提出了BPSO算法。该算法用二进制编码方式来表示空间中的某一维是否被选择, 粒子位置xid每一维被限制为1或者0, 用速度vid表示位置状态改变的可能性, 速度代表粒子位置接近于1的概率, vid越大, xid为1的概率越大, 它被限制在[0, 1]之间, 由sig () 函数实现, 其速度和位置更新公式如下:

其中, vtid和xtid分别为粒子i在第t次迭代中第d维的速度和位置;w为惯性权重;c1和c2为学习因子;r1t和r2t为介于[0, 1]之间的随机数;Ptbestid为粒子i在第t次迭代中第d维的个体极值点的位置;Gtbestid为整个种群在第t次迭代中第d维的全局极值点的位置;rand为[0, 1]之间的随机数。

2.2 基于BPSO算法的最小碰集算法原理

冲突集是由若干系统元件组成, 在这些元件中至少有一个元件是故障元件, 这样才能解释系统模型预期和实际观测差异存在的原因。将每个冲突集CSC映射成0、1表示的N维二值集合, 其中N代表全部冲突集中系统元件的规模 (问题规模) 。每一系统元件存在0、1这2种状态, 0表示正常状态, 1表示故障状态。初始化粒子X为P×N维的随机二值矩阵, P表示粒子群的种群规模。每次迭代过程中, 通过适应度函数评价各粒子位置优劣, 更新粒子的当前最优位置和全体粒子的最优位置, 进而更新粒子的速度和位置, 直到满足迭代次数为止。最终得出的粒子群的全局最优位置就是所求所有冲突集的最小碰集。

2.3 构造适应度函数

适应度是评价粒子优劣的唯一指标, 因此构造合适的适应度函数就尤为重要。适应度函数不仅要能够准确评价一个粒子是否为最小碰集, 而且还要尽可能提高粒子群算法的搜索效率。为此, 本文定义的粒子适应度函数如下:

其中, P为粒子群的种群规模, hnum为粒子X和冲突集簇CS中每个冲突集都有交集的二值集合个数, h为粒子X中包含的不同二值集合的数目。

由于本文的算法是为了找出所有的最小碰集, 所以粒子的适应度值越大越好。又因为hnum和h最大值只可能为P, 所以适应度函数最大值为1。在得到最优适应度函数对应的二值矩阵后, 矩阵中每一行对应的二值集合即为一个最小碰集集合。

2.4 提高算法性能的改进措施

a.线性递减惯性权重策略。

Y.Shi和R.C.Eberhart建议在粒子群算法中采用线性递减权重策略[17,18], 如式 (4) 所示, 该策略使得粒子群算法在开始时探索较大的区域, 快速定位最优解的大致位置, 随着wt逐渐减小, 粒子速度减慢, 着重局部搜索。本文采用的办法是将wt初始化为0.9, 并随迭代次数的增加递减至0.4, 以达到较好的全局和局部搜索能力, 并在诊断实例中与wt取常值时的算法性能进行比较。

其中, wint、wend、Tmax分别为初始权重系数、最终权重系数、最大迭代次数。

b.最小碰集保证策略。

为了加速离散BPSO算法的搜索效率并且保证最终输出结果全为最小碰集, 提出最小碰集保证策略, 其主要过程如下。

步骤1 迭代过程中, 以二值矩阵每一行对应的二值集合为操作对象, 通过适应度函数判断其是否为碰集, 若是则转步骤2, 否则, 转步骤3。二值矩阵中全部二值矩阵遍历结束, 算法结束, 保存遍历结果, 继续进行下一次迭代。

步骤2 扫描当前二值集合, 当对应维数为1时, 将其置为0, 再利用适应度函数对其进行适应度评估, 若还是碰集则保留变化, 否则恢复原先数值, 若当前二值集合扫描完成, 操作结束, 转步骤1。

步骤3 扫描当前二值集合, 当对应维数为0时, 将其置为1, 对其进行适应度评估, 若适应度函数值增加则保留变化, 否则恢复原先数值, 若当前二值集合扫描完成或者当前二值集合已为碰集集合, 则操作结束, 转步骤1。

通过最小碰集保证策略, 二值矩阵每一行对应的二值集合全为最小碰集, 它满足最小碰集基本条件, 本身为碰集集合, 并且它的所有子集都不是碰集集合。通过诊断实例验证表明改进算法在收敛速度和全局搜索性能等方面均有很大优势, 并且保证最终输出结果全为最小碰集。

2.5 算法流程

a.初始化粒子群:初始化粒子X为P×N维的随机二值矩阵。对粒子群规模P、惯性权重w、学习因子c1和c2、迭代次数等参数进行初始化设置。定义全局变量xhit来存储所有最小碰集。

b.计算每个粒子的适应值, 选取粒子个体极值Pbestid和粒子群的全局极值Gbestid。

c.按照速度-位置模型式 (1) 、 (2) 更新粒子群的速度和位置, 并根据适应度值更新粒子个体极值和粒子群的全局极值Gbestid, 采用最小碰集保证策略遍历当前二值矩阵, 将粒子中是冲突集CSC最小碰集的粒子添加到xhit。

d.若达到最大迭代次数, 算法终止。输出集合xhit, 即为冲突集簇CS的最小碰集。

3 诊断实例分析

3.1 基于模型的配电网诊断方案

MBD方法的诊断过程主要包括系统建模、冲突识别、候选产生、诊断鉴别4个阶段。借鉴文献[19-20]中的方法, 给出了一个将MBD理论应用于实际配电网的诊断方案, 如图1所示。

a.建立配电网设计原理模型。通过描述系统中元件内部的约束方程、元件与元件之间的连接关系, 建立整个配电网系统的结构、功能和行为模型。建模时采用分层的结构抽象模型方案[21,22], 不仅可以依据此模型诊断出全部系统故障, 而且模型简单实用。

b.冲突识别。针对设计原理模型及观测信息的分布固定不变的特点, 将最小冲突集的搜索问题分为离线搜索最小冲突集候选[23]与在线识别最小冲突集2个步骤。这种策略能够明显减小在线搜索最小冲突集的空间, 使得实际诊断时具有较好的实时性。根据配电网设计原理模型和观测数据, 得到所有最小冲突集。

c.候选产生。通过计算诊断识别过程中得到的最小冲突集的最小碰集, 得到系统的极小诊断候选。本文引入改进的离散BPSO算法用于求解冲突集的最小碰集。

d.诊断识别。通过诊断识别对得到的多个诊断候选作进一步区分, 以获得最佳的诊断结论。依据系统元件的先验故障概率定性值, 采用贝叶斯定理计算所得的侯选诊断的后验故障概率, 并进行故障概率排序, 优先选择故障概率值较大的候选诊断作为故障点。

3.2 基于模型的配电网诊断实例

图2为某10 k V配电网子网, 节点1—7都布置了相应的采集信息装置 (即电压和电流互感器) , 故障发生时, 可准确测量配电网的故障状态信息。母线节点和输电线路的先验故障概率假设如下:母线节点的故障概率均为0.1;输电线路故障概率都为0.4。

采集信息装置, 线路

假设在该配电网中, 线路L23_A和线路L67_B发生短路接地故障, 通过PSCAD软件仿真获得在此故障情况下配电网内的各互感器的测量值, 将电流、电压互感器测得的配电网的故障状态信息, 代入到离线搜索时得到最小冲突集候选MCSC (Minimal Conflict Set Candidate) 所对应的解析冗余关系中, 得到各解析冗余关系的残差如表1所示。其中残差定义为:一条解析冗余关系是从牵引变电站系统模型中得出的只含有系统可观测变量的约束方程, 该方程在给定任意一组观测值后能够被求值, 模型值与实际值之间的差值称为残差。

从表1中选择相对残差r′>0.4的最小冲突集候选, 得到最小冲突集为:MCS:={MCSC1, MCSC8}, 即MCS:={{B3_A, L23_A}, {B7_B, L67_B}}, B3_A表示节点3出现A相故障, L23_A表示节点2与节点3之间导线出现A相故障, 其他类似。

采用改进的离散BPSO算法求解冲突集的最小碰集, 从而得到配电网系统的所有最小候选诊断MHS (Minimal Hitting Set) 。参数设置如下:搜索空间维数为20, 粒子群规模为80, 最大迭代次数为100, 学习因子c1=2.5, c2=1.5。得到最小候选诊断为MHS:={[B3_A, B7_B], [B3_A, L67_B], [B7_B, L23_A], [L23_A, L67_B]}。

最小候选诊断的后验故障概率排序结果见表2。

由表2可知候选诊断[L23_A, L67_B]后验故障概率最大, 因此, 可判断线路L23_A和线路L67_B存在故障, 与假设结果相符。

3.3 算法性能分析

配电网故障诊断实例中, 引入改进BPSO算法求取冲突集的最小碰集, 并对比不同最小碰集搜索算法性能及不同惯性权重策略对算法收敛性的影响。试验机器配置为:CPU P4200 GHz, 内存512 MB, 操作系统Windows XP, 程序使用Visual C++6.0编译。

a.惯性权重对算法性能的影响。

惯性权重w分别取1、0.8以及采用线性递减惯性权重策略, 计算诊断实例中得到冲突集的最小碰集, 搜索结果如表3所示。采用不同的惯性权重策略, 离散BPSO算法均可以搜索到所有的最小碰集, 但是采用线性递减惯性策略明显可以提高算法的收敛性和全局搜索能力, 提高计算效率, 算法性能优于惯性权重取常数的情况。

b.改进策略有效性验证。

为进一步验证离散BPSO算法求取冲突集的最小碰集的可行性, 将离散BPSO算法与HS-Tree算法[7]、Boolean Algebra方法[10]、遗传算法[12]等算法搜索性能进行比较, 引用文献[10]中算例:假设冲突集簇中均有10个最小冲突集, 各最小冲突集分别为{1, 2, …, l}、{2, 3, …, l+1}、…、{n, n+1, …, n+l-1}, 问题规模 (即n+l-1) 分别取5、15、25、…、85, 实验结果如图3所示。

离散BPSO算法对冲突集规模不太敏感, 适用于求解问题规模较大时的情况, 问题规模越大, BPSO算法相对其他最小碰集算法的搜索效率越高。由实验结果可知, BPSO算法有较高的计算效率和较快的收敛速度, 求解时间节省了约1/3~1/2, 尤其HS-Tree算法和Boolean Algebra方法在问题规模达到50时出现了由于内存溢出而终止的情况, 说明算法实现比较繁琐, 而BPSO算法对问题规模并不敏感, 有效避免此种情况的发生。

4 结论

采用基于模型的配电网故障诊断方法, 可以直接利用量测量来判断故障元件, 而不必在故障后根据保护和断路器动作信息来进行故障定位, 具有较好的实时性。以某10 k V配电网为诊断实例, 通过实际建模、编程和实验表明MBD配电网故障诊断方法可以快速准确地诊断出故障元件, 取得较好效果。

粒子群优化算法综述 篇9

PSO在解决许多GO问题上被证明是一种有效的方法;在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。

1 PSO算法原理

在PSO算法中, 首先随机产生一群粒子, 每一个粒子都是搜索空间的潜在解。然后通过迭代寻找最优解。每一个的粒子都有一个适应于种群的适应值 (fitness) , 及决定粒子飞翔的位移和速度。每次迭代后, 粒子下一时刻的速度和位移通过两个“极值”来更新:第一个极值是迭代后粒子本身的最优解, 称为局部最优解;第二个极值是整个种群的最优解, 称为全局最优解。

假设在一个D维的目标搜索空间中, 有m个粒子组成一个群落, 其中第i个粒子的位置表示为, xi= (xi1, xi2, …, xi D) , i=1, 2, …, m;速度表示为vi= (vi1, vi2, …, vi D) 。第i个粒子目前为止搜索到的最优位置为pi= (pi1, pi2, …, pi D) , 整个粒子群的最优位置为pg= (pg1, pg2, …, pg D) 。

PSO算法采用下列公式对粒子操作:

其中i=1, 2, …, m, d=1, 2, …, D;加速因子c1和c2是非负常数, 分别调节个体最好粒子和全局最好粒子飞行的最大步长。若太小, 则粒子可能远离目标区域, 太大则会导致粒子突然向目标区域飞去, 或飞过目标区域。合适的c1和c2可以加快收敛且不易陷入局部最优, 通常令c1=c2=2;r1和r2是介于[0, 1]之间的随机数。粒子在每一维飞行的速度不超过算法设定的最大速度vmax。

公式 (1) 的第一部分表示粒子当前速度对粒子飞行的影响, 这部分提供粒子在搜索空间飞行的动力;第二部分为“个体认知”部分, 表示粒子根据自己的经验飞行;第三部分为“社会认知”部分, 表示粒子通过交流和合作根据社会成员的经验飞行。文献[3]对公式 (1) 作了如下改动:

其中, w是非负数, 称为惯性因子。公式 (2) 和公式 (3) 也叫基本PSO算法。基本PSO算法需要用户确定的参数并不多, 而且操作简单。但是它的缺点是易陷入局部极小点, 搜索精度不高, 因此研究者们对其进行了各种各样的改进。

2 PSO改进算法

2.1 收敛PSO

文献[4]通过对算法的研究, 证明采用收敛因子能够确保算法的收敛。在收敛因子模型中速度的更新公式为:

其中, φ=c1+c2, φ>4, 通常取φ=4.1, 由此计算得χ=0.729。改进后的公式 (2) 和公式 (4) 被称为标准PSO。

文献[5]在对基本PSO算法分析的基础上, 提出了一种能够保证以概率1收敛于全局最优解的PSO算法———随机PSO算法 (Stochastic PSO, SP-SO) , 并利用Solis和Wets的研究结果对其全局收敛进行了理论分析。文献指出当ω=0时, 公式 (2) 、 (3) 描述的进化方程变为:

其中, 粒子的飞行速度只取决于粒子的当前位置xi、历史最好位置pi和粒子群的历史最好位置pg, 速度本身无记忆性。这样, 对于位于全局最好位置的微粒将保持静止。为了改善公式 (5) 的全局搜索能力, 可保留pg作为微粒群的历史最好位置, 而在搜索空间s重新随机产生微粒i的位置xi。

文献[5]通过将式 (5) 改成一个差分方程, 在理论上分析了当c1+c2<2时, SPSO算法的进化方程线性渐进收敛。

2.2 基于拓扑结构的PSO

最早的粒子群优化版本是全局PSO, 它使用全局 (gbest) 拓扑结构, 社会只能通过种群中最优的那个粒子对每个粒子施加影响。实验证明利用全局PSO训练前向神经网络的权矩阵是有效的。但是在全局PSO中, 粒子间的交流不够充分。文献[6]提出了一种局部 (lbest) 拓扑结构。在这种模型中, 每个粒子都和它的邻居进行交流。例如种群中的第5个粒子和第6个以及第7个粒子进行交流。图1是粒子群的全局和局部拓扑结构。

在局部拓扑结构中, 粒子之间的交流相对比较缓慢。如果第i个粒子找到一个比较好的解, 它可以传递给它的邻居j。若粒子k和j连接但是和i没有连接, 只有当j更新后才可能传给k。因为传递的比较慢, 粒子更容易搜索问题空间中的不同地区。

文献[7]根据对人类社会的模拟进而提出了FIPS (Fully-Informed Particle Swarm) , 认为粒子应受所有邻居的影响。对粒子速度用公式 (6) 进行操作:

其中, N是第i个粒子的所有邻居组成的集合, k是粒子i的第k个邻居, pk是粒子k目前找到的最优值。如果N定义为只包含粒子i它自己和它的最优邻居, 公式 (6) 就是标准PSO。在FIPS中, 粒子的速度是根据粒子当前位置和它的邻居目前找到的最优位置之间的加权平均差来更新。

文献[8]在研究了领域拓扑结构对粒子群算法性能的影响后, 设计了两种动态邻域生成策略, 验证不同的邻域拓扑结构和不同的算法模型能够影响粒子群算法的性能。文献[9]提出了一种该改进的PSO算法PSO-DSF。引进有向类无标度网作为粒子群寻优的拓扑结构, 提出作为粒子邻域拓扑的有向网络动态变化机制, 从而提高算法的多样性, 避免过早陷入局部最优的情况。文献[10]提出基于KRTG的动态拓扑结构的粒子群算法研究。从粒子间的拓扑结构出发, 动态地调整种群的拓扑结构, 增加种群的多样性, 使算法收敛于全局最优解。文献[11]提出了一种动态拓扑结构改进PSO算法。在这种结构中, 用了两种方法改进邻居的拓扑结构:随机边缘移植 (Random Edge Migration, REM) 、邻居重组 (Neighborhood Restructuring, NR) 。随机边缘移植是指随机选取一个邻居数目大于1的粒子节点, 移去一个邻居节点, 并把这个邻居节点和另一个随机选取的未满的粒子节点相连接。邻居重组保持粒子的邻居结构在一段时间内固定, 然后重新构造粒子邻居的结构。通过对六个基准函数的实验表明这种方法是一种好的策略, 对每一个函数的测试都取得了令人满意的结果。研究基于拓扑结构的PSO算法一直在持续, 是一个值得研究的方向。

2.3 混合PSO

文献[12]针对带障碍约束的空间聚类, 提出了一种改进的蚁群算法 (IACO) 和混合粒子群算法 (HPSO) 。首先, 使用蚁群算法获得最短的障碍距离, 然后设计了一个带障碍约束的遗传K中心空间聚类分析算法。

文献[13]中, 使用交叉算子和变异算子, 并结合混合粒子群优化算法以及遗传算法解决柔性作业调度问题, 并提出混合整数编程模型。

文献[14, 15]介绍了一种和差分进化 (Differential Evolution, DE) 算法结合的混合PSO算法。在DEPSO中, 传统的PSO操作和DE操作交替的进行, 当迭代次数为奇数时执行PSO算法, 而当为偶数时执行公式 (8) :

其中, r∈[0, 1]是随机数, k∈[1, D]是整数, 用来保证至少在其中一维产生变异, CR是一个交叉常数, δ2是N=2时的一般差分向量δN, 定义如下:

其中, 是一个差分向量用来表示从一个由粒子组成的集合中选取的两个元素的差, 这个集合包括当前所有的个体最优值 (pbest) 。N是包含的元素个数, 在第d维有:

其中, 和从pbest集中随机选取。在一组基准函数上的测试表明DEPSO优于PSO算法和DE算法。在DEPSO中, 如果知道参数之间的关系, 就能确定一个合适的CR, 但这通常需要人们对问题有很深的了解。

2.4 统一PSO

PSO算法的性能依赖于全局搜索和局部搜索之间 (Exploration and Exploitation) 的平衡能力, 即搜索空间的全局搜索能力和快速收敛于有希望的区域的能力, 分别对应全局变量和局部变量。根据这一思想, 文献[16]提出了一种新的PSO结构UPSO (Unified Particle Swarm Optimization) 。为达到全局搜索和局部搜索的平衡, UPSO将全局变量和局部变量合在一个公式里, 从而更新粒子的位置:

其中, u是统一因子, 在[0, 1]之间取值, 用来平衡全局和局部搜索。u=0和1分别对应着局部PSO和全局PSO。Gnid+1表示在全局PSO变量中粒子xi的速度更新, Lnid+1表示在局部PSO变量中粒子的速度更新, 它们分别用下式计算:

其中, k是迭代次数, g (全局变量) 是整个粒子群目前找到的粒子最优位置的下标, gi (局部变量) 是xi的邻居目前找到的粒子最优位置的下标。

2.5 感知PSO (PPSO)

感知PSO (Perceptive Particle Swarm Optimization, PPSO) [17]与传统PSO的搜索过程相似, 不同的是PPSO在n+1维空间搜索, 附加的维是粒子的适应值。一个n维的目标函数在PPSO中被看成n+1维的自然地形 (Physical Landscape) 。在PPSO中引入了三个参数:感知半径、要观察方向的数量和沿着每个观察方向要观察的点的个数。PPSO允许每个粒子有一个有限的感知范围去观测搜索空间, 并且感知在这个范围内的其他粒子的近似位置, 而不是在临近粒子之间直接交换信息。在PPSO中粒子通过采集固定数量要观察的方向和沿着这些方向的有限数量的点观测搜索空间。例如对一个三维的观察空间, 粒子沿着+x, -x, +y, -y, +z, -z六个不同的方向观测搜索空间。

研究表明:较大的感知半径易于群间个体的交流和扩大粒子的搜索空间。因为当在它的感知范围内没有邻居时, 粒子会飞到自己的最好位置。而要观察方向的数量越多, 得到一个好解的机会越大。观察的点的个数越多, 得到的解越精确。但是观测搜索空间需要的时间也越多。为了获得一个满意的解, 这是值得的。

2.6 主要素PSO (PCPSO)

主要素PSO (Principal Component Particle Swarm Optimization, PCPSO) [18,19]中的粒子在两个分开的空间飞行:传统的n维x空间和经过旋转后的m维z空间。PCPSO在x空间使用下面的公式进行迭代:

其中, 表示和z空间相关, 用下式进行计算:

在z空间用下面的公式迭代:

z空间和c空间之间通过标准正交基U~联系:

其中, U满足U'SU=L, L是一个对角矩阵, S是加权协方差矩阵, 是通过主元素分析 (Principal Component Analysis, PCA) 得到的。

和标准PSO相比, PCPSO的优点是时间复杂度比较低, 它一定能在少得多的迭代次数内找到最优解。实验证明PCPSO是一个很有前途的算法, 能降低求解高维函数最优解的时间复杂度。缺点是因涉及数学计算, 对数学基础要求比较高, 不易掌握。

2.7 带时间加速因子的自组织分层的PSO

文献[20]提出了一个新的参变量:随时间变化的加速因子 (Time-Varying Acceleration Coefficients, TVAC) , 目的是在算法前期提高全局搜索能力, 在算法后期促使粒子收敛到全局最优。方法是通过随时间改变加速因子c1和c2来减少个体认知因素而增加社会因素。研究表明在算法初期, 较大的个体认知因素和较小的社会因素使粒子能有更好的全局搜索能力。相反在粒子的后期, 较小的个体认知因素和较大的社会因素, 则能使粒子更好的收敛于全局最优。c1和c2分别用下式计算:

其中, c1i, c1f, c2i和c2f是常量, iter是当前迭代次数, MAXITER是最大允许迭代次数。

另外, 文献对PSO的另一个改进是去掉了公式 (1) 中粒子上一时刻的速度, 研究表明去掉此速度粒子会很快因为缺乏动力而收敛于局部最优, 并停滞不前。为了解决这个问题, 文献中提出了自组织分层的PSO, 提供粒子寻找全局最优的动力。方法是当粒子停滞不前时 (vid=0) , 重新初始化速度向量的系数。实验表明, 和传统PSO算法相比, HPSO-TVAV在单峰和低维函数上表现不时很好, 但是在多维和多峰函数上表现优异。

3 PSO应用

由于简洁易操作的特点, PSO算法一提出就引起了各方面的关注, 关于PSO算法的应用不断出现, 现已广泛应用于函数优化、神经网络训练、工业系统控制、模式识别及其他遗传算法的应用领域。

PSO最早应用时将其应用于神经网络训练。文献[21]将PSO算法用于神经网络集成, 加强了神经网络的泛化能力。文献[22]将PSO算法用于解决优化网页内容描述的问题中。文献[23]将离散PSO算法用于求解TSP问题;文献[24]提出一种将PSO算法用于文本知识发现的方法;文献[25]将PSO算法用于多目标问题的求解;文献[26]将PSO算法用于人脸识别中。文献[27]则将PSO算法用于软件结构测试数据自动生成也取得了良好的效果。文献[28]将BPSO算法应用于特征选择中, 提出了一种不基于分类器的特征选择方法。

总之, 在解决复杂问题时, PSO算法被证明是一种有效的方法, 已被应用于各个研究领域。

4 PSO展望

PSO是一种新兴的有潜力的基于群智能的演化计算技术。自从2002年PSO算法被引进国内[27], 已经有很多学者对PSO进行了研究。虽然已经取得了一些研究成果, 但是仍然有许多问题值得关注。

4.1 算法的理论基础

PSO算法在实际应用中已被证明是一种有效的优化工具, 已广泛的应用于科学研究和工程实践, 但是其内部机理仍不明确, PSO算法缺乏数学理论支持。PSO的改进算法及其应用也都停留在实验阶段。文献[4, 5]对算法的收敛做了一定的分析, 但是对于这样一个年轻有潜力的算法, 还远远不够。所以开展一些理论研究, 不仅可以加深对PSO算法内部机理的认识, 而且对于扩展PSO的应用领域也有深远意义。

4.2 拓扑结构

文献[7-11]对拓扑结构的研究表明一种好的拓扑结构能有效地改善算法的性能, 并且能在许多优化问题上取得非常不错的结果。寻求一种好的拓扑结构, 加强PSO算法的泛化能力, 使其能在多数优化问题上取得满意的结果, 并不是不可能。

4.3 参数调整模型

尽管目前已经有许多PSO算法的改进版本, 但是都各有优缺点。如何针对问题的不同特点, 构造一个参数调整模型, 达到平衡粒子的全局搜索能力与局部搜索能力, 避免粒子早熟收敛, 对工程应用有十分重要的意义。

4.4 与其他方法结合

PSO算法虽然是一种有效的优化工具, 但同样有其不足, 如迭代后期搜索能力不够, 早熟收敛等。所以, 如何将其他算法引进PSO算法, 以弥补其不足是一个重要方向。

4.5 算法应用

科学与工程实践中的许多问题都可以归结为优化问题。所以如何将PSO算法与实际问题结合, 将会有力的推动PSO算法的发展。

摘要：粒子群优化 (PSO) 算法是一种基于群智能方法的演化计算技术, 通过粒子间的相互作用发现复杂搜索空间中的最优区域, 优势在于简单容易实现而且功能强大。由于它简单易操作的特点, PSO一提出, 立刻引起演化计算等领域学者们的广泛关注, 并在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。介绍了基本的PSO算法、若干类改进的PSO算法及其应用。

离散粒子群优化算法 篇10

在现代电力系统中，随着电网规模的不断扩大，机组单机容量的增加，以及快速励磁系统的投入，低频振荡问题已经成为影响互联电力系统稳定的重要原因之一。同时，低频振荡也是一个向远距离输电线路上增加输电容量的严重瓶颈。低频振荡的发生是由于在电力系统中，发电机经输电线路并列运行时，在小扰动作用下，发电机转子之间会发生相对摇摆，这时电力系统如果缺少必要的阻尼就会失去动态稳定。由于电力系统的非线性特性，动态失稳表现为发电机转子之间的持续的振荡，同时输电线路上功率也会发生相应的振荡，影响了功率的正常输送。由于这种持续振荡的频率很低，一般在0.2～2.5 Hz之间，故称为低频振荡[1]。其振荡时产生的能量通过机电联系来传递，因此又称为机电振荡，表现为发电机电功率和功角的变化。低频振荡严重时会导致系统解列或失去稳定。

为了抑制低频振荡，提高电力系统的动态稳定性，可以采用附加控制信号，通过励磁系统提供附加的正阻尼，以补偿原来的负阻尼，使得系统总的阻尼为正值。通过在发电机励磁系统中加装电力系统稳定器PSS(Power System Stabilizer)为系统提供正阻尼是抑制低频振荡的有效措施，合理配置PSS的参数可以取得理想的系统动态性能，提高系统的稳定性。

目前，国内外学者在PSS参数优化协调方面做了一定的研究工作。多种优化算法如遗传算法、免疫算法、进化规则和粒子群算法已经对PSS的参数进行了优化[2,3,4,5,6]，并且起到了一定的优化效果，但是都存在可操作性差、收敛性差、容易陷入局部极值等缺点。

粒子群算法PSO(Particle Swarm Optimization)是美国Kennedy和Eberhart博士受鸟群觅食行为的启发，于1995年提出的一种生物进化算法[6]。PSO算法采用速度-位置搜索模型，每个粒子代表解空间的一个候选解，粒子在搜索空间以一定的速度飞行，飞行速度根据飞行经验进行动态调整。每个潜在解与粒子运行速度相联系，该速度不停地根据粒子经验以及与该粒子邻近的粒子经验来调整大小、方向，总是希望粒子能朝着更好的方向发展。因此，在搜索过程中全局搜索能力与局部搜索能力的平衡关系对于算法的成功起着至关重要的作用。

惯性权值自适应的粒子群算法PSO-ω(Particle Swarm Optimization)是在全局搜索与局部搜索平衡特性的基础上，得到的一种具有较好的全局搜索能力和寻优速度的群体智能优化算法。在标准PSO算法中,惯性权值ω是平衡算法的全局搜索能力和局部搜索能力的关键参数。PSO-ω算法中，惯性权值ω采用了自适应的方式，以达到更好的全局搜索能力。

本文在前述PSS优化研究工作的基础上，提出了一种PSO-ω算法的PSS设计，在这种方法中，不同于以往只寻找机电振荡模式下阻尼比最小的PSS优化方法[2,3,4,5,6]，根据最优控制原理综合考虑PSS与励磁系统的性能，优化的控制目标设为系统输出按最小误差跟踪给定值的能力，将PSS参数优化协调转化为带有不等式约束的优化问题。用PSO-ω算法对该问题求解，不易使问题的解收敛于局部最优解，并且可以提高寻优速度，从而能够对系统所装PSS的参数进行很好优化，同时证明了该算法的有效性和优越性。再通过Prony[7,8]特征值分析以及故障测试的仿真，验证了所设计PSS的有效性和鲁棒性。

1 PSS的设计

1.1 电力系统模型

电力系统的数学模型用非线性微分方程组表示如下：

式中：X为状态变量向量;U为控制变量向量。

加装PSS后，系统在小扰动情况下，根据李雅普诺夫线性化方法，把描述系统动态特性的微分-代数方程组在平衡点(稳定运行点)处线性化，得到电力系统的状态方程为：

式中：A、B为平衡点估计值;∆X为状态变量的偏差量;∆U为控制变量的偏差量。

1.2 PSS模型

本文PSS采用超前-滞后校正模型，以发电机的转速偏差∆ωp为输入信号，传递函数如下：

式中：U为发电机的PSS输出信号;Tw为隔直环节的时间常数;T1、T2、T3、T4为超前-滞后环节的时间常数;K为PSS增益。

1.3 PSS优化的目标函数和约束条件

目前，大多数PSS优化问题仅仅是寻找机电振荡模式下阻尼比最小的参数，无法综合考虑PSS与励磁系统的性能。而根据最优控制原理，对有约束最优化问题借助于Pontryagin极小值原理[11,12]，控制目标可描述为系统输出按最小误差跟踪给定值的能力，这样就考虑了综合性能指标，实现抑制系统中有功功率、频率等量的振荡，使其保持稳态值。

从动态角度考虑，ITAE准则在处理误差绝对值与时间乘积的积分时，兼顾了受扰动时系统在振荡过程中及趋于平稳时的输出误差[11,12]，故本文选择它作为PSS作用效果的目标函数，误差为各转子角速度与它们各自稳态值的相对误差绝对值之和。对于单目标最优化问题，选取目标函数如下：

式中：ω1(t)为发电机在t时刻的转子角速度;ωs1为发电机转子角速度的稳态值;1a为可调权重因子。

考虑到PSS中各参数的限制，PSS设计问题可以表述为如下带约束的优化问题：

式中：K、T1、T3为待优化的参数。参数K的典型取值范围是[0.1,1000]，T1的典型取值范围是[0.01,1.0]，T3的典型取值范围是[0.01,1.0]，Tw、T2、T4为给定值。

2 粒子群优化算法

2.1 PSO算法的基本原理

PSO算法是从生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成D维搜索空间上的一个点，我们称之为“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整，所有的粒子都有一个被目标函数决定的适应值，并且知道自己到目前为止发现的最好位置(记为Pbest)和当前的位置。这个可以看作是粒子自己的飞行经验，除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(记为Pbest)，这个可以看作是粒子的同伴的经验。每个粒子使用下列信息改变自己的当前位置：1)当前位置;2)当前速度;3)当前位置与自己最好位置之间的距离;4)当前位置与群体最好位置之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个种群中，以迭代的方式进行的。

假设在M维搜索空间(解空间)里，有s个粒子组成的粒子群，其中第i个粒子位置可以表示成M维向量，xi(n)=[xi1,xi2,…,xij,…,xiM]，j表示变量ix的第j维分量;粒子的飞行速度为iv(n)=[vi1,vi2,…,vij,…,viM];该粒子所经历的个体最佳位置可表示为ip(n)=[pi1,pi2,…,pij,…,piM];在整个粒子群中，所有粒子经历过的最佳位置为g i(n)=[gi1,gi2,…,gij,…,giM]，当第i个粒子从n-1代迭代到n代时,可采用下式进行其速度和位置的更新[6]：

式中：ω为惯性权值;Rand为在[0,1]范围内变化的随机数;n为迭代次数;粒子数i=1,2,…,s。

2.2 PSO-ω算法的基本原理

针对PSO算法搜索性能取决于对全局搜索和局部搜索能力的平衡这一特性，本文在其基础上进行改进，提出了一种具有较好的全局搜索能力和寻优速度的PSO-ω算法。

在PSO-ω中，惯性权重采用自适应的方式：

Maxit:最大迭代数;iter：迭代数;

其算法流程如下:

1)t←0;

2)初始化：在搜索空间均匀随机地产生s个初始位置，

3)评价：计算每个粒子个体的位置(解)的目标函数值;

4)比较粒子的适应值和自身最优粒子pbest的适应值，如果当前值比pbest更优，则以当前粒子替换pbest;

5)比较粒子适应值与种群最优值，如果当前值比gbest更优，则置gbest为当前粒子的矩阵下标和适应值;

6)位置更新：按式(8)和式(9)更新粒子的位移方向和步长,产生新种群X(t+1);

7)t←t+1;

8)若不满足进化结束条件,则转3),否则转8);

9)输出结果。

3 PSS参数优化与仿真结果

3.1 PSS参数优化结果

为了检验PSO-ω算法的性能以及PSS参数优化对系统暂态稳定的作用，本文使用Matlab7.0的电力系统仿真模块集Sim Power Systems Blockset(SPB)，对标准的单机无穷大系统进行PSS参数优化和系统性能仿真。

单机无穷大系统仿真模型如图1所示，图中参数均为标么值，其额定容量均为200 MVA，并且均配有自并励静止励磁系统。其中Tw=5,T2=0.05,T4=0.05[7]。通过采用种群大小为100、进化代数为100的PSO-ω算法对Kp、T1、T3三个参数进行优化，且与在相同条件下的全面学习粒子群算法(CLPSO)[6]参数优化结果进行了比较。表1为两种优化算法的参数优化结果。图2所示是在随机选取初始解的条件下，随着进化代数的增加，PSO-ω算法搜索到相对最优参数对应的ITAE变化曲线。

表2为单机系统特征值，单机系统在无PSS时阻尼比为0.062 3，系统是处于临界稳定的状态，安装PSS后系统稳定，但是机电振荡模式下的阻尼比比较小，为0.15。用PSO-ω算法优化后的PSS的阻尼比提高到0.409 0，较大程度地提高了系统的阻尼。

3.2 动态仿真结果分析

为了评价基于PSO-ω算法优化的PSS性能，对系统励磁系统参考电压加5%的扰动、系统发生三相短路、三相断路故障的情况下，对配置了采用CLPSO、PSO-ω算法优化的PSS系统进行动态仿真。

3.2.1 小扰动情况下PSS有效性分析

机端电压参考值加5%方波电压阶跃，对比不同算法得出的PSS对提高静态稳定性的作用。

图3是测试励磁系统参考电压在12 s时发生5%的扰动并持续0.5 s的结果。这种干扰情况会使发电机机端电压产生变化，从而影响系统的暂态稳定。从图中可以看到采用PSO-ω算法优化的PSS，转子角速度摆动幅度比较小，发电机的转子角速度在12.7 s时达到稳定。与其比较，CLPSO算法优化的PSS的发电机在14.5 s才达到稳定。

图4所示为机组的电磁功率动态响应曲线。图中可见采用PSO-ω算法优化的PSS，电磁功率摆动幅度较小，发电机的电磁功率在12.5 s时达到稳定。与其比较，CLPSO算法优化的PSS的电磁功率在14.6 s才达到稳定。

3.2.2 大扰动情况下PSS有效性分析

对于PSS的暂态性能，通过发电机出口t=12 s发生三相短路和t=1 s发生三相断路故障的情况下进行仿真。

图5、6为三相短路故障持续0.1 s后重合闸成功后转子角速度和电磁功率变化的结果。图7、8为三相断路故障持续0.1 s后转子角速度和电磁功率变化的结果。从图中可见采用PSO-ω算法优化的PSS，转子角速度和电磁功率摆动幅度较小，发电机转子角速度、电磁功率达到稳定的时间均比CLPSO算法优化的要快。所以PSS能够很快地平息低频振荡，提高了转子的暂态特性。

4 结论

本文在Matlab环境下，将PSO-ω算法用于单机无穷大系统PSS的参数优化问题。不同于以往只寻找机电振荡模式下阻尼比最小的PSS优化方法，本文根据最优控制原理综合考虑PSS与励磁系统的性能，优化的控制目标设为系统输出按最小误差跟踪给定值的能力，将PSS参数优化协调转化为带有不等式约束的优化问题。通过采用电力系统仿真模块集SPB，单机无穷大系统进行PSS参数优化和系统动态性能仿真。仿真结果表明，经PSO-ω算法优化的PSS在不同的干扰下都具有良好的性能，采用Prony分析法提出的特征值也验证了系统阻尼得到了提升，从而使系统的低频振荡现象得到了很好抑制。对PSO-ω算法采用惯性权值ω自适应的方式，达到了全局搜索与局部搜索平衡的特性，是一种具有较好的全局搜索能力和寻优速度的群体智能算法。

摘要：粒子群算法(PSO-ω)是一种应用于连续空间的、具有较好的全局搜索能力和寻优速度的群体智能优化算法。基于单机无穷大系统模型,通过采用PSO-ω算法对电力系统稳定器(PSS)进行参数优化,以抑制低频振荡。该方法是以最优控制原理为基础,综合考虑PSS与励磁系统的性能,将PSS参数优化协调转化为带有不等式约束的优化问题,控制目标为系统输出按照最小误差跟踪给定值的能力(ITAE准则)。用Matlab软件进行仿真,结果表明,利用该方法设计的PSS,它的稳定性有了较大的提高。