量子离散粒子群（共7篇）
量子离散粒子群 篇1
0引言
为了降低配电网网损,提高电网经济效益,要对配电网络进行优化。配电网重构在配电网络优化中具有降低网损、提高供电电压质量、消除过载等作用。中国配电网络馈线负荷分布很不均匀,电压质量不高,因此配电网重构目标函数不能是单一的,需要将降低配电网网损、提高供电电压质量以及负荷分布均衡化等目标函数综合起来考虑,建立多目标函数模型。配电网重构的研究目标大部分以降低网络损耗为主要目标函数,部分文献将几个目标函数综合起来研究。但这些多目标函数优化算法不能找到较好的全局最优解,计算速度慢,受参数影响较大。如遗传算法、蚁群算法、禁忌搜索性法、模拟退火算法等人工智能算法[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.
[12]ME Baran,F F Wu.Optimal capacitor placement on distributionsystems[J].IEEE Trans on Power Delivery,1989,4(1):725-732.
基于高斯变异的量子粒子群算法 篇2
由Eberhart和Kennedy等于1995[1]年提出的粒子群优化算法(Particle swarm optimization,PSO)是一种基于种群搜索的自适应进化计算技术,它源于对鸟群和鱼群群体觅食运动行为的模拟。与其他生物进化算法类似,PSO算法是一种基于迭代过程的优化方法。PSO作为一种并行优化算法,可以用于解决大量非线性、不可微和多峰值的复杂问题优化。目前在电路及滤波器设计、神经网络训练、机器人控制[2,3,4]等领域均取得了非常好的效果。
由于粒子群算法具有收敛速度快,计算简单,易于实现等优点,因此,当它提出以后就引起了进化计算领域学者们的广泛关注。但由于粒子群算法在对多模函数求解时出现了早熟收敛的现象,许多学者对它进行了改进。文献[5]中指出具有惯性因子的粒子群算法不仅有效的提高了原始PSO算法的收敛速度,而且在收敛精度上也优于原始PSO。因此现在对粒子群算法的研究大都是基于这个版本,在本文中我们称作基本PSO算法。量子-粒子群算法[6](QPSO)相对于标准粒子群算法来说,由于粒子随时具有跳出当前局部点的可能性,因此算法具有了更强的全局搜索能力。但QPSO在迭代后期由于粒子的聚集性,算法依然存在着早熟收敛的趋势。
本文首先针对QPSO算法的缺点,提出了基于高斯变异的量子粒子群算法(GQPSO)。该策略针对群体历史最优解能够有效地引导粒子群前进的方向,对群体历史最优解有效地运用了高斯变异因子。由于该策略在保证粒子有效的进行局部搜索的前提下,同时加大了允许粒子对整个搜索空间进行搜索的可能性,从而保证改进以后的量子粒子群算法能够更为快速有效的进行全局搜索。
1 基本粒子群算法介绍
全局优化问题(p)的多个可行解的一个集合称为一个种群(swarm)。种群中的每个元素(可行解)称为一个粒子(particle),微粒的个数称为种群规模(size)。用n维向量Xi来表示第i个粒子的位置,用Vid来表示第i个微粒第d维的速度。粒子在迭代过程中,它自身经历的最佳位置为Ppi=(Ppi1,Ppi2,…Ppin)T,微粒群所经历过的最佳位置用Pg表示。因此,微粒在每一次迭代中的速度和计算函数的评价函数的位置可通过如下两个公式计算:
其中:i=1,2…m;d=1,2…n;w称为惯性因子,根据文献[5]设置为大小随着迭代次数的减少由0.9下降到0.4;rand1和rand2是服从U(0,1)分布的随机数;学习因子C1和C2为非负常数,C1=C2=2;vid=[-Vmax,Vmax],Vmax是由用户设定的速度上限。
2 基于高斯变异的QPSO算法
文献[6]从量子力学的角度出发提出了一种新的PSO算法模型。该模型以DELTA势阱为基础,提出了量子粒子群算法。通过蒙特卡罗随机模拟的方式得到粒子的位置方程为:
其中u为[0,1]范围内变化的随机数,L被定义为
其中
式中β称为收缩扩张因子。第T次迭代时取为β=0.5*(MAXTIME-T)/MAXTIME,M为粒子的数目。pi为第i个粒子的历史最优解,可以由(6)式求得,φ为[0,1]范围内变化的随机数。
根据(4)式可以看出,在QPSO算法中,只有一个参数β决定粒子的位置,同标准粒子群算法相比较更少,QPSO算法更易于控制。另外由于QPSO算法中的粒子能够以一定的概率出现在整个搜索空间中,甚至是一个远离收敛点P的点,因此相对于标准粒子群算法来说具有着更强的全局搜索能力,图1为高斯概率密度分布图。
基于高斯变异因子的粒子群算法主要是借鉴遗传算法中的变异因子来改善粒子群算法的全局搜索能力。以原点为中心的Gaussian:
其中为了覆盖整个解空间,Gaussian的参数分别设置为σ=0.16。
其中t是在[-1,1]内的随机数。算法迭代过程描述为:
Step1:设置最大进化代数,随机初始化每个粒子的位置,初始化pp、p8。
Step2:repeat:
Step3:for each particle j∈[1…D]
Step4:利用(4),(5)式计算每个粒子的适应度值,并移动粒子到新的位置上。
对gbest使用(7)式进行变异并比较两者结果获得最优值。
Step6:until结束条件成立
3 对比试验
3.1 实验设计
本文设计了4类测试实验以分析提出的GQPSO的总体性能:
(1)PSO优化试验;
(2)GPSO优化试验,参数设置参考文献[7];
(3)QPSO[6];
(4)GQPSO,同时引入6个Benchmark优化问题来进行优化分析。根据文献[8]~[9]对测试函数和测试标准的规定,函数形式以及搜索范围的设置见表1。
本文测试的粒子群数目设置为20。基本PSO中使用的vmax设置为xmax。另外针对Matlab语言的特点,使用rand(‘state’,sum(i*30))语句以保证每种算法运行时对应的rand函数种子相同(其中i表示在算法中的当前运行次数),每一种算法独立运行50次。
测试函数中f1~f3是单模函数,对于单模函数来说,算法的收敛速度比实验结果更值得关注,因此本文在列出比较结果的同时也列出比较函数在单模函数上的收敛比较图;对于f4~f5这种高维的多模函数,实验结果的精度比收敛速度更值得关注,因此在本文中列出了各种比较算法解的平均值和标准方差。对于以上两种函数本文分别测试各种比较算法在10,20以及30维下的运行情况。f6是具有较少局部最优点的低维函数,用以测试比较算法在低维函数上的运行情况。所有测试函数的理论最优解都为0。
3.2 实验结果及分析
对于单模函数来说,由于GQPSO针对gbest使用了Gaussian变异因子,因此能够在当前历史最优解附近进行有效的搜索。根据表2的结果可以看出,在单模函数上相对于其他比较函数来说,GQPSO都获得了最优的成绩。另外,图2的结果论证了该算法在收敛速度上都优于比较函数。对于复杂的多模函数,由于GQPSO相对于其他比较算法来说粒子具有更强的跳出局部最小点的能力,同时由于gbest能够提供给粒子群更为有效的进化方向,因此相对于其他算法来说,GQPSO更为彻底的搜索了解空间。根据实验结果无论是全局搜索能力还是稳定性,GQPSO都获得了最好的成绩。对于低维函数的优化能力参考表3的结果,GQPSO依然获得了最好的结果。
4 结论
针对粒子群算法无法保证搜索到全局最优的缺点和搜索精度低的问题,提出了一种基于Gaussian变异的量子粒子群算法(GQPSO)。典型函数优化的仿真结果表明,该算法不仅可有效的避免标准PSO算法的早熟收敛,而且具有寻优能力强、搜索精度高、稳定性好等优点。同比其他使用变异因子的粒子群算法,GQPSO表现出极强的全局搜索能力和快速的收敛速度,接下来该算法的应用和推广将是研究的重点。
摘要：粒子群算法相对于其他优化算法来说有着较强的寻优能力以及收敛速度快等特点,但是在多峰值函数优化中,基本粒子群算法存在着早熟收敛现象。针对粒子群算法易于陷入局部最小的弱点,提出了一种基于高斯变异的量子粒子群算法。该算法使粒子同时具有良好的全局搜索能力以及快速收敛能力。典型函数优化的仿真结果表明,该算法具有寻优能力强、搜索精度高、稳定性好等优点,适合于工程应用中的函数优化问题。
关键词：粒子群,高斯,变异,全局搜索,收敛速度
参考文献
[1]J.Kennedy and R.C.Eberhart.Particle swarm optimization[C],In ProcIEEE Int.Conf.Neural Networks,IV,Perth:IEEE Press,1995.1942-1948.
[2]Jehad I.Ababneh,Mohammad H.Bataineh.Linear phase FIR filterdesign using particle swarm optimization and genetic algorithms[C].Digital Signal Processing,2008,vol.18(4),pp.657-668.
[3]张长胜,孙吉贵,欧阳丹彤,等.求解车间调度问题的自适应混合粒子群算法[J].计算机学报,2009,32(11):2137-2146.
[4]Saska,M.,Macas,M.,Preucil,L.,Lhotska,L..Robot Path Planning usingparticle swarm optimization of Ferguson Splines[C].IEEE Con.EmergingTech.and Factory Auto.,2006,vol.20(22),pp.833-839.
[5]Daniel Bratton,James Kennedy.Defining a standard for Particle SwarmOptimization[A].Proceedings of IEEE Swarm Intelligence Symposium(SIS),Honolulu,USA.2007:120-127.
[6]SUN J,XU WB.Particle Swarm Optimization with Particle HavingQuantum Behavior[A].IEEE Congress.Evolutionary Computation.2004.325-331.
[7]Andrews.P.S.An Investigation into Mutation Operators for ParticleSwarm Optimization[C].IEEE Cong.On Evolutionary Computation,pp.1044-1051,Sep.2006.
[8]M.M.Ali,C.Khompatraporn,Z.B.Zabinsky.A Numerical Evaluation ofSeveral Stochastic Algorithms on Selected Continuous Global Optimiza-tion Test Problems,Journal of Global Optimization[J].pp.635-672,Nov.2005.
量子离散粒子群 篇3
模糊控制策略是解决非线性和复杂控制问题的一种有效的智能控制方法[1]。模糊控制器的设计通常需要专家经验并要对众多的参数进行整定以达到满意的控制效果。这样一个依赖于专家经验的人工寻优过程会给工程应用带来不便。目前, 很多学者致力于用进化算法来优化模糊控制器的参数[2,3,4], 但是很少有文献提出对控制决策表进行优化。控制决策表是模糊控制器的重要组成部分, 在实时控制中是影响控制效果的关键因素。另外, 用于参数优化的进化算法往往需要调整很多参数, 给优化的实现带来了难度。
基于传统粒子群算法 (Particle Swarm Optimization, PSO) 提出的量子粒子群算法 (Quantum-behaved PSO, QPSO) 具有计算机实现简单、鲁棒性强、可调参数少的优点。本文给出一种免疫量子粒子群算法 (QPSO-immune Algorithm, QPSO-IM) , 它根据系统所要达到的性能指标来优化模糊控制器中的控制决策表, 使模糊控制规则更加完善。该算法将免疫算子引入QPSO算法中, 在保留原算法优点的基础上提高了算法的全局搜索能力。模糊控制器和控制决策表的优化设计在SCON-2000模糊控制平台进行了工程化实现, 在对水箱液位模糊控制中取得了令人满意的控制效果。
2 模糊控制系统简介
常规模糊控制系统如图1所示, 其控制可分为模糊化、模糊推理和解模糊三步。
模糊化就是将基本论域上的精确量:误差e和误差变化率ec, 变换为量化论域上的模糊集的过程。模糊推理过程就是对模糊输入量根据制定的模糊规则和模糊推理方法进行模糊推理, 求出模糊输出量, 继而通过解模糊求得确定的控制量。为提高系统的实时性, 通常是根据上述过程离线计算出控制决策表用于控制。水箱液位模糊控制的控制决策表如表1所示。控制过程中, 根据输入信号e和ec查询控制决策表, 所得增量按比例转换后再施加于被控对象。
在系统投运时, 仅基于专家经验构成的控制决策表往往是不完善的, 还要对控制决策表进行参数整定以取得满意的控制效果。由表1可以看出, 控制决策表是一个13×15的实数矩阵, 其参数的人工整定不仅需要丰富的专家经验, 还要耗费大量时间。因此, 控制决策表的自动调整优化是一项具有实际意义的工作。
3 基于QPSO-IM算法的控制决策表优化
3.1 QPSO算法简介
传统粒子群算法将算法中的可行解看作没有重量和体积的粒子, 粒子在n维搜索空间中追随本身目前所找到的最优位置和整个粒子群所找到的最优位置进行迭代飞行[5]。
Sun等人从量子力学的角度提出了一种新的PSO算法模型——量子粒子群优化算法 (QPSO) 。研究结果证明, 在保证种群规模的情况下, QPSO算法的搜索能力优于PSO算法, 而且QPSO算法的参数少, 更容易实现控制[6]。设粒子i的当前位置为xi= (xi1, xi2, …, xin) ;粒子i所经历的最好位置为pi= (pi1, pi2, …, pin) ;整个粒子群所经历的最好位置为pg= (pg1, pg2, …, pgn) , 即搜索到的最优解。粒子根据式 (1) ～ (3) 进行迭代飞行, 达到迭代次数后飞行结束。
xij (t+1) =p′ij±β|mbestj-xij (t) |ln (1/u) (1)
其中,
mbest是各粒子本身所经历的最优位置的平均位置;φ和u是在[0, 1]上产生的相互独立的随机数;β为伸缩因子, 是QPSO算法中唯一的可调参数。式 (1) 中的正负号以相同概率随机产生。
3.2 人工免疫算子的引入
把QPSO算法中的粒子看作人工免疫系统中的抗体, 将免疫的思想引入QPSO算法可以提高算法的性能[7]。基于人工免疫原理, 浓度选择机制保证了粒子 (抗体) 的多样性从而提高了算法的全局搜索能力。设有N+M个粒子, 每个粒子的适应度值为f (·) , 则第i个粒子的浓度为:
从N+M个粒子中选择N个粒子以避免粒子过度集中, 第i个粒子的选择概率为:
另外, 接种机制用在QPSO中, 以保留最优粒子的形式提高算法的收敛速率[8]。
改进后的QPSO算法称为免疫量子粒子群算法 (QPSO-IM) 。
3.3 基于QPSO-IM算法的控制决策表优化
QPSO-IM算法流程如图2所示, 其实现步骤如下。
(1) 编码。
本文要优化的控制决策表是一个13×15的实数矩阵, 如表1所示。采用实数编码方式, 将该矩阵元素以行序组成一维向量, 作为一个粒子。若矩阵的第i行元素表示为aij, 则粒子编码为:
a1j, a2j, …, a13j (j=1, 2, …, 15)
可见, 每个矩阵的编码是一个195维的行向量, 所以控制决策表的优化是一个高维优化问题。
(2) 初始种群的生成。
本文对已经存在但控制效果欠佳的控制决策表1进行优化调整, 以达到满意的控制效果。因此, 没有必要在实数域内随机产生初始种群。而且, 随机产生的控制决策表几乎都无法达到控制目的, 进化中对它们的评价也就没有意义。因此, 初始种群可在表1的基础上产生。本文的方法是按表1编码的各位加上[-c, c]之间的随机实数, 由此产生初始种群, 在可行解空间范围内搜索最优解。正实数c的选取将影响算法的寻优能力。较大的c有助于提高算法的全局搜索能力;较小的c则有助于提高算法的局部搜索能力。在工程应用中, c的选取受制于控制量的约束范围。在执行机构允许范围内, c的选取可参考表1中的最大元素 (aij) max, 即:
c< (aij) max (i=1, 2, …, 13;j=1, 2, …, 15)
(3) 记忆库。
用于保存进化过程中的最优粒子, 记忆库在迭代过程中不断更新。
(4) 适应度值的确定。
本文采用时间与误差绝对值的乘积的积分 (ITAE) 来评价个体性能, 它综合反映了系统的超调量、上升时间以及过渡过程等性能指标[9], 如式 (6) 所示。
ITAE=∫
其中, 积分上限T的设定关系到能否对个体优劣进行有效区分。过小的T无法有效区分个体优劣程度;过大的T不仅过度放大了较差个体的劣势, 而且会增加计算机的计算量, 从而给算法实现带来困难。通常T可取调整ts的2～4倍。据式 (6) 可知, ITAE值较小的粒子具有较好的控制效果。为了使控制效果更好的粒子具有更大的适应度值, 我们将计算出的ITAE值进行转换, 然后用于浓度的计算。这里采用一种线性转换的方式来计算粒子的适应度, 如图3所示。
在进化过程中, 每一代粒子的适应度值由该粒子的ITAE值以及这一代粒子的最大ITAE值和最小ITAE值确定, 则ITAE值为x的个体的适应度值为:
这种变换令某一代的最差个体和最优个体的适应度值分别为0和1, 能够有效区分个体之间差异。需要指出的是, 该变换得出的适应度值仅在该代中有效, 不同代个体不能利用这种变换得出的值进行比较计算。不同代个体只需直接用ITAE值进行比较即可。
(5) 粒子更新的两种方式。
a.迭代更新。由式 (1) ～ (3) 产生N个新粒子;
b.重新生成M个新粒子。生成方式和初始种群的生成方式相同。
(6) 基于浓度的粒子选择。
用式 (4) 计算N+M个新粒子的浓度, 然后依概率公式 (5) 选择N个粒子组成新的群体。
(7) 接种疫苗。
用记忆库中的免疫记忆粒子替换粒子群中适应度较差的粒子。
(8) 结束条件。
达到预先设定的最大进化代数时寻优结束。
4 应用实例与结果分析
LTT三容液位控制实验装置是高等院校的教学实验设备, 主体由三个圆柱形容器罐、若干手动排水阀和一个蓄水池组成。用液位传感器检测容器水位, 用变频器调节泵的转速, 继而改变泵的供水量。本文在自行研制的SCON-2000先进控制系统的模糊控制平台上进行单容水箱液位模糊控制, 考察跟踪参考输入响应和负荷变化时的响应, 并将优化前后控制决策表的控制效果进行了对比。
初始种群规模N=50, 产生的方式是按表1的编码的各位加上[-2, 2]之间的随机数;每次迭代, 产生新粒子数M=10;伸缩因子β在迭代过程中从1.0到0.5线性下降;粒子的每位限定在[-7.5, 7.5]之间;取式 (6) 的积分时间T=4ts;每次迭代时, 选择种群中3个最差粒子替换为免疫记忆粒子;最大进化代数为200。本文同时利用SCON-2000先进控制系统的建模平台对水箱进行建模, 得到的水箱模型为:
优化后的控制决策表如表2所示。
在SCON-2000先进控制平台上对水箱液位进行实时控制, 设定液位为200 mm, 误差量化因子Ke=2.53, 误差变化率量化因子Kec=125, 控制量比例因子Ku=1, 模糊控制器采用增量形式。优化前后的响应曲线以及控制量曲线如图4、图5所示, 可见优化后的控制决策表性能比优化前有了很大的改善。
(1) 优化前, 系统响应的超调量为30%, 调节时间为3.5min;优化后, 系统响应的超调量为5%, 调节时间为2 min。
(2) 优化前, 系统响应的稳态波动在±25mm内;优化后, 系统响应的稳态波动在±10 mm以内。这表明优化后的控制决策表的精度更高。
(3) 在系统稳态时加入负荷扰动, 优化前的系统需要5.5min恢复稳态, 并有超调;优化后的系统仅用2 min就重新到达稳态, 且没有超调。这表明优化后系统响应具有更好的快速性和平稳性。
5 结束语
本文提出用QPSO-IM算法来优化模糊控制器中的控制决策表。算法实现简单, 可调参数少, 使模糊控制决策表的参数整定易于工程应用。实验结果表明:用QPSO-IM算法优化过的控制决策表明显改进了模糊控制器的性能, 从而达到了优化模糊控制器的目的。
参考文献
[1]孙绪刚, 王丽荣.模糊控制在聚合装置的应用[J].化工自动化及仪表, 2001, 28 (4) :29-32.
[2]LINKENS D A, NYONGESA HO.Genetic Algorithm for FuzzyControl, Part 1:Offline System Development and Application[C]//IEE Proceedings-Control Theory and Applications.U-nited Kingdom:IET, 2004:161-176.
[3]ESMIN A A A, AOKI A R, LAMBERT-TORRES G.ParticleSwarm Optimization for Fuzzy Membership Functions Optimiza-tion[C]//IEEE International Conference on Systems, Man andCybernetics.Tunisia:IEEE, 2002, 3:5.
[4]HOMAIFAR A, MCCORMICK E.Simultaneous Design of Mem-bership Functions and Rule Sets for Fuzzy Controllers Using Ge-netic Algorithms[J].IEEE Transactions on Fuzzy System, 1995, 3 (2) :129-139.
[5]KENNEDY J, EBERHART R.Particle Swarm Optimization[C]//Proceedings of the IEEE International Conference onNeural Networks.Australia:IEEE, 1995:1942-1948.
[6]SUN J, FENG B, XU W B.Particle Swarm Optimization withParticles Having Quantum Behavior[C]//Proceeding of 2004Congress on Evolution Computation.Portland:CEC, 2004:325-331.
[7]LIUJ, SUNJ, XUW B, et al.Quantum-behaved Particle SwarmOptimization Based on Immune Memory and Vaccination[C]//Proceedings of the IEEE International Conference onGranular Computing.USA:IEEE, 2006:453-456.
[8]DASGUPTA D.Artificial Immune Systems and Their Applica-tions[M].New York:Springer-Verlag, 1999.
量子离散粒子群 篇4
关键词：Kriging近似模型,粒子群优化算法,一维势垒
1. 前言
Kriging近似方法是拟合精度较高[1~3]的算法之一, 该方法在国内外都有较为广泛的应用[4, 5]。
然而Kriging近似方法中普遍采用高斯函数构造相关矩阵, 而基于传统优化算法 (如:斐波那契法) 的相关矩阵参数θ寻优, 一方面在寻优过程中, 可能会造成相关矩阵的奇异;另一方面寻优过程对初始值依赖性较大。针对第二个方面, 游海龙[6]及陈鹏[7]等人采用随机进化算法对Kriging改进。但是游海龙[6]及陈鹏[7]的研究虽然避免了相关矩阵参数的初值, 却额外引入了的参数——游海龙引入了交叉概率及变异率等, 陈鹏引入了两个加速因子和变异率, 而参数的过多引入可能会造成计算结果再现性降低。
本文为进一步减少参数输入、提高计算效率及结果再现性, 对已舍弃加速因子的量子粒子群算法进行了改进。并将改进的量子粒子群算法运用到了Kriging模型中, 并验证这种改进了的Kriging模型。
2. 数学模型
2.1 Kriging近似模型[4]
Kriging近似方法最早由南非地质学者Krige于1951年提出, 算法经过Matheron[8]及Giunta[9]等人的理论改进, 广泛运用于诸多领域。
在Kriging模型中, 真实未知函数形式如下:
f (x) 是关于x的未知函数, Z (x) 是均值为0、方差为σ2的随机函数。f (x) 相当于对全部设计空间的全局模拟, 而Z (x) 是对全局模拟的背离。
Z (x) 的协方差矩阵为如下表示形式,
R是相关矩阵, R是相关函数常用如下形式的高斯函数:
即为相关矩阵参数, 根据式 (5) 对的寻优结果很大程度上影响了Kriging拟合的准确性。
2.2 粒子群优化算法
粒子群算法是Kennedy和Eberhart于1995年提出的[10], 然而标准的粒子群算法容易陷入早熟, 国内外针对这个问题提出过多种解决方法。Jun Sun等人以DELTA势阱为基础提出了所谓的量子粒子群算法 (QPSO) [11]。
在QPSO算法中, 粒子的速度和位置信息都归结与一个参数。为保证算法的收敛性, 每一个粒子必须收敛于各自的p点, , 是该粒子在第d维的值。
其中:是介于0和1之间的随机函数。
同时在粒子群中引入一个中值最优位置来计算粒子的下一步迭代变量, 该值定义为所有粒子的局部极值的平均值mbest。
因此可以得到粒子的进化方程:
其中:u是 (0, 1) 的随机数, 是系数创造力, 调节它的值能控制算法的收敛速度。通常情况下, 从1.0线性减小到0.5时, 算法可以达到比较好的结果
为了进一步提高QPSO的全局搜索能力, Wenbo Xu等人提出了所谓的动态适应及强化动态适应QPSO算法 (DAQPSO、EDAQPSO) [12]。DAQPSO就是将从线性变化转变成梯度变化, 而EDAQPSO则是在DAQPSO的基础上引入一个所谓的成熟度 (mutation rate, MR) , 来对粒子局部最优位置进行修改。本论文作者理解, PSO具有记忆性, 这种记忆性可以提高寻优效率, 也可能将算法带入“早熟”。Jun Sun, Wenbo Xu及Bin Feng在QPSO中通过 (1) 将速度和位置信息都归结与一个参数 (2) 引入中值最优位置这两个措施从侧面避免“早熟”现象, 对粒子的记忆性并未做过多干预, EDAQPSO恰恰合适的修改的粒子的“记忆”, 从而有助于使算法跳出局部最优。
另外针对公式 (7) , 项是一个随机项, 因此有可能会出现函数绝对值较大的问题, 本文借鉴标准PSO的内容, 称之为速度项并给定其上限, 从而保证每一次粒子的进化都能最大可能的保留“记忆”。但一味限制也可能造成算法陷入局部最优, 同时成熟度的引入增加了在参数设置上的不确定性。因此作者参考一维势垒的“隧穿”理论思想, 引入“隧穿”效应公式来求解成熟度, 从而得到计算成熟度的公式。
本文为叙述方便将这种改进的QPSO算法简称为EQPSO, 基于EQPSO寻优的Kriging模型简称为E-K模型。
3. 算法的实现
根据上文所述原理, Kriging近似方法采用C语言实现, 具体流程如图1。
图1中“值的寻优”采用EQPSO算法进行寻优;“标准化响应点矩阵”标准化过程与构建标准正态分布的方法类似;“构造相关矩阵”过程中需要使用到公式 (3) ;“计算未知点的预测值”过程中使用到了公式 (4) 。
EQPSO算法也采用C语言实现, 程序流程如图2所示。
图2中“参数设置”中需要设置计算域大小、最大迁徙速度、种群规模、粒子的维度 (反应自变量的个数) 及最大迭代次数;“个体的迁移”过程中使用公式 (14) ;“个体最优位置进化”及“种群的进化”过程, 本质上就是计算结果的比较。
为验证EQPSO算法的有效性, 本论文使用Ackley、Schaffer、Grienwank、Rastrigrin函数来验证, 其自变量的取值范围与最优点分析如下:
Ackley是一个具有大量局部最优点的多峰函数, 全局最小值为f (x) =0, 在处获得;Schaffer函数是一个非常困难的函数, 算法容易陷入位于全局最优点附近的同心圆上的局部最优点, 是优点在 (0, 0) 处取得的, 最小值为0;Griewank函数最优点为 (0, 0, …, 0) , 最优值为0;Rastrigrin函数最优点为 (0, 0, …, 0) , 最优值为0。
在验算时, 最大迭代次数设置为10000, 种群数为100 (Griewank函数的为200) , 搜索范围为[-50, 50], 除了Schaffer函数外, 其他函数维数取4。
4.2 测试结果
基于4.1中的四个测试函数, 论文对标准PSO算法 (简称PSO) 、EDAQPSO算法及本文改进得到的EQPSO算法进行比较。其中标准PSO算法中额外设置了两个加速因子及一个惯性因子, 分别为1.8、1.8及1.0;EDAQPSO算法中额外引入成熟度0.08。
4.2.1 优化结果比较
表1~表4给出了三种粒子群算法的对四个测试参数的优化结果。
从以上四个表中, 可以看出粒子群算法确实在整体上具有较强的优化能力, 但是从表2可以得出在对Griewank函数寻优时, PSO算法及EDAQPSO算法陷入了局部最优, 而EQPSO算法则没有陷入局部最优。另外从整体上看, EQPSO算法的优化精度也要好于其它两种粒子群算法。
4.2.2 收敛速度的比较
图3~图6给出了最优适应度与迭代次数的关系曲线。
从图3~图6可以看出, 量子粒子群算法的收敛速度明显快于标准PSO算法的, 而EDAQPSO的和EQPSO的收敛速度差别不明显, 图3中EDAQPSO的收敛速度快于EQPSO的, 而图4~图6中的EQPSO的要略胜一筹。
结合以上优化结果及收敛速度两个方面的比较, 可以得出本文的EQPSO算法具备一定的优势。另一方面EQPSO算法输入的参数更少, 因为参数输入的减少, 其潜在的优化结果稳定性会有不同程度的提高。
4.3 其它参数对优化结果的影响
一般优化算法在处理高维数问题时, 往往会陷入困境, 因此有必要对EQPSO算法做这方面的考察。针对Ackley、Griewank及Rastrigrin函数, 取种群数为400, 搜索范围为[-50, 50], 维数分别取10、20及50, 考察EQPSO算法在处理高维数问题的能力。
经计算一般情况下随着维数的升高算法的寻优能力有降低的趋势。计算结果指出这三种粒子群算法在处理不同高维函数时有各自的优势, 比如标准PSO算法更适合10维的Ackley函数, 而成熟度为0.08的EDAQPSO算法则适合于高维Griewank函数。
针对Ackley函数, 标准PSO算法在20维以上 (含) 陷入局部最优, EDAQPSO算法在50时陷入局部最优 (成熟度:0.02) ;针对Griewank函数PSO在20维陷入局部最优;而EQPSO算法对这两个函数都保持着较为理想的寻优结果。
另外EDAQPSO算法依赖于成熟度的取值, 可以推测标准PSO算法也依赖于加速因子及惯性因子这三个参数的取值, 因此在处理实际问题时, 参数的设置就将依赖于经验。然而EQPSO算法因没有额外的参数输入, 算法计算结果更加稳定, 虽然在个别的高维函数中并非最优秀, 但是对不同函数的普适性较好, 因此在一般的实际问题中具备较高的可信度。
5. Kriging模型的检测
5.1 算例一
本论文采用的验证函数为, 以该公式为基础设置响应点, 通过函数上的其它点来验证近似精度。比较结果如表8所示。其中EDA-K为基于EDAQPSO算法的Kriging模型。
从表5中在插值点内[点 (0.198, 1.98) , 点 (0, 3) ], E-K算法和EDA-K算法都能得到非常精确的结果, 但是插值点外[点 (0, 0) ]会存在些许误差。另外EDA-K算法中当MR设置为0.08时, 对插值点外的预测可以认为是错误的, 事实上此时对参数寻优得到的值为-0.138344, 而其它对参数的寻优值均为0.163444。参数应该是一个大于0的值, 可见EDA-K算法中当MR设置为0.08时寻优出现了错误。
作者针对各个状态反复进行了验算, 发现当MR设置为定值时, 寻优结果有较小概率出错, 以表8验证为例, 当MR设置为0.08时, 在 (0, 0) 处出错概率很大, 而当设置为0.2时, 出错概率明显降低, 可见MR设置成0.2更适合于这个算例。相比较而言E-K算法则始终保持近似结果健壮, 这也印证了4.3节中的讨论结果。因此可以认为参数引入越多, 近似结果的不稳定性越大。
5.2 算例二
本文将E-K算法运用于一个实际案例中, 输入的响应点为11km高度下DLR-F6的CFD计算结果。在已知攻角α和马赫数Ma情况下近似升力系数Cl及阻力系数Cd。表10给出了E-K算法得到的近似结果与CFD计算结果的比较 (测试点不是响应点) 。
从表6中可以得出E-K算法对升力系数的预测结果误差小于1%, 对阻力系数的预测有一定误差, 其原因可能在于: (1) 本文给定的响应点输入总数较少; (2) 阻力系数的数值较小, CFD的计算结果稍有偏差就会产生较大误差。
综合算例一及算例二, 经本文改进得到的E-K近似模型, 不论在对理论函数的近似拟合上还是在实际案例的运用中, 都具备较高的近似拟合精度。同时与其它算法相比, 设置的参数较少, 从而降低了案例的分析难度, 提高了近似结果的稳定性。
6. 结论
本文基于“隧穿”效应的思想, 得到了对成熟度的计算公式 (15) 及 (16) , 并改进了原来QPSO算法中的“速度项”, 得到了所谓的EQPSO算法。将该算法运用于Kriging近似算法中, 得到E-K算法。
由验算结果得出以下结论: (1) EQPSO算法在保持快速收敛速度的同时, 具备更优越的全局搜索能力; (2) Kriging模型的拟合精度严重依赖于参数, 因此在对参数的寻优的过程中, 引入的参数越多可能会导致拟合结果的差错, 而本文基于EDAQPSO算法改进的EQPSO算法则将引入参数最少化, 从而为得到了稳健的近似结果提供了可能。
参考文献
[1]Sack J., Welch W.J., Mitchell T.J.Design and analysis of computer experiments, Statistical Science.1998, 4 (4) :409-435.
[2]Simpson T.W., Mauery T.M., Korte J.J.Comparison of response surface and Kriging models for multidisciplinary design optimization, Proceeding of the7th AIAA/USAF/NASA/ISSMO symposium on multidisciplinary analysis&ptimization, 1998, St.Louis, USA.
[3]Simpson T.W., Peplinski J.D., Koch P.N.Meta-models for computer-based engineering design:survey and recommendations.Engineering with computers.2000, 17 (2) :129-150.
[4]谢延敏.基于Kriging模型和灰色关联分析的板料成形工艺稳健优化设计研究 (D) .上海交通大学.2007.4.
[5]Jakumeit J., Herdy M and Nitsche M.Parameter optimization of the sheet metal forming process using an iterative parallel Kriging algorithm (J) .Structural and Multidisciplinary Optimization, 2005, 29 (6) :498～507
[6]游海龙, 贾新章.基于遗传算法的Kriging模型构造与优化 (J) .计算机辅助设计与图形学学报.2007, 1:第19卷, 第1期.
[7]陈鹏, 李剑, 管涛.基于PSO的Kriging相关参数优化 (J) .微电子学与计算机.2009, 4:第26卷, 第4期.
[8]杜德文, 马淑珍, 陈永良.地质统计学方法综述 (J) .世界地质.1995, 14 (4) :79-84.
[9]Giunta A A.Aircraft multidisciplinary design optimization using design of experiments theory and response surface modeling[D].Virginia Polytechnic Institute and State University, 1997.
[10]Eberhart R.C, Kennedy J.A new optimizer using particles swarm theory[C].NewYork:IEEE Piscataway, 1995:39-43.
[11]Jun Sun, Bin Feng, Wenbo Xu.Particle Swarm Optimization with Particles Having Quantum Behavior (C) .IEEE Proc.of Congress on Evolutionary Computation, 2004.
量子离散粒子群 篇5
Kennedy博士和 Eberhart教授于1995 年提出了粒子群优化(Particle Swarm Optimization,PSO)算法[1]。粒子群优化方法自提出后,由于其收敛速度快、算法简单等优点,目前已成功应用到组合优化[2]、连续问题参数优化[3]、神经网络训练[4]、数据挖掘[5]、故障识别[6]等领域。但是在实际应用中发现PSO易“早熟”且精度不高。因此许多学者对算法提出了很多改进方法和策略。量子进化算法(QEA)[7]是新近发展起来的一种以量子计算的一些理论为基础的概率进化算法,同传统进化算法相比具有更好的群体多样性和全局寻优能力,群体规模较小但不影响算法的性能等优点。基于量子进化算法的优点,文献[8]提出了一种量子粒子群优化算法(Quantum Particle Swarm Optimization,QPSO)。该算法采用量子位的概率幅表示粒子,但惯性因子、自身因子及全局因子的设置仍沿用标准粒子群的设置方法,因此无法有效避免种群在搜索空间中多样性的丢失。因此,本文提出一种基于混沌优化的双种群量子粒子群(Dual Population Quantum Particle Swarm Optimization Based on Chaotic Optimization,BCQPSO)改进算法。首先,利用混沌序列产生两个种群规模相等的种群,以避免早熟收敛、保持种群的多样性;其二,对于其中一个种群采用线性递减的更改权重,对另一个种群利用本文建立的基于混沌序列的自适应惯性权重策略来更新;最后,对两个种群执行融合变异操作。用典型函数的极值优化问题进行仿真实验,结果表明改进算法在搜索能力和优化效率两方面均优于原粒子群优化算法。
1 量子粒子群算法
粒子采用文献[8]的编码方式:
undefined
,每个粒子代表解空间的两个解,分别对应量子态的|0>和[1]>的概率幅:
Pic=(cos(θi1),cos(θi2),…cos(θin)),
Pis=(sin(θi1),sin(θi2),…sin(θin))
由粒子编码方式可知其遍历空间每维均为[-1,1],则要比较粒子优劣需进行解空间变换。设待优化问题第j维变量的取值区间为undefined,粒子Pj上第i个量子位为[αundefined,βundefined]T,则按下式对粒子Pj的两组解进行变换:
undefined
粒子Pi上量子位幅角增量的更新:
Δθij(t+1)=ωΔθij(t)+c1r1(Δθl)+c2r2(Δθg)
粒子上量子位概率幅的更新:
undefined
故粒子Pi更新后的两个位置分别为:
Pic=(cos(θi1(t)+Δθi1(t+1)),cos(θi2(t)+Δθi2(t+1)),…cos(θin(t)+Δθin(t+1)))
Pis=(sin(θi1(t)+Δθi1(t+1)),sin(θi2(t)+Δθi2(t+1)),…sin(θin(t)+Δθin(t+1)))
粒子量子位幅角增量的更新由三个部分组成:惯性部分ω、自身部分c1和社会部分c2。如何选择和调整这三个参数关系到算法是否能避免早熟而又能快速地收敛。因此本文从如何保持粒子多样性,以及如何平衡算法全局搜索和局部搜索之间的矛盾为出发点,提出以下改进策略。
2 基于混沌优化的双种群量子粒子群算法
目前,大多数PSO粒子的初始位置都是采用随机方式初始化,这种方式有可能造成初始搜索解空间的分布程度不均衡。由于混沌序列具有混沌运动的遍历性、随机性、规律性等特点,利用混沌序列的随机性、遍历性来寻找问题的最优解,其随机性保证了大范围的搜索能力,遍历性使搜索过程能在一定范围内不重复地遍历所有状态[9] ,因此可以有效加强种群多样性,为进行全局搜索打下良好基础。本文引入Logistic混沌序列, Zt+1=μZt(1-Zt),t=0,1,2,…,其中,μ为控制参量,当μ=4时,z0≠0.5,产生的混沌序列可以遍历[ 0, 1] 区间。
2.1 基于混沌序列的双种群粒子位置初始化
在进化算法中,种群规模是一个十分重要的参数,种群规模的大小及多样性直接影响着算法的收敛率、收敛速度、可靠性等方面问题,本文提出以下基于混沌序列的双种群粒子位置初始化方法:
步骤1:用Logistic混沌序列代替原有随机数的方式来初始化各粒子。
步骤2:由于混沌序列产生的值在[0,1]区间,而解空间在[-1,1]区间,故对上面产生的初始解取反,产生[-1,0]区间的值,这样便产生两个种群。
步骤3:将上面两个种群合并,再通过随机分组方式分成种群数相等的两组种群。
步骤4:分别用这两组种群的粒子进行进化寻寻优。
由于混沌序列能在一定范围内不重复地遍历所有状态,因此大大增强了种群的多样性。
2.2 基于混沌序列的自适应惯性权重
惯性权重的引入是为平衡算法全局搜索和局部搜索之间的矛盾,惯性权重取值较大时,全局寻优能力强,局部寻优能力弱;反之,则局部寻优能力增强,而全局寻优能力减弱。文献[10]提出一种惯性权重线性改变方式:
undefined
其中,ωmax、ωmin分别是ω的最大值和最小值;t、tmax分别是当前迭代次数和最大迭代次数。这种递减策略虽然可以调节全局与局部的寻优能力,且运算速度快,但在运算的过程中,线性减小惯性系数ω,使得搜索步长逐渐减小,迭代慢慢地收敛到极值点[11]。故本文提出一种基于混沌序列的自适应改变惯性权重的方法,公式如下:
其中,undefined将权重与进化代数联系起来作自适应调整, 使算法在进化初期以较大的权重进行搜索;随着进化代数的增加, 惯性权重逐渐变小, 有利于进化后期的精细搜索;Zt是Logistic混沌序列值, 能让惯性权重在解空间内进行遍历, 有利于提高搜索效率;ωmax、ωmin分别是ω的最大值和最小值。对于两个种群的量子粒子分别用线性递减权重和自适应权重对ω进行更改,线性递减权重用于快速进化,获取最优解,自适应权重用于精细搜索,扩大解空间遍历性。
2.3 基于混沌序列的双种群融合变异
由2.1节产生的种群,在很大程度上增加了种群的多样性,并且通过2.2节的方式各自改变惯性权重,当两子种群独立进化若干代,需执行融合操作,这样可实现两个种群之间的信息交流,既能提高算法的收敛速度,又能在一定程度上保持种群的多样性,再按以下规则重新划分子种群和变异粒子。
(1)随机产生两个0-1之间的随机数α、β,α用于指导分组操作,β用于指导变异操作。
(2) 产生一个混沌序列值Zt,用Zt与α比较,如果大于则将该粒子从刚合并的种群中删除掉,并加入新种群中,该操作直到合并种群的粒子数与新生成的粒子数相等时停止,这样就又生成两个种群用于以后的进化。
(3)利用步骤(2)产生的混沌序列值Zt与β比较,如果大于则用量子Hadamard门对粒子群种群进行变异,公式如下:
undefined
,由上式可以看出,这种变异是一种旋转,对于第j个量子位,转角大小为undefined。
2.4 算法流程
(1)用2.1节的方法产生两个粒子个数相等的种群。
(2)对粒子进行解空间变换,计算适应度。
(3)根据公式进行调整粒子位置,对于种群1使用线性递减惯性权重策略,对于种群2使用自适应递减权重策略。
(4)根据2.3节合并两个种群,并记录最优粒子,如果满足终止条件则退出,否则转到步骤(2)继续进化。
3 对比试验
为验证提出本文算法的有效性,实验中采用如下2个典型函数作为仿真对象,对算法进行对比。
①Ackley:
undefined
②Rosenbrock :
undefined
对于函数(1)和(2),分别用BCQPSO、 QPSO和PSO各优化50次,然后统计平均结果、收敛次数、平均步数作为对比评价指标。三种算法的种群规模均取100,最大优化步数均取500,性能对比结果如表1所示。
从表1的对比结果可以看出,BCQPSO的优化效果最好。这是由于基于混沌序列生成的种群多样性好,并且通过两种惯性权重改变策略,既加速了寻优速度,又能扩大解空间的遍历性,最后又基于Hadamard门进行变异操作,从而提高了寻优能力。
4 结束语
提出了一种基于混沌优化的双种群量子粒子群优化算法。该算法通过引入混沌理论,采用双种群结构并行运行,每个子种群的惯性权重选用不同的更新策略,同时采用Hadamard门进行变异,这使算法在维持种群多样性的同时加快了收敛速度,扩展了解空间的遍历性,能使算法具有较好的全局搜索和跳出局部最优的能力。实验结果表明,BCQPSO算法的优化性能明显优于PSO算法。
参考文献
[1] Kennedy J,Eberhart R C.Particle swarms optimization[C]//Proceedings of IEEE International Conference on Neural Networks,USA,1995:1942-1948.
[2] Ammar W,Nirod C,Tan K.Solving shortest path problem using particle swarm optimization[J].Applied Soft Computing,2008,8(4):1643-1653.
[3] Marcio S,Evaristo C.Nonlinear parameter estimation through particle swarm optimization[J].Chemical Engineering Science,2008,63(6):1542-1552.
[4] Lin C J, Hong S J. The Design of Neuro-fuzzy Networks Using Particle Swarm Optimization and Recursive Singular Value Decomposition[J].Neurocomputing. 2007, 71(1-3):297-310.
[5] Souda T, Silva A, Neves A. Particle Swarm based Data Mining Algorithms for classification task[J]. Parallel Computing. 2004(30):767-783.
[6] Sahin F, Yavuz M Ç, Arnavut Z,et al. Fault Diagnosis for Airplane Engines Using Bayesian Networks and Distributed Particle Swarm Optimization. Parallel Computing, 2007,33(2):124-143.
[7] Hyun K,Kim J H.Quantum-inspired evolutionary algorithm fora class of combinational optimization[J].IEEE Transactions on Evolutionary Computing,2002,6(6):580-593.
[8] 李士勇,李盼池.求解连续空间优化问题的量子粒子群算法[J].量子电子学报,2007,24(5):569-574.
[9] 李广文, 贾秋玲, 刘小雄,等. 基于反馈和混沌变异的自适应进化策略[J] . 计算机应用研究, 2009, 26(6):2056-2058.
[10] Shi Yuhui, Eberhart R. A Modified Particle Swarm Optimizer[C]//Proc. of IEEE International Conference on Evolutionary Computation.Anchorage, Alaska, USA: [s. n.], 1998.
量子离散粒子群 篇6
粒子群算法 (PSO) 与其他算法一样, 是基于种群和进化的概念, 通过个体间的协作与竞争, 实现复杂空间最优解的搜索[1]。但PSO不像遗传算法那样对个体进行交叉, 变异, 而是将群体中的个体看作是在D维搜索空间中没有质量合体积的粒子 (particle) , 每个粒子以一定速度在解空间运动, 并向自身历史最佳位置Pbest和邻域历史最佳位置lbest移动, 实现对候选解的进化。
文献[2] 提出“分支函数叠加法”来构造适应值函数。文献[3] 对遗传算法在软件测试用例生成的性能进行研究, 并提出了两种提高遗传算法生成测试用例效率的方法。文献[4] 将把量子理论应用于PSO算法中从而提出一种改进的粒子群优化算法。文献[6] 提出了一种基于粒子群算法的人脑成像的方法, 本文提出一种基于量子的PSO方法, 并通过实验验证, 其效率明显优于传统的粒子群算法, 解决了PSO算法容易陷入局部最优解的问题。
一、基本PSO模型
1) 初始化例子位置, 将粒子以速记速度随机分布在D维搜索空间;2) 循环;3) 对每个粒子, 评估当前适应函数值;4) 将适应值与之前最佳值相比较, 如果当前值优于历史最佳值, 则将历史最佳值设为当前值, 如果相等, 则等于当前;5) 确定邻域最佳粒子, 将其下标赋予变量g;6) 根据 (1a) 和 (1b) 式更新粒子的位置和速度;7) 如果达到设定目标 (得到最优解或达到最大迭代次数) , 停止循环。
在 (1a) 中, 右边由三项组成, 一个是惯性 (inertia) 或动量 (momentum) 部分, 反映了粒子的运动习惯, 代表粒子有维持自己先前速度的趋势, 第二部分是认知 (cognition) 部分, 反映了粒子对自身历史经验的记忆, 代表粒子有向自身历史最佳位置靠近的趋势。第三部分是社会学习部分. 第一项代体现了粒子的全局搜索能力, 第二项体现了粒子的局部搜索能力。为了更好的控制搜索区域, Shi and Eberhart在1998 年提出了如下的改进模型:
式中ω为惯性权重, 较大的惯性权重有利于全局搜索, 增加种群多样性; 较小的惯性权重有利于局部搜索。由于 (1a) 为ω=1时的特殊情形, (2a) 和 (2b) 称为标准PSO模型。
二、改进的量子粒子群算法
文献[4] 从量子力学的角度出发提出了一种新的PSO算法模型, 认为粒子具有量子的行为, 并根据这种模型提出了量子粒子群算法。本文引入加权因子, 设λ, λ >0 , 在量子空间中, 粒子的速度和位置是不能同时确定的, 可通过波函数ψ来描述粒子的状态 , 通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数。随后通过蒙特卡罗随机模拟的方式得到粒子的位置方程为:
Step 1 粒子群初始化;Step 2 确定粒子的位置矢量;Step3 更新, 判断迭代次数是否达到最大;达到最大则输出结果; 否则Step 4 更新迭代次数加1;Step 5 计算适应度函数值;Step 6 对粒子进行评价;Step 7 对分支函数进行性计算, 如果函数值为0, 输出最佳参数;Step 8 更新粒子的位置矢量;Step 9 进行迭代, 转入step 3
三、应用
粒子群算法可以应用在CT医学成像领域, 为了检验算法的有效性, 我们对人脑的参数应用改进的新型粒子群算法进行估计, 得到了较好的效果。在频域内, 麦克斯韦方程为:
该算法比较传统粒子群算法误差都有所减少.
四、结论
本文提出了一种基于加权的量子粒子群算法, 该算法能解决局部最优问题, 计算误差比传统粒子群算法有所向下降, 计算速度比传统粒子群算法要快。应用实际表明, 该算法有效。
摘要：本文提出了一种新型的量子粒子群算法 (PSO) 。该算法在PSO算法基础上引入量子的概念, 采用加权办法, 从而构造了新型粒子群算法, 该算法解决了PSO算法搜索空间有限, 容易陷入局部最优解的问题。本文把该算法应用到实际中, 实验证明, 该方法是有效的, 其效率也明显高于传统的GA算法和PSO算法。
关键词：空间搜索,粒子群算法,局部最优
参考文献
[1]J.Kennedy and R.C.Eberhart, Swarm Intelligence.Burlington, MA, USA:Morgan Kaufmann, 2001.
[2]KOREL B.Automated software test data generatiton[J].IEEEtransactions on Software Engineering, 1990, l6 (8) :870-879.
[3]Donald J.Berndt and Alison Watkins.Investigating the Performance of Genetic Algorithm-Based Software Test Case Generation[C].High Assurance Systems Engineering, 2004, 1530-2059.
[4]SUN J, FENGB, XUWB.Particle Swarm Optimization with Particles Having Quantum Behavior[A].Proceedings of 2004 Congress on Evolutionary Computation[C].2004.325-331.
[5]SUN J, XUWB.A Global Search Strategy of Quantum behaved Particle Swarm Op timization[A].Proceedings of IEEE conference on Cybernetics and Intelligent Systems[C].2004.111-116.
[6]D.Ireland and M.E.Bialkowski, “Microwave head imaging for stroke detection, ”[M].Progr.Electromagn.Res.M, 2011, 21:163-175,
量子离散粒子群 篇7
MIMO可以在无需增加带宽的情况下,大幅提高信道容量,被认为是下一代无线通信的关键技术[1]。但在实际应用中MIMO信道容量受多方面的影响,很多学者对实际环境中MIMO信道容量的影响作了大量研究[2,3,4,5,6,7],这些研究论文都从一个或几个方面对影响MIMO信道容量的因素进行了深入探讨,并据此给出了一些理论建议,这对于实际应用中尽可能达到最大容量是有益的。然而如何在实际中限制性条件下使MIMO信道容量最大化是一个要考虑的问题。本文综合考虑影响MIMO信道容量的因素,利用量子粒子群算法,在既定的条件下给出MIMO系统架构的最优方案。
1 MIMO信道容量影响因素
1.1 天线数量
MIMO信道容量是随着收发天线数的较小值成线性增加的关系[8,9],图1是对MIMO在不同收发天线数目下的信道容量的仿真,其中Tx为发射天线数,Rx为接收天线数。
由图1可以发现,相比较于传统的一发一收形式,MIMO的信道容量有了显著增加,但实际应用中空间和复杂度的限制,天线数目并不能无限扩展,这就需要在有限的条件下给出最合理的天线设计。
1.2 天线阵列结构
以线性天线阵为例,在不同的天线间隔,以及不同的扩展角条件下,MIMO的信道容量有较大差别[10,11],因为这些因素都在不同程度上影响天线之间的相关性,而天线之间的相关性是决定MIMO信道容量的关键因素[12],图2仿真的是不同相关系数下MIMO信道容量的比较,这里以2×2为例。
由图2可以看出,MIMO信道容量随着相关系数的增加变化较大。天线之间相关性受天线之间的间隔以及扩展角度等因素的影响,而这种影响并不是一个简单的增减函数[13],这就需要在实际条件下仔细分析给出最优的架构。
1.3 天线高度
图3是接收端场强随发送端天线高度变化的趋势,这里假设接收端高为1.5 m。
图3可以看出,接收端的场强不是随发送端天线高度成线性变化的,如果发射天线设计不合理极有可能造成接收端信号的极度衰弱。所以有必要结合实际情况所确定的高度范围对发送端天线进行合理的设计。
1.4 其他典型因素
除了以上提到的关键因素外,还有较多的重要因素影响MIMO的信道容量,在已知和未知信道状态信息的情况下,尤其是在天线数量较多时,MIMO信道容量差距较大[14];而在巷道里,MIMO的信道容量又受巷道尺寸的影响[4];不同的移动速度对MIMO信道容量有不同的影响程度[2]等,这些都是需要考虑的。
2 MIMO信道容量优化
透过以上的分析,发现有必要结合实际情况对MIMO的天线做合理的布置,但同时可以看到,MIMO信道容量受多方面的影响,要作出合理设计需要多点考虑。量子粒子群优化算法[15]在解决这类问题上具有很大优势。
量子粒子群算法是对传统粒子群算法的改进,由于引入了量子的概念,使得此算法具有更高的全局搜索能力,而且需要的参量更少。这里解决主要问题的有粒子的构造,这是最基本的,目的是要寻找最优的粒子;构建惩罚函数,以使得算法能按照既定的要求搜索最优粒子;得到粒子的搜索空间,这就要结合实际条件给出恰当的范围。
2.1 算法设计
首先要构造一个基本粒子X(m1,m2,m3,m4,…),为了节省问题的处理,这里假定m1, m2,m3分别表示天线的间隔、天线高度、天线数目,其他因素可以再继续加上。
其次要构建一个惩罚函数,这是寻找粒子的依据,根据以上的分析,给出一个简单的公式
式中:;μ1,μ2分别表示影响因子;Imin是指M,N中的最小值所组成的单位矩阵;det(·)表示行列式;ξ是信噪比;H表示瑞利矩阵,HH表示H的共轭矩阵;λ,σ,ω,l分别表示波长、角能量分布的标准差、中心到达角以及天线间隔;p,d,r,λ,h1,h2分别表示发送端有效辐射功率、方向系数及收发天线间隔、波长以及收发天线高度;Q定义为[9]
再次,要根据实际情况给出粒子的范围,比如天线高度在50～100 m,天线允许间隔在0～20 cm,天线数目在2～4根,这样就给出了粒子的三维搜索空间。
这些基本的参数给出以后,初始化一群粒子,如X(2,60,3),X(3,58,2),X(5,63,3)等,然后代入迭代公式[15]
式中:pbest,gbest,M分别为个体极值、全局极值以及总的粒子数;ε1,ε2,u分别是在0～1之间的随机数;η是收扩系数。根据式(3)就可以找出一系列的粒子,这里要用到惩罚函数以确定是否为最优粒子。最后根据粒子的范围以及粒子的精度或者迭代次数终止循环迭代,以找出最优的粒子。
2.2 仿真及分析
这里精确到小数后4位,迭代次数为100,然后对信噪比在0～30 dB之间的MIMO信道容量进行优化,同时再对得出的最优粒子进行比较,取其中数值最小的粒子作为最优粒子,这是由于惩罚函数的震荡性导致求出的最优粒子有多个,而其中的最小值代表着成本的最小值,因为数值越小表示高度越低,间隔越小,天线数目越少,这样可以减少信号处理和天线架设的成本。
依据上述条件得出最优粒子X(20,54.374 9,4),这表示天线间隔为20 cm,高度为54.374 9 m,收发天线均为4根时为最优方案,这样根据得出的最优方案再对MIMO信道容量作计算,图4是优化前后的比较。
从图4可以看出,根据量子粒子群算法所得出的最优方案比未进行优化的MIMO信道容量有了较为明显的提高,而实际情况下若无优化,架设天线时很难人工准确找到最佳的方案,所以MIMO信道容量具有一定的随机性。虽然某些情况下未优化的MIMO信道容量也能达到最优值,但是其随机性较大,这会一定程度上影响通信的质量。 而优化之后的MIMO信道容量稳定性较好,没有出现较大的跳跃性,这对实际的应用是有利的。
3 结论
MIMO作为下一代无线通信的关键技术,具有很高的信道容量,但是实现其高容量受到很多方面的限制。本文综合考虑影响MIMO信道容量的各个因素,并给出了其中几个关键因素的仿真情况,透过这些仿真发现,要实现MIMO高信道容量需要对天线根据实际情况作出合理的设计布置。据此,依据量子粒子群优化算法,给出了其中的惩罚函数,并构造了基本粒子,这样根据算法的迭代函数,就可以求出最佳粒子,依据此最佳粒子可以对天线做合理的优化布置。本文中给出的参数中有几个是与MIMO信道容量成正比的,这会很大程度上影响量子粒子群算法的优势,然而在实际情况中,影响MIMO信道容量很多的因素是与其成一定的函数关系,而不是正比例关系,所以本文给出优化算法对此类问题的处理有一定的参考意义。