小生境离散粒子群算法

小生境离散粒子群算法（精选6篇）

小生境离散粒子群算法 篇1

1小生境 PSO 算法

小生境(Niche)是来自于生物学的一个概念,是指特定环境下的一种生存环境。生物在其进化过程中,一般总是与自己相同的物种生活在一起,共同繁衍后代,这些生物赖以生存的环境资源,称为小生境。人们把这种思想提炼出来,运用到优化算法中来。优化算法实现小生境的方法最早由Cavicchio于1970年提出,该方法叫做基于预选机制的小生境方法[1];1975年DeJong提出了基于排挤机制的小生境实现方法[2];Goldberg在1987年提出了基于共享机制的小生境实现方法[3]。随着研究的深入,越来越多的小生境实现方法被提出,小生境在优化算法中的应用也越来越广泛。文献[4]提出了小生境粒子群优化算法。在标准PSO算法中,种群中的粒子会不断向当前最优位置靠拢,算法迅速收敛,但同时种群的多样性也快速下降。在NPSO算法中,若某个粒子在连续几代的进化过程中,适应度值只有很细微的变化,那么该粒子和它的邻居将就会形成一个小生境粒子群,该粒子是这个小生境粒子群的中心。具体算法如下:

Step1:初始化主粒子群,并设置小生境的参数。

Step2:主粒子群中的粒子进行速度、位置和适应度值的更新。

Step3:对每个小生境粒子群中的粒子进行速度、位置和适应度值的更新。

Step4:根据小生境半径的设置,查看是否有需要合并的小生境粒子群。

Step5:查看主群中是否有粒子进入了小生境范围,若有,则将该粒子吸收进入小生境粒子群中。

Step6:搜索主群中是否有满足产生新的小生境的条件的粒子,若有满足条件的粒子,则建立以该粒子群为中心的新的小生境子粒子群。

Step7:返回至Step2,直到满足算法终止条件。

NPSO算法实现过程中,需要输入两个参数μ和δ ,μ是判断子群是否合并的阈值,δ是判断子群是否产生的阈值,算法的实现效果依赖于参数的设置。在文献[5]中,小生境子粒子群的合并依赖于参数μ,如果该参数的选择不合适,算法很容易将处在不同山峰上的两个小生境子群合并,造成寻优效率下降;在文献[4]中,新的小生境子群的产生依赖于给定的 参数δ,不同的参 数其算法 性能也不同,算法需要先验知识才能保持其稳定性。

2改进的小生境粒子群优化算法

在NPSO进化过程中,需要根据参数μ和δ的设定进行。若有一种简单的方法能够判断两个粒子是否在同一个山峰上,此方法可以大大提高NPSO算法的收敛速度和收敛性能,也可以避免算法过于依赖参数设置。文献[6]设计了一个hill-valley函数,能够判别搜索空间的任意两点是否在同一个山峰上。将此函数应用到遗传算法上可求解多峰值问题,本文将此函数与NPSO算法相结合,进行多峰函数的求解。

设搜索空间的任意两点e1和e2,hill-valley(e1,e2)为判断e1和e2是否在同一山峰上的函数,若e1和e2不存在适应度值同时小于e1和e2适应度值的内点,则e1和e2在同一个山峰上,hill-valley函数的返 回值为0,否则hillvalley函数的返回值为非0值,则e1和e2不在同一个山峰上。e1和e2之间的内点由抽样向量samples确定:

其中,j=1,…,L,L是抽样向量samples的长度,本文中L的取值为5。

一维hill-valley函数如图1所示,图中e1、e2之间的内点i1、i2的适应度值均大于e1和e2的适应度值,不存在适应度值小于该两点的内点,判定e1和e2在同一个山峰;图中e3和e4之间的内点i3、i4、i5、i3的适应度值大于e3和e4的适应度值,而i4、i5的适应度值小于e3和e4的,故e3和e4 不在同一 座山峰上。 将上述hill-valley函数应用 到NPSO算法中,解决NPSO算法依赖参数设置的弊端,新算法称为改进的小生境粒子群优化算法(ImprovedNicheParticleSwarmOptimization,INPSO)。算法具体 实现如下:

Step1:参数设置及主粒子群的初始化,主粒子群以认知模型进行更新。

Step2:判断主粒子群中的每一个粒子xi是否为潜在的最优解,如果是,则产生一个以xi为中心的小生境子粒子群。判断最优解时,设粒子xi的适应度值变化为σi,在算法进化过程中若在连续几代(本算法中设置是5代)内均满足σi <δ(δ设定的一个很小的阈值),则产生新的小生境子群。

Step3:对每一个子群中的粒子进行迭代。

Step4:对所有子群进行合并操作,当任意两个子群的最优粒在同一个山峰时,合并这两个子群。假设子群Di(i≥1)的最优粒子xm,子群Dj(j≥1)的最优粒子xn处于同一山峰时,即hill-valley(xm,xn)=0时,合并两个子群。合并后的子群粒子数目变大,保留适应度值较好的R个粒子,其余粒子移到主粒子群中。

Step5:对每个子群进行吸收粒子的操作,主群中的粒子xm移动到小生境的Di(i≥1)范围内,即对于任意xm∈Di都有hill-valley(xm,xn)=0,且Di中的粒子 数目小于R,则粒子xm被吸收到小生境子粒子Di中,若Di中的粒子数目等于R,用xm替换Di中适应度值最小的粒子。

Step6:判断是否满足终止条件,若不满足转到Step2。

3实验分析

为了验证INPSO算法的有效性,针对3个典型的多峰函数做了两组实验,第一组实验测试算法能否搜索到多峰函数的所有山峰;第二组实验测试算法的精度。测试函数如下:

(1)f1(x)=xsin(10πx)+2.0,x∈ (-1,2)。该函数具有17的局部最大值,这些峰值大小不等,间隔相等,当x =1.850549时,函数有全局最大值[7]为3.850274。

函数具有19个局部极大值,当x=-7.0835、-0.8003、5.4829时,函数有3个全局最大值:14.508008。

(3)f3(x,y)=cos(x)2+sin(y)2,x∈ (-5,5),y∈(-5,5)。函数具有12个局部极大值2。

测试中的参数设置 为:迭代次数50,惯性权重 ω =0.729 ,学习因子c1=c2 =1.49,实验结果为30次独立实验的平均值。

第一组实验是为了验证新算法的有效性,函数f1和f2 的初始种群规模为100,函数f3的初始种群规模为80。

3个函数运行的结果如图2所示,其结果是30次运行结果的平均值。图中星星表示粒子,a、b、c图是函数的图形表示,d、e、f图是小生境子群中最优粒子在图形中的位置。d图是函数f1的运行结果,基本上最优的粒子都爬到了山峰的顶端。e是函数f2的运行结果,所有的峰值都有粒子。f1 和f2是的维度是一维,函数f3的维度设定为二维。f图是函数f3的俯视效果图,图上的白色星星表示粒子。从图形上可以看出粒子处在山峰的顶端位置,本算法能够找到所有的峰值。因此,本算法对多元函数仍然适用。

第二组实验是为了验证新算法的有效性,将本文所得测试结果与NPSO算法[8]所得结果进行对比分析。参数的设置和第一组实验中的参数设置基本相同,个别参数设置如表1所示。本文INPSO算法不需要设置参数,是否合并两个子群由hill-valley判断两个子群中的最优粒子是否在同一山峰上实现。两种算法的实验对比结果如表2所示。

从实验结果可知,本文提出的INPSO与文献[8]提出的NPSO算法在一维函数f1和f2上都得到了较好的结果,收敛率是100,而在二维函数运行上INPSO算法每次都能搜索到函数的全部峰值,而NPSO算法只有26次找到全部峰值,收敛率87%。另外,INPSO算法搜索到每个峰值的平均位置偏差要比NPSO算法要小,说明本文提出的INPSO算法的精确度高于NPSO算法。

4结语

本文引入一个函数判断两个粒子是否在同一座山峰上,克服了NPSO算法需要输入两个参数的弊端。通过对3个典型函数的优化实验可以看出,本文所提出的算法能够找到多峰函数的所有峰值,并且在平均偏离度和收敛率上都优于NPSO方法,是一种有潜力的优化方法。改进后的小生境粒子群算法有更强的全局搜索能力和更高的收敛速度,能够高效地寻找到多个全局最优值是一种寻优能力、效率和可靠性更高的优化算法,其综合性能比基本NPSO算法有显著提高。

摘要：传统的小生境粒子群优化算法(NPSO)需要两个参数的输入,一个是判断子群合并的阈值,另一个是子群产生的阈值。参数设置的不当,将直接影响计算结果。引入一个函数判断两个点是否在同一座山峰上,以克服NPSO算法需要输入参数的弊端。在程序运行时,无须严格限定小生境的半径,也不需太多的先验知识。实验结果证明,该算法合理有效,能够能快速有效地找到多峰函数的全局最优点。

关键词：小生境,NPSO算法,粒子群优化算法,多峰值函数

小生境离散粒子群算法 篇2

微粒群优化算法PSO属于群体智能方法的一个分类,是1995年首次由Kennedy与Eberhart等首次提出的[1],是一种新的进化算法。但当面临复杂的优化问题,由于目标存在很多的局部极值,也不可避免地存在早熟、收敛速度慢等一些缺陷。

本文针对这一问题,提出以全局性更好的小生境策略,小生境中各个子种群互相排斥,动态形成自己独立的搜索空间,各自追逐自己搜索范围内的极值点,使小种群在搜索空间有效地分布,避免了协同中的种群汇聚;进一步引入淘汰更新机制,迭代一定次数后更新最劣子种群,以保证整个种群不断向前进化,直至搜索到全局最优点;引入变尺度混沌变异,进一步提高了本文算法的搜索精度。

2004年Sun等在研究了Clerc等人关于粒子收敛行为的研究成果后,从量子力学的角度提出了一种新的PSO算法模型。认为粒子具有量子行为,并根据这种模型提出了量子粒子群算法(QPSO)[2],并且得到了很好的实验效果。

1 粒子群和量子粒子群算法

1.1 粒子群算法(PSO)

由Kennedy和Eberhart提出的PSO算法[3],是将寻优的参数组合成群体,通过对环境的适应度来将群体中的个体向好的区域移动。与其他进化算法不同,个体没有体积的微粒(点),结合微粒的历史最佳位置和群体历史最佳位置信息,以一定的速度向目标值逼近。

1.2 量子粒子群算法(QPSO)

从量子力学的角度提出了一种新的PSO算法模型[4,5]。认为粒子具有量子行为,并根据这种模型提出了量子粒子群算法(QPSO),在量子空间中粒子的满足聚集态的性质完全不同,它可以在整个可行解空间中进行搜索,因此QPSO算法的全局搜索的性能远远优于标准PSO算法。在量子空间中,粒子的速度和位置是不能同时确定的。通过波函数来描述粒子的状态,并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数,又通过蒙特卡罗随机模拟方式得到粒子的位置方程。在具有量子行为的粒子群优化算法中,粒子的主要迭代公式:

undefined

Pid=ϕ*Pid+(1-ϕ)*Pgd ϕ=rand (2)

xid=Pid±β*|mbest-xidundefined

这里mbest是粒子群pbest的中间位置,Pid为Pid和Pgd之间的随机点,ϕ和μ都是[0,1]的随机数,β为QPSO的收缩扩张系数。

QPSO的算法流程可以这样描述:

(1) 初始化粒子群;

(2) 根据公式(1)计算mbest的值;

(3) 求每一个粒子的适应度值,比较求出Pid;

(4) 对于每一个粒子比较Pid,求得Pgd;

(5) 更新Pgd;

(6) 对于粒子的每一维,根据公式(2),在Pid和Pgd之间取得一个随机点;

(7) 根据公式(3)获得一个新的位置;

(8) 重(2)～(7)直到条件不满足,则迭代过程结束。

2基于混沌变异算子的小生境量子粒子群算法

2.1 RCS小生境进化策略

小生境策略以其能有效解决多峰函数优化问题而广泛应用于进化算法[6]。本文采用文献[7]提出的RCS(Real time Control System)策略作为构造小生境的基础。通过控制子种群之间的排挤和竞争,使各个子种群在进化中动态形成各自独立的搜索空间,从而实现对多个局部极值进行同步搜索,避免了算法的早熟收敛。

算法中的小生境半径定义了各个子种群独立的搜索空间,一旦某个小生境最优个体进入了其他小生境的搜索空间,则重置该个体,并在其所在的小生境内重新选择最优个体。从而使每个小生境子种群自然形成,减少了标准PSO算法和QPSO算法的所有个体作为整体种群陷入局部最优的概率。

2.2 变尺度混沌变异

混沌是自然界广泛存在的一种非线性现象,具有随机性、遍历性、初始条件敏感性等特点,已被广泛应用于随机优化[8],在局部寻优领域具有优越的性能。本文使用的混沌映射Logistic迭代方程为:

βundefined=μβundefined(1-βundefined) k=1,2,… (4)

β∈(0,1) β≠0.25,0.5,0.75

其中βundefined是对应于粒子Xundefined的第j个混沌向量,当μ=4时,logistic方程完全进入混沌状态。经过多次试验可以证明,利用混沌的遍历性,可以很好地实现局部搜索。

在寻优的过程中,对每个小生境的种群最优个体进行混沌迭代变异,变异空间随着代数的增加而逐渐减小。对第i个种群的最优个体Pibest=[x1,x2,…,xj,…,xn]进行混沌变异最优粒子Pnbest变量的搜索空间随着代数的增加而围绕小生境的极点逐渐缩小。这样,在进化初期变异尺度大,有利于算法在广阔的空间搜索全局最优解;在进化后期变异尺度小,在小空间内紧紧围绕局部极点精细搜索,有利于提高解的精度。

2.3 基于混沌变异算子的小生境量子粒子群算法

结合小生境策略全局优化与变尺度混沌变异精细搜索各自的优点,本文提出一种全新的粒子群算法,并在算法中引入了种群淘汰策略,结合小生境的子种群竞争策略一起使用。运行中首先利用RCS竞争策略,使各个小生境子种群形成独立的搜索空间,追逐不同的极值点;然后每隔一定代数,对陷入局部最优的最劣子种群进行随机初始化。这样可使种群在不断的竞争和更新中向前进化,从而避免了算法早熟收敛,保证了收敛到全局最优。而没有更新的小生境种群继续向前进化,又保证了搜索精度的连续提高。NCQPSO(Niche Chaotic mutation Quantum-Behaved Particle Swarm Optimization )算法具体流程如下:

(1) 初始化小生境粒子种群;

(2) 计算粒子适应度,找出每个小生境种群中的最优粒子;

(3) 实施RCS小生境淘汰选择进化策略,确定每个小生境独立搜索空间的最优个体;

(4) 如果迭代次数到达一定代数,则对最劣的小生境子种群进行更新初始化;

(5) 对所有小生境子种群的最优个体实行变尺度的混沌变异,进一步提高搜索的精度;

(6) 对每一个小生境子种群独立进行QPSO优化;

(7) 如果满足条件,则停止迭代,输出最优解,否则转向(2)。

3 实验结果和分析

为了测试基于混沌变异小生境的量子粒子群算法(NCQPSO)的性能,本文使用了3个典型测试函数来进行实验,并且将实验的结果和标准的PSO和原始的QPSO算法进行比较。所用函数如图1所示,Rosenbrock函数是一个经典复杂优化问题,其全局最优点位于一个平滑、狭长的抛物线形山谷内,由于函数仅仅为优化算法提供了少量信息,使算法很难辨别搜索方向,找到全局最小点的机会微乎其微,因此,Rosenbrock函数通常用来评价优化算法的执行效率。Rastrigrin和Griewank函数是典型的非线性多模态函数,它们具有广泛的搜索空间、大量的局部极小点和高大的障碍物,通常被认为是遗传算法很难处理的复杂多模态问题。表1给出的是3个测试函数的初始空间,以及理论值,维位置的上限。

本文比较了NCQPSO算法和标准的PSO算法,原始的QPSO 算法对于基准函数测试的结果。算法的粒子种群为25,分为5个子种群,每个子种群的粒子数是5。标准PSO的参数的设置如下:

c1=c2=2 wmax=0.9 wmin=0.1

算法统一的迭代的次数定为2000次,2000次以后认为算法停滞。各个算法分别运行50次,取平均结果来表示算法对函数测试的结果。与此同时,将各个种群的空间维数固定为20,以便于各个算法进行比较,同时设小生境的半径Rnich为10-4。另外还将在50次运算当中成功找到最优解的次数作为解的稳定性的衡量。

从表2可以看出NCQPSO与另外两种算法相比较具有更加优秀的搜索最优解的能力,即拥有更高的稳定性和更加精确的搜索精度。为了进一步说明NCQPSO的优越性,本文给出几种算法对于Rosenbrock函数的测试曲线,如图1所示。

4 结 论

本文算法利用广泛应用于多目标函数优化的小生境策略掌控粒子群的全局搜索方向,其竞争策略使子种群在搜索过程中自动追寻不同的极值点,形成不同的搜索空间;淘汰策略则使子种群不断更新。两种策略的有机结合,成功地避免了算法的早熟收敛,提高了全局寻优能力;变尺度混沌变异的引入,则显著提高了算法的搜索精度。实验结果表明,与传统的PSO算法和QPSO算法相比,本文算法寻优能力强、搜索精度高、稳定性好,适用于处理高维多极连续函数的优化问题。

摘要：针对粒子群算法早熟收敛和搜索精度低的问题,提出了基于混沌变异的小生境量子粒子群算法(NCQPSO)。该算法结合小生境技术并加入了淘汰机制。使算法具有良好的全局寻优能力。变尺度混沌变异具有精细的局部遍历搜索性能。使算法具有较高的搜索精度,实验结果表明,NCQPSO算法可有效避免标准PSO(Particle Swarm Optimization)算法的早熟收敛,具有寻优能力强、搜索精度高、稳定性好等优点。也优于原始的量子粒子群算法QPSO(Quantum-behaved Particle Swarm Optimization)。

关键词：混沌变异,小生境,粒子群优化算法,量子粒子群优化算法

参考文献

[1]Kennedy J,Eberhart RC.Particle Swarm Optimization[A].Proceed-ings of the IEEE Service Center,1995:1942-1948.

[2]Sun J,Feng B,Xu WB.Particle SwarmOptimization with Particles Hav-ing Quantum-Behavior[A].Proceedings of 2004 Congress on Evolu-tionary Computation,2004:325-331.

[3]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C].Proc of Int’1 Symp on Micro Machine and Human Science.Pis-cataway,IEEE Service Center,1995:39-43.

[4]Sun J,Xu WB.A Global Search Strategy of Quantum-behaved ParticleSwarm Optimization[A].Proceedings of the IEEE Congress on Cyber-netics and Intelligent System,2004:111-116.

[5]Maurice Clerc,James Kennedy.The Particle Swarm:Explosion,Stabili-ty,and Convergence in a Multi-Dimensional Complex Space.IEEETransactions on Evolutionary Computation,2002:58-73.

[6]陈辉,张家树,张超.实数编码混沌量子遗传算法[J].控制与决策.2005,20(11):1300-1303.

[7]Lee C G,Cho D H,Jung H K.Niche genetic algorithm with restrictedcompetition selection for multimodal function optimization[J].IEEETrans on Magnetics,1999,35(3):1122-l125.

小生境离散粒子群算法 篇3

为了降低配电网网损,提高电网经济效益,要对配电网络进行优化。配电网重构在配电网络优化中具有降低网损、提高供电电压质量、消除过载等作用。中国配电网络馈线负荷分布很不均匀,电压质量不高,因此配电网重构目标函数不能是单一的,需要将降低配电网网损、提高供电电压质量以及负荷分布均衡化等目标函数综合起来考虑,建立多目标函数模型。配电网重构的研究目标大部分以降低网络损耗为主要目标函数,部分文献将几个目标函数综合起来研究。但这些多目标函数优化算法不能找到较好的全局最优解,计算速度慢,受参数影响较大。如遗传算法、蚁群算法、禁忌搜索性法、模拟退火算法等人工智能算法[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.

小生境离散粒子群算法 篇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

空间遥感技术自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.

小生境离散粒子群算法 篇6

参数辨识主要有基于残差灵敏度分析和增广状态估计法, 由于直接将支路参数作为状态变量增广到状态估计中进行计算易于处理, 在实际应用中较为广泛[7,8,9]。 但该方法容易导致系数矩阵条件数过大, 降低了程序稳定性。 文献[10]用可疑支路潮流补偿量代替支路参数来做参数辨识, 一定程度上改善了数值稳定性。 文献[11]利用粒子群 (PSO) 算法对参数辨识进行求解, 但该方法运行效率不高, 难于直接用于实际电网。 非线性内点法[12]和PSO算法在WLAV参数辨识的应用已取得了一定的经验和成果。 前者具有收敛性好、鲁棒性强的优点, 但难于处理变压器档位等离散变量;后者具有很强的离散变量处理能力和全局收敛的优点, 但寻优速度慢, 使得其单独在参数辨识的应用受到限制[13]。文中将原- 对偶内点法和离散粒子群 (DPSO) 算法相结合, 给出了一种输电网参数辨识方法, 并进行了算例仿真。

1 WLAV参数辨识数学模型

在给定结构和网络参数的条件下, 电力系统的遥测量方程可表示为:

式中:Zi, hi, ri分别为系统中测点i的量测值、量测函数和量测误差;x为系统状态, 包括节点电压幅值和相角;m为系统中测点数目。

状态估计的加权最小绝对值数学模型为:

式中:c=[c1, … , cm]T, 为权系数向量, 一般取ci=1/σi2, σi2为第i个量测误差的方差。

参数估计的增广状态估计, 就是将待估计参数作为变量, 与原节点状态量一起参与估计。 相应的增广状态估计量测方程为:

式中:p为参数状态量。

2 非线性内点法

对式 (2) 模型进行求解, 引入松弛变量l > 0, u > 0, l∈Rm, u∈Rm, 文献[4]提出利用l+u替代|r|, 即:

将式 (2) 的等式约束改造为障碍函数, 可得拉格朗日函数如下:

式中:y∈Rm, α∈Rm, β∈Rm为拉格朗日乘子。该式的库恩- 塔克 (Karush-Kuhn-Tucker) 条件为:

式中:▽xh (x) 为h (x) 的雅可比矩阵;μ为扰动因子;L, U, A, B分别为以l, u, α, β作为对角元素的对角阵;e=[1, …, 1]T。将式 (6) 各式进行泰勒级数展开, 并保留Ll与Lu的高阶项, 得到:Δ

式中:▽2xh (x) 为h (x) 的海森矩阵。由式 (7) 、式 (9) 相加得, 定义对偶间隙作为收敛判据 (例如Cgap<10-6则算法收敛[6]) , 若不满足收敛条件, 则修正障碍参数:Δ

然后进行下一次迭代计算, 直至算法满足收敛条件。 式中 σ 为中心参数, 一般取0.1, 在大部分情况下能够获得比较好的收敛性。 利用阻尼牛顿法可对以上线性方程组进行求解, 并计算:

式中: αp, αd分别为原、对偶变量的迭代步长, 其目的是保证各变量满足大于0 的条件。各变量修正方程为:

3 DPSO算法

Clerc提出一种针对离散变量优化问题的DPSO算法, 该算法中粒子也是通过追踪2 个极值粒子进行迭代寻优。 DPSO算法的数学描述如下:

式中:xidk, vidk分别为粒子i在第k次迭代时的位置和速度;w为惯性权重;c1, c2为学习因子, 一般取1.9~2.1;r1, r2, r3为0~1 之间均匀分布的随机数;pbest，id为粒子i本身找到的最优解;gbest，id为整个粒子群的最优解;S (v) =1/ (1+e-v）为sigmoid转换函数。 以线路Lij为例, 说明该线路可疑程度的适应度函数为:

式中:l为该线路上的量测数目, 包括首末端功率量测及节点电压量测。

4 混合算法在WLAV参数辨识的应用

4.1 混合算法

针对内点法和DPSO算法的特点, 文中提出一种有效的混合算法[13，14]:首先忽略变压器分抽头等离散变量, 将参数辨识转化为一个连续的非线性规划问题, 利用内点法直接求解;在此基础上, 根据变量的性质, 将参数辨识分解为连续优化和离散优化2 个子问题, 分别利用内点法和DPSO算法交替求解, 直到取得满意的优化结果。

在利用内点法处理连续优化子问题时, 以离散优化的变压器分抽头辨识结果为基础, 从而将参数辨识问题转化为不含离散变量的优化问题。 在利用DPSO算法处理离散优化子问题时, 又以内点法的优化结果为基础, 仅计算变压器分抽头等离散变量, 这样可有效减少计算量, 提高参数辨识的效率。 为此, 基于原- 对偶内点法和DPSO算法的参数辨识流程如下:

(1) 输入量测数据, 获取系统的节点信息和支路信息, 将可疑支路集中变压器分抽头等离散变量赋值于DPSO算法, 确定DPSO的粒子群规模等参数, 并对粒子位置及速度初始化。

(2) 假定离散变量为常数, 利用内点法对参数辨识进行求解, 每次调用时重复如下步骤:1 初始化参数, 给原变量和对偶变量赋初值, 同时计算障碍参数的初值;2 在当前建立牛顿方程组式 (7—12) , 计算牛顿方向;3 利用式 (13—16) 计算原变量和对偶变量的迭代步长, 更新原- 对偶变量, 修正障碍参数;4 计算对偶间隙Cgap, 若Cgap<10-6则迭代终止转步骤 (3) , 否则转步骤2。

(3) 计算DPSO适应度值, 其中变压器分抽头状态为上一步最终的计算结果。

(4) 更新粒子的历史最优位置pbest，id和全局最优位置gbest，id以及适应度值。

(5) 按式 (17) 和式 (18) 更新DPSO种群;计算最优适应度值, 判断是否满足收敛条件, 如是, 则转 (2) , 否则转至步骤 (3) 。

4.2 仿真实验

4.2.1 单一算法的辨识结果

以IEEE 30 节点系统为例, 首先利用内点法和DPSO算法单独进行参数辨识。 该系统共有4 台2 卷变压器, 各变压器的分接头位置均设为21 档 (从-10~10) , 抽头位置每调节一档, 变比变化0.01。 所有算法均基于C语言实现, 在至强E-1230 V2、主频3.3 GHz的个人机器上仿真。 其中, DPSO算法的种群规模都设为30, 最大迭代次数为100;内点法迭代过程中对偶间隙的收敛判据为10-6 (标幺值) 。 仿真试验用的生数据由潮流结果加2%标准差随机误差获得, 通过对生数据置零的方式获得仿真量测数据。 参数辨识结果见表1, 内点法和DPSO寻优过程如图1 和图2 所示。

由图1 可知, 基于内点法的WLAV参数辨识迭代11 次收敛, 计算时间仅为0.457 s, 满足工程要求。 由表1 可知, 内点法的参数辨识结果与真实值较接近, 最大误差仅为0.001 2, 能有效抑制不良数据的影响。 但内点法得到的结果为连续解, 不满足实际系统中分接头调节的离散要求, 若对内点法辨识结果就近取整, 则T4-12 的档位 (-4) 又与真实值 (-3) 不符。 因此, 单独靠简单的取整策略无法解决内点法难于处理离散变量的问题。而DPSO算法由于将分抽头变量看作离散变量, 不存在以上问题, 但DPSO算法寻优过程迭代次数太多, 平均计算时间为18.643 s, 且存在容易陷入局部最优解的不足, 不适于求解大规模参数辨识。

由以上分析可知, DPSO算法和内点法各具特色, 也各有不足, 单独利用上述2 种方法均无法取得满意的效果。 因此, 充分发挥两类方法的优势, 采用优势互补的高性能混合算法非常必要。

4.2.2 混合算法辨识结果

为了验证该混合算法的有效性, 仍以IEEE 30 节点系统为例进行参数辨识, 并与单一算法进行比较, 结果见表2。 仿真中, DPSO算法的种群规模设置为30, 最大迭代次数为100; 内点法的对偶间隙收敛判据为10-6, 最大迭代次数为25。 图3 给出了混合策略参数辨识过程。

由表2 可知, 在内点法迭代过程中, 不断利用DPSO算法对变压器分抽头等离散变量进行更新, 辨识结果与真实值基本一致。此外, 利用该混合算法进行参数辨识时, 能动态调整分接头的档位, 使寻优方向更加准确, 这与其实际迭代次数减少的现象相符。

4.2.3 算法稳定性讨论

DPSO算法是一种随机优化方法, 每次优化所需的计算时间和辨识结果不尽相同。 该混合算法中包含DPSO算法, 因此在辨识参数过程中也含有随机性。 同时, 为了验证混合算法和DPSO算法对更大规模系统的实际性能, 针对IEEE 118 节点系统进行100 次参数辨识, 变压器分接头档位的统计结果对比见表3。 该系统分接头档位仍为21 档, 调节步长为0.01。

由表3可知, 单独采用DPSO算法对IEEE 118节点系统变压器分抽头进行辨识时, 部分最终档位偏离真实值, 且由于优化变量包含节点电压幅值和相角等连续变量, 最大波动幅度为0.052 6, 而混合算法将离散变量与连续变量分解, 波动幅度仅为0.001 5, 为DPSO算法的12.4%, 表明混合算法更加稳定、可靠。同时, 在计算效率上, DPSO算法的平均计算时间为116.742 s, 而混合算法仅需7.497 s, 具有明显的优势。

5 结束语