自适应动态反馈算法（通用7篇）
自适应动态反馈算法 篇1
摘要：对变步长LMS滤波算法进行研究,提出一种新的变步长LMS自适应滤波算法。该算法基于Sigmoid函数,通过引入误差因子反馈来调整函数参数,解决了类Sigmoid函数中参数设置的问题,并使算法具有较快的收敛速度和较小的稳态误差。计算机仿真表明,相对于其他变步长算法,该算法在收敛速度和稳态误差方面均表现优异,具有较好适用性。
关键词：LMS算法,自适应滤波,收敛速度,稳态误差
0 引言
LMS(Least mean square)自适应滤波算法[1]由Widrow和Hoffman提出,该算法计算简单、稳定性好、易于实现,被广泛应用在控制、雷达、系统辨识等领域。但是这种固定步长的LMS算法在收敛速率和稳态误差之间的要求是相互矛盾的,而且该算法在处理相关信号时,其收敛速度显著下降。
经典的LMS算法的局限在于其固定步长无法兼顾收敛速度和稳态误差。为了解决这一问题,人们在此基础上提出了各种各样的变步长LMS滤波算法。其核心思想都是用变步长代替固定步长,使算法在大的误差范围内具有快速的收敛性,在小的误差范围内具有较小的失调量。文献[2]提出了变步长参数正比于误差的算法,其性能有所提升,但并不理想。文献[3]给出了一种称为S函数的变步长LMS算法(SVLMS),该算法的步长调整策略有一定的先进性,但该算法在误差接近零时步长变化剧烈,可能导致稳态误差增大。文献[4]在文献[3]的基础上做了进一步的改进,修正了步长在误差接近零时变化剧烈的问题,但算法中的关键参数需要通过实验手工设置,而参数设置不当将严重影响算法的性能。文献[5-6]则分别基于其舌线、双曲正切函数和反正切函数提出了相应的变步长LMS算法,在一定程度上缓解了收敛速度和稳态误差之间的矛盾。文献[7]提出了基于变换域的LMS滤波算法,变换域的LMS算法能够提高运算速度,但收敛速度和稳态误差之间的矛盾并没有解决。
可见目前的研究大多集中在变步长策略。变步长策略的实质是找到误差和步长之间的一个对应关系,此对应关系能自动调节函数的收敛速度和稳态误差。本文在文献[4]的基础上提出基于Sigmoid函数的EFLMS(Error Feedback Least Mean Square)算法。该算法利用反馈的思想,通过在参数中引入误差因子,解决Sigmoid函数参数设置的问题,使算法在收敛速度和稳态误差等性能指标上均有所改善,同时算法具有广泛的适应性。
1 相关工作
变步长LMS滤波算法的实质是通过误差自适应的调节步长,即在误差较大的收敛阶段用较大的步长以提高收敛的速度,在误差较小的稳态阶段用较小的步长以获得较小的误差。其核心思想是用误差来反馈调节步长,也就是找到误差和调节步长之间的函数关系,使算法在稳态误差和收敛速度上找到一个好的平衡。
文献[4]提出了一种基于Sigmoid函数的变步长滤波算法。该算法的Sigmoid函数相对简单,而且在误差接近零处变化不大,具有缓慢变化的特征。其算法设计如下:
算法的核心是公式(2)。通过式(2)建立起误差e(n)和步长μ(n)之间的对应关系,当误差大时步长变大,收敛速度提高;当误差逐渐变小时,调整步长变小,算法趋于稳态。式(2)中α和β是常数,其中α>0,其控制函数的形状和收敛速度,参数β>0控制函数的取值范围。其中参数α是影响算法性能的关键之一,其取值的大小将直接影响算法的收敛速度和稳态误差值。
但是文献[4]中并没有就参数的取值提出明确的设置方法,而是采用实验的方法确定参数的最优值。而参数设置不当将严重影响算法的性能,同时也使算法的适用性受到了一定的限制。
本文提出的EFLMS算法基于Sigmoid函数,通过在参数中引入误差因子解决了函数参数设置的问题。下面介绍EFLMS算法。
2 算法描述
EFLMS算法基于文献[4]提出的变步长策略,并在其基础上做了进一步的改进,通过在参数中引入误差反馈实现参数自动调整。
算法中设计步长和误差的函数如下:
其中:
式中:参数α(n)控制算法步长变化的形状和速度,而β(n)控制函数的取值范围。式中的常数b0用于调整取值范围以满足算法收敛。
两个参数α(n)和β(n)都是误差比值e(n)e(n-1)的函数。当e(n)e(n-1)的比值较大时,说明误差变化较大,算法还处在收敛阶段,那么这时相应的参数α(n)对应较大的值,这时对应得到的步长μ(n)较大,算法的收敛速度加快。随着误差e(n)e(n-1)比值的逐渐变小,这时α(n)变小使步长μ(n)变小,算法趋于稳态。在参数β(n)中,当e(n)e(n-1)比值较大时,说明误差变化较大,算法处在收敛阶段,这时β(n)较大,相应此时步长μ(n)变大,算法收敛加快;当e(n)e(n-1)比值逐渐变小,这时β(n)变小使步长μ(n)变小,算法趋于稳态。当极限时e(n)e(n-1)~1,此时β(n)=(1-b0)β(n-1),保证了系统不会出现不稳定的情况。
下面在Matlab仿真平台上对EFLMS算法进行仿真实现,验证算法的性能。
3 仿真分析
自适应滤波算法的性能指标主要有收敛速度和稳态误差,为此对算法的步长和误差进行仿真实验。这里主要对文献[4]中的自适应算法和EFLMS算法进行仿真,以验证EFLMS算法的性能。
仿真设置如下:自适应滤波器阶数为20,输入信号为单频正弦波,参考的输入信号为零均值、方差为1的高斯白噪声,采样点数为900。其中文献[4]中的参数α=0.5,β=0.01。而EFLMS中的参数设置如下:式(5)中的k=2,式(6)中的b0=0.02。
3.1 步长变化仿真
算法的调整步长是误差的函数,步长的变化反映了算法的运行情况。优秀算法步长应该是在收敛阶段较大,使系统具有较快的收敛速度;达到稳态阶段较小,以使系统获得较小的误差。所以步长的变化规律在一定程度上反映了算法的合理性。
文献[4]的算法中步长随迭代次数的变化曲线如图1所示,是EFLMS算法的步长变化曲线如图2所示。图中横坐标是迭代次数,纵坐标是算法的调整步长。
可以看到,两种算法的步长都随着迭代次数的增大而减小,达到一定的迭代次数之后趋于稳定。图1中,其步长在迭代160次左右时趋于稳定,而图2中步长在迭代60次左右就趋于稳定。可见EFLMS算法的步长调整策略更加合理,其收敛速度显著优于文献[4]的算法。这是因为EFLMS算法自适应特性更强,其对参数设置的依赖程度更小,其步长调整更合理。
3.2 误差仿真
误差反映了算法的输出信号和原信号之间的差别,达到最小误差所用的迭代次数越少,说明算法的收敛速度越快,最小误差值越小说明算法的精度越高,滤波效果越好。所以误差值的在一定程度上反映了算法的性能。
图3和图4分别是文献[4]和EFLMS算法的误差变化曲线图。随着迭代次数的增加,两个算法的误差都逐渐变小,小到一定程度之后都趋于稳定,此时系统也趋于稳定。
图3中所示算法的误差在迭代160次左右达到稳定,图4中的算法在迭代60次左右误差达到稳定,显然图4的算法达到稳定误差所需的次数更少,收敛速度更快,而且在系统稳定之后的误差也更小,对信号的滤波效果更好。这是因为EFLMS算法能根据误差的变化自适应调整步长的能力更强,在收敛阶段误差较大时其步长较大,所以其收敛速度很快;而在误差变小之后调整步长更小,使系统获得更高的精度。
可见,EFLMS算法的性能优异,无论在收敛速度还是在稳态误差上均优于文献[4]的算法。
4 结语
本文提出一种基于Sigmoid函数的变步长LMS自适应滤波算法——EFLMS算法。该算法通过引入误差因子来调节参数,解决了Sigmoid函数参数需要手工设置的问题,使算法的步长调整策略更合理。在仿真平台上对算法进行验证,仿真结果表明,相对文献[4]滤波算法,EFLMS算法在收敛速度更快,精度更高,验证了算法的可行性和优越性。
参考文献
[1]WIDROW B,STEARNS S D.Adaptive signal processing[M].Englewood Cliffs,NJ:Prentice Hall,1985.
[2]YASUKAWA H,SHIMADA S,FURUKRAWA I,et al.Acu oustic echo canceller with high speech quality[C]//IEEEICASSP.[S.l.]:IEEE,1987:2125-2128.
[3]覃景繁,欧阳景正.一种新的变步长LMS自适应滤波算法[J].数据采集与处理,1997,12(3):171-174.
[4]高鹰,谢胜利.一种变步长LMS自适应滤波算法及分析[J].电子学报,2001,29(8):1094-1097.
[5]邓江波,侯新国,吴正国.箕舌线的变步长LMS自适应算法[J].数据采集与处理,2004,19(3):282-285.
[6]郑莎莎.智能天线变步长最小均方算法的研究与仿真[D].长春:吉林大学,2007.
[7]BEAUFAYS F,WIDROW B.Transform-domain adaptive fil ters:an analytical approach[J].IEEE Transaction on SignalProcessing,1995,43(2):442-431.
动态自适应微粒群优化算法 篇2
关键词：粒子群优化算法,惯性权重系数,动态自适应
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.
自适应动态反馈算法 篇3
在智能光网络中,动态RWA(路由与波 长分配)问题的核心是控制平面为客户业务请求实时地选择合适的路由和分配波长资源。动态RWA问题的优化目标是降低网络连接的阻塞率和提高网络资源的利用率。RWA问题属于NP-C问题[1],常见的解决思路有两种:(1)分别处理路由选择问题和波长分配问题;(2)是采用分层图模型的并行计算方案。分层图模型简化了动态RWA问题的复杂性,对于解决有波长一致性限制的RWA问题较为 有效[2],但缺点是扩大了网络规模,在解决大型网络问题时耗费 时间较长;同时对带 波长转换 能力的RWA问题,优化效果不太明显[3]。而第一种方案结合启发式算法对解决此问题有较好的效果。
ACO (蚁群优化)算法是由M.Dorigo和V.Maniezzo等从蚁群的 觅食行为 中提炼出 来的[4]。蚁群算法的本质是运用分布式并行计算和正反馈原理寻找最优解。但蚁群算法存在过早收敛、容易陷入停滞和全局搜索能力不足等缺点。信息素挥发系数ρ对算法全局收敛性和跳出局部最优解的影响较为突出。段海滨等对蚁群算法的全局收敛性进行了深入的理论研究[5],提出了对挥发系数采取阀值函数ρ(t+1)=φ·ρ(t)(式中,φ为挥发约束系数,且φ∈[0,1])的改进方法。本文针对光网络中动态RWA问题的求解,提出一种改进的ADACO(自适应蚁群优化)算法,将挥发约束系数定义为一种渐进的过程,与算法当前的迭代和算法总的迭代次数相关,使φ的值随着迭代次数的增加逐渐减小,从而获得较好的算法性能。
1基于 ADACO 算法的 RWA机制
1.1改进的 ADACO 算法
在传统的ACO算法中,全局信息素更新规则可以表示为
式中,Δτij(t,t+n)为路径(i,j)上产生的信息素增量;τij(t,t+n)为更新后路径(i,j)上的信息素浓度;τij(t)为路径(i,j)上累计的信息素;ρ为[0,1]区间的常数,为信息素的挥发系数。
在优化求解过程中,若ρ取值过大,会降低算法全局搜索能力;若ρ取值过小,会减慢算法的收敛速度,使优化结果陷入局部解。本文将ρ改为可变函数ρ(t+n),以平衡算法的全局搜索能力和收敛速度。改进后的信息素更新规则如下:
式中,φ为挥发约束系数,且φ∈[0,1]。为了避免ρ变化波动过大,将φ表示为一个渐进的过程,其函数关系为
式中,w为当前迭代步数;wmax为算法总的迭代次数。由于w≤wmax,满足φ∈[0,1],且φ(w)为单调递减函数;随着迭代步数的增加,φ(w)的值逐渐减小,调节ρ动态更新。
1.2改进的 ADACO 算法在 RWA中的应用
将改进的ADACO算法应用到RWA中,主要实现步骤如下:
(1)业务请求到达时,需要进行路由选择,按文献[6]提出的规则进行下一跳j的选择。
(2)下一跳j选择结束后,采用式(5)对链路(i,j)进行信息素局部更新:
式中,τinjew为更新后的链路的信息素;τiojld为累积的信息素;ε为[0,1]区间的常数;Δτij为链路上产生的信息素增量。
(3)待所有蚂蚁均进行完一次搜索后,运用式(2)对所建立的路径进行全局信息素更新。
(4)当迭代次数达到预设最大值时,从搜索到的路由集合中选取一条路径作为最佳路由,以路径信息素浓度最大结合路径节点数最少作为选取标准。
2仿真与性能分析
在不同网络拓扑上进行了数值仿真,分析和比较ADACO算法与传统的Dijkstra算法对网络阻塞率性能的改善,波长分配均采用FF(首次命中)算法。仿真的网络结构分别是14个节点、21条链路的NSFNET(国家科学基金会网络)和16个节点、32条链路规则对称的Mesh网络[7]。为了便于 仿真,设定网络拓扑中相邻节点间采用4条链路相连接,对每一条链路的可用波长数目设定为6。算法的仿真参数设置如下:ρ的最小值ρmin =0.4,ρ0 =0.6,其他参数按文献[6]设置。仿真结果如图1所示。
(a) Mesh 网 络(b) NSFNET
从图1(a)可以看出,对于规则对称的Mesh网络:相比较于Dijkstra+FF算法,本文提出的改进算法在改善网络阻塞率性能方面效果明显。特别是在业务强度较小时,采用ADACO+FF算法,网络阻塞率几乎为0;在增大业务负载的过程中,改进算法的阻塞率性能改善能力逐渐下降;当业务强度趋于网络最大承载能力时,由于网络波长资源有限,网络性能已发挥到最大,此时两种算法的网络阻塞率均趋于0.6。从图1(b)可以看出,对于NSFNET:改进算法对降低网络阻塞率也有明显的效果,仅略逊于同一算法对Mesh网络的改善效果。当业务强度较小时,改进算法对网络阻塞率性能改善明显;随着业务强度的增大,ADACO+FF算法对阻塞率性能改善能力降低,但仍优于传统的Dijkstra+FF算法;当业务强度趋近于网络最大承载能力时,受到波长一致性要求和网络资源的限制,算法对阻塞率性能的改善不太 明显。与Dijkstra+FF算法相比,ADACO+FF算法在Mesh网络和NSFNET中阻塞率的改善量最大分别为0.3和0.2。
3结束语
自适应动态反馈算法 篇4
关键词：自适应模拟退火,连续搅拌釜式反应器,动态优化
模拟退火算法 (SA) 是近些年来发展起来的一种基于固体退火过程模拟的随机全局优化方法。由于它具有高效、通用、灵活的特点, 因此被广泛应用于解决各种工程优化问题。
连续搅拌釜式反应器 (Continuous Stirred Tank Reactor, CSTR) 具有采用连续操作方式, 过程在恒速操作条件下可达定常态, 以及物料质点在釜内的停留时间各不相同等三大特征。
本文分析了CSTR的动态优化模型, 研究了一种改进的自适应模拟退火算法 (ASA) , 并将其应用于求解CSTR的动态优化问题。
1 改进的自适应模拟退火算法
优化问题通常可以归结为求某一函数在一定范围内的最小值问题。但是以往传统的优化算法都是运用某种局部的比较去决定寻优路径, 带来的后果就是如果初始值选取不当将很容易陷入局部极小值。SA作为一种随机搜索法, 不仅接受使函数值下降的点作为新解, 而且按照一定比率接受使函数值上升的点作为新解[1], 因为暂时使函数值上升的方向也有可能找到全局最小值, 这样就可以使函数轻松逃离局部极值。
由于SA为了避免函数落入局部极值, 通常采用Metropolis接受准则, 而每一温度下要使状态达到平衡又是一个很漫长的过程, 为了提高算法的效率主要从以下几点进行改进。
1.1 新变量产生函数
根据Corana 1987年提出的自适应邻域模拟退火算法 (ASA) [2]对变量进行扰动:
现取随机扰动γ为柯西分布:
由于柯西分布有一平坦的拖尾, 因而具有迅速跳出局部极值的能力。模型可以在高温时进行大范围搜索, 而在低温时仅在当前模型附近搜索。因此加入柯西分布可以使函数具有更快的收敛速度[3]。
mu为自适应步长, 由如下公式确定
式 (3) 中:接收率
1.2 接收概率采用Metropolis准则
即当f (y
1.3 降温方式
采用Ingber (1989) 提出的VFSA中的降温方式:
TK=T0exp (-CK1/N) (5)
式 (5) 中:T0为初始温度;K为温度迭代次数;C为给定常数;N为参数个数。一般将式 (5) 变形为式 (6) , 通常0.7≤α≤1。
TK=T0αK1/N (6)
2 CSTR动态优化模型
CSTR的优化要经过目标函数的确定, 自由度分析以确定决策变量, 可行域 (约束条件) 的确定及优化问题的求解等几个步骤[4]。
在初始状态和要求达到的终态已知的情况下控制冷剂流量u (t) , 使反应器能够以最短的时间从一个稳态过渡到另一个稳态。目标函数形式如下:
式 (7) 中下标为“des”的均代表期望达到的过渡终值。α1, α2, α3为各个状态 (浓度、温度) 和操作变量 (冷剂流量) 的权重系数。
为了有效近似 (7) 式, 我们使用Radau求积公式得 (13) 式。并且用正交配置法对微分方程进行离散。离散后微分方程约束变为一组代数方程, 其中第k个有限元离散如下:
质量平衡:
能量平衡:
连接点处的质量和能量平衡:
总过渡时间:
其中hk为第k段有限元长度, N为有限元内配置点个数, A为配置矩阵, Ne为有限元个数。
Nc为包括右边界在内的正交配置点数, 在此Nc=3, y1, ij、y2, ij和uij分别代表第ij个离散点处的无因次浓度、温度和冷剂流速。Wj为Radau求积公式中的求积系数。他们试验了不同的权重系数, 并且发现最优过渡依赖于权重系数的取值。在这里考虑到浓度是主要的输出变量, 因此所占权重较大。
由以上离散后, 变成了如下形式的连续多变量优化问题:
目标函数:
3 优化处理及仿真结果
CSTR过渡过程中参数设置如表1。
配置点选为[0.211 0.789], Radau求积权重W=[0.376 0.512 0.111]T。
CSTR优化问题中的目标函数是关于控制变量、状态变量的一个函数。在此只需要填加一个计算目标函数的子程序即可。经过计算, 最优过渡曲线如图1与图2所示, 最优控制曲线如图3所示。
图中可以看出, 在给定最优控制后, 连续搅拌釜中的温度以及浓度都以较快速度过渡到了指定稳定状态, 达到了比较理想的控制效果。
4 结论
本文基于改进的自适应模拟退火算法, 很好地解决了CSTR的动态优化问题。通过MATLAB/SIMULINK对CSTR的模拟和动态优化过程的仿真, 验证了算法对动态优化过程最优解的求取不仅缩短了计算时间, 而且取得了令人比较满意的优化结果。
参考文献
[1]康立山, 谢云, 尤矢勇, 等.非数值并行算法——模拟退火算法.北京:科学出版社, 1994
[2]Silva A B, Flores A T, Arrieta J J C.Dynamic trajectory optimization between unstable steady-states of a class of CSTRs.Netherlands:Computer Aided Chemical Engineer, 2002;10:547—552
[3]王知人, 章胤, 李新乔.一种改进的模拟退火算法.高等学校计算数学学报, 2006;28 (1) :15—19
[4]Hicks G A, Ray W H.Approximation methods for optimal control synthesis.canada.Can J Chem Eng, 1971;40:522—529
自适应动态反馈算法 篇5
当前, 入侵检测技术可以分为滥用检测和异常检测两种。滥用检测由于受现有已知异常样本的局限, 无法检测出未知的异常;而异常检测由于能够发现未知异常而受到广泛关注。现有异常检测技术中主要有基于统计方法、数据挖掘[1]、遗传算法[2]、蚁群算法[3]、神经网络[4]、支持向量机[5]、人工免疫算法[6,7,8]。然而由于实际系统的正常行为是随时间动态改变的, 要求系统正常行为的样本库或训练样本也要动态, 即入侵检测系统必须能自动适应正常行为的改变。而这些方法都是离线训练或者样本不能动态适应环境的改变, 因此, 自动适应正常、异常行为的改变成为当前入侵检测系统的一个主要问题。
人工免疫系统作为新的软计算方法, 通过模拟人体免疫学理论建立了阴性选择算法、克隆选择算法和免疫网络三大算法模型[9,10,11]。阴性选择算法随机产生检测串, 并删除能识别“自我” (正常样本) 的串, 从而使该算法产生的检测串能检测除“自我”以外的“非我” (异常样本) 。由于阴性选择算法只需知道“自我”的训练样本即正常样本, 被广泛应用于异常检测[9,12,13]。为了使检测器能自动适应“非我” (异常行为) 的变化, 基本扩展的非我选择算法 (本文中命名为基于亲和力培育的动态阴性选择算法DNSA-AM (Dynamic Negative Selection Algorithm based on Affinity Maturation) 通过模拟亲和力培育原理被提出用于产生动态适应“非我”变化的检测器[14]。
匹配规则是阴性选择算法中的一个核心部件, 并有多种匹配规则[15,16]。但是, 无论哪一种匹配规则, 都有含有参数亲和力阈值 (r) 。由于该参数必须在算法运行前设定, 引起了算法的“自我”自适应问题, 即r设定困难且由于固定设置而无法适应“自我” (正常行为) 的改变。
在T胞培育过程中, T细胞经历两个选择处理, 即阳性选择和阴性选择。阳性选择要求T细胞和所有“自我”细胞的亲和力必须大于某一最小值, 而阴性选择要求T细胞和所有“自我”细胞的亲和力必须小于某一最大值[16]。在本文中, 通过模拟T细胞的培育过程, 提出了由最大亲和力selfmax和最小亲和力selfmin构成的匹配区域模型。基于该模型对DNSA-AM算法进行改进, 从而得到用于异常检测的算法, 即基于匹配区域模型的动态阴性选择算法DNSA-MRM (Dynamic Negative Selection Algorithm based on Match Range Model) 。该算法中不存在参数亲和力阈值, 因为亲和力阈值被由“自我”决定的匹配区域参数selfmax、selfmin所代替, 而且selfmax、selfmin是检测器通过同所有“自我”进行匹配得到的最大最小亲和力, 其值决定于所有“自我”, 从而能自动适应“自我”的改变, 解决了“自我”自适应问题。
1基于匹配区域的动态阴性选择算法
1.1匹配区域模型
U={0, 1}n, n为二进制串的长度;自我集合定义为Selves, 非我集合定义为Nonselves, Selves∪Nonselves=U, Selves∩Nonselves=Φ;假设字符串Ag=g1g2…gn, Ab=b1b2…bn, 则海明距离计算如式 (1) :
检测器定义为Detector={<d, selfmin, selfmax, age>|d∈U, selfmin, selfmax, age∈N}, 其中, d为检测器的二进制串, selfmax为最大亲和力, selfmin为最小亲和力, age为检测器的存活年龄;检测器集合定义为Detectors。Selfmax、selfmin的运算setMatchRange (str, Selves) 如式 (2) , str∈U, i∈[1]Selves|]:
式 (2) 用于建立匹配区域模型, [selfmin, selfmax]构成的区域称为“自我”区域, 此外的区域为“非我”区域。
给定一个待检测串Antigen∈U, Antigen同检测器Detector的海明距离x=hamming (Antigen, Detector) , 当x不属于[Detector.selfmin, Detector.selfmin]区间时, 两者相匹配, Antigen识别为非我串。本文把该规则定义为区域匹配规则Match (Antigen, Detctor) , 如式 (3) , 结果为1表示匹配, 即Antigen为非我串。
1.2检测器的产生
当给定一个随机串RandomStr∈U, 通过式 (2) setMatchRange得到RandomStr.selfmax、RandomStr.selfmin。由于对于任意一个Selfi, 其hamming (RandomStr, Selfi) ∈[RandomStr.selfmin, RandomStr.selfmax], Match (RandomStr, Selfi) =0, 即随机串设置selfmax、selfmin以后不会同任何自我串匹配。RandomStr不会识别到任何“自我” (即自我耐受) , 从而成为有效检测器并加入Detectors。而在阴性选择算法中, 随机产生的随机串通过匹配Match处理后, 部分串会由于识别自我不能成为有效检测器而被丢弃, 因此阴性选择算法产生有效检测器的速度要比较慢。
此外, 根据式 (2) , selfmax、selfmin的值由Selves决定, 而当Selves变化时, 检测器的selfmax、selfmin能跟随Selves的变化而变化, 从而解决了DNSA-AM算法的“自我”自适应问题。
1.3检测过程
给定一个待检测串Antigen∈U, Antigen同Detectors中的所有检测器Detector进行匹配, 式 (3) , 只要有一个检测器同Antigen匹配, 则Antigen被识别为非我。检测过程Detected (Antigen, Detectors) 定义如下式 (4) , k∈[1]Detectors|]。
1.4算法实现
为了加速检测速度, 人体免疫系统通过亲和力培育 (affinity maturation) 机制使淋巴细胞能够快速学习并记住特殊病原体的结构[15]。亲和力培育机制主要有三个特征[14,15,17]:克隆变异机制、受体编辑机制、“自我”耐受机制。本文基于DNSA-AM算法和匹配区域模型提出了DNSA-MRM, 算法中检测器和检测对象的亲和力为海明距离 (检测器的适应值) 。算法为了模拟克隆操作, 单个父个体产生的后代数量正比于父个体的亲和力, 产生最大的后代数量为种群大小PSize×繁殖率α;为了模拟超变异操作, 仅采用变异操作, 变异位数为 (编码长度-亲和力) /2;算法通过随机产生检测器来模拟受体编辑机制, 使产生的后代个体有较好全局搜索能力, 产生最大的后代数量为种群大小×繁殖率β;通过式 (2) 分别计算检测器同所有“自我”的亲和力, 得到最大亲和力selfmax和最小亲和力selfmin, 由于检测器同所有“自我”的亲和力一定不大于selfmax并且不小于selfmin, 检测器不会同任何一个“自我”匹配, 即式 (3) Match=0, 从而实现“自我”耐受。当一个待检测对象经过MaxUndetectGen代数仍未能识别, 则认为是正常的。
2实验与分析
本实验主要目的是: (1) 通过DNSA-MRM和DNSA-AM的比较实验, 验证DNSA-MRM的改进后的效果; (2) 验证DNSA-MRM是否解决了自适应问题; (3) 对DNSA-MRM算法的其他特性进行分析。
2.1DNSA-MRM和DNSA-AM的比较
为了进行比较, 本文采用任意字符串进行模拟实验[14]。实验中, 编码位数为64, α=0.95, β=1-а=0.05, PSize=200, MaxGen=MaxUndetectGen=250, “自我”的数量为1000。
2.1.1 对不同亲和力阈值下DNSA-AM的实验分析
为了获得DNSA-AM算法的最优亲和力阈值, DNSA-AM在不同的亲和力阈值下进行了20次重复实验。其中, “非我”的数量为1, 运行结果如图1所示。
图1 (上) , 亲和力阈值为44时, 算法的代数耗费最小 (在本文中, 代数耗费定义为检测全部异常需要的进化代数) ;图1 (中) , 亲和力阈值为45时, 算法的时间耗费最小。当亲和力阈值大于45时, 算法能够搜索到足够数量的有效检测器图1 (下) , 因而检测到异常的所需繁殖代数为代数、时间耗费的主要影响因素, 由于亲和力阈值越小, 检测器的检测范围越大, 因而单个检测器检测到异常的概率越大, 从而导致算法代数、时间耗费越小, 如图1 (上) 、 (中) 所示。当亲和力阈值在43和45之间时, 算法只能搜索到较少数量的有效检测器图1 (下) , 此时, 算法搜索有效检测器所需的繁殖代数为代数、时间耗费的主要影响因素, 在图1 (下) 中, 算法的阈值越小, 有效检测器数量越少, 所以算法搜索到有效检测器的难度越大, 从而产生有效检测器所需的代数、时间耗费越大, 如图1 (上) 、 (中) 所示。
2.1.2 DNSA-AM和DNSA-MRM的实验比较
两个算法在不同“非我”个数下各自独立运行20次, 运行结果如图2所示。
从图中可以看出DNSA-AM算法的代数耗费较小, 因为算法选取了较优亲和力阈值。但是DNSA-MRM算法的时间耗费最小, 因为DNSA-MRM每产生一个检测器, 经过设置selfmin、selfmax后, 都可以成为有效检测器, 而DNSA-AM由于亲和力阈值的限制会产生部分无效检测器, 所以DNSA-AM产生同样数量的有效检测器所需的时间耗费就相对较大。
2.2DNSA-MRM算法的自适应性
实验中, 编码位数为64, α=0.95, β=1-α=0.05, PSize=200, MaxGen=MaxUndetectGen=250, “自我”的数量在第5代以前为50, 在第5代时, “自我”的数量改变为1000, 算法在“非我”数量为10时独立运行20次, 结果如图3所示。在第4代和第10代之间, 由于“自我” 数量的改变, 算法有一个自适应的过程。在此自适应过程中, “自我”数量的增多使检测器的匹配区域 (selfmax-selfmin) 变大。
2.3DNSA-MRM的其他特性分析
该实验目的为了解攻击序列对算法检测速度的影响。实验仍采用任意字符串进行模拟实验, 编码位数为64, α=0.95, β=1-α=0.05, MaxGen=MaxUndetectGen=250, “自我”数量为1000, PSize为200, 在第[0, 5, 10, 15, 20]代出现“非我”, 其中, 出现的“非我”数量见图4标注中的数组。
本文把速度定义为“非我”数量/代数。在图4中, 曲线斜率的倒数 (即检测到的“非我”数量/平均耗费代数) 定义为检测速度, 曲线越陡表示检测速度越慢。假设“非我”数量以每n代出现m个“非我”的速度发生, 则m/n定义为攻击速度。在下半图中, 当攻击速度大于等于4/5时 (即Test6, 7, 8三次实验) , 曲线斜率趋于恒定, 把此时的检测速度定义为最大检测速度MaxSpeed, 即系统满负荷运行, 当“自我”和检测器数量一定时, MaxSpeed将一定;而当攻击速度小于4/5时 (即Test4, 5两次实验) , 曲线斜率较大, 即检测速度较小, 说明系统没有满负荷运行。因此, 下半图反映了系统的运行情况, 攻击速度越大, 系统的运行功率越大, 其中, 运行功率=当前检测速度/MaxSpeed=检测到的“非我”数量/平均耗费代数/MaxSpeed。上半图则反映了攻击速度变动时系统的功率变化情况。
3结论
在现实系统中, 正常样本的随时间动态改变要求入侵检测系统的检测器也能动态改变, 本文基于匹配区域模型对DNSA-AM进行改进。通过以上实验分析, DNSA-MRM能够自动适应正常行为的改变, 且有其优越的特性:
1) 当DNSA-AM的亲和力设为最优值时, DNSA-MRM的时间耗费仍比DNSA-AM小, 但是代数耗费比DNSA-AM大;
2) 通过利用匹配区域模型, 算法能够动态适应“自我”的改变。
摘要：基于亲和力培育的动态阴性选择算法用于产生能适应“非我”变化的检测器, 该检测器可以用于入侵检测。由于算法参数亲和力阈值必须设定为常数, 从而不能适应“自我”的变化。通过模拟T细胞的培育过程, 提出了匹配区域模型, 基于该模型进而提出了改进的动态阴性选择算法。通过设置匹配区域使检测器实现了自我耐受和自动适应“自我”的变化, 从而解决入侵检测系统的自适应问题。通过异常检测的模拟实验表明所提出的算法更加有效, 如时间耗费小、匹配区域能自动适应“自我”的变化。
自适应动态反馈算法 篇6
随着现代远程教育的飞速发展,要求网络在线考试系统具备智能组卷功能,即在考试大纲的规定与用户指定的要求下在有效的时间内生成一定数量的有差别的等效试卷,其中的核心问题是题库的计算机智能组卷。使用传统算法解决智能组卷显得力不从心,而遗传算法能以较大概率在有限时间内搜索到全局最优解或近似最优解,但其本身存在着易早熟收敛、遗传算子无方向性和收敛速度慢等不足,需要在具体的应用中引入问题域的启发式知识做适当的改进。
2. 建立组卷问题的数学模型
组卷问题实质上是一个多目标和多约束的组合优化问题,通常可根据某效用函数将多个目标依照各自权重组合成单一目标来优化处理以期找到问题的近似最优解。
2.1 问题描述
组卷的目标是生成多份有差别的能准确考核学生对知识的掌握情况的高质量等效试卷,基于组卷的实际需要与问题的复杂性,精选试题的属性定义试卷;在组卷策略中,采用的试题相关属性定义如下:
(1)题目编号:试题的唯一标识,使用整数数据类型;(2)题型编号:主要包括单项选择题、多项选择题、填空题、判断题、简答题、综合题等题型,使用整数数据类型;(3)题分:试题的分值,使用实数数据类型;(4)知识点编号:试题所考核的知识点,与科目的章节有关,使用整数数据类型;(5)难度:试题的困难程度,取值范围:难(0.8-1.0),较难(0.6-0.8),一般(0.4-0.6),较易(0.2-0.4),易(0-0.2)[2],使用实数数据类型;(6)考核要求编号:试题在教学内容上的要求层次,一般分为:了解、理解、掌握、熟练掌握与综合,使用整数数据类型;(7)估时:完成该试题所需的时间,以分钟为单位,使用整数数据类型;(8)区分度:试题对学生学习水平的鉴别能力,取值范围:好(0.4-1),较好(0.3~0.4),一般(0.2~0.3),差(0.2~-1),使用实数数据类型;(9)选用次数:该题曾被选中的次数,表示使用频度,使用整数数据类型。
假设生成的一份试卷的试题数目为n,试卷则由以下矩阵S决定,其中每道试题上述的9个属性决定矩阵S某一行元素的值[3]:
这就是求解组卷问题的目标状态矩阵。
2.2 目标函数
组卷问题实质上一个多目标多约束的组合优化问题,上述矩阵S的列元素的分布分别体现了以上9种用户指定的试卷要求,假定这些要求(约束)与用户指定的要求的误差为fi,fi可等于0或者较小值,为了不至于各误差互相抵消,fi都取绝对值[4],每个约束的重要性各不相同,用户可根据组卷实际需要自定义其权重wi;本文采用多目标加权法将每个目标函数值fi乘以相应的权重wi,以其加权和作为问题的目标函数f,用单目标优化法求最优解:
其中:fi为第i个约束与用户要求的误差的绝对值,考虑到题型内的题数固定,f1=0;wi为用户对第i个约束条件指定的权重系数。组卷时候用户可以根据考试的需要对不同约束条件赋予相应的权重系数,使整卷误差f最小的试卷即是所求解,可见,组卷问题可转化为满足多约束条件下的最小化问题。
3. 智能组卷的改进式遗传算法设计与应用
由于经典遗传算法在解决智能组卷问题时存在收敛速度慢、易出现“早熟”现象、盲目搜索与全局寻优能力弱等先天缺陷,致使出卷质量差,难以满足题库多变的需要,为此,本文提出了基于整数编码与动态自适应技术遗传算法,利用组卷问题的特征对经典遗传算法的多个关键组成部分进行改进,引入问题域的启发式知识,采用动态自适应技术,以提高改进遗传算法的搜索效率、减少“早熟”现象、加强全局寻优能力,算法流程如图1所示。
设计时,主要考虑以下几个方面:
3.1 染色体编码方案的改进
经过分析发现经典遗传算法中的二进制编码方案在求解组卷问题时候已不大适用:染色体(个体)的二进制位串太长、计算量大、编码与解码过程复杂。为此根据组卷问题的特征,采用分段式整数编码方案。设某一染色体:H(a1a2…ai…an),其中ai为非负整数的题目编号,n为试卷题目数量,在染色体H中相同题型的题目编号放在一起形成一段,在本文的组卷策略中,试卷里某种题型的题数由用户指定后固定不变(见约束1),映射到染色体每段的长度也固定,可用一个整数数组A[n]存放染色体H,如在一份试卷中用户指定单选题数量为20,则“单选题”段长度固定为20,数组A0到A19存放单选题的题目编号(假定单选题放在染色体始端),其它题型段以相同规则依次存放到染色体H。分段式整数编码方案以题目编号作为基因组成染色体,不存在解码问题,加快了算法的速度,此外采用分段式组织基因,有利于算法的遗传操作。
3.2 群体规模的改进
遗传算法的进化过程有两个关键点:群体多样性和选择性压力,显然,这两个因素都受群体规模的影响[5]。如果群体规模太小,遗传算法可能收敛得太快;如果太大,则运算时间成本太高。经典遗传算法使用不变的群体规模,存在一定的不合理性,大量实验表明:在进化过程的不同阶段,可能存在“最优”不同群体规模。本文提出一种群体规模动态自适应方案,在群体的迭代过程中,通过侦测当前群体的适应值的“稀疏”程度来动态调节群体规模;用适应值的样本标准差F与群体平均适应值fa之比r作为“稀疏”系数来表示群体适应值的“稀疏”程度,即r由下面公式确定:
稀疏系数r=F/fa(2)
其中P群体为规模,fa为群体评价适应值,fi为群体个体适应值。
根据“稀疏”系数r动态调节群体规模P:
当r∈[a,b],P保持不变;当r∈[0,a),P=P+P*r;当r∈[b,∞),P=P-P*r。
其中80≤P≤140,a,b取经验值:a=0.15,b=0.45,而关于群体规模变化部分P*r的选取策略将在选择运算中详述。由本文组卷模型的实验数据表明,群体规模P初始值取100为宜,而在进化过程当中限制P在区间[80,140]内变动较为合适。
3.3 群体初始化
根据用户输入的试卷参数,从试题库中随机抽题放到染色体相应的题型段中,直到随机生成P个染色体为止。
3.4 确定适应度函数
在遗传算法中,以适应度函数值大小来评价染色体的优劣,一般而言,适应度函数是由目标函数经过尺度变换而形成的。由上述的目标函数f可知,本文的组卷策略实质是求目标函数f的最小化问题,经分析将目标函数f经过指数变换法成为适应度函数f’=e-af。其中系数a决定了选择的强制性,其值越小,选择的强度就越趋向于那些具有最大适应度的个体[1];根据本文组卷实际需要,本文a取值0.03。
3.5 遗传算子的改进
(1)动态自适应的交叉概率与变异概率
交叉概率pc与变异概率pm的选用是影响遗传算法行为和性能的两大关键参数,对算法的收敛性影响很大,pc越大,新个体产生的速度越快,对群体的多样性有利,但也存在高适应值的较优个体的结构很快被破坏的风险;而pc过小,会使搜索过程缓慢,以至停滞不前。同一对变异概率pm,如果过小,就不易产生新个体结;如果pm,过大,那么遗传算法就变成了纯粹的随机搜索算法[1]。经典遗传算法使用固定不变的交叉概率与变异概率,显然有待改善,为此本文采用交叉概率与变异概率自适应策略,pc与pm能够随个体的适应度自动调节:当适应值低于平均适应度值时,对它采用较大的pc与pm,以淘汰性能不够好的染色体;反之,采用较小的pc与pm,以保留性能优良的染色体。这对群体进化的后期很有利,而对进化初期不利:群体中的初期“最优”个体难以发生改变;为此需进一步改进:使群体中的初期“最优”个体的pc与pm都不为0,以保证它们不会处于近似停滞不前的状态。交叉概率pc与变异概率pm的与个体适应值函数关系如图2所示:
综上所述,交叉概率pc与变异概率pm的计算公式如下所示:
其中,fm为群体中最大的适应值,fa为每一代群体的平均适应度值,f’为要配对交叉的个体中较大者的适应度值,f为要变异的个体的适应度值。根据经验值,各参数取值为:pc1=0.9,pc2=0.6,pm1=0.1,pm2=0.001。
(2)交叉运算
经典遗传算法采用单点交叉的方式,在两个染色体间交换相同长度的DNA片断,基于上述的染色体编码方案,本文采用多点交叉再修正方式:首先对规模为P(下同)的群体中的每个染色体H(长度为m,下同),产生一个在区间[0,1]的随机数r,如果r小于交叉概率pc,则选中此染色体H,预计有P*pc个染色体被选中,如果P*pc为奇数,则随机移走一个被选中的染色体,保持P*pc为偶数以便配对交叉;在选中的染色体中随机选取配对,在配对的染色体中随机产生m*pc个不同的交叉位置,然后按下面方式交叉(假定随机产生了3个位置:i,j,k):
产生的两个子个体C1、C2,为避免在相同题型内存在重复抽题的现象,即题号相同,有必要修正此两个子个体:检查每个题型段,如果出现题号重复情况,则从题库内随机选取同题型不同题号的试题替换重复的试题。
(3)变异运算
本文的变异运算采用类似于二进制编码遗传算法中的基本位变异方式。群体中每个染色体的每个基因(即题号)有均等的变异机会,整个群体有m*P个基因,预计平均每代有m*P*pm次变异,可对群体中的每一位产生一个在区间[0,1]内的随机数r,如果r小于变异概率pm,则变异此位:从题库内随机选取同题型不同题号的试题替换原试题。使用与交叉运算同样的方法修正变异后的子染色体,以避免同一染色体内出现重复抽题的现象。
3.6 选择运算
为了保持群体的多样性,提高算法的鲁棒性,避免群体出现“早熟”现象,在确定群体规模P后,采用跨世代精英选择策略与无重复串的稳态繁殖技术[1]来选择个体的方案,具体步骤如下:
(1)混合父子两代群体生成备选池,并按适应值的降序排序;
(2)采用无重复串的问题繁殖技术,在备选池中选取靠前的P个相异个体组成新的群体,如果选取的个体数目小于P,则再从题库中随机抽取试题组成若干个体,补充到新的群体中,使群体规模达到P。
3.7 算法结束条件
算法结束采用下面3种标准:(1)适应函数值f满足用户要求后结束;(2)算法运行到一定的时间后,进化效果停滞不前可结束;(3)算法运行到一固定的次数后结束。
4. 实验结果与分析
根据上述改进式遗传算法的思想采用基于web的ASP.NET编程技术开发了网络考试系统,并针对电大计算机课程《数据库基础与应用》的题库进行计算机自动组卷实验,结果验证了本文提出的改进式动态自适应遗传算法的可行性与有效性,其性能与经典遗传算法性能相比有明显改善。
5. 结束语
计算机智能组卷问题是一个多目标多约束的组合优化问题,本文通过对组卷问题的分析研究,改进经典遗传算法多个关键部分:采用整数编码组织染色体,采用指数尺度变换目标函数为适应度函数的方法,引入动态群体规模和自适应交叉与变异概率技术,采用跨世代精英选择策略与无重复串的稳态繁殖技术的个体选择方案等等。这些改进措施提高了算法寻优速度,有力避免经典遗传算法易出现的“早熟”现象,较好地解决了计算机自动组卷问题。
参考文献
[1]王小平,曹立明.遗传算法---理论、应用与软件实现[M].西安:西安交通大学出版社,2002.
[2]陆亿红,柳红.基于整数编码和自适应遗传算法的自动组卷[J].计算机工程,2005,31(23):232—233.
[3]全惠云,范国闯,赵霆雷.基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报(自然科学版),1999,45(5):758—760.
[4]华如海,王俊普.基于约束满足的智能组卷方法的研究与实现[J].计算机应用研究,2000,11:20—22.
自适应动态反馈算法 篇7
北斗是中 国正在实 施的自主 发展 、 独立运行 的全球卫 星导航系 统 ,与目前应 用最成熟 的GPS或其他类 型导航设 备可构成 组合导航 系统 ,为工作在 复杂环境 中的飞行 器提供可 靠导航信 息 , 而飞行器 机动性未 知 , 组合导航 系统运动 模型以及 噪声统计 特性存在 误差 。 为了处理 各种误差 , 文献 [1] 直接对GPS接收机的 输出结果 进行动态 滤波 ; 文献 [2] 设计一种 容错型联 邦强跟踪 滤波器并 应用于COMPASS、GPS、GLONASS组合导航 系统中 ;文献 [3-4] 对GPS、GLONASS、GALILEO组合导航 系统提出 自适应联 邦Kalman滤波以及 双重自适 应算法 。
标准Kalman滤波是一 种在正确 的运动模 型和噪声 统计特性 下对导航 系统动态 数据进行 实时滤波 的有效方 法 ,但在实际 应用中受 限 。 Sage-Husa算法利用 噪声估计 器对未知 且时变的 噪声统计 特性进行 估计[5],而北斗/ GPS组合导航 系统维数 较高 , 计算量大 , 一旦Q ( 过程噪声 协方差阵 ) 和R( 量测噪声 协方差阵 ) 分别失去 半正定性 和正定性 会导致滤 波发散 。 简化Sage-Husa算法删去q ( 过程噪声 均值 ) 和r ( 量测噪声 均值 ) 的计算 , 认为Q稳定 ,并改进R估计表达式[6]。 而实际情况下的Q会变化 , CS模型中加 速度上下 限取值过 大或过小 , 均导致系 统噪声方 差与实际 不符 ,跟踪精度 低 。 为此 ,本文提出 一种适应 飞行器运 动状态的 改进自适 应算法 , 它实时估 计R , 且利用速 度滤波 、 预测估计 间的差值 改进加速 度协方差 计算表达 式 , 实现Q自适应于 飞行器的 机动特性 , 并提高跟 踪能力 。 通过实验 仿真与标 准Kalman、 简化Sage - Husa算法进行 了比较和 分析 。
1北斗/GPS组合导航系统模型的建立
1.1联邦滤波器设计
视北斗 、GPS为两个相 互独立的 联邦成员 , 并分别设 计自适应 子滤波器 ,采用容错 性最好的 无反馈重 置联邦滤 波器对各 子滤波器 进行数据 融合 ,见图1。 若北斗 、 GPS子滤波器 局部状态 估计和相 应估计协 方差阵分 别为 ( X赞1, P11) , ( X赞2, P22) , 且各局部 估计互不 相关 , 即Pij= 0 ( i ≠ j ) , 则全局最 优估计为 :
北斗 、GPS子滤波器 数学模型 的建立方 法相同 , 不妨以GPS为例 。 子滤波器 建立的状 态方程有12个状态变 量 , 观测方程 有由接收 机输出的3个观测量 , 且每组状态变量和对应观测量相 互独立 。 可分别对e,n,u(东北天坐 标系 )三个轴向 的状态变 量以及对 应观测量 单独滤波 ,以e轴模型建 立进行讨 论 。
1.2北斗/GPS组合导航系统状态方程建立
由于飞行 器是在三 维空间的 运动 , 考虑飞行 器的位置 、速度 、加速度以 及GPS在e轴方向上 的总误差 ,采用CS模型[7]描述飞行 器的运动 。
状态方程 为 :
式中 ,X =[xeveaeεe]T, xe、 ve、 ae分别为东 向位置 、 速度和加 速度 ;εe为e轴方向上 的总误差 , 等效一阶 马尔可夫 过程 ;Uk - 1为加速度 “ 当前 ” 均值 ;Wk - 1为系统噪 声 ; 状态转移 矩阵为 Φk , k - 1, 系统噪声 协方差阵 为Qk - 1。将加速度 一步预测 作为 “当前 ”加速度均 值 ,则状态一 步预测方 程为 :
式中 :
1.3北斗/GPS组合导航系统观测方程建立
系统的观 测量包括 接收机输 出的飞行 器东向 、 北向和天向坐 标分量xe、 xn、 xu, 各个方向 的总误差 εe、 εn、 εu以及量测 噪声 ωZe、 ωZn、 ωZu( 观测方程 中仅列出 东向观测 量 )[1], 实验中经 纬高度量 测值单位 为m, 并用量测 值叠加高斯白 噪声 。
观测方程 为 :
式中 , 观测值Zk= E , 量测噪声V = ωZe, 量测矩阵H = [ 1 0 0 1 ] 。
Rk为观测噪 声协方差R的离散化 形式R=Re2。
2算法描述
2.1简化Sage-Husa算法
在线同时 估计噪声 统计特性 会使维数 较高的组 合导航系 统实时性 变差 , 认为R对滤波影 响最为明 显 ,视Q为定值[6]。
设线性离 散时间系 统为 :
式(6)、式(7)中Xk是n维状态向 量 ,Zk是m维观测序 列 ,Φk , k - 1是维状态 转移矩阵 ,Hk是m×n维观测矩 阵[8]。 Wk - 1和Vk是相互独 立的正态 白噪声序 列 。 算法描述 如下 :
2.2改进自适应算法
因飞行器 的飞行环 境复杂 ,且其运动 规律未知 ,系统干扰存在不 稳定性 , 仅仅实时 估计量测 噪声不能 明显获得高精度导航信息,以及实时并准确估计出系统干扰。
可以通过CS模型中加 速度协方 差估计出 系统干扰 , 但是在CS模型中 , 当飞行器 弱机动时 , 其当前加 速度a赞k较小 , 与较大的 加速度上 下限amax差值偏大 , 加速度协方差 σa偏大 ,导致Q偏大 。 可见 ,加速度上 下限不能 自适应飞 行器的机 动特性 ,滤波器跟 踪能力较 差 。 因此 ,本文对加 速度协方 差的计算 进行改进 。 利用速度 估计 、速度滤波 预测之间 的差值改 进了加速 度协方差 的计算表 达式 :
由式 (9) 可知 , 当飞行器 弱机动或 无机动时 , 其速度滤 波vk、 预测估计vk , k - 1之差较小 , 加速度协 方差较小 ; 当飞行器 强机动时 ,其速度滤 波vk、 预测估计vk , k - 1之差值较 大 ,加速度协 方差较大[9]。 因此 ,不管飞行 器机动性 如何 ,滤波器都 能保持较 好跟踪 。
在进行滤波过程中,不仅能实时估计R,而且根据飞行器的机动特性计算出加速度方差,从而较准确地估计出Q。
3实验过程以及算法仿真
3.1实验过程
实验所用 的接收机 为国内和 芯星通公 司的北斗/ GPS双模模块 , 将其安置 在无人飞 行器上 , 通过无线 数传模块 与上位机CDT软件进行 通信 。让无人飞 行器保持 一定高度 在操场实 时采集并 存储数据 , 采集频率1 Hz, 实验时间350 s。 飞行器的 初始位置 为纬度25.28°,经度110 . 33 ° , 初始速度 为1 m / s , 初始状态 协方差P0= diag ( 402, 1 . 02, 0 . 12, 402) , 初始加速 度为0 。 滤波参数 如下 :
3.2算法仿真分析
实验仿真 曲线 、数据均来 自MATLAB。
实验1:改进自适 应算法仿 真
根据建立 的北斗/GPS组合导航 系统数学 模型 ,利用标准Kalman滤波 、简化Sage-Husa算法和改 进自适应 算法对该 模型经度 方向误差 进行滤波 估计 , 滤波效果 如图2和图3所示 。 同时统计 了两种算 法下的经 纬度 、 速度均方 根和均值 误差 , 如表1所示 。 对每种方 法进行M = 100次蒙特卡 罗仿真 , 用均方根 误差衡量 滤波精度 , 每一时刻 的均方误 差为(dik为真值与 观测值的 偏差):
从图2、 图3的仿真曲 线可知 , 在相同时 刻 , 改进自适 应算法得 到的位置 滤波效果 显然要优 于另外两 种算法 , 因为飞行 器采集数 据过程中 , 其运动规 律和噪声 未知 。 标准Kalman、 简化Sage-Husa算法均未 同时估计Q和R, 也没有考 虑加速度 上下限对 状态估计 精度的影 响 , 改进自适 应算法不 仅估计R, 而且根据 飞行器的 机动特性自 适应调整Q,跟踪精度 提升 。 表1的统计结 果也说明 了这一点 。
实验2:北斗/GPS组合导航 系统计算 仿真
利用无反 馈重置联 邦滤波器 对北斗 、GPS信息进行 融合 ,子滤波器 均采用改 进自适应 算法 。 将北斗/GPS组合导航 系统的导 航信息与 实际飞行 数据作差 ,并分别与 北斗、GPS子系统的仿真结果进行对比,仿真结果见图4~ 图6,相关统计 量见表2。
从图4~图6可以看出 ,GPS、北斗系统 的位置误 差分别在1 m、2 m以内 , 而北斗/GPS组合导航 系统的位 置误差在1.2 m以内 , 其误差处 于GPS和北斗系 统之间 。 表2的误差统 计结果表 明北斗/GPS组合导航 系统的位置误差仅 次于GPS。 这是由于 北斗 、GPS同属于卫 星导航系 统 , 系统性能 、 误差特性 相似 , 优劣相当 , 因此同种 类型导航 系统之间 的信息融 合效果不 及于不同 类型导航 系统之间 取长补短 带来的滤 波效果 。 然而采用 无反馈重 置联邦滤 波器的北 斗/GPS组合导航 系统 , 容错性能 最好 ,且计算量 少 ,满足导航 系统实时 性高的要 求 。
4结束语
本文提出一种改进自适应算法,根据飞行器的运动状态实时估计Q, 并估计出R, 同时融合北斗 、GPS系统信息,通过与标准Kalman、简化Sage-Husa算法的仿真比较, 验证改进自适应算 法能明显提高组合 导航系统 的导航精 度。 将改进自适应算法应用于北斗/GPS组合导航系统中, 其定位精度虽与GPS相当,但是提高了系统容错性。 随着中国北斗的不断发展,与其他卫星导航系统以及不同类型导航设备(如捷联惯导)之间的组合拥有更大的应用潜力。
摘要：北斗与GPS或其他类型导航设备可构成组合导航系统,为无人飞行器提供高精度、高可靠导航信息。在处理动态导航数据采用“当前”统计模型(CS模型)并利用标准Kalman滤波方法时,系统动态噪声和观测噪声未知且时变,而且加速度上下限值不能自适应于未知运动规律的无人飞行器当前加速度,导致导航精度降低。为此,提出一种适应于飞行器运动状态的改进自适应算法,并应用于北斗/GPS动态导航系统中。实验仿真验证了该算法能有效提高组合导航系统的精度和可靠性,并能更好地自适应于无人飞行器的机动特性。