微粒群优化算法

2024-08-16

微粒群优化算法（共9篇）

微粒群优化算法篇1

摘要：群体智能是目前智能领域非常活跃的新兴研究领域,微粒群算法作为其典型的实现形式,受到普遍的关注。本文分析了基本微粒群算法的特点,改善了动态自适应微粒群优化算法,实验结果证明该方法的优越性。

关键词：粒子群优化算法,惯性权重系数,动态自适应

1 引言

粒子群优化算法(Particle Swarm Optimization,PSO)是由James Kennedy博士和R. C. Eberhar博士于1995年提出的。该算法源于对鸟群、鱼群觅食行为的模拟。该算法具有易于描述、便于实现、需要调整的参数很少、使用规模相对较小的群体、收敛需要评估函数的次数少、收敛速度快、并行处理、鲁棒性好等特点,能以较大的概率找到问题的全局最优解且计算效率比传统随机方法高,有深刻的智能背景,既适合科学研究,又适合工程应用。因此, PSO一经提出立刻引起了演化计算领域研究者的广泛关注,并在短短几年时间里涌现出大量的研究成果,在函数优化、神经网络训练[1]、函数优化问题[2]、模糊系统控制、分类、模式识别、信号处理、机器人技术等领域获得了成功应用。

2 粒子群优化算法描述

2.1 算法原理

PSO先生成初始种群,即在可行解空间中随机初始化一群粒子,每个粒子都为优化问题的一个可行解,目标函数为之确定一个适应值(fitness value) 。PSO不像其他进化算法那样对于个体使用进化算子,而是将每个个体看作是在n维搜索空间中的一个没有体积和重量的粒子,每个粒子将在解空间中运动,一个速度决定其方向和距离。通常粒子将追随当前的最优粒子而动,经逐代搜索最后得到最优解。在每一代中,粒子将跟踪两个极值,一为粒子本身迄今找到的最优解pbest,另一为全种群迄今找到的最优解gbest。假设在D维搜索空间中,有m个粒子组成一群体,第i个粒子在D维空间中的位置表示为Xi=(xi1,xi2,Lxid),第i个粒子经历过的最好位置记为Pi=(pi1,pi2,…pid,), 每个粒子的飞行速度为Vi=(vi1,vi2,…vid),i=1,2,…m。在整个群体中,所有粒子经历过的最好位置为Pg=(pi1,pi2,…pid),每一代粒子根据下面的公式更新自己的速度和位置:

Vi=wvid+c1r1(pid-xid)+c2r2(pgb-xid) (1)

Xi=Xi+Vi (2)

其中,w为惯性权重;c1和c2为学习因子;r1和r2是[0,1]之间的随机数。公式由三部分组成,第一部分是粒子先前的速度,说明了粒子目前的状态;第二部分是认知部分,是从当前点指向此粒子自身最好点的一个矢量,表示粒子的动作来源于自身经验的部分;第三部分为社会部分,是一个从当前点指向种群最好点的一个矢量,反映了粒子间的协同合作和知识的共享。三个部分共同决定了粒子的空间搜索能力。第一部分起到了平衡全局和局部搜索的能力。第二部分使粒子有了足够强的全局搜索能力,避免局部极小。第三部分体现了粒子间的信息共享。在这三部分的共同作用下粒子才能有效的到达最好位置。更新过程中,粒子每一维的位置、速度都被限制在允许范围之内。如果当前对粒子的加速导致它在某维的速度Vi超过该维的最大速度Vdmax,则该维的速度被限制为该维最大速度上限Vdmax。一般来说,Vdmax的选择不应超过粒子的宽度范围,如果Vdmax太大,粒子可能飞过最优解的位置;如果太小,可能降低粒子的全局搜索能力。

3 粒子群优化算法的改进策略

分析基本粒子群优化算法,其搜索过程有两个不足:1)初始化过程是随机的,随机过程虽然大多可以保证初始解群分布均匀,但对个体的质量不能保证,解群中有一部分远离最优解。如果初始解群较好,将会有助于求解效率与解的质量。由于粒子初始化和进化过程的随机性,使pbest和gbest的更新带有一定的盲目性,影响了进化过程的收敛。2)利用式(1)和(2)更新自己的速度和位置,本质是利用本身信息、个体极值信息和全局极值三个信息,来指导粒子下一步迭代位置。这实际上是一个正反馈过程,当本身信息和个体极值信息占优势时,该算法容易陷入局部最优解,分析式(1)和(2)进一步可以发现,当某些粒子的位置及其pbest接近群体的gbest时,其速度更新由wvid决定。w<1时,粒子的运行速度越来越小,接近于零,粒子运行出现“惰性”。随着进化的进行,其他粒子将很快聚集到这些惰性粒子的周围,使进化过早地收敛到局部最优点。总之,微粒群算法存在两个缺点:其一是粒子群优化算法的收敛速度比较慢。其二是粒子群优化算法容易陷入到局部极值点中,导致得不到全局最优解。

为改善粒子群优化算法的不足,改进策略可谓层出不穷,这方面的研究非常庞杂,这些改进基于各种不同的策略和方法。但从根本目的来说,都是为了改进粒子群优化算法的以上两个缺点。对于第一种缺点,在解决实际问题时,通常需要在一定的时间内达到相应的精度,如果耗费很长的计算时间来得到一个可行解,有时是不值得的。造成这种问题的原因是粒子群优化算法并没有很充分的利用计算过程中得到的信息,在每一步迭代中,仅仅利用了全局最优和个体最优的信息,此外,算法本身没有比较充分的优选机制,以淘汰比较差的待选解,从而导致算法收敛速度较慢。要解决这方面的问题,需要充分的吸收进化算法的优点,在粒子的操作中,加入繁殖、变异和优选算子[3],以加快算法的收敛速度。另外一个思路就是把粒子群优化算法较强的全局搜索能力与基于梯度算法的较好局部搜索能力相结合,设计一种混合算法,以克服二者的缺点,发挥二者的优点。造成第二种现象的原因有两方面,一是待优化函数的性质,有许多测试函数是多峰函数、形状复杂,而粒子群优化算法并不是从理论上严格证明收敛于任何类型函数的全局极值点,因此对于复杂的测试函数,很可能难以得到满意的结果。二是粒子群优化算法在运行时,由于算法的参数设计或者是粒子数的选择不恰当等原因,导致在计算的过程中,粒子的多样性迅速的消失,造成算法“早熟”现象,从而导致算法不能收敛到全局极值点。这两个因素通常密不可分的纠缠在一起,很难说在一个具体的问题中,到底是那一个因素在起作用,使得算法不能收敛到全局极值点。有比较多的改进是基于这两个方面的因素,对于第一个方面的缺点,有些研究者试图在函数优化的过程中,动态的改变函数的某些全局或局部的形态,使得函数的形状逐渐的变得简单,但同时又不改变函数的全局极值点的性质。比如可以设计一个变换,随着优化过程的进行,使得函数最终由多峰函数变为单峰函数,从而克服此问题。第二个方面的问题通常可以采用如下方法解决:对粒子群的多样性设置某些指标,比如粒子群的炳,随着计算的进行,实时监测这些指标,这些指标超过某个事先设定的临界值,则对整个群体实施某种操作比如按指定的概率重新初始化,从而改善群体的多样性,克服早熟的问题。

基于上面的理论分析,本节重点讨论以下几个方面PSO算法的改进策略及其效果:调整惯性权重,采用不同的惯性权重调整策略,兼顾全局与局部的寻优能力;引入收缩因子,加快算法的收敛速度,提高算法的性能。

3.1 引入收缩因子

引入收缩因子的粒子群优化算法,其速度更新如下式所描述:

Vid=∅[vid+c1v1(pid-xid)+c2r2(jpgd-xid)]

其中,收缩因子

undefined

实验结果表明,与使用惯性权重的粒子群优化算法相比,使用收缩因子的粒子群优化算法有更快的收敛速度。其实只要恰当地选取因子,带收缩因子的粒子群优化算法可被看作是PSO算法的一个特例。

3.2 调整惯性权重

PSO算法存在易陷入局部最优,出现早熟收敛的问题,许多研究都集中于参数惯性权重w的改进上,w对算法能否收敛具有重要作用,它使粒子保持运动惯性,使其有扩展搜索空间的趋势,改变其取值可以调整算法全局和局部搜索能力的平衡。

在PSO中,搜索陷入局部极值往往表现为微粒几乎停止不动。当群体的最优适应值长时间未发生变化(停滞)时,应根据群体早熟收敛程度自适应地调整惯性权重。若对整个群体采用同样的自适应操作,则一方面全局寻优和局部寻优是矛盾的,不能够同时进行;另一方面,当群体已收敛到全局最优附近时,优秀粒子被破坏的概率会随着其惯性权重的增加而增加,这使PSO算法的性能有所下降。为了充分发挥自适应操作的效能,本文的自适应调整策略,不仅用到群体早熟收敛信息,还根据个体适应值的不同将群体分为三个子群,分别采用不同的自适应操作,使得群体始终保持惯性权重的多样性。惯性权重较小的粒子用来进行局部寻优,加速算法收敛;惯性权重较大的粒子早期用来进行全局寻优,后期用来跳出局部最优,避免早熟收敛。这样,具有不同惯性权重的粒子各尽其责,全局寻优和局部寻优同时进行,在保证算法能全局收敛和收敛速度之间做了一个很好的折衷。

适应值为fi的粒子,其惯性权重w的具体调整方法如下:

3.2.1 fi优于f′arg

满足此条件的粒子是群体中较优的粒子,已经比较接近全局最优,所以应被赋予较小的惯性权重,以加速向全局最优收敛。本文根据粒子适应值按式(3)调整粒子w的惯性权重:

undefined

其中wmin为w的最小值,本文取wmin=0.5。粒子适应值越佳,其惯性权重相应越小,加强了局部寻优。

3.2.2 fi优于farg,但次于f′arg

满足此条件的粒子是群体中一般的粒子,具有良好的全局寻优能力和局部寻优能力。如果惯性权值ω随着搜索的进行按余弦规律减小,开始搜索时ω能较长时间保持较大值以提高搜索效率,在搜索后期ω能较长时间保持较小值以提高搜索精度,本文ω的修正公式为:

undefined

其中: ωmax为搜索开始时最大的ω,ωmin为搜索结束时最小的ω,iter为迭代所进行的步数,MaxStep为允许最大迭代步数。

3.2.3 fi次于farg

满足此条件的粒子是群体中较差的粒子,对其惯性权重的调整引用文献[4]中调整控制参数的方法:

undefined

算法停滞时,若粒子分布较为分散,则△较大,由式(5)降低粒子的w,加强局部寻优,以使群体趋于收敛;若粒子分布较为聚集,如算法陷入局部最优,则△较小,由式(5)增加粒子的w,使粒子具有较强的探查能力,从而有效地跳出局部最优。式(5)中参数k1和k2的选择对算法的性能有较大的影响。k1主要用来控制w的上限,k1越大,w的上限越大。根据前面分析,k1的选取应使式(5)能够提供大于1的惯性权重。本文取k1=1.5,显然w∈(0.5,1.1)。k2主要用来控制式(5)的调节能力,若k2过大,在早期停滞时,w会迅速变得很小,这虽然会加快收敛,却使算法在早期全局寻优能力不足,若k2过小,则式(5)的调节能力不是很明显,尤其是在后期算法不能有效地跳出局部最优。

此外,当算法未搜索到全局最优适应值时,或不满足最优要求时,可采用惯性权重的变异策略。对种群当前的最优粒子的惯性权重按下式进行变异:

w=w(1+ησ) (6)

其中,σ为满足高斯分布的随机数。如此,即可以较大的概率产生小幅度的扰动以实现局部搜索,又可适当产生大幅度扰动以实现大步长迁移来走出局部极小区域。η初值为1.0,每隔一定的迭代代数置η=βη,其中β为[0.01,0.9]之间的随机数。

3.3 算法流程

动态自适应粒子群优化算法DAPSO是在基本粒子群优化算法的基础上,根据群体早熟收敛程度和个体适应值来调整惯性权重的一种改进粒子群优化算法。Logistic方程是一个典型的随机动态系统:

zn+1=μzn(1+zn)n=0,1,2,… (7)

式中μ为控制参量,取μ=4,设0≤z0≤1,系统(7)完全处于随机运动状态。由任意初值z0∈[0,1],可迭代出一个确定的时间序列z1,z2,z3,…。本算法采用次方程对最优位置进行动态优化。算法具体流程如下:

Step 1:初始化设置最大允许迭代次数或适应度误差限,以及相关参数。

Step 2:动态初始化粒子位置和速度。

1)随机产生一个n维每个分量数值在0-1之间的向量,z1=(z11,z12,z12,…z1n),n为目标函数中的变量个数,根据式(7),得到N个向量z1,z2,z3,…zn。

2)将zi的各个分量载波到对应变量的取值区间。

3)计算粒子群的适应值,并从N个初始群体中选择性能较好的M个解作为初始解,随机产生M个初始速度。

Step 3:如果粒子适应度优于个体极值pbest,pbest设置为新位置。

Step 4:如果粒子适应度优于全局极值gbest,gbest设置为新位置。

Step 5:根据公式(1), (2)更新粒子的速度和位置。

Step6:对最优位置Pg=(Pg1,Pg2,…PgD)进行动态优化。将Pgi(i=1,2,…D)映射到方程(3.5)的定义域[0,1],zi=(pgi-ai)/(bi-ai),(i=1,2,…D),然后,用Logistic方程进行迭代产生随机运动变量序列zi(m)(m=1,2,…),再把产生的变量序列通过逆映射pgi(m)=ai+(bi-ai)zi(m)返回到原解空间,得:

Pg(m)=(Pg1(m),Pg2(m),…PgD(m))=(m=1,2,…)

在原解空间中对随机动态变量经历的每一个可行解Pg(m)(m=1,2,…)计算其适应值,得到性能最好的可行解P*。

Step7:用P*取代当前群体中任意一个粒子的位置。

Step8:判断算法的终止条件是否满足,若满足转向Step 10,否则执行Step 9;

Step 9:根据粒子适应值不同采取相应的自适应策略,分别按照公式(3),(4),(5),(6)调整惯性权重w,转向Step 3;

Step 10:若满足停止条件,则搜索停止,输出全局最优位置。

3.4 算法效果分析

为了检测动态自适应粒子群优化算法的效果,采用四个典型的测试函数进行实验,这些函数是:f1(Rastrigrin Function)、f2(Rosenbrock Function)、f3(Griewank Function)、f4(Ackley Function),函数的具体表示形式如下:

(1) 函数f1(Rastrigrin Function)

f(x)=undefined[xi2-10cos(2πxi+10)],|xi|≤5.12

minf(x*)=f(0,0,L 0)=0

Rastrigrin函数为多峰函数,当xi=0时达到全局极小点,在s={xi∈[-5.12,5.12],i=1,2,…n}范围内大约有10n个局部极小点。

(2) f2(Rosenbrock Function)

f(x)=undefined(100(xi+1-xi2)2+(xi-1)2),|xi|≤50

minf(x*)=f(1,1,… 1)=0

Rosenbrock函数由K.A.DeJONG提出,此函数是非凸的病态二次函数,其极小点易于找到,但要收敛到全局极小点则十分困难。

(3)函数f3(Griewank Function)

undefinedundefined

undefined

Griewank函数,当xi=0时达到全局极小点,当undefined时,达到局部极小点。

(4)函数f4(Ackley Function)

undefinedundefinedundefinedundefinedcos(2πxi))+20+e,|xi|≤32

minf(x*)=f(0,0,… 0)=OAckley函数,当xi=0时达到全局极小点。动态自适应算法的实验结果:

从上述结果可以发现,动态自适应微粒群算法基本保持了基本PSO算法的简单、容易实现的特点,而且计算精度比基本PSO算法精度要高,改善了粒子群优化算法摆脱局部极值点的能力,提高了算法的收敛速度,且兼顾全局寻优和局部寻优,能够有效地避免早熟收敛。

4 结论与展望

本论文在分析基本微粒群算法的基础上,评析了微粒群算法的优缺点,并对惯性权重进行了调整,改进了微粒群算法的性能。PSO的研究领域在不断持续发展,仍然存在大量有待研究的问题。如:选择具有最大改善的粒子作为社会影响源,对这种粒子可进行动态变异自适应;没有速度的PSO算法,没有速度的粒子群将改变我们以往对群体的观点;并行PSO算法,开发高效的并行算法,充分利用PSO算法的隐并行性。以上列出的仅仅是PSO算法研究中一部分具有挑战性的问题,实际的研究不仅于此。考虑如何建立智能优化算法的统一框架,加强算法的理论基础研究,以及将算法扩展应用到不同的实际领域,都是有价值的努力方向。

参考文献

[1]　刘宇,覃征,卢江.多模态粒子群集成神经网络.计算机研究与发展,2005(9):1519-1526.

[2]　王俊伟,.粒子群优化算法的改进及应用.东北大学博士论文,沈阳市,2006.

[3]　孟庆红,多目标进化算法及其应用研究.西安电子科技大学博士论文,西安市,2005.

[4]　吴浩扬,朱长纯,常炳国等..基十种群过早收敛程度定量分析的改进自适应遗传算法[J].西安交通大学学报,199933(11):27-30.

微粒群优化算法篇2

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

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

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

微粒群优化算法篇3

微粒群优化算法 (ParticleSwarm Optimization, PSO) 1995年由Kennedy和Eberhart率先提出, 它借鉴了鸟群或鱼群捕食过程的社会行为, 是一种有别于遗传算法的并行进化计算技术。经过近10年的发展, PSO已广泛应用于函数优化、人工神经网络训练、模糊系统控制等领域, 成为目前进化计算研究的一个新的热点[1]。1998年Shi等引入惯性权重形成了目前的PSO基本算法, 并对PSO模型中的参数选择作了较详尽的阐述[2]。1999年Kennedy及Suganthan分别从邻域算子角度分析了PSO算法的性能[3,4]。2002年Clerc和Kennedy给出了PSO算法较完整的理论分析[5]。2003年Trelea在确定情形下研究了PSO算法的收敛性及参数选择[6]。在此分析的基础上, 本文就具有随机数的PSO算法的收敛性进行了较严密的分析, 同时给出了参数选择的范围。

1PSO优化算法

标准的PSO算法可描述如下

$\overset{ϖ}{v}_{k + 1} = a \otimes v_{k} + b_{1}^{μ} \otimes (p_{k}^{b} - x_{k}^{ϖ}) + b_{2}^{μ} \otimes (p_{k}^{g} - x_{k})$ (1)

xῶk+1=c⨂xῶk+d⨂vῶk+1 (2)

这里vῶk表示第k次迭代速度向量, xῶk表示第k次迭代微粒所在的位置向量, x $_{k}^{ϖ b}$ 表示到第k次迭代为止微粒的最好位置向量, p $_{k}^{ϖ g}$ 表示到第k次迭代为止所有微粒的最好位置向量, aῶ表示惯性权重向量, 使微粒保持运动惯性使其有扩展搜索空间的趋势, 有能力搜索新的区域, b $_{1}^{μ}$ 和b $_{2}^{μ}$ 表示所有分量随机取正值的随机数向量, ⨂表示两个向量对应分量相乘的向量乘法。由式 (1) 和式 (2) 易见, 每个分量的更新都是彼此独立的, 各个分量之间只是通过目标函数联系在一起, 因此, 不失一般性, 下面先就一组情形对PSO算法进行分析。一维情形下PSO算法的迭代公式为:

vk+1=avk+b1 (p $_{k}^{b}$ -xk) +b2 (p $_{k}^{g}$ -xk) (3)

vk+1=cxR+dxk+1 (4)

为了便于对PSO算法进行分析, 取

b=b1+b2 (5)

$p_{k} = \frac{b_{1} p_{k}^{b} + b_{2} p_{k}^{g}}{b} = λ p_{k}^{b} + (1 - λ) p_{k}^{g}$ (6)

这里 $λ = \frac{b_{1}}{b}$ 为在 (0, 1) 内随机取值的随机数, 于是b1=λb, b2= (1-λ) b, 这样无论b是否是随机数, 都可以保证b1, b2随机取值。在这里为了便于讨论, 只考虑b取常数情形。从而 (3) 式、 (4) 式变成了

vk+1=avk-bxk+bp $_{k}^{}$ (7)

xk+1=cxk+dvk+1 (8)

这里a, b, c, d是确定的实常数。类似于文献[6]的讨论, 这四个参数只有两个真正有用, 而另外两个可以固定, 下面针对c=d=1和c=1两种情形讨论PSO算法的收敛性问题。为此首先给出如下几个引理。

引理1 矩阵级数 $\sum_{k = 0}^{\infty} A^{(k)}$ 为绝对收敛的充要条件是 $\sum_{k = 0}^{\infty} ∥ A^{(k)} ∥$ 为收敛级数。

这里 $∥ A ∥ = \sqrt{λ_{1}} ‚ λ_{1}$ 为A*A的最大特征值, A*为A的共轭转置。

引理2 如果A= (aij) n×n的所有特征值的模均小于1, 则 $\lim_{k \to \infty} A^{k} = 0$ 。

引理3 设A= (aij) n×n, 如果A*A的所有特征值的模均小于1, 则矩阵级数 $\sum_{k = 0}^{\infty} A^{k}$ 绝对收敛。

引理4 设A∈Cn×n, 则A的谱半径ρ (A) 不大于A的任何一种具有相容性的范数值, 即ρ (A) ≤‖A‖。

2收敛性分析

2.1c=d=1时PSO算法收敛性分析

此时, 若令

$y_{k} = (\begin{array}{l} x_{k} \\ v_{k} \end{array}) ‚ A = (\begin{array}{l} 1 - b a \\ - b a \end{array}) ‚ B_{k} = (b b)^{Τ} p_{k}$

, 由 (7) 式和 (8) 式得PSO的矩阵表达形式为

yk+1=Ayk+Bk (9)

定理1 设序列{yk}由PSO算法迭代公式 (9) 产生的迭代序列, 序列{pk}有界, 如果a2<2b (1-b) , 则由PSO算法迭代公式 (9) 产生的迭代序列{yk}收敛, 即序列{xk}收敛到平稳点[6]。

证明由yk+1=Ayk+Bk得:

$y_{k + 1} = A^{k + 1} y_{0} + \sum_{i = 0}^{k} A^{i} B_{k - i}$ (10)

因此由引理1、引理2、引理3和引理4易知, 只要ATA的特征值都小于1, 序列{yk}必收敛。由迭代公式易知vk→0 (k→∞) , 即序列{xk}收敛到平稳点。

下面只需证明当a2<2b (1-b) 时, ATA的特征值都小于1即可。

$\begin{array}{l} | λ Ι - A^{Τ} A | = | \begin{array}{l} λ - (1 - b)^{2} - b^{2} 2 a b - a \\ 2 a b - a λ - 2 a^{2} \end{array} | = \\ λ^{2} - (2 a^{2} + 2 b^{2} - 2 b + 1) λ + a^{2} 。 \end{array}$

$\begin{array}{l} 又 (2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2} = \\ (2 a^{2} + 2 b^{2} - 2 b + 1 - 2 a) (2 a^{2} + 2 b^{2} - 2 b + 1 + 2 a) = \\ [2 (a - \frac{1}{2})^{2} + 2 (b - \frac{1}{2})^{2}] [2 (a + \frac{1}{2})^{2} + 2 (b - \frac{1}{2})^{2}] > 0 。 \end{array}$

故a, b取任何值时, ATA均有正的实特征值, 其特征值为:

$λ_{1, 2} = \frac{2 a^{2} + 2 b^{2} - 2 b + 1 \pm \sqrt{(2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2}}}{2}$ 。

由于 $2 a^{2} + 2 b^{2} - 2 b + 1 = 2 a^{2} + 2 (b - \frac{1}{2})^{2} + \frac{1}{2} > 0$ 。

所以, 当

$\frac{2 a^{2} + 2 b^{2} - 2 b + 1 + \sqrt{(2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2}}}{2} < 1$ 。

即a2<2b (1-b) 时, ATA的特征值都小于1。证毕。

2.2c=1时PSO算法收敛性分析

此时yk和pk与2.1相同, 而矩阵, 由 (7) 式、 (8) 式得PSO算法的矩阵表达形式为

yk+1=Ayk+Bk (11)

定理2 设序列{yk}由PSO算法迭代公式 (11) 产生的迭代序列, 序列{pk}有界, 如果a2d2+b2d2+b2-2bd<0, 则由PSO算法迭代公式 (11) 产生的迭代序列{yk}收敛, 即序列{xk}收敛到平稳点[6]。

证明类似于定理1的证明, 只需证明a2d2+b2d2+b2-2bd<0时, ATA的特征值都小于1即可:

$\begin{array}{l} | λ Ι - A^{Τ} A | = | \begin{array}{l} λ - (1 - b d)^{2} - b^{2} a b - (1 - b d) a d \\ a b - (1 - b d) a d λ - (a d)^{2} - a^{2} \end{array} | = \\ λ^{2} - [(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}) λ + a^{2} 。 \end{array}$

于是ATA的特征值为:

$λ_{1, 2} = \frac{(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2} + \sqrt{[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2}}}{2} 。$

由ATA为实对称阵知

$[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2} \geq 0$ , 从而当

$\frac{(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2} + \sqrt{[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2}}}{2} < 1$ 。

即a2d2+b2d2+b2-2bd<0时, ATA的特征值都小于1。证毕。

参考文献

[1]杨燕, 靳蕃, Kamd M.微粒群算法研究现状及其进展.计算机工程, 2004; (21) :3—4

[2]Shi Y, Eberhart R C.A modified particle swarm optimization.Pro IEEE International Conference on Evolutionary Computation, Anchor-age, 1998;69—73

[3]Kennedy J, Small worlds and mega-minds:effeets of neighborhood to-pology on particle swarm performance.Proc of the IEEE Congress of Evolutionary Computation, 1999;3:1938

[4]Suganthan P N.Particle swarm optimizer with neighborhood operator.Proc of the IEEE Congress of Evolutionary Computation, 1999;3:1958

[5]Clerc M, Kennedy J.The particle swarm:explosion stability and con-vergence in a multi-dimensional complex space.IEEE Trans Evolu-tion Comput, 2002;6 (1) :58—73

微粒群优化算法篇4

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

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

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

微粒群优化算法篇5

微粒群算法 (Particle Swarm Optimization, PSO) 是Kennedy和Eberhart受鸟群觅食行为的启发, 于1995年提出的一种群体搜索方法[1]。粒子群算法可以解决大量非线性、不可微和多峰的复杂问题, 并已在科学和工程领域广泛应用。2002年, Coello[2]等人发表了针对多目标粒子群优化算法的论文, 此后多目标粒子群这一概念便逐渐得到学者们的重视。

微粒群算法的特点是优化效果好、收敛速度快并且易于实现。但是当要解决的问题存在较多局部最优解时, 算法较易收敛于伪最优解。

基于以上原因, 本文将分布估计算法的思想融入到改进后的微粒群算法中, 提出一种新的分布估计微粒群混合算法 (MOPSO-EDA) , 用于对多目标优化问题的非劣最优解集的搜索。通过发挥分布估计算法全局寻优的优势, 使得算法快速得到较好的解集。最后, 本文利用MOPSO-EDA算法对常用的测试函数进行了检测。优化结果表明改进的多目标微粒群算法取得了较好的Pareto解。

1 多目标微粒群算法

1.1 微粒群算法介绍

粒子群算法模拟鸟群的捕食行为。鸟通过搜索当前距离食物最近的鸟的周围区域来找到食物。PSO初始化为一群随机微粒 (随机解) , 然后通过迭代找到最优解。在每一次迭代中, 微粒通过跟踪两个“极值”来更新自己。

微粒根据公式 (1) 和公式 (1) 来更新当前自身的速度和位置:

V[]是微粒的速度, w是惯性权重, present[]是当前微粒的位置。p Best[]和g Best分别是个体极值和全局极值, rand () 是介于 (0, 1) 之间的随机数。c1, c2是学习因子。通常c1=c2=2。

1.2 p Best[]和g Best的选取

合适的g Best和p Best[]对微粒的"飞行"至关重要。

本文选择文献[3]提出的选择策略:在每个粒子速度更新时, 用各个g Best[i]的"均值"作为全局极值g Best;每个粒子的p Best[i, j]是通过判断它相对于g Best[i]的离散程度决定是取p Best[i, j]的均值还是在p Best[i, j]中随机选取。这种算法使得每个粒子都移向解区域中不同的解, 避免了收敛于非劣最优解集的局部区域。

2 MOPSO-EDA算法步骤

EDA算法通过采用统计学习的手段建立解分布概率模型, 然后对概率模型随机采样产生新的种群[4]。由于分布估计算法良好的探索能力, 足以弥补粒子群算法的全局寻优能力的不足。

具体流程图如图1。

算法框架如下:

(2) 根据步骤1计算的适应度值对粒子进行排序。

(3) 根据前N/4粒子的基因值建立概率分布模型, 采用PBIL算法 (公式4) 对该概率模型更新:

(4) 新种群中, 一半粒子来自原先的种群, 另一半粒子来自对概率模型随机采样的结果。

(5) 利用2.2节介绍的选择策略计算个体极值PBest[]和全局极值g Best。

(6) 更新粒子群并判断算法是否结束。输出最优解或转向步骤1继续执行。

3 数值实验与结果

为了检测本文算法的优劣, 笔者将MOPAO-EDA算法和其他两个著名算法 (NSGA-Ⅱ、SPEA2) 在GD (解集距离) 和SP (解的分散性) 两方面进行比较。测试函数ZDT1~4均来自文献[5], 大部分多目标优化问题算法都用其做测试以验证算法的有效性。在实验中, 设定N=100, t=100, c1、c2、w根据实验过程中迭代次数的变化而变化。每个函数独立运行20次。实验结果如表1、表2所示。

表1显示了三种算法在GD的均值和标准差方面的比较。可以看出MOPSO-EDA算法相对于其他两种经典算法来说, 具有较好的收敛性, 并且在非连续或者较难收敛的ZDT3和ZDT4上都能保持一定的收敛稳定性。

表2显示了三种算法在四个测试函数上最优解的分布性。可以看出对于较易收敛的ZDT1和ZDT2, SPEA2优于MO-PSO-EDA;对于ZDT3和ZDT4来说, MOPSO-EDA则具有较好的分布性。

4 结语

为了提高多目标非劣解集的收敛性和分布性, 本文提出了一种基于建模训练的微粒群多目标优化算法 (MOPSO-EDA) 。其核心思想是在每次迭代初期, 种群中一半的粒子会通过分布估计算法进行更新, 产生的新的粒子具有较好的解的适应值。仿真结果表明, MOPSO-EDA算法具有较好收敛性和分布性, 能较快且准确的趋近Pareto前沿。

参考文献

[1]Kennedy J, Eberhart R.Particle swarm optimization[C].Proceedings of IEEE International Conference on Neutral Networks, 1995:1942-1948

[2]REYES-SIERRA M, COELLO A.Multi-objective particle swarm optimizers:a survey of the state-op-the-art[J].International Journal of Computational Intelligence Research, 2006, 2 (3) :287-308

[3]张利彪, 春光, 马铭, 刘小华.基于粒子群算法求解多目标优化问题[J].计算机研究与发展, 2004, 41 (7) :1286-1291

[4]周树德, 孙增圻.分布估计算法综述[J].自动化学报, 2007, 32 (2) :113-124

微粒群优化算法篇6

作业车间调度问题(Job-shop scheduling problem, JSP)通常理解为运用多台机器进行生产加工,加工包含多个工件,每个工件又包含多道工序,同时每道工序在指定的机器上进行加工。在过去相当长的时间中, 算法得到了充分的研究,涌现出了不同的算法与理论, 如人工神经网络与模拟退火算法等等。不过由于算法各自的缺陷以及车间生产作业调度的复杂性,标准的算法很难满足求解的需求。为充分发挥各种算法的优势,取长补短,将算法进行有效地结合,可以大大提高算法的求解效率,因而混合算法应运而生,成为算法优化的一大亮点。

1混合微粒群(PSO)算法设计

1.1改进的微粒群算法原理

微粒通过跟踪个体极值Pbesti(微粒本身所找到的最优解)和全局极值Pgbest(整个种群目前找到的最优解)来不断更新自己的速度和位置,更新公式如下:

其中:vk为微粒的速度向量;k为迭代次数;xk为当前微粒的位置;w为惯性权重,决定了对微粒当前速度的继承,w一般取(0,1)之间的随机数;c1、c2表示群体的认知系数,使微粒具有自我总结和向群体中优秀个体学习的能力,c1、c2取(0,2)之间的随机数;r1和r2为 (0,1)之间的均匀分布的随机数。

1.2改进的PSO算法设计策略

微粒群算法最初用于求解连续性优化问题,具有较好的全局收敛性。不过在求解离散组合优化问题时,往往具有参数敏感、收敛速度慢等特性,因此需要对混合PSO算法做如下改进:

(1)PSO算法对于初始解具有较强的鲁棒性,是因为PSO算法具有很好的全局收敛性。但在实际生产中,由于优化模型的复杂程度大小不一,这就导致了算法的收敛对初始解具有很大的依赖。本文提出优化选择机制,既保证了初始解的多样性,又提高了算法的收敛性能。

(2)标准PSO算法中通常采用基于编码点的交叉方式,在复杂JSP中具有较慢的收敛速度。本文提出了一种遗传算法的整段交叉思想,在一定范围内提高了收敛速度。同时为了避免PSO算法因收敛速度过快而产生早熟现象,本文提出了一种遗传算法的变异思想。结合遗传算法的变异和交叉思想很好地提高了算法的收敛性。

(3)为保证种群全局最优解和自身最优解的突跳性,以及算法能跳出全局最优,混合微粒群算法采用模拟退火算法的Metropolis抽样准则来作为设定全局最优解与自身最优解的接受准则。

(4)本文的混合PSO算法以机器加工时间最小为优化目标。采用优化选择机制,将目标适应度值按从小到大的顺序排序,并按照该顺序选择出种群。

1.3混合PSO算法种群变异设计

混合PSO算法粒子的位置更新涉及每个粒子的历史最好位置Pbesti、群体当前最好位置Pgbest和平均最优值Mbest,运用遗传算法的变异和交叉操作,其表达式如图1所示。

变异操作:假设父代向量为x,随机产生2个交换点i和j,交换向量x位于交换点i和j上的元素,其他元素不变。

交叉操作:假设父代向量为x和y,经过交叉操作产生子代向量z。首先,随机产生2个交换点i和j, 将向量x位于交换点i和j之间的元素复制到向量z的相应位置;其次将向量x上其余元素按照它们在向量y上出现的先后顺序依次填入向量z的位置。粒子的位置更新流程如图2所示。

1.4模拟退火操作

混合PSO算法在标准PSO算法的基础上引入模拟退火操作的Metropolis抽样准则,参照目标函数, 比较微粒与微粒自身最优解之间的适应度的大小,按照Metropolis抽样准则接受比微粒自身最优解大的解,使自身最优解具有一定的突跳性。

2混合PSO算法的求解流程

结合混合PSO算法的求解过程,给出混合PSO算法的求解流程图,如图3所示。

图3中,Pbesti(t)表示微粒i经过t次迭代后相对目标函数适应度最小的一代微粒;Pgbest(t)表示t次迭代后所有微粒中相对目标函数适应度最优的微粒; xi(t)表示微粒i经过t次迭代时的微粒。

3混合PSO求解实例

3.1对FT06问题的求解

求解种群为10个粒子,计算代数为1 500代,连续计算20次,通过MATLAB 7.0软件求解,结果显示混合PSO能很好地解决FT06问题,它能9次取得其最优解55,其余解大多都很接近最优解55,而且平均用时达到6s左右,收敛速度比标准PSO快。

3.2对LA01问题求解

求解种群为50个粒子,计算代数为1 500代,连续计算20次,通过MATLAB 7.0软件求解,结果显示混合PSO能很好地解决LA01问题,混合PSO算法求解20次中有15次取得最优解666,平均收敛代数为550,平均用时达到55s左右,收敛速度比标准PSO快。

4结语

微粒群优化算法篇7

关键词：微粒群算法,车间调度,甘特图

0 引言

生产调度是整个生产管理的核心内容,是制造系统的研究热点,也是理论研究中最为困难的问题之一。其任务是在企业车间有限的资源约束下,确定工件在相关设备上的加工顺序和加工时间,以保证所选定的生产目标最优[1]。

遗传算法和其他一些智能算法已经被成功地应用于生产调度问题中,并取得了较大的成果,但目前还没有人将其应用到印染企业生产调度中。而对于十年前刚刚出现的微粒群算法,虽然在国外已经得到了许多学者的关注,但国内对该算法的研究还处于起步阶段,能够应用于实际生产调度的就更少。本文在前人对生产调度和智能算法研究成果的基础上,立足实际,着重用较新颖的微粒群算法解决花布印染企业的车间生产调度问题。最终取得了满意的效果。

1 微粒群算法概述

微粒群算法(PSO)是继蚁群算法提出之后的又一种新的进化计算技术,由Eberhart和Kennedy于1995年提出,其灵感源于对鸟群捕食行为的研究。

1.1 微粒群算法原理

微粒群算法不像其他进化算法那样对个体使用进化算子,而是将每个个体看作是n维搜索空间中一个没有质量和体积的微粒,并且在搜索空间中以一定的速度飞行,同时该飞行速度由个体的飞行经验和群体飞行经验进行动态调整。设微粒群体规模为n,其中每个微粒i(i = 1,2,…,n)在n维空间中的坐标位置可表示为xi;微粒i的速度定义为每次迭代中微粒移动的距离用vi表示;pid表示当前微粒所经历的最好位置(即具有最好的适应值),其与当前微粒位置之差被用于该微粒的方向性随机运动设定;pgd表示群体中所有微粒经历过的最好位置,其与当前微粒的位置之差被用于改变当前微粒向全局最优值运动的增量分量;ω为惯性权重;c1和c2为加速常数,即学习因子;rand1()～U(0,1)和rand2()～U(0,1)为两个相互独立的随机函数。于是微粒i在第d(d=1,2,…,n)维子空间中状态更新方程如下:

${\begin{cases} v_{i d} = ω v_{i d} + c_{1} r a n d_{1} () (p_{i d} - x_{i d}) + c_{2} r a n d_{2} () (p_{g d} - x_{i d}) \\ x_{i d} = x_{i d} + v_{i d} \end{cases} (1)$

1.2 标准微粒群算法的流程

(1) 初始化

即初始化微粒群,设置微粒群规模为m,并随机设定微粒的速度和位置;

(2) 适应值计算

根据给出的优化公式计算每个微粒的适应值;

(3) 更新pid

对每个微粒,将其当前适应值与所经历过的最好位置pid的适应值相比较,选择较好的一个作为当前的pid;

(4) 更新pgd

对每个微粒,将其适应值与全局(群体)所经历过的最好位置pgd的适应值进行比较,选择较好的一个作为当前的全局(群体)最优位置;

(5) 更新微粒的位置和速度

根据当前的pid和pgd,利用式(1)更新微粒的位置和速度;

(6) 算法结束的判断

如未达到结束条件(如:足够好的适应度值,预设的迭代次数),返回第2步继续执行。

2 微粒群优化算法解决混合流水车间调度问题

2.1 流水车间调度问题描述

混合流水车间调度问题HFSP(hybrid flow-shop scheduling problem),是一般Flow-shop问题的扩展,其特点是全部工序或部分工序上存在并行机器,即通常说的柔性流水线FFL(Flexible Flow Line)。

混合流水车间调度问题可以描述为:需要加工多个产品;每个产品需要经过所有工序,即都是从第一个工序开始依次加工到最后一个工序;不允许抢先作业;加工任务不能分割;每台设备每次只能加工一个任务;所有工序中至少有一个工序存在着并行机器;机台设备之间有足够的缓冲区;每个订单仅当其当前工序加工完成后,下一道工序才能开始加工;对于每道工序,每个产品在各并行机台上的加工时间都相同。调度目的是确定并行机的分配情况以及同一台机器上产品的加工顺序。

2.2 微粒群算法的编码方法

本文采用改进的微粒群算法,使之达到混合流水车间调度的要求:每个微粒本身表示所有作业的一个排列,即调度微粒群算法中的微粒位置和速度都是连续变量,因此它能直接应用于连续优化问题。但对于生产调度这一类组合优化问题,由于处理的是离散的变量,所以需要作一些调整和改变。我们借鉴文献[2]和基于工序编码的遗传算法中所述方法进行微粒编码设计和计算。由于柔性作业车间调度不仅要确定工序的加工顺序,还需为每道工序选择一台合适的机器,因此粒子的位置向量和速度向量都采用基于工序和机台的两层编码方法:第一层基于工序,第二层基于机台。

2.3 算法收敛图例及应用实例

2.3.1 微粒群算法收敛图例

图1至图4分别是应用2.2节介绍的微粒群算法在同一次执行过程中分别进化100、200、300和500代后生成的演化图。由图3和图4可知,算法在进化到250代左右时就已经趋于收敛。

2.3.2 流水车间生产调度甘特图的生成

各产品在各工序(机台)上加工时间如表1所示。

我们约定各工序上所拥有的并行机台数量如表2所示(约定各并行机台处理同一产品时间相同,如表1所示)。

(1) 产品经过所有工序甘特图

在满足上述加工时间(各并行机台加工时间相同)和机台数量的前提下,用微粒群算法生成的经过所有工序的混合流水车间调度甘特图如图5所示。

图5中,相邻连个横线之间的图形反映在相同工序的不同机台上的产品加工顺序。产品在各机台上的分配情况用(j,k)表示,其中j表示作业号,k表示该作业在当前工序上被分配的机台。

(2) 产品经过部分工序

表3是各产品在各工序并行机台上的加工时间(值为0表示不经过对应工序),其特点为同一产品在各工序所有并行机台上的加工时间都相同。对应生成的甘特图如图6所示。各工序上并行机台数量如表2所示。

图6中,相邻连个横线间的图形反映在相同工序的各机台上的产品加工顺序。产品在各机台上的分配情况用(j,k)表示,j表示作业号,k表示分配给该作业的机台。

3 结束语

我们成功地把微粒群算法应用到了印染企业的车间调度当中,取得了较快的收敛速度和优化效果,同时为计划编排人员提供了直观的甘特图来辅助其计划的编排。

本文虽然成功地把善于处理连续变量问题的微粒群算法应用到了离散变量的车间调度中,但仍有许多需要改善之处,主要有以下几个方面:

(1) 对微粒群算法作进一步改进,使之能更好地适应处理离散变量的生产调度。

(2) 采用最新的量子粒子群算法,达到快速全局搜索的目的。

(3) 本文处理的车间调度问题,仅仅考虑了并行机及不同工艺路线的情况,而没有考虑多功能机台的情况。这是下一步工作的重点。

(4) 本文中的车间调度实际上处理的仅仅是对作业进行排序优化,并没有考虑到生产当中共享资源的分配。这也是下一步要完成的工作,使微粒群算法真正地适用于生产调度。

(5) 在实际生产中,还有部分产品具有作业车间调度的特点,因此必须予以考虑。

参考文献

[1]武志军,宁汝新,万春辉,等.基于人机协同的动态车间生产调试问题的研究与实现[J].计算机系统应用,2006(4):21-24.

[2]谷峰,陈华平,卢冰原,等.粒子群算法在柔性工作车问调度中的应用[J].系统工程,2005,23(9):20-23.

[3]高慧敏,曾建潮.钢铁生产调度智能优化与应用[M].冶金工业出版社,2006.

[4]Gupta J N D.Heuristics for hybrid flowshops with controllable process-ing times and assignable due dates.Computers and Operations Research,2002,29:1417-1439.

[5]Pinedo M.Scheduling Theory.Algorithms and Systems.Prentice Hall,2002.

[6]Tasgetiren M,Liang Yunchia,Mehmet Sevkli,et al.A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J].European Journal of Operational Research,2006,177:1930-1947.

[7]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.

[8]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.

[9]Liu Shixin,TangJiafu,SongJianhai.Order-planningmodel and algorithm for manufacturing steel sheets[J].International Journal Production Eco-nomics,2006,100(1):30-43.

[10]Lian Zhigang,Gu Xingsheng,Jiao Bin.Asimilar particle swarm optimi-zation algorithm for permutation flowshop scheduling to minimize makespan[J].Applied Mathematics and Computation,2005,175(1):773-785.

[11]Oguz C,Ercan M F.A genetic algorithm for hybrid flow shop scheduling with multiprocessor tasks.Journal of Scheduling,2005,8:323-351.

微粒群优化算法篇8

1 数字PID简介

离散的PID表达式如(1)式所示:

其中kp,ki,kd为PID参数,T为采样周期。

进行PID参数寻优时,采用(2)式做为性能指标[7]:

g1、g2为系数,根据具体情况确定。

2 微粒群算法原理

PSO(Particle Swarm Optimization)算法由于简单,易于实现,得到了广泛应用,如(3)式和(4)式所示

公式中参数的具体意义参考文献[6]。

3 改进的微粒群算法

改进的微粒群算法的步骤为

Step1:采用佳点集的方法产生具有N个(N为偶数)粒子的初始种群,并将种群平均分成两组,第一组侧重于全局寻优,第二组侧重于局部寻优,并在算法执行过程中交换信息;

Step2:计算粒子的适应度,得到第一组与第二组子微粒群的全局最优解和局部最优解,并将两个子种群中的全局最优解中最好的一个做为两个子种群的全局最优解;

Step3:第一组先按(3)式和(4)式进行更新,为保持群体的多样性,对于越过边界的粒子不是强制为最大值或最小值,而是采用边界缓冲墙[8]的方法对越界的粒子进行缓冲;并以概率0.2对粒子进行变异;该方法有利于保持群体多样性,全局寻优化能力极强,但是局部寻优能力较弱;

第二组先按(3)式和(4)式进行更新,然后将该组各粒子与两组的最优解以概率0.8进行交叉操作,如公式(5)所示:

其中xj表示第二组中的某一个粒子的解,λ1,λ2,λ3为权重(λ1+λ2+λ3=1);

第二组子微粒群具有局部寻优化能力好的优点,与第一组强全局寻优能力形成互补。

Step4:计算两组微粒的适应度,并按适应度时行排序,对于第一组最优的30%的微粒以概率0.65变异操作,对于第二组最差的30%的微粒,以概率0.65直接用第一组最优的30%的个体最优解代替;

Step5:判断是否已经满足条件或已经达到了迭代次数,否则转Step2。

4 基于改进的微粒群算法的PID参数优化在电阻炉中的应用

具有滞后环节的电阻炉数学模型为,采用PID算法进行电阻炉温度控制,并采用改进的PSO算法进行PID参数寻优,仿真结果如下:

曲线IPSO-PID为采用改进的PSO+PID算法的控制结果,曲线PSO-PID为采用普通PSO+PID的控制结果。

5 结论

采用改进的微粒群算法能找到更好的PID参数,控制结果具有超调小,响应快的优点,明显好于采用一般微粒群算法找到的PID参数。仿真结果表明,采用本文提出的改进的微粒群算法寻优PID参数,能较好的控制电阻炉的温度。证明本文提出的方法切实可行,能用于电阻炉的温度控制。

参考文献

[1]李祥飞,邹恩,张泰山.等.基于混沌优化的规范化PID控制器及其应用[J].中南工业大学学报,2002,33(3):301-304.

[2]廖芳芳,肖建.基于BP神经网络PID参数自整定的研究[J].系统仿真学报,2005,17(7):1711-1713.

[3]孟安波,叶鲁卿,殷豪等.遗传算法在水电机组调速器PID参数优化中的应用[J].控制理论与应用,2004,21(3):398-404.

[4]谭冠政,李文斌.基于蚁群算法的智能人工腿最优PID控制器设计[J].中南大学学报(自然科学版),2004,35(1):91-96.

[5]宋莉莉,张宏立.基于微粒群算法的PID控制器优化研究[J].计算机仿真,2012,29(5):231-234.

[6]曾现峰,李波,侯春,等.基于改进微粒群优化的PID控制器参数整定[J].自动化技术与应用,2012,31(12):24-27.

[7]刘金琨著.先进PID控制及其MATLAB仿真[M].北京:电子工业出版社,2003:228-229.

非单调的微粒群信赖域算法篇9

1 非单调信赖域子问题

对于无约束最优化问题minf(x),x∈Rn，其中f(x)∶Rn→R1是二次连续可微函数。在点xk处，选取下面的信赖域方法模型子问题

其中，用拟牛顿法的BFGS公式构造出的Bk是一个对称矩阵，信赖域半径Δk为给定正数，随迭代调整。针对上述的无约束优化问题，基本的信赖域算法采用计算真实下降量和预估下降量之间的比率

由此决定sk是否被接受且下一步迭代信赖域半径Δk+1的取法。而非单调信赖域算法的信赖域半Δk+1由下式决定

其中，为常数，当m=0时，非单调Wolfe线搜索便是一般Wolfe搜索。类似文献[4]，可定义为

其中，ωki∈[0,1]是的权，且满足

2 非单调微粒群信赖域算法的思想

对于极小化问题，目标函数值越小，位置则越好。根据微粒群算法的基本思想，得出一个公式以决定微粒的当前最佳位置。如下

设群体中所有微粒经过的最佳位置为pg，称其为全局最佳位置，即

可得到新的迭代方程

其中，j表示维数;t表示迭代次数;i表示第i个微粒;加速常数通常取0～2之间的数。

3 非单调的粒子群信赖域算法的步骤

算法1

4 收敛性分析

在以下两个条件成立的情况下对非单调的微粒群信赖域算法的收敛性进行分析。

(2)设满足Lipschitz条件，即则满足

引理1[9]若假设(3)成立，则{fl(k)}单调非增且收敛。

引理2设连续，{xk}是由上述算法产生的点列，若μ是正常数，则存在正常数δ，使得

引理3若条件(1)成立，序列{xk}由非单调的微粒群信赖域算法产生。

引理4[10]设{Δk}和{Mk}是任意的两个数列，若存在常数τ>0，α1>0，α2∈(0,1)，及{1,2，…}的一个子集I，使则必有。

定理1 若条件（1）和条件（2）成立，其中则非单调的微粒群信赖域算法产生的点列{xk}必满足

证明若定理1结论不成立，则fk有下界，则存在正常数μ使得由引理1，存在正常数δ，使成立。定义集合I={k rk≥m}，则{fk}有下界，结合Step5、Step6和Step7的构造准则及引理1和引理2知

5 数值试验

为说明算法的有效性，利用Matlab编写程序对本文算法进行数值测试，有关参数取值Δ'=6，Δ0=1,

表1和表2中，n表示测试问题的维数;TR表示标准的信赖域算法;PO-FTR表示最终得到的非单调微粒群信赖域算法;GA-STR表示基于遗传优化的自适应信赖域算法;Pn表示采用非单调的微粒群信赖域算法产生下一迭代点次数;Tn表示求解信赖域子问题的次数，其中每个Pn和Tn均是进行20次试验所得到的平均次数，TIME表示程序运行的时间(其中第3列的TIME是进行20次实验所得到的平均次数)，单位s。

例1洛森布骆克检定函数

例2扩展洛森布骆克检定函数

摘要：文中对无约束优化问题提出了一类非单调信赖域算法,将搜索性能良好的微粒群算法和总体收敛性良好的信赖域算法有效融合,并提出了基于微粒群的信赖域算法,在适当的条件下,证明了算法的全局收敛性。

关键词：无约束优化,非单调线搜索,微粒群算法,信赖域,全局收敛性

参考文献

[1]杨洁,焦宝聪.一类新拟牛顿非单调信赖域算法[J].数学的实践与认识,2011,41(22):192-197.

[2]高雷阜,于冬梅.非单调信赖域方法求解无约束非光滑优化问题[J].计算机工程与应用,2013(8):48-50.

[3]陈国初,俞金寿.微粒群优化算法[J].信息与控制,2005,34(3):318-324.

[4]仝建.无约束优化的混合信赖域算法研究[D].太原:太原科技大学,2008.

[5]王念桥,姚四改.基于改进粒子群优化算法的排课问题[J].计算机应用,2013,33(1):207-210.

[6]屈向红,郭靖,夏桂梅.求解约束优化问题的粒子群算法[J].太原科技大学学报,2012,33(5):406-409.

[7]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1997.