改进多粒子群优化算法（精选10篇）
改进多粒子群优化算法 第1篇
感应耦合电能传输(ICPT)技术采用电磁感应耦合的方式实现电能传输,克服了传统接触传输方式存在的移动不灵活、电击、火花、噪音等缺点[1]。ICPT系统采用电磁松耦合的电能传输方式,极大地限制了电能传输容量和传输效率[2]。为了在实现系统传输功率的同时,最大限度地提高效率,针对ICPT系统可变参数较多,系统设计困难等特点,本文基于粒子群算法对系统效率进行优化分析。
粒子群优化算法(PSO)易于理解,算法简单,速度快,易于收敛[3],但其收敛性受参数和粒子分布的影响,设置不当会导致无法搜索到全局最优解。文献[4]提出了一种改进PSO,但其粒子位置很难满足等式约束条件,影响收敛速度和精度。文献[5-6]分别引入变异算子和收缩因子,较大提高PSO的收敛性。本文结合文献[4-6]所讲,在文献[4]的基础上同时引入变异算子和收缩因子,提出了一种新的粒子群多参数优化算法,大大提高了算法的收敛速度和精度。本文分析讨论并给出一个新的ICPT数学模型,针对一个特定输出功率的ICPT系统,基于改进PSO,通过优化系统互感耦合系数、谐振频率、负载电阻等多个参数,最大限度地提高系统的效率,仿真结果验证了算法的有效性。
2 感应耦合电能传输系统效率数学模型
2.1 感应电能传输系统概述
ICPT系统由初级能量变换环节、电磁变换环节以及电能拾取与变换环节组成。为了实现ICPT系统的最大化能量传输,通常需要对原副边励磁电感进行补偿,根据原副边功率变换与补偿环节结构的不同,可分PS,PP,SS,SP四种拓扑结构。
本文以采用SS拓扑结构的电压型ICPT系统为例,对系统在额定传输功率下的效率进行优化分析,其原理图如图1所示,对于其他拓扑模式的ICPT系统,可以采用相同的分析方法。
图1中,Cp、Cs分别是原副边励磁电感Lp、Ls的串联调谐电容,Rp,Rs分别是原副边电感的等效串联电阻,通常Rs很小,可以忽略不计。Ip,Is分别为谐振网络原边线圈电流和副边线圈电流。RL为系统负载电阻,M是原副边电感之间的互感。
2.2 数学模型
由上分析ICPT系统拓扑结构原理图可知,电能通过磁场松耦合传输,耦合效率低,为了提高传输功率,系统采用谐振补偿电路,所以,模型中忽略电路中无功功率的作用。
在系统设计过程中,系统优化问题可描述为:在系统额定传输功率要求下,优化系统各项参数(互感耦合值M,工作角频率ω,负载电阻RL),以最高的效率为目标函数,确定各个参数的最优组合。具体的数学模型描述为:
式中,Pneed是系统实际要求输出功率;Mm ax是系统所能取到的最大互感值;km ax是系统所能达到的最大耦合系数。
为了实现系统的最大功率传输,通常要求系统原副边均工作在谐振状态,即原副边补偿电容Cp,Cs的选取需满足
为了减少绕线的集肤效应,原副边绕组采用李子线,高频交流绕线电阻随频率变换的关系为
其中,Rpdc、Rsdc分别是原副边绕线直流电阻;李子线分别由Nps、Nss根单股线组成;D1是单股线的直径,一般取0.1mm;D2 p、D2 s分别是原副边李子线的直径。
由图1可求得系统输出功率和效率分别为:
其中,Vp为原边输入直流电压;Rp为原边绕线电阻;Rs为副边绕线电阻。
由式(6)和式(7)可知,可通过改变互感耦合值M,工作角频率ω以及负载电阻RL等参数的大小来改变ICPT系统的效率。本文通过改进PSO对式(6)和式(7)中参数进行优化,从而最大限度地提高系统效率。
3 有等式约束优化问题的粒子群算法
3.1 标准粒子群算法(PSO)
PSO先生成初始种群,即在解空间中随机初始化一群粒子,粒子的位置表示待优化问题的解,解的优劣程度由目标函数确定的适应值决定。每个粒子将在解空间中运动,并由一个速度决定其飞行方向和速率大小,然后通过逐代搜索找到最优解。在每一代中,粒子通过跟踪个体极值和全局极值来更新自己的速度和位置。
设第i个粒子在d维解空间中的位置表示为xi=(xi1,xi2…xid),其速度vi=(vi1,vi2…vid)。它的个体极值pi=(pi1,pi2…pid),种群的全局极值pg=(pg1,pg2…pgd)。
粒子根据以下公式来更新其速度和位置:
式中,w为惯性权重,表示为:
其中,iterm ax为总的迭代次数;iter为当前迭代次数。惯性权重控制着粒子的先前速度对当前速度的影响程度。
rand()是均匀分布在(0,1)之间的随机数;c1、c2为两个学习因子,一般取c1=c2=2。另外,粒子在每一维飞行的速度不能超过算法设定的最大速度Vm ax,即当式(8)的│vik│>Vm ax时,取│vik│=Vm ax。
3.2 粒子群算法的改进
PSO解决高维度问题具有很大的优越性,但遇到具有较多局部极小点的搜索空间时,搜索效率可能会大大降低,且不能保证收敛于最优解,针对此问题,本文对标准PSO进行了改进。文献[4]提出了一种改进的求解有等式约束优化问题的PSO,文献[5]提出了一种带变异算子的PSO以及文献[6]提出了一种引入收缩因子的PSO。本文结合上述文献提出了一种全新的改进方法,即在有等式约束优化算法的基础上,引入收缩因子和变异算子,从而达到大大提高算法收敛速度和精度的目的。
由文献[4]可知多目标有等式约束优化问题可以描述如下:
Clerec[7]的研究表明使用收缩因子可以保证粒子群算法收敛。引入收缩因子和惯性权重因子后粒子的速度和位置表达式分别如下:
其中引入的收缩因子x为:
其中,l=c1+c2m,l>4,m为粒子群中粒子数。变异算子实际上是在标准PSO的基本框架中,分别对粒子配置不同的最大加权系数值,如某些粒子赋予的最大加权系数为0.9,这部分粒子拓展搜索空间,定位一些接近最优解的区域;另一些粒子赋予的最大加权系数为0.6,这部分粒子在己经搜索到的最优解区域内进行局部搜索。这样就避免了迭代过程中难以大幅度调整的问题,较好地协调了算法的局部与全局搜索能力,而收缩因子保证算法收敛。
该改进PSO的流程图如图2所示。
改进PSO具体步骤流程为:
(1)初始化粒子群
1)设置参数:给定群体规模N,规定最大迭代次数iter;学习因子c1=c2,设置加权系数最大值wm ax,wm in。粒子最大更新速度Vm ax;
2)初始化群体:随机产生每个粒子的位置X和速度Vi。
(2)迭代过程
1)根据如下适应度函数,计算出每个粒子的适应度值Fit(i);
其中,k>0,B(Xi)=Σjp=Imax(0,gj),本文中k=1。
2)比较各粒子的适应值,找出粒子位置的个体极值pB est[i]和全局极值gB est;
3)判断迭代次数,当n>iter1时,加权系数最大值改为wm ax;
4)根据式(8)以及式(13)~式(15)更新每个粒子的新速度和新位置,并确保粒子在要求范围内;依据中止条件n≤iter判断是否结束算法;当n>iter时,结束算法;否则,返回1)重新迭代。
4 算法的性能测试及比较
为了测试改进PSO的性能,以文献[7]所提有等式约束PSO以及本文提出的新的改进PSO对下文列举的基准函数F进行测试比较。
本文在Matlab中完成上述数值实验。初始化PSO参数为:c1=c2=0.5、w=0.9、vm ax=3,粒子群维数为30,最大叠代次数为100。
表1给出了文献[7]中算法(记为DC)以及本文改进的新算法(记为NC)针对上述两种函数所得的9次最好结果。其中文献[7]中的ε=0.1。
由表1数据可以看出,本文改进的新算法NC收敛精度明显优于算法DC,同时所得最优解也更加稳定。对于函数F1,从表1中可见NC算法所得最优解为9.1000,此时对应的最优点为(4.1000,1.000,1.000,9.1000),而DC算法所得最优解徘徊在9.1009左右;对于函数F2,从表1中可见NC算法所得最优解为6.0777,此时对应的最优点为(1.0274,2.0111,1.000,6.0777),而DC算法所得最优解徘徊在6.09左右。
图3和图4分别给出了函数F1基于两种算法的粒子进化曲线和函数F2基于两种算法的粒子进化曲线。由图中可以看出,无论针对F1函数还是F2函数,基于DC算法的适应度收敛所需迭代次数均多于NC算法,速度明显慢于NC算法,且由表1可知,两种函数基于NC算法的收敛精度明显高于DC算法。显然本文改进的粒子群算法以较少的迭代次数和更高的精度完成了算法收敛,并且不会出现陷入局部极小的问题。
5 改进粒子群算法在ICPT系统中的实现
5.1 改进粒子群算法参数优化
本文应用改进的粒子群算法对式(1)所示ICPT系统数学模型进行优化设计。根据以上优化算法,设定粒子群算法参数初始化为:c1=c2=0.5、wm ax=0.8、vm ax=3,粒子群维数为30,最大叠代次数为150,适应值函数中的ε取0.1,同时设定ICPT系统其他参数见表2。
那么,根据式(4)~式(6),以改进的粒子群算法求解此问题,最优算法结果如图5所示。
而且,在假设逆变电路完全工作于软开关模式,系统效率近似为100%的情况下,可以得出,ICPT系统优化下的参数取值分别为ω=106740rad/s,M=38.36μH,RL=18.725Ω;谐振耦合电路效率为94.71%。
由图5可知,应用改进粒子群算法来优化ICPT系统效率模型,不仅不会陷入局部极小,而且可以在很少的迭代次数下完成整个优化过程,快速精确地得出ICPT系统中互感耦合值、工作频率、负载电阻等多个参数的优化值。
5.2 仿真验证
搭建ICPT系统模型,对理论分析结果进行验证。测得在不同参数选取下系统传输效率见图6。
其中,图6(a)为当工作角频率ω一定时,系统传输效率与系统互感耦合系数M和负载电阻R的关系曲线;图6(b)为当负载电阻R一定时,系统传输效率与系统互感耦合系数M和工作角频率ω的关系曲线;图6(c)为当系统互感耦合系数M一定时,系统传输效率与负载电阻R和工作角频率ω的关系曲线。由图6(a)可知,在工作角频率ω一定的条件下,通过调节系统互感耦合系数M和负载电阻R的值,可优化得到,当系统各参数值分别为ω=106740 rad/s,M=35.89μH,RL=21Ω时,系统谐振耦合电路效率为91.11%,与理论分析结果94.71%基本一致。但考虑到实际仿真过程中,逆变电路未完全实现软开关工作模式以及电路未完全理想谐振,实际仿真测得逆变电路效率为92.3%,因此,本文通过仿真最终测得系统最大效率为84.1%。但本文对谐振耦合电路仿真结果与理论优化分析基本一致,证明了理论分析方法的正确性。
由图6(b)和图6(c)可知,不论是在负载电阻R一定还是在系统互感耦合系数M一定的条件下,系统的传输效率都会随着工作角频率的减小而增大,且随着工作角频率越来越小,传输效率也会增大的越来越慢。
6 结论
本文通过对ICPT系统的分析,将粒子群算法应用于ICPT系统传输效率的优化问题,提出了一种引入变异算子和收缩因子的有等式约束问题的新的粒子群优化算法。通过仿真实验验证了该方法不仅解决了标准粒子群算法容易陷入局部极小的问题,而且能够更加快速精确地完成整个优化过程。将其应用于ICPT系统的效率优化问题,所得优化数值大小与电路仿真结果基本一致。
参考文献
[1]Boys J T,Green A W.Inductively coupled power trans-mission concept-design and application[J].IPENZTrans,1995,22(1):1-9.
[2]Chwei-Sen Wang,Grant A Covic.Power transfer capabili-ty and bifurcation phenomena of loosely coupled inductivepower transfer systems[J].IEEE Transactions on Indus-trial Electronics,2004,51(1):148-157.
[3]杨维,李歧强(Yang Wei,Li Qiqiang).粒子群优化算法综述(Survey on particle swarm optimization algo-rithm)[J].中国工程科学(Engineering Science),2004,6(5):87-93.
[4]刘伟,蔡前凤,刘海林(Liu Wei,Cai Qianfeng,LiuHailin).基于参数方程处理等式约束优化的粒子群算法(Particle swarm optimization algorithm based on para-metric equation method to handle equality constraints)[J].计算机工程与设计(Computer Engineering andDesign),2008,29(3):697-699.
[5]熊伟丽,王振兴,徐保国(Xiong Weili,Wang Zhenx-ing,Xu Baoguo).带变异算子粒子群算法在多序列比对中的应用(Application of the PSO algorithm with mu-tation operator to multiple sequence alignment)[J].控制工程(Control Engineering of China),2008,7(4):357-359.
[6]刘国岩(Liu Guoyan).第四方物流企业调度管理优化的模拟退火粒子群算法研究(Research on fourth-partylogistics scheduling optimizing based on SA-PSO)[J].软科学(Soft Science),2010,24(8):134-137.
改进多粒子群优化算法 第2篇
基于改进粒子群优化算法的新安江模型参数优选
新安江模型是一种实用有效的水文模型,在洪水预报以及水资源评估和管理中得到了广泛的应用.为此,结合新安江模型参数的`特点,提出了基于改进粒子群优化算法的新安江模型参数优选方法,并将该模型应用到日径流预报中.实例表明,该方法能快速地完成参数寻优,并能较好地寻找出参数的全局最优解.
作 者：刘力 周建中 杨俊杰 刘芳 安学利 Liu Li Zhou JianZhong Yang JunJie Liu Fang An XueLi 作者单位：华中科技大学水电与数字化工程学院,湖北,武汉,430074刊 名：水力发电 ISTIC PKU英文刊名：WATER POWER年，卷(期)：200733(7)分类号：O224 TV125关键词：参数优选 新安江模型 粒子群优化算法 径流预测
改进多粒子群优化算法 第3篇
关键词：粒子群算法；单目标；多目标；传递率；传递函数矩阵；无穷范数；状态反馈控制；控制力传递率
中图分类号：TU112.41文献标识码：A
单自由度、双自由度体系是研究设备振动隔离的主要模型方法，且隔振体系性能与隔振参数关系密切，选择合适的参数，能提高系统的隔振性能，如果参数选择不当，就会适得其反，所以隔振参数的优化研究显得非常必要.文献1将遗传算法与最大熵法结合，给出了两级隔振系统参数优化设计的一种混合方法；宋鹏金等2采用傅里叶变化法和直接积分法分别对时域函数和频域函数进行参数优化，提出了一种锻锤隔振参数优化的新方法；文献3根据超精密隔振器的内部结构和隔振系统的布置形式，建立了超精密隔振系统的动力学模型，并在此基础上推导出理论频响函数、进行了系统参数的辨识研究；LIU等4基于整星隔振体系进行了参数优化；ESMAILZADEH5采用梯度优化方法对汽车悬挂体系进行了隔振参数的优化研究；文献6提出了一种隔振参数线性变化的方法，主要通过刚度迟滞模型实现；刘春嵘等7基于反共振原理在小振幅假设下建立了两级浮筏系统的数学模型，并分析了隔振机理，推导出了力传递率的表达式.
作为新型的群智能算法——粒子群优化算法PSO自1995年提出以来，就因其简单、易实现、收敛快，可调参数少等优点得到了广泛应用8.由于传统粒子群算法的局限性，许多学者对其做出了改进.Shi9等提出了关于权重的线性调整策略，获得了满意的优化效果；李军等10在Shi的基础上提出了自适应权重变化策略，克服了传统粒子群算法寻优过程的早熟情况，能使粒子群算法达到局部最优及全局最优的平衡.Coello等首次提出了多目标粒子群优化算法MOPSO，掀开了多目标优化问题的新篇章，主要思想是通过Pareto最优解集决定粒子飞行方向以及在全局知识库中得到之前发现的非支配向量，以指导其它粒子飞行11.
状态反馈控制是振动控制领域的常用方法，通常包括线性二次型最优控制、极点配置控制、基于观测器的控制器等，由于实际问题的不确定性，鲁棒H2H
SymboleB@ 控制被提出并广泛应用 12.上述方法在机械、结构等振动控制领域中发挥了巨大作用，其实质是通过控制器产生基于输出的反馈控制力，以优化控制系统响应.
1粒子群算法
1.1标准粒子群算法
粒子群优化算法模型中，每一个粒子的自身状态都由一组位置和速度向量描述，分别表示问题的可行解和它在搜索空间中的运动方向.粒子通过不断学习它所发现的群体最优解和它在搜索空间中的运动方向，并不断更新它所发现的群体最优解和邻居最优解，从而实现全局最优解.粒子的速度和位置更新方程是PSO的核心，由式1表示：
1.3多目标粒子群算法
多目标粒子群算法的主要计算步骤如下所述：
Step1：初始化粒子群，计算各对应粒子的目标函数向量，将其中的非劣解加入到外部档案之中；
Setp2：初始化粒子的局部最优值pbest和全局最优值gbest；
Setp3：在搜索空间内，通过式1，2调整粒子的飞行速度和位置，形成新的pbest；
Step4：根据新的非劣解维护外部档案，并为每个粒子选取gbest档案的内容决定全局最优值的选取；
Step5：是否达到最大迭代次数，若否则继续计算，若是则停止计算，输出pareto最优解集及全局最优解.
多目标粒子群优化算法与单目标粒子群优化算法的主要区别就是全局最优解的选取方式及外部档案的设定和更新.需要着重指出的是，关于全局最优解的选取问题；对于多目标优化，直接计算会存在一组等价的最优解集，很难从每一次迭代中确定一个全局最优解.解决该问题最直接的方法即是利用Pareto支配的概念，考虑档案中的所有非劣解，并从中确定一个“主导者”，通常采用密度测量的方法来确定全局最优解.本文将采用基于粒子最近邻拥挤程度评判的最近邻密度估计方法
6结语
基于粒子群优化算法，以控制输出的传递率为目标函数，在单自由度、双自由度隔振体系传递率分析的基础上，分别进行了隔振参数的单目标和多目标优化设计研究.
传统的振动控制设计，往往是在已知隔振参数的情况下创新控制方法或者优化控制器，却忽略了隔振参数对控制系统的重要性，盲目地从控制角度优化体系，不仅容易造成控制能源浪费，还可能会引起系统响应发散.
我国《隔振设计规范》15仅对单自由度隔振体系的传递率等相关参数做了规定，事实上，本文研究表明，双自由度隔振体系更适用于常见的工程振动控制.本文亦为最优隔振体系设计及最优振动控制设计提供了新思路，对《隔振设计规范》接下来的修订工作具有指导意义.
参考文献
1 魏燕定，赖小波，陈定中，等. 两级振动隔振系统参数优化设计J.浙江大学学报，2006，405：893-896.
WEI Yanding， LAI Xiaobo， CHEN Dingzhong， et al. Optimal parameters design of twostage vibration isolation systemJ.Journal of Zhejiang University， 2006， 405：893-896.In Chinese
2宋鹏金，陈龙珠，严细水.锻锤隔振基础参数优化的新方法J.振动与冲击，2004，233：96-98.
SONG Pengjin， CHEN Longzhu. YAN Xishui. The new parameters optimization method of vibration isolation base of hammer J. Journal of Vibration and Shock， 2004， 233：96-98. In Chinese
3董卡卡，蒲华燕，徐振高，等. 超精密隔振系统的建模与参数辨识J.武汉理工大学学报，2013，31：126-128.
DONG Kaka， PU Huayan， XU Zhengao， et al. Modeling and parameter identification of the ultraprecision vibration isolation system J. Journal of Wuhan University of Technology， 2013， 31：126-128. In Chinese
4LIU L K， ZHENG G T. Parameter analysis of PAF for wholespacecraft vibration isolation J. Aerospace Science and Technology， 2007， 116： 464-472.
5ESMAILZADEH E. Design synthesis of a vehicle suspension system using multiparameter optimization J. Vehicle System Dynamics， 1978， 72： 83-96.
6ZHANG F， GRIGORIADIS K M， FIALHO I J. Linear parametervarying control for active vibration isolation systems with stiffness hysteresis J. Journal of Vibration and Control， 2009， 154： 527-547.
7刘春嵘，肖卫明，徐道临. 双层流体浮筏的隔振特性研究J.湖南大学学报：自然科学版，2013，401：43-48.
LIU Chunrong， XIAO Weiming， XU Daolin. Study of the vibration isolation of twodegreeoffreedom fluidtype floating raft J. Journal of Hunan University：Natural Sciences， 2013，401：43-48. In Chinese
8KENNEDY J， EBERHART R C. A new optimizer using particle swarm TheoryCProceedings of the Sixth International Symposium on IEEE.Micro Machine and Human Science， 1995： 39-43.
9SHI Y， EBERHART R C. A modified particle swarm optimizer CIEEE World Congress on Computational Intelligence.NewYork： IEEE，1998：69- 73.
10李军，许丽佳.一种带压缩因子的自适应权重粒子群算法 J.西南大学学报，2011，337： 118-120.
LI Jun， XU Lijia. Adaptive weight particle swarm optimization algorithm with construction coefficient J.Journal of Southwest University， 2011， 337： 118-120. In Chinese
11COELLO A C， LECHUGA， MOPSO M S： A proposal for multiple objective particle swarm optimizationC Proceedings of the 2002 Congress on IEEE.Evolutionary Computation， 2002， 2： 1051-1056.
12欧进萍.结构振动控制——主动、半主动和智能控制M. 北京：科学出版社，2003：61-68.
OU Jinping. Structure vibration controlactive， semiactive and smart controlM.Beijing： Science Press， 2003：61-68. In Chinese
13DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGAII J. IEEE Transactions on Evolutionary Computation， 2002， 62： 182-197.
14GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimizationC Proceedings of the Second International Conference on Genetic Algorithms and Their Applications.Hillsdale， NJ： Lawrence Erlbaum， 1987： 41-49.
15GB 50463-2008 隔振设计规范S.北京：中国计划出版社，2008： 36-40.
改进多粒子群优化算法 第4篇
电力系统无功优化,是指在满足系统安全运行的前提之下,适度调节变压器档位,发电机端电压以及无功补偿等控制变量,使得电力系统中的无功潮流达到最优分布,提高电能质量,减少有功网损[1]。对于大多数无功优化问题主要是从减少有功网损的单目标出发的,然而,随着经济社会的发展,某些特殊行业机构不仅追求经济效益,而且对电能质量越来越重视。所以,有必要找寻一种既能节约成本,提高效益,又能满足用户对电能质量的需求的多目标无功优化算法。
多目标优化问题中,往往各个目标之间存在竞争,无功优化也是如此,这就需要对多个目标作出折中以得到我们满意的解。传统的多目标优化方法是通过加权法将多的目标优化问题转化为单目标优化问题来解决,这种方法忽略了多目标之间的相互竞争关系,单纯优化所得到的结果往往不具选择性[2]。针对多目标无功优化问题,本文提出了1种改进的多目标粒子群算法,该算法利用NSGA-Ⅱ[3]中的非支配排序和拥挤距离[4]策略,引入变异算子[5]和动态权重,增强全局寻优能力,避免陷入局部最小值,并且输出1个Parato非劣解集合[6],能为用户提供考虑多个目标的折中解,为不同的应用场合及不同的需求提供选择。
1 电力系统多目标无功优化模型
传统的无功优化方法单纯以有功网损为单目标,将节点电压约束在安全电压范围内,通过这样的模型求出的结果中的节点电压很容易趋近极限值,从而使有功网损与安全电压之间发生冲突,所以本文采用有功网损与电压偏移量双目标构建多目标无功优化模型。
1.1 有功网损
式中,Ploss为有功网损,kW;N为系统支路数;i,j为节点编号;GK(i,j)为节点i,j之间电导;Vi为节点i节点电压,V;δi为节点i电压相角。
1.2 电压偏移
式中,Vi spec为负荷节点i电压期望幅值,V;n为系统负荷节点数;Vi max为节点i允许的最大电压偏差,V;其中:
1.3 约束条件
该模型约束条件:g(u,x)=0;h(u,x)≤0。式中,x为控制变量,是对电力系统进行无功优化的控制对象。
X=[UGT,TT,QCT]。QG为发电机的节点电压,V;T为变压器的变比;QC为无功补偿电容,F。U为状态变量,由潮流方程得到。
U=[ULT,QGT]。UL为负荷节点电压,V;UG为发电机无功出力,Var。
1.4 等式约束
电力系统无功优化的等式约束即是电力系统的潮流平衡方程:
式中,Pi为有功功率,W;Qi为无功功率,Var。
1.5 不等式约束
电力系统的不等式约束包括控制变量约束和状态变量约束。
1.6 控制变量约束
1.7 状态变量约束
式中,NG,NT,NC,NL分别为发电机节点数,变压器支路数,无功补偿装置节点数,负荷节点个数。
2 粒子群算法
粒子群优化算法(PSO)是Eberhart和Kennedy于1995年提出的,是基于群体的进化算法。粒子群算法的原理是将撒向搜索空间里的每个粒子赋予一定的初速度飞行,并且根据个体和群体经验在飞行过程中不断调整飞行方向和速度,最终锁定目标函数最优值的过程。
粒子速度和位置的更新公式如下。
式中,ω为惯性权重系数,使粒子保持飞行运动的惯性;c1,c2为加系常数;r1,r2为[0,1]之间的随机数,Xtipbest和XtiGbest分别为t时刻粒子i的个体最优位置和全局最优位置。
2.1 改进的多目标粒子群算法
2.1.1 精英解集的更新
精英解集即粒子群在更新过程中发现的优良个体通过1个构造的解集收集起来,方便子代从中挑选优秀个体作为经验寻找多目标优化问题的最优解。具体方法是:a)将父代R1与子代R2合并Rk=R1∪R2,Rk的个体大小为2N;b)将种群Rk进行非支配排序并且计算每个个体的序值和拥挤距离,再对Rk中个体先进行序值升序排列,拥挤距离降序排列,选择前10%的个体作为精英解集;c)选择经过排序后的前50%的个体(即经过排序后的前N个个体)作为新的父代R3;d)按照公式更新R3得到新的子代R4。将R4与R3合并后重复b)、c)步骤。
根据这种修剪策略,拥挤距离小的个体将被去除,这是因为同一前端中,拥挤距离越大,个体间就不拥挤,种群多样性越好。这样更新后,子代不仅含有父代的优秀经验,而且也保持了自己的个性,因此加强了算法的搜索范围,保证了精英解集的多样性和领导性。
2.1.2 个体最优值和群体最优值的更新
在改进的最优值选择策略中,如果更新后的粒子支配个体粒子最优值,那么就用新的粒子作为个体粒子最优值;如果更新后的粒子受个体粒子最优值,那么个体粒子最优值不变;如果更新后的粒子和个体粒子最优值彼此不支配,那么就在两者中随机选择1个粒子最为个体粒子最优值。群体粒子最优值则随着迭代更新后的精英解集中随机选择,以保持子代的多样性。
2.1.3 动态惯性权重策略
如果动态惯性权重ω随着粒子群算法的迭代而线性减小,那么将明显改善算法的收敛性能。
本文的动态惯性权重策略为:
式中,ωmax为加权系数;ωmin为加权系数;itercur为迭代次数;itermax为迭代次数。
2.1.4 变异策略
a)控制变量编码。在无功优化控制变量中,包含发电机的节点电压UG,变压器的变比T,无功补偿电容QC,其中发电机节点电压为连续变量,故采用实数编码,而变压器变比和无功补偿电容受到控制过程中档位的限制,故采用整数编码;
b)对约束条件的处理。对于控制变量的约束可以限制初始化和更新后的范围,而对于状态变量负荷节点电压UL和发电机无功出力QG,是由等式约束决定,所以不能使用上述方法,只能依靠惩罚函数的方法降低越限解的生存能力进而淘汰该解;
c)改进粒子群算法的电力系统多目标无功优化流程。(a)读入电力系统数据,包括支路参数,节点参数,负荷数据等;读入算法数据,包括粒子群规模,迭代次数,范围限制,加速常数等;(b)初始化粒子群Xi及速度v,通过潮流计算和适应度计算得到其对应的有功网损f1(Xi)和电压偏移f2(Xi),设定初始化粒子群Xi为当前个体最优值Pi,通过Parato非支配策略得到群体最优值Pg;(c)根据粒子群更新公式得到新一代粒子Xi+1,通过潮流计算和适应度计算得到其对应的有功网损f1(Xi+1)和电压偏移f2(Xi+1);(d)通过Pareto非支配策略比较粒子优劣,更新个体最优粒子;(e)将父代粒子群Xi与子代粒子群Xi+1合并得到R21,根据改进的精英解更新策略和种群修剪策略得到精英解集和新的子代R2;(f)计算最新子代R2的收敛距离(收敛距离表示当前算法所获得的伪劣解与真实的Pareto解的接近程度),对收敛距离进行逆序排列,前5%采取变异策略,防止种群陷入局部最小化;(g)判断终止条件,否则转入步骤(c);(h)输出数据结果及Pareto前端;
d)IEEE14节点系统无功优化算例。为了验证改进的多目标粒子群算法无功优化的效果,本文将用上述算法对IEEE14节点系统进行无功优化计算。粒子群算法参数设置根据文献[8],编码方式采用实数编码,种群大小100,迭代次数100,精英个数10,变异采用约束自适应变异方式(见表1)。
从图1中我们可以看出,有功损耗和电压偏差这2个目标函数互相矛盾,因此只能根据实际需要来从Pareto解集中进行选择,表2从解集中选取5个解,当决策者以有功损耗为主要目标时,可采用5号解提供方案,当决策者以电压偏差为主要目标时,可以采用3号解提供方案。
3 结语
多目标粒子群算法是近年来比较热门的多目标算法,本文对多目标粒子群算法进行深入研究和改进,提高了MOPSO的搜索能力,并将其应用于电力系统无功优化,运行后可以得到1组Pareto解集,决策者可根据实际需求来选择不同的解决方案。随着电力系统的不断发展,人们进行无功优化时考虑的因素会越来越多,相信MOPSO也会不断改进,进而为无功优化问题提供1个较好的算法支持,具有重要的现实意义。
参考文献
[1]冯士刚,艾芊.利用强度Pareto进化算法的多目标无功优化[J].高电压技术,2007,33(9):115.
[2]马清亮,胡昌华.多目标进化算法及其在控制领域中的应用综述[J].控制与决策,2006,21(5):481.
[3]Kalyanmoy Deb,Amrit Pratap,Sameer Agarwal,et al.Afast and elitist multi-objective genetic algorithm:NSGA-I[I J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[4]魏武,郭燕.基于拥挤距离的动态粒子群多目标优化算法[J].计算机工程与设计,2011,4(32):1421-1423.
[5]刘衍名,牛奔,赵庆祯.基于交叉和变异的多目标粒子群算法[J].计算机应用,2011,31(1):83.
[6]李炜,张兴华.一种改进的基于pareto解的多目标粒子群算法[J].计算机仿真,2010,27(5):96-97.
[7]张伯明,陈寿孙.高等电力网络分析[M].北京:清华大学出版社,1996:54-57.
改进多粒子群优化算法 第5篇
基于粒子群优化算法的无人机航迹规划
提出一种基于粒子群优化算法的无人机路径规划方法,利用粒子群优化算法,将约束条件和搜索算法相结合,从而有效减小搜索空间,得到一条全局最优路径.仿真结果表明:该方法能够快速有效地完成规划任务,获得满意的三维航迹.
作 者：陈冬 周德云 冯琦 CHEN Dong ZHOU De-yun FENG Qi 作者单位：西北工业大学电子信息学院,西安,710072刊 名：弹箭与制导学报 PKU英文刊名：JOURNAL OF PROJECTILES, ROCKETS, MISSILES AND GUIDANCE年，卷(期)：27(4)分类号：V279关键词：无人机 航迹规划 粒子群优化
改进多粒子群优化算法 第6篇
铜卷加工制造兼有离散型制造和流程型制造的特点,属于典型的混合型生产方式[1],其生产过程的非线性、随机性、不确定性,导致该类问题的生产约束条件更为多样,其生产调度问题具有更大的复杂性,求解更加困难。而调度问题本身往往需要综合考虑生产成本、资源能耗和产品周期等多个因素,而且各因素之间往往会存在冲突,属于多目标优化问题(multi-objective optimization problem,MOP)[2],混合型制造业也是典型的MOP。MOP往往不存在使各目标都为全局最优的解,而是存在一个在多个目标间折衷的均衡解的集合,即Pareto最优解集,求解多目标问题的关键就是找到数量足够多且分布均匀的Pareto最优解[3]。
自从Kennedy等[4]在1995年提出粒子群优化(particle swarm optimization,PSO)算法以来,PSO算法就以其概念简单、容易实现和需要调整的参数较少等优点吸引了大批学者进行研究,逐步渗透到各个应用领域[5,6,7]。而将PSO算法应用到MOP需要解决三个问题:如何产生非支配解并构成Pareto解集;采用何种策略更新全局极值和个体极值;如何保持Pareto前沿上优化解的多样性。目前,在铜卷加工等混合型生产调度中应用PSO算法的研究相对较少,但由于混合型生产在现代制造生产中具有典型的代表意义,并且属于多目标优化问题,以及PSO算法自身的优势和容易与其他算法进行融合的特点,使得研究PSO算法在混合型多目标生产调度中的应用有着深刻的意义与广阔的前景。
1 多目标铜卷加工生产调度模型
1.1 铜卷加工生产方式描述
相对于传统的离散型或连续型生产方式而言,铜卷加工的生产方式有自己的特点:生产过程更为复杂、多种生产方式并存、多品种小批量生产等。以某铜卷生产企业的黄铜卷加工为例,产品的生产从投料到最终生产出成品需要经过若干个连续生产加工的过程(每个生产过程为一个单元):熔炼炉→罩式炉退火1→粗扎机1→罩式炉退火2→粗扎机2→中间退火(罩式炉)→脱脂机→精扎机→气垫炉→罩式炉退火3→脱脂机→拉弯机。企业的生产是按订单驱动的,并且每件在制品在任一连续生产过程结束时都要进入缓冲区暂存。
1.2 铜卷加工生产调度问题模型
在生产计划调度中,由于企业接到的订单种类和产品类别都不唯一,各产品的交货期也会有差别,因此在调度之初需对订单进行分解,并将分解后的订单进行合并来安排生产,以便将同种类型以及交货期接近的产品作为一类产品进行加工。根据该铜卷加工企业的生产调度问题,建立企业生产调度问题模型如图1所示。企业从X个客户接收到一些订单,将订单基于交货期和产品种类进行分解和合并,产生要加工的产品系列a、b、c、d、f,每个产品都要经历M个生产单元,每个单元对应一台生产设备,则生产调度问题就是将这些产品在M个生产设备上的加工时间和顺序进行优化。
对于问题模型必须有一定的约束条件才能使调度算法有合理的解空间。为方便建立模型,我们对该铜卷加工企业的生产进行如下的约定:①产品的加工工艺路线是确定的;②企业的一批订单共涉及N种产品(序号为1,2,…,N),第j种产品的交货期为Tj(天);③产品经历M个连续生产单元,第j种产品在第i个生产单元上所用的时间为tij,开始加工时间为tsij,结束的时间为teij,产品最后实际完成加工时间为TeMi,后一个加工单元必须在前一个加工单元完成后方可开始加工工件;④任一连续生产单元在任一时刻只能加工一种产品;⑤在零时刻,任何一种产品均有可能被加工。
考虑到铜卷企业生产实际的需求,本文选择交货期满意程度和完成时间两项指标[8]建立多目标优化函数。交货期满意度指标用产品最大拖期Td度量,第j种产品的拖期表示为Tdj;完成时间用产品最大完成时间Tf度量。因此,铜卷加工多目标调度优化模型为
其中,式(1)表示调度问题的目标函数;式(2)表示最大完成时间为所有工件在最后一台设备上完成时间的最大值;式(3)表示最大拖期取所有产品拖期的最大值,其中当所有产品均提前完成时,最大拖期为0;式(4)表示每个产品的拖期等于实际完工时间与交货期之差;式(5)表示加工时间等于结束加工时间减去开始加工时间;式(6)表示某种产品在某个连续生产单元上的结束加工时间大于开始加工时间。
2 求解MOP的自适应改进PSO算法
2.1 多目标优化问题描述
一般地,一个多目标优化问题就是要求所有目标函数在满足约束条件下越小越好,一个含有n个决策变量、m个目标变量的多目标优化问题可表述为[9]
其中,x为n维的决策矢量,x=(x1,x2,…,xn)∈X⊂Rn;X为n维的决策空间;y为m维的目标矢量, y=(y1,y2,…,yn)∈Y⊂Rm;Y为m维的目标空间。
2.2 外部种群的更新
非支配排序遗传算法(non-dominated sorting genetic algorithm,NSGA-Ⅱ)[10]是目前公认高效的多目标优化算法,NSGA-Ⅱ中非支配排序思想已成为目前MOPSO(PSO for multi-objective problem)构成Pareto最优解的主流方法[11]。利用外部种群保留种群进化过程中产生的非支配解是目前比较高效的精英策略。
本文借鉴文献[12]中的基于拥挤距离排序的方法更新外部种群,其操作过程如图2所示。设内部种群为Ps,进化到第t代时内部种群粒子数为St;外部种群为Pt,外部种群粒子数为Sp,设置外部种群最大粒子数为Sm(Sp≤Sm)。内部种群Ps进化后,将产生的非支配个体(Np为非支配个体的个数)复制到外部种群,形成种群P′t。
(1)删除P′t中的重复个体(目标值相同的个体即为重复个体,随机删除一个而保留另一个);标记并删除P′t中的非支配个体,此时记P′t中包含的非劣个体数为m2(m2≤Sm+Np);
(2)计算P′t中拥挤距离Di并降序排列,记为种群P″t;
(3)判断m2与Sm的数值关系,若m2≤Sm,如图2中情况①所示,则将P″t记为新外部种群Pt+1,此时Pt+1的后Sm-m2个个体为空;否则,如图2中情况②所示,调用外部种群的缩减过程,仅保留P″t中的前Sm个个体,删除后m2-Sm个最密集个体,形成缩减的外部种群Pt+1,由此来保持外部种群的个体数在最大值Sm之内,避免了随着进化运算的进行,非支配个体数无限增多而降低算法效率;同时,外部种群缩减时删除最密集的多余个体而保留大量分散个体,保证了Pareto前沿的均匀分布。
其中对于非支配个体拥挤距离的计算,本文根据非支配个体与其周围的两个空间点的欧几里得距离来计算:
式中,fi,j(x)表示第i个个体的第j个目标函数值;i-1、i+1为外部种群基于各目标函数排序后个体i附近的两个个体。
另外设置各目标函数排序后的第一个个体和最后一个个体的拥挤距离D1和DSp均为无穷大。
2.3 最优值更新策略
MOPSO希望获得分布均匀的Pareto前沿,因此不同于求解单目标问题时只选取目标函数值最大或者最小的点,而是要选择处于Pareto前沿中分散区域的点,从而引导原始粒子群向分散区域进化。图2所示的外部种群Pt更新完成后,全局最优值Pg的更新策略分为如下两种情况:
(1)若Pt中只包含极少数边界个体,即所有个体的拥挤距离均为无穷大,则随机选择一个作为全局最优位置Pg;
(2)若Pt中包括拥挤距离不为无穷大的个体,则使用轮盘法选择,即以较大概率选择拥挤距离较大的个体为Pg,计算公式为
式中,PB(xi)为粒子xi被选中的概率;Di为xi的个体拥挤距离。
个体拥挤距离含有无穷大会造成轮盘法选择失效,因此计算概率时定义边界个体的拥挤距离为除去这些个体后其余个体拥挤距离的中位数。
通过比较个体历史最优值与当前粒子的支配关系来确定是否更新个体最优值。若当前粒子支配该粒子的个体历史最优值,则用当前粒子替换历史最优值;若当前粒子与历史最优值互不支配,则随机选择二者之一作为新的个体最优;否则,保持历史最优值不变。
2.4 种群多样性保持策略
2.4.1 粒子编码与计算
借鉴遗传算法的矩阵编码方法对粒子进行编码,编码矩阵如下:
矩阵A是所有工件对应所有生产单元的完全编码,其每一列对应一个生产单元,每一行对应一个工件。矩阵元素aij是区间(0,1)内的一个实数,其大小决定了每个工件在第j个生产单元上的加工顺序。
解码时,对矩阵A的第j(j=1,2,…,M)列的元素a1j,a2j,…,aNj进行大小比较,按照数值从小到大的顺序进行排列,排列结果即为这N个工件在第j个生产单元上的加工顺序。显然,从第二个生产单元开始,还得考虑工件在前面一个生产单元的结束时间,将结束时间和排序结果相结合来决定该工件在该生产单元上的加工顺序。具体说来,若该工件在前一个生产单元的加工没有结束,则考虑编码矩阵排序结果中排在其后的工件是否已结束前一个生产单元的加工,若已结束,则安排该工件进行加工。
2.4.2 基于动态自适应惯性权重进行进化计算
根据上述编码,计算时不再单独考虑粒子在各维空间的信息,而是将编码矩阵A整体作为搜索空间中的一个粒子,直接更新粒子的速度和位置的整体信息。
PSO算法的基本思想是随机初始化一群没有体积没有质量的粒子,将每个粒子视为优化问题的一个可行解,粒子的好坏由一个事先设定的适应度函数来确定。每个粒子将在可行解空间运动,并由一个速度变量决定其运动方向和距离。假设一个由M个粒子组成的群体在D维搜索空间以一定的速度飞行,其中粒子i的位置的第d维分量x(t)id∈[xmin,d,xmax,d],xmin,d、xmax,d分别为搜索空间的下限和上限;速度的第d维分量v(t)id∈[vmin,d,vmax,d],vmin,d、vmax,d分别为最小和最大速度;个体最优位置为P(t)i,全局最优位置为P(t)g。则粒子在t+1时刻的位置和速度通过下式更新获得[5]:
式中,ω为惯性权重;r1、r2为均匀分布在(0,1)之间的随机数;c1、c2为学习因子,通常取值为2;Pid为第i个粒子第d维的个体最优值;Pgd为所有粒子第d维的全局最优值。
惯性权重ω的大小决定了粒子对当前速度继承的多少,较大的ω有利于全局寻优,较小的ω则有利于局部寻优,而根据进化代数进行惯性权重的自适应调整策略有利于加强保持种群多样性的能力,因此本文采取了动态自适应惯性权重调整策略:
其中,r3为均匀分布在(0,1)之间的随机数。本文根据前人经验取ω0=0.9,ω1=0.35。
2.4.3 基于非支配解的内部种群规模自适应调整策略
如果进化多目标优化算法采用小规模种群,那么对于一些复杂的多目标优化问题将很难收敛到理想Parato前沿面,而且很难获得均匀分布的Pareto最优解。因此,如何根据问题的复杂度自适应地调整种群的规模是需要进一步研究的问题[13]。根据非支配解在当前种群中所占的比例来自适应地调整种群规模是解决该问题的一个可行方向[9]。本文采取下式来更新内部种群大小:
St+1=St(1+Pp) St∈[Ss,Se] (14)
Pp=Np/St (15)
式中,Ss、Se分别为最小、最大内部种群规模;Pp为非支配解在当前内部种群中所占比例。
由式(14)可知,种群规模是逐渐增大的,因此本文采取随机单点交叉策略产生新的个体补充到原始种群以形成新的内部种群。具体操作如下:记录内部种群进化结束时非支配解的个数Np,从原始种群中随机选取Np个个体,从外部种群中随机选取Np个个体,然后采用单点交叉方式产生新的个体复制到内部种群,同时将粒子的当前位置设置为个体最优值,由此形成新的内部种群进入下一代的进化,从而有效地保持了种群的多样性。
2.5 基于自适应的改进PSO算法流程
基于以上分析,本文提出的求解MOP的改进PSO算法流程如图3所示。
针对图3,对该方法的操作步骤描述如下:①初始化内部种群Ps的粒子数为最小规模Ss,迭代次数t=0(初始化时未开始迭代),随机初始化粒子速度vi和位置xi,并将粒子当前位置作为该粒子的个体最优值。②判断St中每个粒子是否是非支配解,若是,则将其放入外部种群,记录外部种群粒子数Sp,转③;否则,转⑥。③删除外部种群中的重复个体以及被支配个体,保留非劣个体。④计算外部种群Pt中各粒子的拥挤距离Di,并将所有粒子基于Di降序排列。⑤判断Sp是否大于Sm,若是,则删除Pt中后Sp-Sm个个体,转⑥;否则,直接转⑥。⑥更新全局极值Pg。判断内部种群规模St是否超出规模上限Se,若是,直接转⑦;否则,单点交叉产生新的粒子,并放入内部种群,并记录个体极值,转⑦。⑦t←t+1。进化计算内部种群中个体速度和位置,根据进化计算结果更新个体极值。⑧判断是否达到最大迭代次数tmax,若是,则输出外部种群中的Pareto解集,结束;否则,转②。
3 性能验证与实例仿真
3.1 测试函数和指标及性能分析
将本优化方法应用于经典的多目标优化函数ZDT1:
本文采用了如下2个评价非支配解集优劣的量化标准[14]进行算法的性能分析:
为Pareto解集和Pareto最优解集在目标向量空间上的距离。该指标越小,说明通过本优化方法所找到的非支配解集逼近Pareto最优解集的程度越高。
为量化优化方法所得的非支配解彼此之间分散的程度。该指标越小,说明本优化方法得到的非支配解之间的分布越均匀。
其中外部种群的粒子个数Sp是优化方法所得的非支配解的个数;DSi为第i个解到Pareto最优解在目标空间上的最短距离;di是第i个解到其他解在目标空间上的距离;为di的平均值。
仿真环境:计算机处理器为英特尔Celeron(赛扬) 2.66GHz,内存768MB,Windows XP操作系统,采用MATLAB7.0编写算法程序。
参数设置如下:NSGA-Ⅱ、SPEA2(强度Pareto进化算法)[15]的交叉概率为0.8,变异概率为1/L(L为染色体编码长度),SPEA2的外部集设为200;NSPSO(基于非支配解的PSO算法)[16]内部和外部种群大小均为200。本文算法的内部种群初始规模为200,最大规模为400,外部种群最大规模为200,迭代次数为1000,设置参数c1=2,c2=2,ω0=0.9,ω1=0.35。表1所示为10次独立运行的数据统计结果。
表1的实验结果[17]表明,本文所提算法在收敛性和分布性方面与其他三种算法相比具有较大优势,满足了求解多目标优化的要求。
3.2 应用实例
将本文算法应用于某铜卷加工企业,通过仿真结果验证算法的有效性。
选取该企业的5个加工单元对企业接到的一批订单进行生产调度优化。各产品在各生产单元上的加工时间和交货期如表2所示。
鉴于最大完成时间的方差相对最大拖后时间要小,因此令目标f1为最大完成时间的5倍,目标f2为最大拖后时间的2倍[18]。
算法参数设置:内部种群初始规模Ss=20,最大规模Se=40,外部种群最大规模Sm=20,迭代次数tmax=100,设置参数c1=2,c2=2,ω0=0.9,ω1=0.35,外部种群粒子数初始化Sp=0。
根据以上建立的数学模型与设计的算法,利用MATLAB7.0编程进行调度问题的求解,最终得到外部种群Pareto解集的分布如图4所示。由图4可以看出,算法得到了完整的Pareto解集,并且图中Pareto最优解的目标向量比较均匀地分布在最优界面附近,说明基于拥挤距离排序的策略对外部种群保持的必要性。仿真结果表明,该改进的PSO算法用较小的迭代次数就可以得到较好的Pareto解,保持了算法的快速收敛性,体现了该调度方法的合理和有效性。
4 结语
本文根据铜卷加工生产调度问题的特点,采用改进的粒子群优化算法求解该调度问题。首先采用外部种群保留进化过程中产生的Pareto最优解,同时在外部种群中基于拥挤距离概率更新全局极值,最后基于非支配解的概率使用单点交叉方式产生新的粒子来自适应调整内部种群的大小,同时采用动态自适应调整的惯性权重来更新粒子速度和位置。仿真实例验证了该算法能较好地保持种群的多样性,使算法能够快速收敛到Pareto最优解集。如何将该算法进行调整用于更多约束和评价的混合型生产调度模型,需要进一步研究。
摘要：针对多目标铜卷加工生产调度问题,提出一种自适应的改进粒子群优化算法。该算法采用基于个体拥挤距离排序的外部种群保留策略以避免陷入局部极值,基于个体拥挤距离概率更新全局极值以及基于支配关系更新个体极值,同时采用基于非支配解和单点交叉的内部种群规模自适应调整策略以及自适应动态惯性权重来保持种群的多样性。通过应用实例验证了该方法求解多目标铜卷加工生产调度问题的有效性。
改进粒子群算法的无功优化 第7篇
电力系统的无功优化指在初始运行方式及负荷给定的情况下充分利用电力系统的无功电源,改善电压质量,减小网络损耗。无功优化是典型的非线性规划,具有多变量、多约束、非线性、不连续等特点。粒子群优化算法是基于群智能的随机优化算法,在初始时,粒子群的多样性好,收敛速度快;随着迭代次数增加,种群多样性较差,易于陷入局部最优,这是粒子群算法的主要缺点。针对粒子群算法的上述缺点,提出了梯度粒子群优化算法,将传统的梯度算法与粒子群算法相结合;根据粒子在迭代过程的梯度信息,改变惯性权值,有效提高了粒子在整个可行解空间的搜索能力。其算法的全局搜索能力优于一般的粒子群优化算法。通过算例仿真,表明该算法应用到电力系统无功优化是有效可行的。
1 无功优化的数学模型
电力系统运行应满足安全性和经济性,无功优化是通过调节控制变量(发电机端电压、变压器变比、投切补偿电容器),利用系统无功电源保证用户电压质量,达到网损最小,其优化模型为
式中NK为支路集合;Gk(i,j)为支路k的电导;θij为节点i与节点j之间的电压角度差。
等式约束为
式中PDi 、PGi分别为负荷节点有功功率、发电机节点注入有功功率;QDi、QGi、QCi分别为负荷节点无功功率、发电机节点注入无功功率和补偿节点的补偿无功功率;Ni为与节点i关联的节点号集合,包括节点i本身;s为平衡节点;NPQ为P、Q节点的集合;Gij和Bij为节点导纳阵的系数。
不等式约束为
式中NG、NC、NT、NB分别为发电机节点集合、补偿电容器节点集合、变压器支路集合和总的节点集合; VGi、VGimax、VGimin分别为发电机的端电压幅值、上限和下限;QCi、QCimax、QCimin分别为无功补偿容量、上限和下限;TKi、TKimax、TKiminx分别为变压器分接头的位置、上限和下限;Vi、Vimax、Vimin分别为节点i的电压幅值、上限和下限;QGi、QGimax、QGimin分别为发电机的无功出力、上限和下限。
将负荷节点电压幅值和发电机无功出力不等式约束,以惩罚项的形式处理,构成1个新的目标函数(即罚函数)FQ,可表示为
undefined
式中λ1(t)、λ2(t)为罚因子,罚因子的取值是否适当对算法的收敛速度影响很大。采用undefined为最大迭代次数,t为迭代次数)提高算法的收敛速度。
2 梯度粒子群算法
2.1 粒子群算法
粒子群优化算法是1995年由美国James Kennedy和Russel Eberhart共同提出的[4]。在PSO 算法中,每个粒子的当前位置是优化问题的可行解。PSO 算法是随机初始化1群粒子,然后在迭代过程中通过学习2个“极值”来寻找最优解。1个极值是每个粒子当前所找到的最优解,即个体极值Pbest(d);另1个极值是整个种群当前找到的最优解,即全局极值Gbest(d)。粒子在迭代过程中根据这2个值更新自己的速度向量vi(d)和位置向量xi(d),表达式为
式中t=1,2, … ,t为迭代次数;c1和c2是学习因子,通常c1=c2=2;rand()是介于0和1之间的随机数;ω为惯性权重。
2.2 梯度粒子群算法
梯度粒子群算法[6,7]是利用粒子群在迭代过程中的梯度信息,对惯性权重ω进行调整。由于GPSO算法存在早熟收敛现象,因此,在算法全局最优值出现停滞时,沿负梯度方向变异,改变种群搜索方向,防止算法陷入局部最优。
粒子群算法在求解minf(x)问题的迭代过程中,负梯度方向为
undefined
GPSO算法是根据梯度信息来调整惯性权重的, 将式(11)中ω进行如下调整,以提高ω、vundefined(d)与f(x)负梯度方向一致的概率,加快算法搜索速度,表达式为
undefined
式中 ω1>0,ω2>0,ω3>0,rand()是(0, 1)上的1个随机数, ρ∈[0, 1]。由于梯度法也是局部最优方法,易陷入局部最优,因此ρ一般取1个较小值。
全局最优值f(xgb)连续多次都未更新,则xgb沿其负梯度方向变异,使种群跳出本区域进行搜索,从而使算法跳出局部最优。xgb负梯度方向为
undefined
式中xgb,old为xgb最近1次更新前的xgb。若无xgb,old,即xgb尚未更新过,则xgb沿其随机方向作变异调整。
该方法不需要直接求解目标函数的梯度,也能将梯度法融入粒子群优化算法。
3梯度粒子群算法在无功优化的应用
GPSO算法利用粒子群迭代过程的梯度信息对参数ω进行调整。该算法在参数-1<ω<1都能收敛[7],但参数ω设置决定了算法的收敛速度。因此,采用动态惯性权重的方法,粒子群在初始时多样性较好,参数ω取较大值有利于加快算法的搜索速度。随着迭代次数的增加,粒子群的多样性较差,参数ω应取较小值,有利于提高算法的精度。根据以上分析,参数ω表示为
undefined
式中Tmax为最大迭代次数;t为迭代次数;ω=[0.1,0.8]∪[-0.8,-0.1]。
GPSO算法是1种局部优化算法,在算法全局最优值出现停滞时,对xgb沿负梯度方向变异。在无功优化中的变量中,不仅含有连续变量和离散变量,在变异时应将连续变量和离散变量分开,让所有粒子在该维上的位置重新均匀分布在[-xmax,xmax]上。
从以上的分析,可以得到该算法的步骤如下:
a.输入配电网的原始数据。
b.粒子群初始化。
c.对初始化的粒子群中每个粒子个体逐一进行潮流计算;计算群中每个粒子的适应函数值,得到初始群体最优解和自身最优解。
d.根据式(15)和(17)设置参数ω(设初始=0.8);根据式(12)和(13)调整vundefined(d)和xundefined(d)。
e.对更新后的粒子群中每个粒子个体逐一进行潮流计算;计算群中每个粒子的适应函数值;若粒子的状态优于粒子迭代过程中记录的历史个体极值,以此时状态更新记录;另外,若群中有粒子个体的状态优于历史记录的全局极值,以该个体更新记录。
f. 判断是否满足变异操作的条件,如满足则转至步骤g,不满足则执行步骤h 。
g.首先判断是否满足向负梯度方向变异,然后回到步骤d。
h.判断是否满足优化终止准则,如满足则执行步骤i;若不满足,则返回到步骤d进行迭代循环计算。
i. 输出最优解和无功配置。
4 算例分析
该算法程序应用MATLAB7.1编制,参数设置:粒子群体规模M=50,最大迭代次数maxITER=200,精度为d=0.000 1。
4.1IEEE-30节点系统
对标准IEEE-30节点系统进行测试,详细参数见参考文献[8],IEEE-30节点系统包括41条支路、22个负荷节点、6台发电机、4台变压器和2个无功补偿点。为了验证算法的可行性,在相同的条件下通过标准PSO算法和GPSO算法进行比较,GPSO算法在迭代过程利用梯度信息能够加快算法的收敛速度,算法后期通过变异能够防止PSO陷入局部最优,提高PSO算法的收敛速度和精度,因此GPSO运用到无功优化中更有实用性。通过文献[8]中的GA算法、PSO算法、免疫PSO算法的无功优化进行比较如表1所示。
在初始运行状态下,系统总有功网损为5.72MW。从表1可见, GPSO算法的计算结果优于GA算法、PSO算法和免疫PSO算法,能够更好的获得全局最优解,并且节点电压幅值都在合格范围之内;发电机的无功出力均无越限。本算法优化后的控制变量如表2所示。
4.2IEEE-57 节点系统
对标准IEEE-57节点系统进行测试, IEEE-57节点系统包括80条支路、45个负荷节点、7台发电机、15台变压器和5个无功补偿点。在相同情况下,将标准PSO算法和GPSO算法进行比较,如图1所示。
从图1可以看出,PSO算法收敛速度较快,但易陷入局部最优,GPSO算法在迭代过程利用梯度信息调整参数ω,提高算法的收敛速度,并在算法全局最优值出现停滞时,对粒子沿负梯度变异,能有效防止PSO 陷入局部最优,提高算法的精度,因此GPSO运用到无功优化中更有实用性。为了验证算法的稳定性,在相同情况下单独运行10次,如表3所示。
在初始运行状态下,系统总有功网损为27.88MW。从表3可以看出,在相同条件下,GPSO的收敛精度要优于PSO,说明GPSO算法能够防止PSO算法易陷入局部最优。
5 结论
GPSO算法是传统算法与PSO算法的有效结合,将其运用到无功优化中能有效地提高算法的收敛速度和收敛精度。通过算例仿真,结果表明GPSO算法无功优化能得到优质量的解,进一步降低网损,具有在线运用发展前景。
摘要：通过对传统梯度算法和粒子群算法的研究,提出了将梯度算法和粒子群算法(GPSO)相结合的梯度粒子算法。建立了无功优化的数学模型,将梯度粒子算法运用到无功优化中,通过算例验证,梯度粒子算法能够获得更好的全局最优解,此表明该算法运用到实际中将有利于在线电力系统无功优化。
关键词：梯度,粒子群,无功优化,数学模型,算法
参考文献
[1]赵波,曹一家.电力系统无功优化的多智能体粒子群优化算法[J].中国电机工程学报,2005,25(5):1-7.
[2]邱晓燕,张子健,李兴源.基于改进遗传内点算法的电网多目标无功优化[J].电网技术,2009,33(13):27-31.
[3]吴强.基于改进粒子群算法的无功优化研究[D].成都:四川大学,2006.
[4]Kennedy J,Eberhart R.Particle swarm optimization[A].In:Proceedings of IEEE International Conference on Neural Networks[C].1995,4:1942-1948.
[5]Eberhart R C,Shi Y.Comparing inertia weight s and co-nstriction factors in particle swarm optimization[C].Proc of the IEEEConf on Evolutionary Computation.California:IEEE Service Cen-ter,2000:84-88.
[6]李军军,吴燕翔,甘世红,等.基于梯度PSO算法的PID参数整定[J].科学技术与工程,2009,9(9):2463-2467.
[7]肖健梅,李军军,王锡淮﹒梯度微粒群优化算法及其收敛性分析[J].控制与决策,2009,24(4):560-564.
粒子群优化算法的改进与分析 第8篇
自然界中许多生物体具有一定的群体行为,人工生命的主要研究领域之一就是探索自然界生物的群体行为,从而在计算机上构建其群体模型。通常群体行为可以由几条简单的规则进行建模,如鱼群、鸟群等。虽然每个个体具有非常简单的行为规则,但是群体行为却非常复杂。
微粒群算法(PSO)是由Kennedy和Eberhart等[1,2]于1995年开发的一种演化计算技术,粒子群的概念来源于对一个简化社会模型的模拟。由于粒子群算法简单,编码容易实现,在短短的几年里,PSO算法获得了很大的发展,并成功应用于一些领域。其中“群(Swarm)”符合Millonas[3]在开发应用于人工生命(Artificial Life)的模型时所提出的群体智能的5个基本原则。而“微粒(Particle)”则是一个折衷的选择,因为既需要将群体中的成员描述为没有质量、没有体积的,同时也需要描述它的速度和加速状态。
1 基本粒子群优化算法
粒子群算法是对鸟群捕食行为的模拟。设想这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在那里,但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。粒子群算法从这种模型中得到启示并用于解决优化问题(粒子群算法中,每个优化问题的解看作是搜索空间中的一只鸟,我们称之为“粒子”)。所有的“粒子”都有一个由被优化的函数决定的适应值(Fitness),每个粒子还有一个速度决定它们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。
1.1 算法基本原理
粒子群算法初始化一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体最优解,另一个极值是整个种群目前找到的最优解,这个极值是全局极值。在找到这两个最优值时,粒子根据这两个值来更新自己的飞行速度和新的位置。
一个由m个粒子(Particle)组成的群体(Swarm)在D维搜索空间中以一定的速度飞行,每个粒子在搜索时,考虑到了自己搜索到的历史最好点和群体内(或邻域内)其它粒子的历史最好点,在此基础上进行位置(状态,也就是解)的变化。
第i个粒子的经历过的历史最好点表示为:
群体内(或邻域内)所有粒子所经过的最好的点表示为:
粒子的位置和速度根据如下方程进行变化:
这里,C1、C2称为学习因子,为常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。r1、 r2是在[0,1]区间内均匀分布的伪随机数。粒子的速度被限制在一个最大速度的Vmax范围内。其中K表示迭代次数,迭代中止条件一般选为达到最大迭代次数或粒子群目前搜索到的最优位置满足预先设定的最小适应度值。
粒子群算法中有全局和局部两个模型。在全局模型中,将粒子群中所有的粒子都作为粒子的邻域成员。在局部模型屮,有两种方式组成邻域:一种是按粒子的编号来取粒子的邻域,另外一种就是按照粒子的欧式距离来取粒子的邻域。
1.2 算法基本原理
PSO的算法流程如下:
①初始化一群微粒(群体规模为m),包括随机位置和速度;
②计算每个微粒的适应值;
③对每个微粒,将其适应值与其经历过的最好位置作比较,如果较好,则将其作为粒子个体历史最优值,用当前位置更新;
④对每个微粒,将其适应值与群体内或者邻域内所经历的最好位置作比较,如果较好,则将其作为当前的全局最优解;
⑤根据方程(1)、(2)变化微粒的速度和位置;
⑥如未达到结束条件(通常为足够好的适应值或达到一个预设最大迭代次数),则返回步骤②。
2 粒子群算法的改进
基本粒子群算法概念简单,收敛快,其核心代码也只有短短的几行,实现起来比较容易。但其搜索的精度低,而且很容易陷入局部最优解。在基本PSO算法的基础上,己经出现了各种有意义的通过参数来改进PSO的算法。下面将主要介绍两种基于惯性权重的粒子群算法。
2.1 基于固定惯性权重的粒子群优化算法
由式(1)可以看出,公式的右边由三部分组成:第一部分是粒子更新前的速度,而后两部分反映了粒子速度的更新。美国的Shi与Eberhart研究发现公式(1)的第一部分V1由于具有随机性且其本身缺乏记忆能力,有扩大搜索空间,探索新的搜索区域的趋势,因此,具有全局优化的能力。在考虑实际优化问题时,往往希望先采用全局搜索,使搜索空间快速收敛于某一区域,然后采用局部精细搜索以获得高精度的解。于是为了改善算法的收敛性能和为了更好的控制算法的探索和开发能力,Shi和Eberhart在1998年的论文中引入了惯性权重的概念[4],将速度更新方程修改为:
这里W称为惯性权重,其大小决定了对粒子当前速度继承的多少,合适的选择可以使粒子具有均衡的探索和开发能力。固定权重的选择就是选择某一常数作为权重值,在优化过程中不变。可见,基本PSO算法是惯性权重为1的特殊情况。
2.2 基于时变惯性权重的粒子群优化算法
早期将粒子群算法中的惯性权重定义为常数,但是后来实验发现,动态的惯性权值比固定获得更好的寻优结果。动态惯性权值可以在PSO搜索过程中线性变化,也可以根据PSO性能的某个测度而动态改变,比如模糊规则系统。目前,采用较多的惯性权值是Shi和Eberhart建议的线性递减权值策略,即:
其中,Tmax为最大进化代数,Winit为初始惯性权重,Wend为进化至最大代数时的惯性权值。
3 实验分析
为了研究参数取值对粒子群优化算法的影响,本文选取进化计算中的标准函数——Schaffer函数进行测试。Schaffer函数的表达式如下;
其中5),X=[Xi X2],x1,x2∈(-100,100),函数维数为二维。函数的最大值为1,且全局极大点在[0,0]处,在距全局最优值周围有无限多个局部极值。由于该函数的强烈震荡特点及全局极大点被无限多个局部极大点包围的特点使得一般算法很难找到该函数的全局最优值。因此,选取该函数可以很好地测试粒子群算法中参数取值对算法优化性能的影响。
3.1 固定惯性权重和时变惯性权重粒子群算法优化性能的表现
惯性权重是PSO算法中一个重要的参数,在固定惯性权重下,粒子群算法具有相同的开发和探索能力,时变惯性权重可以使粒子群在不同的优化时期具有不同的开发和探索能力。以下是基于固定惯性权重和时变惯性权重粒子群算法在函数优化中的不同表现,如表一所示。
参数设置:参数一:w=0.6.C1=c2=1.7[5];参数二:w=0.729,c 1=c2=1.494[6];参数三:线性递减范围,0.9-0.4/4000,C1=C2=2,0.9-0.4/1000,c1=c2=2;粒子的规模都为20,种群最大迭代次数都为4000次,函数运行20次。
表一固定惯性权重和时变惯性权重粒子群算法在函数优化下的表现
实验结果表明:在基本粒子群优化算法中,通过多次选取参数都很难达到收敛的效果,函数也无法找到最优值。加入了惯性权重后,算法在收敛性和稳定性有了很大的提高。文中推荐的固定惯性权重和相应的学习因子都具有不错的优化效果。如果将时变惯性权重的递减率提高后,基于时变惯性权重的粒子群算法有很好的收敛率和收敛速度。当惯性权重线性变化的范围缩小时,粒子群优化算法若能搜索到全局最优点,那么需要的迭代次数可能较少。这是因为较大的惯性权重有利于增强粒子群优化算法的全局搜索能力,较小的惯性权重有利于增强粒子群优化算法的局部搜索能力。
3.2 种群规模对PSO算法在函数优化上的影响
实验中,c1,c2均取为常数2,时变权重范围为0.9-0.5,粒子最大速度100,最大迭代次数2000,种群进化过程中惯性权重随迭代次数线性变化。表二列出了在Schaffer函数优化过程中种群规模与达优率的关系。
实验结果表明:当种群规模变大时,粒子群优化算法的达优率增大。这是因为粒子越多增大了粒子群优化算法搜索到全局最优点的概率。但是,种群规模越大,粒子群优化算法的复杂度也相应的增加。因此在求解优化问题时综合考虑粒子群优化算法的效率和计算复杂度,不宜选择过大的种群规模。
3.3 学习因子对PSO算法在函数优化上的影响
实验中,时变惯性权重范围为0.9-0.5,种群规模为30,粒子最大速度100,最大迭代次数2000,群进化过程中惯性权重随迭代次数线性变化。表三给出了在Schaffer函数优化过程中学习因子与达优率的关系。
由表三可知,当c1和c2取四组不同值时算法的达优率也有所不同,其屮c1=2,c2=2时算法的达优率最好达到了85%。这表明粒子的“自我认知”和“社会认知”在算法中具有相等的权重时候,算法有较好的搜索和开发能力,能以更大的概率找到全局最优值。
4 结束语
粒子群算法简单,表达式中包含的参数较少,所以参数取值的变化直接影响着算法的性能。早期基本粒子群算法是将惯性权重定为1的特殊情况,但是只取固定惯性权重时求解的结果并不理想。惯性权重随时间线性减小,可以调节粒子群算法中的开发和探索能力,即全局和局部搜索能力。因为搜索前期较大的值可以使粒子快速找到较好的搜索区域,后期较小的值使粒子可以在较好值附近进行高强度搜索。实验表明惯性权值值从1.4到0、0.9到0.4[7]线性变化的时候比w取固定值要更好。
种群规模取值通常不用太大,根据shi等人的研究[8]表明粒子群算法对种群规模不是特别的敏感;当种群中粒子数目小于50的时候,它对算法的优化性能影响较大;当粒子数目大于50的时候,规模的变化对优化算法的影响开始减小。同时,粒子数目过多也会增加整个算法的复杂度,使得计算时间变长。因此在实际应用中,一般问题将粒子数目控制在30个,只有对于较复杂的问题,粒子群规模取值为50或者稍大于50。
在早期实验研究当中,通常将c1,c2均取为常数2,使得“自我认知”分量和“社会认知”分量的权重相等。但是经过大量的实验表明:c1,c2取常数时可以得到较好的解,但不一定必须为2。也有其它研究表明当W=0.7298时,c1和c2均取1.49445较好。
参考文献
[1]Kennedy J, Eberhart R.Particle Swarm Optimization[C].IEEE Int'l Conf.on Neural Networks. Perth,Australia,IEEE Service Center Piscataway NJ, 1995:1942-1948.
[2]Eberhart R,Kennedy J.A New Optimizer Using Micro Machine and Human Science,Nagoya,Japan:IEEE Service[C].Center Piscataway NJ,1995:89-43.
[3]epstein J M,Axtell R.Growing Artificial So- cieties-Social Science from the Bottom Up[M],MA:MIT Press,1996.
[4]Shi Y,Eberhart R.A modified particle swarm optimizer[C].In.IEEE World Congress on Computational Intelligence.1998:69-73.
[5]Ozcan E,Mohan C.Particle swarm optimization: Surfing the waves[A],Proc of the congress on Congress on Evolutionary Computation[C],Washington DC,1999: 1939-1944.
[6]Eberhart R C,Shi Y,.Comparing inertia weights and constriction factors in particle swarm optimization [A],Proc IEEE Int Conf on Evolutionary Computation [C],San Diego,2000:84-88.
[7]Shi Y,Ebcrhart R C.Empirical Study of par- ticle swarm optimization[C].Procedings of Congress on Evolutionary computation.Piscataway:IEEE Service center,1999:1945-1949.
一种改进的粒子群优化算法 第9篇
各种生物均具有一定的群体行为。群体智能(Swarm Intelligence,SI)[1]的概念正是源于对蜜蜂、蚂蚁等群居生物群体行为的观察和研究。通常将这样一种模拟群居性生物中的集体智能行为的智能计算或优化方法称为群体智能[2]。典型的方法有蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(PSO)。因受到人工生命的研究结果启发,J.Kennedy与R.Eberthart[3]在1995年的IEEE国际神经网络学术会议上正式发表了题为“Particle Swarm Optimization,PSO”的文章,标志着粒子群算法的诞生。粒子群算法是一种演化计算技术,该算法中将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置,当一只鸟飞离鸟群而飞向栖息地时,将导致它周围的其它鸟也飞向栖息地,即通过个体间的信息传递,导引整个群体向可能解的方向移动,在求解过程中逐步增加发现较好解的可能性。
1 PSO算法原理
1.1 PSO基本原理
首先初始化一群随机粒子(随机解),然后通过迭代找到最优解,用粒子的位置表示待优化问题的解,粒子由一个速度决定其飞行方向和速率大小,然后粒子们就追随当前的最优粒子在解空间中搜寻。在每一次迭代中,粒子通过跟踪2个“极值”来更新自己。第一个极值就是粒子本身所找到的最优解,这个解叫做个体极值pbest;另一个极值是整个种群目前找到的最优解,这个极值是全局极值gbest。在找到这2个最优值后,粒子根据这2个值来更新自己的飞行速度和新的位置,直到最后找到最优解[4]。
设群体规模为N,在一个D维的目标搜索空间中,群体中的第i(i=1,2,…,N)个粒子可表示为一个D维矢量Xi=(Xi1,Xi2,…,XiD)T,同时用Vi=(Vi1,Vi2,…,ViD)T表示第i个粒子的飞翔速度,用Pi=(Pi1,Pi2,…,PiD)T表示第i个粒子自身搜索到的最好点。而在这个种群中,至少有一个粒子是最好的,将其编号记为g,则Pg=(Pg1,Pg2,…,PgD)T就是当前种群所搜索到的最好点,即种群的全局历史最优位置。粒子群算法更新迭代计算的公式如下:
Vundefined=wVundefined+c1r1(Pundefined-Xundefined)+c2r2(Pundefined-Xundefined) 。 (1)
Xundefined=Xundefined+Vundefined。 (2)
其中:k为迭代次数;w为惯性权重,取值范围在0.1～0.9之间;c1、c2为加速常数,一般的取值在1.5～2之间;r1、r2为0～1之间的随机数。
1.2 基本PSO算法流程
图1为基本PSO的算法流程,其步骤如下:
(1)依照初始化过程,对粒子群的随机位置和速度进行初始设定。
(2)计算每个粒子的适应值。
(3)对于每个粒子,将其适应值与所经历过的最好位置Pi的适应值进行比较,若较好,则将其作为当前最好位置。
(4)对于每个粒子,将其适应值与全局所经历过的最好位置Pg的适应值进行比较,若较好,则将其作为当前的全局最好位置。
(5)根据2个迭代公式对粒子的速度和位置进行进化。
(6) 如未达到结束条件(通常为了得到足够好的适应值或达到一个预设最大代数(Gmax))执行步骤(7),否则返回步骤(2)。
(7)输出gbest。
2 动态迭代次数的粒子群算法
2.1 动态迭代次数的粒子群(DIPSO)算法原理
由于PSO容易陷入局部最优,跳不出自身的循环,因而必须对其进行改进。这里引入了两个动态的参数,一个是加速因子Pspeed,另外一个是聚集因子Ptogether[5]。具体地说就是,如果目标是寻求极小值,那么当前的最优值一定小于前一次的最优值,Pspeed就可以用下面的公式表示为:
Pspeed=F(gbestT)/F(gbest(T-1)) 。
其中:F(gbestT)为迭代次数为T次时的适应度值;F(gbest(T-1))为迭代次数为T-1次时的适应度值。假定适应度函数的值恒大于零,如果适应度值不满足这个条件,那么就在原适应度值的基础上加上一个正数来满足这个要求。根据上面的假设和定义,0
Ptogether=(gbest·popsize)/paccount 。
其中:popsize为粒子群的个数;paccount为当前迭代次数为T时所有粒子适应度值的总和。Ptogether越大,粒子的聚集程度越大,多样性越小,此时算法容易陷入局部最优。在此基础上把每次仿真的累计迭代次数之和记为temp。在每次仿真过程中,达到收敛的迭代次数是不完全相同的,但是还有一些在仿真过程中也是不收敛的,引入temp这个参数就是用来动态调整的。当迭代次数的累计之和已经达到了事先规定的temp值时,就会对其重新进行初始化。这样做就会使得原先达不到收敛条件的粒子进化速度增加,算法可以在较大的搜索空间内持续搜索,粒子就可以保持大范围的寻优,粒子群就不易陷入局部最优。
2.2 DIPSO算法流程
(1)初始化粒子群的位置、速度,计算粒子群的适应度值。
(2)初始化粒子群的个体最优和全局最优。
(3)如果达到了粒子的收敛条件,执行步骤(7),否则执行步骤(4)、步骤(5)。
(4) 用迭代速度和位置公式对粒子群进行更新,并计算粒子的适应度值,更新粒子的全局最优值和个体最优值。
(5) 判断temp是否大于事先给定的一个值,如果大于给定的值,就重新进行初始化,执行步骤(1)。否则执行步骤(4)、步骤(5)。
(6)将迭代次数加1,并执行步骤(3)。
(7)输出gbest和相应的最优适应度值。
3 仿真实验和结果
下面讨论Freudenstein-Roth函数和Goldstern-Price函数的优化问题。这两个函数用基本PSO进行优化收敛速度比较慢,当仿真次数为50次,迭代次数为700代时,有35个多仿真次数均达不到收敛。
图2为PSO和DIPSO两种算法下Freudenstein-Roth函数最优适应度进化曲线。从图2中可以看出,PSO和DIPSO算法在刚开始时收敛速度是一样的,当算法进入第3代以后DIPSO算法收敛速度明显优于基本PSO算法。在进行到30代时DIPSO算法已经很好地达到了所要求的精度,而基本PSO的函数值还在0.7左右。表1为两种算法的性能比较,粒子的个数为20个,运行50次,收敛精度为10-5,迭代次数为100。
图3为PSO和DIPSO两种算法下Goldstern-Price函数最优适应度进化曲线。从图3中可以看出,PSO和DIPSO算法在刚开始时收敛速度是一样的,当算法进入第4代以后DIPSO算法收敛速度明显优于基本PSO算法。在进行到19代时DIPSO算法已经很好地达到了所要求的精度,而基本PSO的函数值还在3.2左右。表2为两种算法的性能比较,粒子的个数为20个,运行50次,收敛精度为10-5,迭代次数为700。
4 结论
基本PSO算法的主要缺点是易陷于局部极小点,对此本文提出了一种改进的PSO算法——动态迭代次数PSO算法,它既保持了PSO算法结构简单的特点,同时又引入了动态的迭代次数,从而帮助算法摆脱局部极小点的束缚,提高非线性优化的精度。仿真实验结果表明,本文所提出的DIPSO算法优于线性减小惯性权的基本PSO算法。
摘要：针对粒子群算法容易陷入局部最优的缺点,在改变动态惯性权值的基础上,提出了一种动态迭代次数粒子群算法DIPSO(Dynamic Iterative Particle Swarm Optimization)。该算法根据每个周期内达到收敛的迭代次数不同,在一个周期内,当其和累积小于某个值时,就对其重新进行初始化,从而使算法具有动态的自适应。通过对几种典型测试函数的优化,结果表明,DIPSO算法的收敛速度明显优于PSO算法,收敛精度也有所提高。
关键词：粒子群,迭代次数,自适应
参考文献
[1]王万良,唐宇.微粒群算法的研究与展望[J].浙江工业大学学报,2007,35(2):135-140.
[2]Reynolds C.Flocks,herds,and schools:a distributedbehavioral model[J].Computer Graphics,1987,21(4):25-34.
[3]Kenned Y J,Eberhart R.Particle swarm optimization[C].Perth:IEEE Piscataway,1995:1942-1948.
[4]曾建潮,崔志华.一种保证全局收敛的PSO算法[J].计算机研究与发展,2004,41(8):1333-1338.
基于熵的改进粒子群优化算法 第10篇
关键词：粒子群优化,系统熵,全局搜索能力
1 引言
粒子群优化 (Particle Swarm Optimization, 简称PSO) 是由Kennedy等提出的一类模拟群体 (swarm) 智能行为的优化算法[1]。其思想来源于对鸟群捕食行为的研究, 它与遗传算法和蚁群算法相比, 有算法简单、容易实现、可调整参数少等特点, 因此被广泛地用于结构设计[2]、电磁场[3]和任务调度[4]等工程优化问题。
目前对PSO算法研究的论文很多, 部分学者对PSO的算法进行了各种各样的改进, 如Leandro dos Santos Coelho提出了一种带有混沌变异算子的量子粒子群优化算法[5], 文中利用混沌序列代替随机序列从而增加粒子的多样性, 防止粒子陷入局部收敛;Chen DeBao等给出了一种自适应规模的粒子群优化算法及其应用[6], 从而保持粒子的多样性; Yan Jiang等给出了一种改进的粒子群优化算法[7], 在这篇文章中, 粒子被分解为几个子群体, 每一个群体独立地进行搜索, 每个一定的周期后, 粒子将被重新分解, 以便信息共享;Bilal Alatas等提出了一种混沌粒子群优化算法[8], 该算法对参数采用混沌系统, 即每次进化时随机数的值由混沌发生器产生;Xingjian Cai等提出了一种分散式的粒子群优化算法[9], 该算法对原始PSO算法中的社会系数进行了重新的设定, 依据为外在的选择压力即每个粒子根据自身的记忆及群体的记忆来确定搜索的方向, 且设定采用了一种与自适应相关的分散式方式;Xiyu Liu等提出了一种小生境的粒子群优化算法[10], 本文将PSO算法和动态的小生境共享技术结合在一起, 并给出了其在建筑物设计上的应用;Bin Jiao等给出了一种动态惯性权重的粒子群优化[11], 在这篇文章中, 惯性权重的值随着迭代次数的增加是逐渐减小的;Jin Yisu等提出了一种自适应的粒子群优化[12], 该算法根据每一维粒子的分布来更新速度, 为了跳出局部搜索, 该算法采用了一定概率的交叉更新策略;陈国初等给出了一种两群的微粒群优化算法[13], 将粒子的搜索空间及粒子分解为均匀的两部分, 这两部分粒子的搜索目标是相反的, 当粒子有可能陷入局部最优解时, 交换两组粒子及搜索到的历史最优和最差位置;巩敦卫等提出了一种新型的粒子群优化算法[14], 该算法中粒子的位置只与粒子自身速度及其领域内的最优粒子的位置有关, 且提出了一种粒子速度小概率变异, 劣势速度随机赋值的方法;李勇刚等提出了一种弹性的粒子群优化算法[15], 粒子的速度仅仅依赖于其方向信息, 与粒子的位置信息无关, 且在搜索中弹性地修正粒子速度的幅值;刘建华等提出了一种相似度的新型粒子群优化算法[16], 本文给出了粒子相似度的概念, 根据相似度的不同来动态的调整惯性权重。除此之外, 还有很多学者都对PSO算法进行了改进。纵观国内外的研究可以发现, 对PSO算法的改进主要集中在算法参数的各种各样的调整和粒子更新的结构进行调整, 目的基本上都是使粒子跳局部最优, 使其全局搜索能力和局部搜索能力达到最佳的平衡状态。也有部分的学者是研究离散的PSO算法, PSO的理论研究目前还比较少。
本文将PSO算法中的粒子、搜索空间等看做是一个系统, 从系统中熵的变化对PSO算法的影响角度进行分析研究, 给出了两种改进的策略, 目的都是为了增加系统的熵, 使系统呈现混沌状态, 从而提高PSO算法的性能。
2 基本的PSO算法
PSO以模拟鸟的群体智能为特征, 以求解连续变量优化问题为背景。在PSO中, 每只鸟被称之为一个粒子, 每个粒子用其几何位置和速度向量表示, 在问题的求解中, 每个粒子参考自己的既定方向, 所经历的最优方向和整个鸟群所公共认识到的最优方向来确定自己的飞行。PSO是Kennedy和Eberhart[1]于1995年首先提出, 后采用下列的公式对粒子群进行操作:vid=wvid+c1r1 (pid-xid) +c2r2 (pgd-xid) (1)
xid=xid+vid (2) 其中, i=1, 2, …, m, d=1, 2, …D;学习因子c1, c2是非负常数;r1, r2是[0, 1]间的随机数, vid=[-vmax, vmax]; vmax是常数。w为惯性系数, 为非负数, 第i个粒子用一个D维的向量xi= (xi1, xi2, …, xiD) 表示, 它在空间的飞行速度其用vi= (vi1, vi2, …, viD) 表示;第i个粒子迄今为止搜索到的最优位置用pi= (pi1, pi2, …, piD) 表示, 整个粒子群迄今为止搜索到的最优位置用pg= (pg1, pg2, …, pgD) 表示。
迭代终止条件根据具体问题一般选为最大迭代次数或粒子群迄今为止搜索到的最优位置满足预定最小适应阀值。方程 (1) 和 (2) 是基本的PSO算法迭代公式。
3 两种基于系统熵的改进的PSO方法
3.1 PSO系统熵的分析
熵是系统有序度或混乱度的量度。系统的混乱度与系统的熵是正比例的关系, 即系统混乱度越大, 系统的熵越大;系统的熵越大, 系统的混乱度越大。熵是一个状态函数。PSO系统的熵在搜索最优解的过程中是时刻变化的, 粒子越有序, 此时系统的熵越小, 越不利于全局搜索。而当粒子陷入局部最优时, 此时系统地熵已经很小, 要想让粒子跳出局部最优, 就需要增加系统的熵, 即粒子的混乱度需要增加。学者Boltzmann用统计学方法证明系统的熵和系统可能存在的微观状态数有关, 系统的熵随着系统微观状态数的增加而增加的, 具体为系统熵与系统的微观状态数的对数成正比例关系。所以在PSO系统中, 当PSO系统的熵变小时, 此时可以通过增加粒子数来改变此时的系统状态, 从而改变系统的混乱度, 增加系统的熵, 增强全局搜索。又根据最小熵原理, 种群如果在没有强烈干扰的情况下, 它本身的总熵总是在减少的, 有序性是在逐渐地增加的, 从这个意义上看, 我们在迭代达到一定的代数后也需要给种群一个干扰, 使其总熵变大, 增强混乱性。但是根据最大熵原理, 若系统达到熵的最大的无序状态时, 意味着系统的解体和生命的死亡。所以在增加PSO系统熵的时候, 要有一定的限度, 本文采用的是在搜索的过程中, 熵的值应该一直保持在初始状态熵值之下。
在PSO系统中, 当粒子陷入局部搜索时, 系统的熵变小, 此时系统有序, 为了增强全局搜索能力, 即增加系统的熵。我们采用两种办法, 一是增加PSO系统中粒子的数量, 但系统中的粒子数会很大, 这样就降低了计算的效率, 再结合最大熵原理, 所以在一定的进化代数后, 要减少系统中一些作用不大的粒子;再一种是增加粒子的无序性, 即采用一定的差的个体来增加系统的无序性。以社会进化而言, 当社会有序时, 可以适当的加入一些差的个体, 从而更快地推动社会的进步, 因为只有解决社会中存在的问题, 社会才能不断地进步。
3.2 两种改进的PSO算法
(1) 动态改变粒子数的PSO算法 (DCPS-PSO)
根据上面分析, 给出一种动态改变粒子数的PSO算法, 其核心思想是:当粒子连续Δ次找不到最优解时, 即连续Δ次进化的最优解值没有改善, 此时粒子的有序性在很大的程度上增强了, PSO系统的总熵减小了, 不利于全局搜索, 即此时粒子很可能陷入了局部最优, 为了增强全局搜索, 使粒子跳出局部最优, 必须增加系统的熵, 此时我们采用增加粒子的数量来达到增加系统熵的目的。但是当粒子数增加到一定数量时, 根据最大熵原理, 为了保证系统不解体, 将粒子数限制在一定的范围内。当粒子数超过最初粒子数的Ω倍时, 将随机保存与最初数量相等的粒子, 其他粒子均删除。也可以采用文献[17]删除粒子数的办法。需要注意的是当粒子数增加时, 虽然全局搜索能力提高了, 但是求解效率降低了 (他们之间的具体关系可参见文献[17]) , 从这个层面上来看, 当粒子数增加时, 也应该给其一个上限。下面给出DCPS-PSO算法的步骤:
Step1:随机初始化粒子群中粒子的位置与速度, 置Δ=15;进化代数i=1, Υ=0, 初始粒子数设为M=M0;
Step2:将粒子的pb (i) 设置为第i代进化后的当前最优位置, pg (i) 设置为第i代进化后群体最佳位置;
Step3:判断算法收敛准则是否满足, 如果满足, 转Step8;否则, 执行step4。
Step4:根据下式计算Υ (其中f (pg (0) ) =0) :
Step5:判断Υ与Δ的关系, 如果Υ≥Δ, 改变PSO系统中的粒子数为
Step6: 判断式M≥ΩM0是否成立, 若成立, 则M=M0, 即从现在的粒子中随机保留M0个, 其余删除, 转step1;
Step7:对粒子群中的所有粒子, 根据式 (1) 、式 (2) 更新粒子的位置与速度, i=i+1, 转step2;
Step8:输出fopt=min{pg (i) }, 算法运行结束。
(2) 部分依赖于最差粒子位置信息的PSO算法 (PDWI-PSO)
PDWI-PSO算法的核心思想是:当PSO系统中的粒子进化到一定的程度后, 同上即此时粒子可能连续Δ次找不到最优解时, 那么粒子的有序性在很大的程度上增强了, PSO系统的总熵减小了, 不利于全局搜索, 从PSO的整个系统内的粒子来看, 可能所以的粒子呈现趋同性, 即此时粒子很可能陷入了局部最优。从社会进化的角度进行分析, 此时相当于社会系统内的所有个体呈现趋同性, 这是很不利于社会进化的。所以将增加粒子的混乱度, 使粒子的进化部分的依赖于系统群体的最差信息, 在算法中表现为粒子的速度与群体的最优位置信息及与粒子自身的最优位置信息无关, 而只依赖于群体的最差位置信息。从系统熵的角度看, 加入了群体的最差位置信息, 系统的混乱度也相应的增加了, 所以系统的总熵也随着增加了, 个体的群同性降低了, 易于粒子进行全局寻优。下面给出PDWI-PSO算法的具体步骤:
Step1:随机初始化粒子群中粒子的位置与速度, 置Δ=15;进化代数i=1, Υ=0;
Step2:将粒子的pb (i) 设置为第i代进化后的当前最优位置, pg (i) 设置为第i代进化后群体最佳位置, pw (i) 设置为第i代进化后群体最差位置;
Step3:判断算法收敛准则是否满足, 如果满足, 转Step7; 否则, 执行step4。
Step4:根据下式计算Υ (其中f (pg (0) ) =0) ;
Step5:判断Υ与Δ的关系, 如果Υ≥Δ, 按照vjd=wvjd+c2r2 (pwd-xjd) 更新粒子的位置, 否则, 转step6;
Step6:对粒子群中的所有粒子, 根据式 (1) 、式 (2) 更新粒子的位置与速度, i=i+1, 转step2;
Step7:输出fopt=min{pg (i) }, 算法运行结束。
上面的算法中Δ表示连续找不到最优解次数的阈值, Υ表示计算中连续找不到最优解的实际次数, Ω为限制粒子数的范围, 它的大小影响着粒子的收敛速度。
4 数值实验及结果分析
分别用上述两种方法和基本PSO方法对几个函数进行了求解, 在实验中, 根据文献[18], 取c1=c2=1.494, w=0.729, 初始的粒子数M0=30。我们现给出Ω取值的实验结果。
图1、图2分别给出了当粒子数的取值不同时, 函数的收敛情况。图1是以单峰函数Sphere为例, 图2是以多峰函数Griewank为例。
从图1、图2可以看出, 对于单峰函数, 粒子数量的增大会减缓收敛速度。如图1, 而对多峰函数而言, 粒子数量的改变对收敛速度的影响还是比较大的, 通过对实验的分析和其它多峰函数的验证, 表明对于不同的多峰函数, 其粒子数量的改变对收敛速度的影响是不同的, 在此取一个平均的最优值, 通过实验分析, 取Ω=1.2, 即粒子的数量在初始数量的[1, 1.2]倍间时, 收敛的速度是最佳的。
v∈[xmin, xmax], 具体函数及参数为:
①Rastrigin’s函数:
+1, 函数计算时取-600≤xi≤600, xmax=vmax=600, 维数D=30。此函数是多峰函数, 其最优状态和最优值为:min (f (X*) ) =f (0, 0, …, 0) =0。
③Rosenbrock函数:
, 函数计算时取-32≤xi≤32, xmax=vmax=32, 维数D=30。此函数是连续多极点函数, 其最优状态和最优值为:min (f (X*) ) =f (0, 0, …, 0) =4.44×10-16.
分别用PDWI-PSO算法和DCPS-PSO算法及基本的PSO算法 (简称B-PSO) 计算上述几个函数, 下面各表分别给出了上述4个函数在Intel Celeron M processor 1.50GHz 1.50GHz, 704MB PC上运行计算的结果比较。表中Qmax表示进化到最大迭代次数得到的最优值数量级绝对值的最大值对应的的数量级, Qmin表示进化到最大迭代次数得到的最优值数量级绝对值的最小值对应的数量级。Qavg表示进化到最大迭代次数得到的最优值数量级的平均值, tavg表示平均迭代时间。fmax表示进化到最大迭代次数得到最优值绝对值最大值对应的函数值, fmin表示进化到最大迭代次数得到最优值绝对值最小值对应的函数值, favg表示进化到最大迭代次数得到最优值平均值 (针对下降比较快的函数, 比较其最优值的数量级;针对下降较慢的函数, 比较其最优值) , Nc表示最大进化代数。每个问题运行了20次。其中e-∞的含义为此时的函数值为零, e-∞ (a%) 表示搜索到最优值为零的比率为a%.
下面给出这三种算法用于求解单峰函数和多峰函数的收敛性比较图 (以Sphere函数和Ackley’s函数为例作图) 。同时图5给出了粒子的分布情况随着进化阶段不同的变化情况。
从上面的实验结果 (图3和表3) 看出, DCPS-PSO算法和PDWI-PSO算法求解Sphere函数和Rosenbrock函数时, 结果并不比用基本PSO算法求解好, 这主要是因为这两个函数都是单峰函数, 不会陷入局部最优值, 依据我们前面DCPS-PSO算法和PDWI-PSO算法的基本思想可以知道即使此时Sphere函数和Rosenbrock函数值多次未改变, 那是因为已经在全局最优解的附近了, 按照我们改进的两种算法的思路, 要增加PSO系统的熵, 那么此时系统的混乱度增加, 就很有可能使粒子从全局最优解的附近跳出, 然后继续搜索全局最优解, 这样不仅浪费时间, 也在很大的程度上减缓了搜索的效率, 尤其是会导致PDWI-PSO算法求得的解会合最优解偏差很大, 这是因为当粒子并没有陷入局部最优解时, 而根据算法的执行判断会误判粒子陷入了局部最优, 从而粒子速度的更新会依赖于群体中最差的粒子位置信息, 故而导致解在很大程度上的偏离, 这也解释了表3中有的数据为什么会很大。所以建议DCPS-PSO算法和PDWI-PSO算法最好不要用来求解单极值点的函数。
从表1、表2、表4中的数据可以看出, 对具有多个极值点Rastrigin’s函数、Griewank函数和Ackley’s函数, 用DCPS-PSO算法和PDWI-PSO算法来求解效果还是比基本的PSO效果要好, 但是对于不同的函数来说, 其性质也是不同的, 所以对一个特定的函数来说, 用DCPS-PSO算法可能比PDWI-PSO算法要好, 但有时用PDWI-PSO算法可能比DCPS-PSO算法要好, 例如对于Ackley’s函数, 当维数为100时, 用PDWI-PSO算法求解比用DCPS-PSO算法求解要好, 但当维数为300时, 用DCPS-PSO算法求解比用PDWI-PSO算法求解要好, 但是都比用基本的PSO算法来求解好。
图5中从上面到下面的行依次表示粒子的位置变化的变化情况, 进一步说明了粒子多样性的变化情况, 初始时刻系统的熵比较大, 粒子的多样性比较强, 随着迭代的进行, 系统熵在减少, 多样性在下降, 当改变粒子的数目以后, 粒子的多样又有所增加。但随着粒子找到最优解, 其多样性又将减少, 收敛于全局最优解。
5 结论与展望
本文通过分析PSO系统熵的变化情况给出了两种改进的PSO算法, 思想都是在系统的熵减小的情况下增加系统的熵, 采用两种策略达到增加系统熵的目的, 形成了两种改进的PSO算法。这两种算法对于求解多极值函数是有效的, 一般不用于求解单峰函数。通过对几个复杂函数的数值实验, 说明这两种改进的PSO算法用以求解多峰函数是可行的, 有效的, 效果都好于基本的PSO算法。
下一步需要研究的工作可能有以下几个方面:对本文改进的两种PSO算法进行理论分析, 研究其收敛性; 根据影响社会进化的因素, 类比于PSO系统中粒子的进化, 从而更好的更具有针对性地改进PSO算法。
【改进多粒子群优化算法】相关文章：
协同粒子群优化算法08-08
基于粒子群优化的图像去噪算法09-11
粒子群优化算法及其在电力系统中的应用10-13
协同粒子群算法06-07
小生境粒子群算法05-17
粒子群算法的边界问题07-16
混沌粒子群优化07-08
基于粒子群算法的DBSCAN聚类算法研究12-23
离散二进制粒子群优化06-12