自适应信赖域算法

2024-05-08

自适应信赖域算法（精选八篇）

自适应信赖域算法篇1

以上的信赖域算法都是采用二次模型来逼近原问题, 并且传统的信赖域算法中的子问题二次模型的逼近精度和信赖域大小的选择是影响算法收敛速度的关键, 目前理论和算法均相对较为成熟。1980年, Davidon首次提出了锥函数, 随后有许多学者对锥模型进行了深入的研究, 对于一些非二次性态强, 曲率变化剧烈的函数, 采用锥模型信赖域算法在实际计算中是具有某些优势的算法。为克服锥函数可能无界性, 在2005年倪勤提出了关于锥模型信赖域子问题一种新的可行集对妻子问题考虑了更一般的情形, 去掉b必须满足1-bTd>0的限制, 将新的可行集分成3种情形, 由此可得到3种不同类型的锥模型信赖域子问题。

在上述基础上本文提出了一种改进的非单调自适应的新锥模型信赖域算法, 将一种新的非单调技术运用在新锥模型中, 并加入了自适应技术和线性搜索技术。

1 新锥模型信赖域子问题

新锥模型信赖域子问题为

B={d∈Rnd≤Δk}, S={d∈Rn1-bTkd≥ε0}, ε0∈ (0, 1) 。在文献[9]中将上述信赖域子问题的可行域重分为3类, 得到了3种不同的锥模型信赖域子问题。自从新锥模型子问题提出后, 有许多研究工作者对该问题进行了研究, 并提出了不同的关于锥模型子问题的求解方法, 但仍有待改进。

2 非单调Wolfe线性搜索准则

非单调Wolfe线性搜索准则形式:λk满足

其中, c1∈ (0, 1) , c2∈ (c1, 1) , 0≤m (k) ≤min{m (k-1) +1, m}, 其中m (0) =0, M≥0为常数

定义fl (k) =0≤jm≤amx (k) f (xk-j) , k=0, 1, 2, … (4) 注:当m=0时, 非单调Wolfe线搜索则是一般的Wolfe搜索。

3 锥模型拟牛顿算法及其改进

一般的Bk+1, bk+1的构造采用锥模型拟牛顿法, 拟牛顿法中的Bk满足拟牛顿方程, 如

其中yk=gk+1-gk, sk=xk+1-xk;著名的Bk校正公式有

Broyden族校正公式

其中Ф∈R1是一个参数, 式 (6) 和式 (7) 是式 (8) 的一个特例。本文采用Broyden族校正公式产生Bk+1。

其中

引理1[15]假设Bk为正定对称矩阵, 当ykTsk>0时。则Broyden族校正式 (8) 。当Φ≥0时, 使Bk+1保持正定对称且满足拟牛顿方程式 (5) 。

引理2当gkTdk<0时, 在迭代公式xk+1=xk+λkdk中, 假设λk是由非单调Wolfe线搜索式 (2) 和式 (3) 求得, 则ykTsk>0成立。

4 非单调自适应新锥模型信赖域算法

Step1给定ε>0, x0∈Rn, 正定对称矩阵B0∈Rn×n, Δ0>0, η∈[0, 1], c1∈ (0, 1) , c2∈ (c1, 1) , k=0, m (0) =0, m≥1, c∈ (0, 1) , p=0, Δmax>Δ0>0, τ∈ (0, 1) ;

Step2计算gk, 若满足gk≤ε则终止;否则转Step3;

Step3用折线法去求解如下子问题 (1) , 得到近似解dk;且dk满足

Step5确定试验步的可接受性。若ρk≥η, 则接受dk, 令xk+1=xk+dk;否则求得步长λk, 使其满足式 (2) 和式 (3) , 令xk+1=xk+λkdk

Step6更新信赖域半径:

Step7计算m (k+1) ;令k=k+1, 根据式 (8) 和式 (9) 更新Bk和bk;转Step2。

5 算法的收敛性

为证明算法的全局收敛性, 给出如下假设, 记:

H1水平集S={x f (x) ≤f (x0) , x∈Rn}有界, 且{xk}∈S;

H3f (x) 在水平集S上二次连续可微, 且存在M>0, 使得。

引理3[17]设{xk}是由算法生成的序列, 其中k≥0, 则xk∈S, k。

引理4[17]若假设H1和H3均成立, 则数列{fl (k) }非增且收敛。

引理5[6]若H2~H4均成立, 若存在常数ε>0, 对全部的k满足, 则存在常数v>0, 使得k∈J, 有λk≥v。

引理6若H2~H4均成立, 若存在常数ε>0使得k, 有, 则存在A>0, 有

定理1若假设H1~H4均成立, 则由第4节算法产生的点列满足

证明反证法;假设式 (14) 不成立, 则, 根据引理5和引理6可得,

当k∈I时

当k∈J时

由式 (15) 和式 (16) 可知, 有fl (k) -f (xk+dk) ≥w Zk即

在上面不等式两边取最大值, 有k, fl (k) ≥max{fk+1, fk+2, …, fk+m+1}+w/Zk+m+1。因为fl (k+m+1) ≤max{fk+1, fk+2, …, fk+m+1}, k, 得到fl (k) -fl (k+m+1) ≥w/Zk+m+1。又因数列{flk}非增且收敛以及上式得, 则有上式及序列Zk, k=0, 1, 2, …单调上升, 可得

这与假设H4矛盾。假设不成立, 则原命题成立。

6 数值试验

为了说明算法的有效性, 利用Matlab编写程序对本文算法进行数值测试, 其中, Nf、Ng分别表示函数值和梯度值的迭代次数;n表示问题的维数。参数选择:Δ0=1.5, η=0.75, c1=0.1, c2=0.3, m=4, 终止准则为:。

测试问题:Penalty-I Function

三维空间中Penalty-I函数的图像, 如图1所示。

7 结束语

自适应信赖域算法篇2

将自适应收缩可行域的遗传算法与视纵向电导微分成像法相结合,反演瞬变电磁测深中的导电薄层,计算结果证明:该算法通过对可行域的.自适应收缩,加快了计算速度、提高了计算精度;并在一定程度上克服了瞬变电磁测深的等值性,缩小了等值范围.通过对导电薄层模型的模拟计算和实例分析,并与常规反演曲线进行对比,使用本法反演成像的结果,明显地显示出导电薄层的存在.

作者：李貅薛国强宋建平郭文波武军杰沈梅芳 Li Xiu Xue Guoqiang Song Jianping Guo Wenbo Wu Junjie Shen Meifang 作者单位：李貅,Li Xiu(西安通大学电子与信息工程学院,陕西,西安,710049;长安大学地质工程与测绘工程学院,陕西西安,710054)

薛国强,宋建平,郭文波,Xue Guoqiang,Song Jianping,Guo Wenbo(西安通大学电子与信息工程学院,陕西,西安,710049)

自适应信赖域算法篇3

关键词：无约束优化,信赖域方法,新锥模型,非单调技术,全局收敛性

考虑无约束优化问题

其中,f( x) ∶ R × R是二次连续可微的函数。对于求解问题式( 1) ,学者已提出很多的迭代方法,大致可以分为线性搜索方法和信赖域方法［1 －2］,线性搜索方法易于求出新的迭代点,而信赖域具有很强的收敛性和解决问题的有效性。信赖域的关键在于信赖域半径Dk的选取,传统的信赖域算法主要是利用二次模型来逼近目标函数,而信赖域的半径Dk的选取取决于模型函数和目标函数的拟合的结果,因此导致了信赖域半径的选取取决于真实下降量与预估下降量的比 γk,其中,当 γk越接近于1时,表明拟合程度越好,在下次迭代中信赖域半径可以适当的扩大; 相反,当 γk很小时表明拟合程度很差,信赖域半径应缩小。1982年为了解决在无约束优化问题中遇到的马太效应,Chamberlain et al.［3］放松了线性搜索的条件,提出将Watchdog技术用于解决约束优化问题,受到这个想法的启发,Grippo, Lamparillo和Lucidi［4］将非单调线性搜索应用于牛顿算法,通过实验可以看出,非单调性可以提高收敛速度和寻找全局最优解的可能性。Deng［5］第一次提出了将非单调技术运用于信赖域算法,自此众多学者将非单调引入到信赖域算法中,虽然这种算法得到了良好的结果, 但是由于此非单调技术也存在遗漏最优点和实验结果依赖于M的选取等缺点,为了克服这些缺点,Masoud Ahookhosh［6］在二次模型的基础上提出了一种新的非单调技术。实验表明了这种单调技术的有效性。

传统的信赖域方法所用的二次模型对于非二次性态强,曲率变化较为剧烈的函数,逼近的效果一般不佳,针对这一缺陷。1980年Davidon［7］提出了锥模型, 为了克服锥函数的可能无界性,之后倪勤［8］等提出了新锥模型信赖域子问题,去掉b必须满足1 - bTd > 0的限制,将新的可行集分成3种情形,由此可得到3种不同类型的锥模型信赖域子问题。

在上述基础之上本文提出了一种改进的非单调自适应的新锥模型信赖域算法,将一种新的非单调技术运用在新锥模型中,并加入了自适应技术和线性搜索技术。

1算法

1. 1新锥模型的子问题

新锥模型信赖域子问题将锥模型子问题

其中,W = B·S,B = { d∈Rn‖d‖ ≤ Δk} ,S = { d∈ Rn||1 - bkT|d ≥ε0} ,转化为以下3种情况进行讨论:

( 1) 当1 - ε0≥Δk‖bk‖时,子问题转换为

( 2) 当|1 - Δk‖bk‖< ε0时,子问题转换为

( 3) 当1 - ε0≤Δk‖bk‖时,子问题转换为

1. 2非单调技术

Masoud Ahookhosh［6］在二次模型的基础上提出了一种新的非单调技术

其中,Dk= ρkfk+ ( 1 - ρk) flk,flk= max { fk － j|0 ≤ f ≤ m( k) } ,m( k) = max{ m( k - 1) + 1,2M} ,运用非单调技术将比值 γk的制转换为

1. 3非单调自适应信赖域算法

Step0给定x0∈Rn,Δ0> 0,ε > 0,k = 0,p3,1,0 < c < 1,0 < u1< u < 1。

Step1计算gk,若‖gk‖≤ ε 则停止,否则转Step2。

Step2用折线法［10］求出该子问题的近似解dk。

Step3计算γk。

Step4若 γk≥u,则令xk + 1= xk+ dk,否则利用回溯线性搜索寻求满足f( xk+ αkidk) < f( xk) 的最小的正整数i,令xk + 1= αik dk+ xk。

Step5若γk≥u,则令Δk+1=max{B-1k+1·gk+1,4Δk};若γk≤u,令p=p+1,Δk+1=cpB-1k+1gk+1;否则,令Δk+1=Δk。

Step6 k = k +1,更新bk,Bk,若 ρk≥u,则令Mk + 1= M + 1,转Step1。

2收敛性的证明

假设:

H1序列{Bk},{bk}一致有界,即存在M>0,对

H2水平集L ( x0) = { x f( x) ≤f( x0) } 有界且f( x) 在水平集上二次连续可微且有下界。

H3 g( x) 在水平集上是Lipschitz连续的。

引理1［9］算法产生的点列xk满足

引理2算法产生的点列xk满足

引理3若假设H2成立,则数列{fl(k)}非增

证明由Dk,flk的定义,可以得到,

由式( 7) 可知本算法产生的迭代点满足

因此,得到

由m( k) 的定义易知m( k +1) ≤m( k) +1,从而

综上可知,序列fl( k)是单调递减的数列。

引理4算法产生的点列{ xk} 满足fk + 1≤Dk + 1且{ xk} 在水平集L( x0) 中

证明由fl( k)的定义可知fl( k + 1)≥fk + 1

显然,由Dk的定义可知D0= f0,由引理3可得

综上可知引理成立

推论1数列fl( k)收敛。

为了进一步的证明算法的收敛性假设存在c > 0使得dk满足

引理5［6］若以上假设都成立则算法产生的序列满足

推论2若以上假设都成立则算法产生的点列{ xk} 满足

证明由Dk的定义易知fk≤Dk≤fl( k)结合式( 15)可得

引理6若以上假设成立

证明易知算法产生的迭代点满足

将上式的k用l( k) -1来代替可得

由推论1可知

结合引理1中的式( 5) 可得

同理可得

由l'l( k)- k - 1≤M + 1,所以有

由f( x) 的连续性,可得

又由式fl( k)- f( xk + 1) ≥ - uφk( dk) ,两边取得极限可得

定理1算法产生的点列满足

证明反证法:若存在ε≥0和无限之列{ki}使得存在Δ>0,使得对于k∈K有,Δk≥Δ,由引理1可知这表明对k∈K,有相矛盾。

3数值试验

为说明算法的有效性,利用Matlab编写程序对本文算法进行数值测试,其中Nf,Ng分别表示函数值和梯度值的迭代次数; n表示问题的维数。测试问题如下:

例1 Penalty - I funtion

例2 Wood function

自适应信赖域算法篇4

现代信息与网络的开放性给数字媒体内容的安全问题带来了越来越大的隐患,使之成为业界的一大难题,制约着其进程。数字水印作为一项很有潜力的解决手段,最近几年成为了商业界和学术界共同关注的焦点,在多媒体信息的版权保护中发挥着重要作用[1,2,3]。到目前为止,数字水印从研究对象上看主要涉及图像水印、音频水印、图象水印、文本水印和三维网格数据水印等几个方面。其中大部分的水印研究和论文都集中在图像研究上,其原因在于图像是最基本的多媒体数据,且互联网的发展为图像水印的应用提供了直接大量的应用需求。而稳健性是数字水印算法的主要问题之一。根据视觉特点和信号特性实现水印分量的自适应嵌入是提高水印稳健性的有效途径[4]。本文利用人工智能原理自适应地寻找合适的图象部位和嵌入强度,提出了一种基于小波变换域的自适应图象水印算法。

2 现有的各种图象水印算法及其性能比较

对图像水印技术的研究根据水印嵌入时采用的变换形式可分为空间域水印技术和变换域水印技术。

将水印信息直接叠加到图象的空间域上的算法叫空域算法。即直接在原始图象数据中嵌入水印,嵌入的水印信号一般是添加在亮度分量上的,有时也有一部分或全部加入到颜色分量中[5]。此类方法的优点是:对载体的影响很小,计算速度快,隐藏的信息较多,适合多媒体。空间域的典型算法有最低有效位算法,Patchwork算法,纹理块映射编码算法等。

变换域算法也称频率域算法,是在原始图象的某个变换域中进行水印的嵌入和提取。指将原始图象进行某种图象变换处理后,选取某些特定的变换域系数,对这些系数的值进行修改来嵌入水印的方法。变换域算法可以嵌入大量比特的数据并且同时能保证较好的不可见性。常用的图象变换主要有三种,即离散余弦变换DCT,离散小波变换DWT,傅里叶变换FT或FFT。其优点是:可以嵌入大量的水印数据依然能保持较好的不可见性的,且对常用的压缩处理具有很好的鲁棒性。缺点是:其抵抗几何变换等攻击的能力较弱。

基于非线性理论的算法。其典型代表有基于分形图象编码的数字水印算法,基于混沌特性的数字水印算法;基于神经网络的数字水印算法等。

3 用于版权保护的图象水印要实现的关键技术

版权保护的目的有两方面的要求:保证图象载体可用;标志其产权所有人。为达到此两项要求,必须实现两大技术指标。

其一,实现水印的鲁棒性[6]。只有具有鲁棒性的水印才能抵抗一般的数字信号处理操作。如D/A转换,A/D转换,图象增强,有损压缩等。同时也能抵抗一般的几何处理操作如旋转、裁剪、缩放等。

其二,确保水印的透明性,此即不可见性。水印信息应不影响载体作品的使用价值和商品价值。

4 基于模糊推理的自适应水印嵌入强度的计算

根据人类视觉模型的相关理论,人眼对不同的灰度有不同的敏感性,对中等灰度最为敏感,且向低灰度和高灰度方向非线性下降[7]。为了实现水印鲁棒性和不可见性的最佳平衡,可以对低频带小波系数进行L×L分块,然后计算每一图象块的均值、方差、纹理、边缘等特征值,并通过模糊推理计算出每一块的嵌入强度,从而实现自适应的嵌入水印。

gij表像素(i,j)的灰度值。

将经过量化后的Bk和Ek作为模糊控制器的输入,水印的嵌入强度Uk作为模糊控制器的输出。设计如下的模糊规则和模糊控制器。设Bk、Ek、Uk的语言变量词集为{最小,小,中,大,最大},它们的录属函数均取为高斯函数。

规则1:if e=最大and c=最大,then u=最大

规则2:if e=最大and c=大,then u=大;

……

规则25:if e=最小and c=最小,then u=最小;

最后使用录属度函数加权平均判决法[8],由模糊控制器的输出Uk计算出每一个图象块的实际嵌入强度。

5 一种新的自适应图象水印算法

对图象二维小波系数的分布特点和振幅进行定性定量分析,可以得到以下结论:水印嵌入在低频子带系数中,可以获得较好的稳健性[8]。为了在保证不可见性的前提下尽可能提高水印分量的强度,本文提出将低频子带中的小波系数进行分块,根据各图象块的特征,自适应地调整嵌入水印的强度。

1)水印信息预处理

为使加载了水印的图象能具有抗剪切能力,将原始水印信息W进行置乱,再将置乱后的水印信息W'嵌入到原始图象中。在此,采用简单直观的Arnold变换对水印置乱。假设大小为N*N的水印图象的像素坐标为x,y∈{0,1,2…,N-1}。设(x,y)T为输入,(x',y')T为输出,则Arnold变换为:

迭代公式如下:

上式中A为变换矩阵,n代表迭代的次数。由于N*N个像素所能表现的图象是有限的,因此迭代过程呈周期性。通过离散点集的置换,同时把图象信息的值进行移动,当遍历原图象所有的点之后,便产生了一幅新的混乱不堪的图象,此即经过加密的水印信息W'。

将置乱后的水印图象{0,1}值转换为{-1,1}系列,以增强嵌入水印后图象的统计不可觉察性,转换方法如下:

对转换后的mi,通过二值伪随机序列进行调制,得到水印序列

2)水印嵌入方案:

对原始图像进行三级小波分解后,其低频分量LL3是对原图象的近似,所以在该频段中所加入的水印具有较强的鲁棒性。但人眼对于低频分量加入水印的敏感性要远高于对高频分量加入信息。另一方面,由图象压缩知识可知,在高频段加入的水印在图象进行有损压缩的操作中较易被丢失。综合以上考虑,本文算法选有

实际意义的二值图象作为水印信息,为了使水印信息与原始图象的纹理特征相适应,这里引用了人类视觉模型,采用模糊控制器计算出不同的小波块对应的嵌入强度。

嵌入过程如下:

第一步:读入原始图象I(大小为M*M)和水印图象W(大小为N×N),对初始水印进行置乱得到最终待插入的水印序列。

第二步:对原始图象进行三级小波分解,并将低频系数LL3分成大小为L×L的小波块,计算出各小波块的特征值,设计模糊控制器,并据其输出即得出各小波块的水印嵌入强度

第三步:通过修改小波块的平均值,将水印信息嵌入到各小波块的平均值中,从而实现将水印嵌入到低频子带LL3中。

其中α为嵌入尺度因子,其值根据实验经验取为0.5。T(k)为第K个小波块对应的嵌入强度。循环使用式(1),直至将所有的水印信息嵌入止,即得到嵌入水印后的系数。

第四步:重构并显示嵌入水印后的图象。通过对嵌入水印后的系数进行小波反变换[9],即可获得加水印后的图象。

3)水印的检测和提取:

本算法水印是嵌入在图像小波域低频子带的系数上,但水印嵌入后,改变了原图像的能量分布。因此提取时要采用相同级数的小波分解。由于使用的是有意义的水印图象,提取出的水印很容易辨认出来,不需要进行检测。具体提取过程如下:

1)对含水印图象进行3层小波逆变换;

2)水印提取。按照嵌入的方法选择小波低频系数,并根据下式来重构水印图象序列:

3)得出水印图象后,通过解调,再对提取的水印序列进行Arnold反变换,即得到最终的水印图象。

6 实验结果及性能分析

本文对实验结果进行仿真,采用标准的测试图象LENA(512×512)进行测试。水印信息为一个二值图像,大小为32×32(如下图)。

1)透明性评估:

含水印图象的透明性是通过PSNR来评估的[10],计算得到的载体图像与含水印图像峰值信噪比270.3743dB。为了能更好地说明算法的性能。从视觉效果来看,即使和原始图象放在一起比较,仅凭肉眼也感觉不到水印的存在。可见,算法保证了嵌入过程中水印透明性的基本要求。

2)鲁棒性评估:

对鲁棒性的评估是通过对含水印图象进行各种不同类型的攻击,提取出攻击后的水印图象并与原始的水印图象进行相似性评估来实现的。相似性通过归一化均方差(NMSE)来实现。检测出的水印图像W*与原水印图像W进行比较,W*与W的相似度可通过归一化相关系数NC[11]比较,如表1所示。

上述实验以MATLAB为工具[11],仿真实验结果表明:嵌入水印对多种攻击,如加性Gaussian噪声、高压缩比的MPEG-2压缩编码等具有很好的鲁棒性。

6 结束语

本文主要研究了用于版权保护的图象水印技术,提出了一种新的基于小波变换的非盲提取的自适应图象水印算法。实验表明,算法具有较好的不可见性和安全性,可用于图象媒体的版权保护领域。这种方案除了对传统攻击具有教好的鲁棒性,也能很好地抵抗一般的几何攻击。下一步的工作是:进一步改善算法,使其对于旋转等几何攻击具有更好的鲁棒性并推测出所经历的几何攻击的具体类别及相关参数。

参考文献

[1]Jason R.Kaufman.Digital Video Watermarking Using Singular Value Decomposition And Two-dimensional Principal Component Anal-ysis[J].the master of sciece degree paper.2006

[2]William Kordsmeier;Rebecca Gatlin-Watts;Joseph V.Arn.University Administrators'Understanding of Multimedia Copyright Guidelines[J],Educational Technology&Society,2000,3(1):112-118

[3]Judy NAGY;Chris BIGUM.BOUNDED AND UNBOUNDED KNOWLEDGE:Teaching and Learning in a Web2world[J],The Turk-ish Online Journal of Distance Education,2007,8(3):76-86

[4]COX I J,MILLER M I.The first50years of electronic watermarking[J].Journal of Applied Signal Processing,2002,56(2):126—132.

[5]高倩,周丽娟.图像及视频版权保护中的数字水印设计[J].科学技术与工程,2007,7(11).

[6]兰红星,陈松乔,胡爱娜,等.基于小波域的第二代数字水印算法的研究[J].电子学报,2007,35(9).

[7]刘伟灵.模糊自适应的彩色图像数字水印算法[J],计算机应用研究,2007,10。

[8]李士勇.模糊控制.神经控制和智能控制论[M].哈尔滨:哈尔滨工业大学出版社,1998.

[9]金聪.数字水印理论与技术[M].北京:清华大学出版社,2008.

[10]侯祥勇.一种灰度水印的自适应鲁棒算法[J].重庆师范大学学报(自然科学版),2006,2.

自适应信赖域算法篇5

1 Arnold变换[1]

Arnold是在遍历理论研究中提出的一种变换。数字图像经常使用的是二维Arnold变换。二维Arnold变换可以有如下表示:

其中x,y∈(0,1,2…,n-1),(x,y)表示某像素点在原矩阵中的坐标,表示该点变换后的坐标,N是图像矩阵的阶数。

2 DCT变换

离散余弦变换DCT(Discrete Cosine Transform),是一种实数域上的研究信号的频谱方法。根据DCT系数的自相关性还可以减少信息的冗余,达到压缩的目的。目前DCT变换已经在图像压缩编码和一系列视频压缩编码中得到广泛的应用。

二维DCT定义如下:设f(x,y)为M×N的数字图像矩阵,则

式中:x,u=0,1,2…M-1;y,v=0,1,2…N-1。

二维DCT逆变换定义如下:

式中:x,u=0,1,2…M-1;y,v=0,1,2…N-1。

3 数字水印的嵌入

首先对水印图像进行Arnold置乱,置乱后的图像进行4×4分块,对各分块进行DCT变换。对原始图像提取绿色分量[2],8×8分块进行DCT变换,对每一块计算平均灰度和方差[3]。平均灰度和方差值的计算公式分别为

按方差值从大到小排序,选取前4倍的水印分块个数。对这些分块,根据人类视觉特性公式计算分块的自适应嵌入系数[4]。

最后按照嵌入公式修改原始图像的绿色分量的DCT系数,把水印图像插入其中。插入时采取一份水印系数嵌入到4份载体图像的中频系数中[1]。再对各分块进行反DCT变换,8×8分块重组,再把绿色分量合到原始图像中,就得到了嵌入水印后的图像。

4 数字水印的提取

分别对原始图像和嵌入水印后的载体图像进行通道分离,提取绿色分量。进行8×8分块DCT变换。逐个对分块计算其平均灰度和方差,并按方差值的大小排序。选取前4倍的水印分块个数。对这些分块,根据人类视觉特性公式计算分块的自适应嵌入系数。根据水印嵌入的位置分别对原始图像和含有水印的载体图像分块,提取相应的中频系数,通过公式对水印进行提取计算。按照嵌入过程的逆过程,从4个载体图像分块中提取出4个水印分块信息,对这4个水印分块信息求平均值后得到最终的水印分块信息Gw(u,v)。对水印分块信息进行4×4分块反DCT变换,然后进行Arnold反置乱最后得水印图像。

5 算法实验与分析

本算法原始图像选用了24位彩色的大小为512×512的lena图像如图1所示,原始水印图像选用了大小为64×64的二值图像如图2所示。对原始水印图像进行Arnold置乱后的如图3所示。把水印信息嵌入到原始图像后如图4所示,用肉眼从图像上看不出有什么变化。

本算法采用了峰值信噪比来作为图像水印嵌入前后质量的差异,用归一化相关系数来客观的说明提取出来的水印和嵌入的原始水印之间的相似程度。

峰值信噪比公式和归一化相关系数公式分别如下:

数字水印最主要的应用方面就是版权保护,用于该方面的水印应该具有很高的鲁棒性,对载体图像进行一般性的基本操作不能影响水印的检测提取。上述算法生成的水印,在对载体图像进行加噪、压缩、剪切等操作后,仍能从中提取出嵌入水印的大致轮廓。因此,该算法具有较好的鲁棒性。

摘要：改进了一种基于分块DCT域的数字水印算法,运用Arnold置乱方法对水印图像进行加密;彩色图像的绿色分量进行水印嵌入,根据DCT变换结果进行图像噪声的视觉敏感性分析。通过仿真实验结果表明,对常见的几种数字图像处理操作如剪切、添加噪声JPEG压缩、等有较好的鲁棒性。

关键词：数字水印,Arnold变换,DCT变换

参考文献

[1]黄西娟.一种DCT变换域的鲁棒数字水印[J].计算机工程,2011,(20):145-148.

[2]鲍昀霞,何东健.基于DCT的彩色图像水印算法.微电子学与计算机,2007,(1):91-93.

[3]包全磊.DCT域的图像数字水印算法[J].太原大学学报,2011,(45):117-119.

自适应信赖域算法篇6

随着Internet技术与多媒体技术的飞速发展,数字化信息以不同的形式在网络上方便、快捷地传输,在数字信息与网络给人们带来方便的同时,也给人们带来了隐患。因此,信息的安全与保密显得越来越重要,信息安全已经成为人们关心的焦点。由于小波理论本身的研究日趋完善,小波多尺度分析方法的应用愈来愈广泛,尤其是在信号和图像处理中良好的时频特性,使得小波域中的信息隐秘技术成为近年来的研究热点。文献[9]提出了一种在小波域通过纹理分析将图像划分成不同的区域,在不同的区域嵌入不同的比特数。文献[10]提出了一种基于混沌系统和遗传算法的JPEG图像中的密写方法,该方法将logistic的初值作为遗传染色体,图像峰值信噪比(PSNR)作为目标函数,利用基本遗传算法(SGA)对信息嵌入效果进行优化。

本文提出了一种基于模糊C-均值图像分类和自适应遗传算法的信息隐藏算法。首先利用模糊C-均值对载体图像的Y分量小波低频系数进行纹理分析,将低频系数分成三类:平滑区、纹理区、边缘区,在不同的区域嵌入不同的信息量;然后将秘密图像转换成二进制比特流,利用logistic混沌映射对其进行置乱,将置乱后的比特流和待嵌入信息的比特流进行异或运算,统计相同比特位的个数。最后利用遗传算法对混沌置乱初值最优化,并将统计的比特位个数作为目标函数。本算法要求在小波变换及逆变换过程中不能丢失信息,否则会导致提取信息的丢失。所以采用第二代小波变换的整数形式,并且选择CDF(2.2)作为小波基。

1模糊C-均值聚类算法

模糊C-均值聚类FCM算法[11]是基于目标函数的模糊聚类算法理论中最完善、应用最为广泛的一种算法,其目标函数J(U,V)定义为:

$J (U, V) = \sum_{k = 1}^{n} \sum_{i = 1}^{c} (μ_{i k})^{m} (d_{i k})^{2}$ (1)

式中:U=[μik](i=1,2,…,c;k=1,2,…,n)为模糊聚类矩阵,V={v1,v2,…,vc}是c个聚类中心的集合,且vi∈Rp,m∈[2,∞]为加权指数,dik为第k个样本到第i类聚类中心的距离,定义如下:

(dik)2=‖xk-vi‖2=(xk-vi)T(xk-vi) (2)

式中:xk为数据样本,且xk∈Rp,T表示矩阵转置,‖·‖为范数,表示欧几里得距离。

聚类准则为求取J(U,V)的极小值min{J(U,V)},为了得到数据样本集合X的最佳模糊C划分,FCM聚类算法采用迭代优化方案来得到min{J(U,V)}:

1) 确定聚类数目c(2≤c≤n)与加权指数m(m∈[2,∞]);

2) 设置模糊聚类矩阵U的初始值U(l)=[μ $_{i k}^{(l)}$ ]令l=0;

3) 计算各类的聚类中心vi:

$v_{i} = \sum_{k = 1}^{n} (μ_{i k})^{m} x_{k} / \sum_{k = 1}^{n} (μ_{i k})^{m}$ (3)

4) 计算新的模糊聚类矩阵U(l)(l=l+1)。求Ik={i|1≤i≤c;dik=‖xk-vi‖=0}和 $\bar{Ι_{Κ}} = {1, 2, \dots, c} - Ι_{k}$ ,若Ik=ϕ,则:

$u_{i k} = 1 / \sum_{j = 1}^{c} (d_{i k} / d_{j k})^{2 / (m - 1)}$ (4)

否则,对所有 $i \in \bar{Ι_{k}} ‚$ 置μik=0,并取 $\sum_{i \in \bar{Ι_{k}}} μ_{i k} = 1$ 。

5) 若‖U(l-1)-U(l)D‖的值小于阈值,则停止;否则转至步3)。

2自适应遗传算法

遗传算法是模拟自然界生物进化过程的计算模型。它依据适者生存、优胜劣汰的进化原则对包含可能解的群体反复进行遗传操作,找出最优或近似最优解。应用于本文的遗传算法有如下6点描述:

(1) 编码编码是应用遗传算法时要解决的首要问题。本文采用二进制编码方法的变种格雷码编码方法对logistic混沌映射初值进行编码,格雷码编码方法的优点是可以克服二进制编码Hamming悬崖缺点,以及可以提高局部搜索能力。格雷码编码方式为:

${\begin{cases} x_{i} [k] = y_{i} [k] \oplus y_{i} [k + 1] k \in Ν 0 \leq k \leq n - 1 \\ x_{i} [k] = y_{i} [k] k = n \end{cases}$

(5)

其中:yi[yi(0),yi(1),…,yi(n)]为原二进制码;xi[xi(0),xi(1),…,xi(n)]为转换后的格雷码;⊕表示异或。

(2) 种群种群规模定为100,初始种群的染色体由随机产生。

(3) 遗传算子包括选择算子、交叉算子、变异算子。选择算子采用竞技选择法和最优保存策略相结合。竞技选则法通过相互竞争,优胜者成为下一代个体。最优保存策略可以使适应度最好的个体尽可能地保留到下一代群体中。交叉算子采用多点交叉和均匀交叉相结合的方式来实现。变异算子采用基本位变异算法实现。

(4) 自适应交叉率和变异率

标准遗传算法的交叉率和变异率是固定的。要为某个特定的优化问题设置好交叉率和变异率。算法需经过反复地实验且难以丰富种群中优良解的多样性。文献[3]提出了一种自适应遗传算法,对交叉算子和变异算子进行了优化。该方法对自适应交叉率及变异率调整曲线进行了非线性化。将个体的适应度与当代种群的平均适应度进行比较。结合最佳个体计算出该个体的交叉率及变异率,在种群演化中有效地保留了优秀个体的模式,增强了较差个体的变异能力,使算法能跳出局部最优解,克服早熟的缺点。该文献利用sigmoid函数设计出的交叉率及变异率的自适应调整公式[3]如下:

$Ρ_{c} = {\begin{matrix} \frac{Ρ_{c m a x} - Ρ_{c m i n}}{1 + \exp (A (\frac{2 (f^{'} - f_{a v g})}{f_{\max} - f_{a v g}}))} + Ρ_{c m i n} & f^{'} \geq f_{a v g} \\ Ρ_{c m a x} & f^{'} < f_{a v g} \end{matrix}$

(6)

$Ρ_{m} = {\begin{matrix} \frac{Ρ_{m m a x} - Ρ_{m m i n}}{1 + \exp (A (\frac{2 (f - f_{a v g})}{f_{\max} - f_{a v g}}))} + Ρ_{m m i n} & f \geq f_{a v g} \\ Ρ_{m m a x} & f < f_{a v g} \end{matrix}$

(7)

式中fmax表示种群的最大适应度;favg表示种群的平均适应度;f′表示参与交叉的两个个体中较大的适应度;f表示变异个体的适应度;Pcmax和Pcmin表示交叉率取值的上限和下限;Pmmax和Pmmin表示变异率取值的上限和下限;A=9.903438。

(5) 适应度函数 FCM模糊分类将载体图像Y分量小波低频系数分为3类:平滑区、纹理区、边缘区。根据图像特征,YCbCr空间Y分量与RGB空间的三分量具有相同的纹理特性,以及低频子带保留原始图像的主要信息,所以对Y分量的小波低频系数分类结果同样适用于对R、G、B分量的分类[9]。根据纹理掩蔽特性,平滑区每个系数嵌入1bit,嵌入位置第2bit位;边缘区嵌入2bit,嵌入位置第2、3bit位;纹理区嵌入3bit,嵌入位置第2、3、4bit位。利用logistic对秘密图像比特流进行混沌置乱,将置乱的结果和待嵌入信息的比特流进行异或运算,求出相同比特位的个数,不同的logistic初值可以得出不同的异或运算结果。将此结果作为适应度函数,利用自适应遗传算法寻找最优的logistic初值。

(6) 终止条件循环的终止条件是设定最大终止代数,本文设定100代,满足条件则终止循环。

3算法实现

3.1载体图像直方图调整

在小波域进行图像数据嵌入时,对小波系数的改变容易使逆变换后的灰度发生“溢出”,需对载体图像直方图进行调整。根据本文所选载体图像Lena,Tree的直方图可知:图像的像素值主要集中在直方图的中部,两侧边缘像素值个数偏少。基于这样的特点,本文采用的方法使得原始图像灰度值的取值范围从[0,255]调整为[11,244],避免“溢出”发生,同时对图像的失真可以降到最小。具体介绍如下:

在像素值区间[0,22],将像素值为21的像素全部加1,像素值变为22,然后将像素值为20的像素全部加1,最后将像素值为0的像素全部加1,第一轮过后,像素值为0的像素个数为0;第二轮将[1,21]按照同样的方法,使像素值为1的像素个数为0。经过十一轮的移动,像素值区间[0,10]的像素个数为0,达到了像素值调整的目的。在像素值区间[233,255]上采用同样的方法最终使得像素值区间[245,255]的像素个数为0。

3.2图像分类和信息嵌入与提取

本文利用信息熵、变异系数对Y分量小波低频系数进行纹理分析:首先利用信息熵、变异系数计算出每个系数块(3×3)所包含的信息量和波动程度,得到信息熵矩阵和变异系数矩阵;然后将信息熵矩阵利用FCM划分成两类:平滑区和非平滑区;再将变异系数矩阵利用FCM划分为两类;属于非平滑区同时又属于变异系数第一类的图像块划分为纹理区,变异系数第二类划分为边缘区。

(1) 信息熵定义[9]

$Η = - \sum_{j = 1}^{Ν} Ρ (a_{j}) \times \log_{2} Ρ (a_{j})$ (8)

其中,N表示图像块不同像素个数,P(aj)表示不同像素aj出现的概率。

(2) 方差及变异系数定义[9]

$v a r = \sum_{x, y = 1}^{n} \frac{(f (x, y) - \bar{f})^{2}}{n - 1}$ (9)

$c = \frac{v a r}{\bar{F}}$ (10)

其中, $\bar{f} = \frac{1}{n} \sum_{x, y = 1}^{n} f (x, y), n$ 为图像块像素个数(n等于9),f(x,y)为像素灰度值, $\bar{F}$ 是图像的平均灰度值。

图1为载体图像Lean的Y分量小波低频系数分类结果。

图2为logistic混沌映射初值利用遗传算法寻优流程图。

图3为信息嵌入流程图。

提取过程是嵌入过程的逆过程,这里不再阐述。

4仿真结果与分析

为了验证本文所提出的彩色信息隐藏算法的有效性,以下采用258×258×3bits标准彩色图像Lena,Tree为载体图像;64×64×3bits彩色图像Boy为秘密图像,单分量共计32768bit;并与文献[9]进行了对比。实验中,载体图像分类图像子块大小(n1×n2)选取为3×3。同时本文采用峰值信噪比(PSNR)评价原始载体图像与载密图像之间的差别。载体图像和秘密图像如图4所示。

文献[9]依据纹理特性,采用阈值分类方法将载体图像分为3类,阈值分类方法人为地确定阈值对图像进行划分,不同的阈值可以得到不同的嵌入强度,但未考虑图像本身的特点,阈值y1=2.8,y2=7。而本文采用模糊C-均值进行无监督分类。表1为分类情况及嵌入量统计对比。

表2列出秘密图像R,G,B三分量混沌映射分别采用的最优初值,以及由此得到的适应度函数值等。图5给出载体图像Lean和载密图像Lean的对比;图6是给出秘密图像和恢复图像的对比,由于算法的特点,提取出的秘密图像可以达到错误率(BER)为零。本文利用峰值信噪比(PSNR)对载体图像和载密图像进行客观分析,显示出载体图像与载密图像差别大小。

根据信息嵌入结果进行对比:首先,文献[9]采用的直方图调整方法将像素取值范围[0,255]调整为[10,245],且每个像素都有相应的变化,所以图像的失真相对明显;而本文根据图像本身特点,将像素取值范围[0,255]调整为[11,244],且只有高亮度和低亮度值的像素发生变化,相对来说对图像的变化不是很明显。其次,文献[9]]采用的图像分割方法可以人为地控制图像块的特性,即:y1过小,可以使本属于非平滑区的图像块进入平滑区当中;过大,又可以使本属于平滑区的图像块进入非平滑区当中;y2也是如此。所以这样的分类未考虑图像的特征,势必会影响载密图像的质量。最后,文献[9]在信息嵌入时,只是用秘密图像的比特流替换载体图像待嵌入信息的比特流,没有考虑比特流的相似度。假如比特流1为(010),比特流2为(101),这样的替换会造成3个比特全部改变。而本文利用自适应遗传算法最优化logistic映射初值,使得经过混沌映射的秘密图像比特流可以和载体图像待嵌入信息的比特流有更大的相似度,所以才会使信息嵌入对图像的影响较小。从上面的结果中也可以看出:不管是Lean还是Tree纹理图像,在相同嵌入量的情况下,本文算法的嵌入效果都比文献[9]要好,有更好的隐蔽性。

5结语

本文依据人类视觉纹理掩蔽特性,即:人类对图像的纹理区域最不敏感,边缘区域次之,平滑区域最敏感,利用FCM将图像分成3类,不同区域嵌入不同的比特量,然后利用logistic混沌映射对秘密图像比特流进行混沌置乱,将经过置乱的比特流和载体图像待嵌入信息的比特流进行异或运算,统计相同比特位的个数作为遗传算法的适应度函数;最后利用自适应遗传算法对置乱初值进行寻优。该方法的特点是:(1) 利用FCM通过信息熵和变异系数对图像进行分类,分类结果由图像本身的特性决定;(2) logistic混沌映射和自适应遗传算法相结合,既保证了秘密图像的秘密性,也使得信息嵌入对载体图像的影响进一步减小。实验结果表明:本算法不仅具有较好的隐蔽性,而且在嵌入量方面也有了很大的提高。

摘要：基于人类视觉系统的纹理掩蔽特性,提出一种基于模糊C-均值(FCM)和自适应遗传算法小波域彩色信息隐藏算法。首先对彩色载体图像Y分量实施整数小波变换;然后结合视觉纹理特性,对低频进行FCM聚类分析,将其分成3类:平滑区、纹理区、边缘区,并在不同的区域确定不同的嵌入强度和位置;最后,利用自适应遗传算法对logistic混沌映射的初值进行寻优,使其找到合适的初值,从而使秘密图像对载体图像的影响较小。实验结果表明:该方法不仅具有较好的透明性,而且在嵌入量方面也有很大的提高。

关键词：模糊C-均值,遗传算法,logistic置乱,纹理分析,信息隐藏

参考文献

[1]张定会,潘永华,张兴华,等.彩色数字图像的混沌加密和解密方法研究[J].通信技术,2009,42(01):245-247.

[2]董敏,王向阳.基于模糊聚类的小波域数字图像水印算法[J].计算机应用研究,2007,24(06):94-96.

[3]邝航字,金晶,苏勇.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用,2006,42(12):93-96.

[4]王向阳,养红颖,赵红,等.基于模糊聚类分析的自适应图像空间域水印技术[J].小型微型计算机系统,2005,26(07):1255-1259.

[5]张玉芳,罗俊玮,熊忠阳.基于模糊C均值算法的类合并聚类算法研究[J].计算机工程与应用,2009,45(24):122-124.

[6]Weiche Chen,Mingshi Wang.A fuzzy c-means clustering-based fragilewatermarking scheme for image authentication[J].Expert Systems withApplications,2009,36(02):1300-1307.

[7]Ranzan Wang,Chifang Lin,Jachen Lin.Image hiding by optimal LSBsubstitution and genetic algorithm[J].Pattern Recognition,2001,34(03):671-683.

[8]Xiangyang Wang,Juan Bu.A fast and robust image segmentation usingFCM with spatial information[J].Digital Signal Processing,2010,20(4):1173-1182.

[9]王媛媛,俞一彪.基于小波域纹理分析的图像自适应信息隐藏[D].苏州:苏州大学,2008.

[10]李婷.JPEG图像中数字密写技术的研究[D].北京:北京交通大学,2008.

自适应信赖域算法篇7

随着中国经济的快速协调发展,电力工业快速发展,电网规模也得到快速扩张,电网架构、输电方式等都发生了巨大的变化。由于受输电走廊通道资源等因素的制约,为了提高线路单位走廊的输电容量和土地利用率,降低电力建设成本,发展同杆多回线输电方式已成为必然趋势。目前,东北、华东和广东电网都已建设了500 kV/220 kV同杆四回输电线路。其中,2006年国内首条500 kV同杆四回输电线路——利港电厂至梅里变输电线路顺利投运。

输电线路故障的准确测距对于减少停电检修时间、提高电网输供电可靠性具有重大意义。迄今为止,针对同杆双回线故障测距的研究较多[1,2,3,4],关于同杆四回线故障测距的研究较为缺乏,据目前所知,仅有文献[5,6]提出了相关的故障测距方法。文献[5]提出基于12序分量法实现解耦的同杆四回线故障测距频域方法,由于该方法建立在集中参数模型的基础上,没有考虑线路的分布电容,当线路较长时,对故障测距精度有较大的影响;文献[6]提出基于单端电气量的同塔四回线故障测距方法,利用故障状态各回线路序电压的内在联系建立方程,消除了过渡电阻对测距的影响,然而当线路近末端发生故障时,该算法存在较大的原理性误差。另外,高压输电线路在实际运行中受沿线地质、气候等因素变化的影响,线路参数时常发生改变而偏离原有的实测值,不准确的线路参数将给故障测距带来较大误差。因此,同杆四回线故障测距的研究必须考虑线路参数的多变性影响。因此,对同杆四回线故障测距算法仍需进一步深入研究。

本文提出适应于同杆四回线故障测距的模变换分析方法和自适应的双端故障测距频域算法。

1 同杆四回线相模变换

同杆四回线阻抗模型如图1所示。

同杆四回线电压和电流的矩阵形式为:

$U_{Ρ} = Ζ Ι_{Ρ} (1)$

式中:

$\dot{U}_{Ⅰ A}, \dot{U}_{Ⅰ B}, \dot{U}_{Ⅰ C}, \dot{U}_{Ⅱ A}, \dot{U}_{Ⅱ B}, \dot{U}_{Ⅱ C}, \dot{U}_{Ⅲ A}, \dot{U}_{Ⅲ B}, \dot{U}_{Ⅲ C}, \dot{U}_{Ⅳ A}, \dot{U}_{Ⅳ B}, \dot{U}_{Ⅳ C}, \dot{Ι}_{Ⅰ A}, \dot{Ι}_{Ⅰ B}, \dot{Ι}_{Ⅰ C}, \dot{Ι}_{Ⅱ A}, \dot{Ι}_{Ⅱ B}, \dot{Ι}_{Ⅱ C} ‚ \dot{Ι}_{Ⅲ A}, \dot{Ι}_{Ⅲ B}, \dot{Ι}_{Ⅲ C}, \dot{Ι}_{Ⅳ A}, \dot{Ι}_{Ⅳ B}, \dot{Ι}_{Ⅳ C}$ 分别为各回线的A,B,C三相电压和电流;ZS为各回线每相的自阻抗;ZM为各回线相间的互阻抗;ZXM1和ZXM2分别为相邻回线的线间阻抗和非相邻回线的线间阻抗。

对于存在互感的同杆四回线,可将其电流分解为对称的e序分量、f序分量、g序分量和h序分量,如图2所示。

由于每序分量电流在其他三序分量回路中产生的感应电动势相互抵消,因此消除了各回路之间的互感[7],其变换矩阵可为:

$Ρ = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - j & - 1 & j \\ 1 & - 1 & 1 & - 1 \\ 1 & j & - 1 & - j \end{matrix} 〗$

由P矩阵与对称分量矩阵结合,可得同杆四回线模变换矩阵T为(其中a=ej120°):

$Τ = \frac{1}{12} [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & j & j & j & - 1 & - 1 & - 1 & - j & - j & - j \\ 1 & 1 & 1 & - 1 & - 1 & - 1 & 1 & 1 & 1 & - 1 & - 1 & - 1 \\ 1 & 1 & 1 & - j & - j & - j & - 1 & - 1 & - 1 & j & j & j \\ 1 & a & a^{2} & 1 & a & a^{2} & 1 & a & a^{2} & 1 & a & a^{2} \\ 1 & a & a^{2} & j & j a & j a^{2} & - 1 & - a & - a^{2} & - j & - j a & - j a^{2} \\ 1 & a & a^{2} & - 1 & - a & - a^{2} & 1 & a & a^{2} & - 1 & - a & - a^{2} \\ 1 & a & a^{2} & - j & - j a & - j a^{2} & - 1 & - a & - a^{2} & j & j a & j a^{2} \\ 1 & a^{2} & a & 1 & a^{2} & a & 1 & a^{2} & a & 1 & a^{2} & a \\ 1 & a^{2} & a & j & j a^{2} & j a & - 1 & - a^{2} & - a & - j & - j a^{2} & - j a \\ 1 & a^{2} & a & - 1 & - a^{2} & - a & 1 & a^{2} & a & - 1 & - a^{2} & - a \\ 1 & a^{2} & a & - j & - j a^{2} & - j a & - 1 & - a^{2} & - a & j & j a^{2} & j a \end{matrix} 〗 (2)$

利用该矩阵,可得同杆四回线路上任意一点的电流和电压相分量与序分量的关系为:

${\begin{cases} Ι_{m} = Τ Ι_{Ρ} \\ U_{m} = Τ U_{Ρ} \end{cases} (3)$

式中:

$\dot{Ι}_{e_{0}}, \dot{Ι}_{f_{0}}, \dot{Ι}_{g_{0}}, \dot{Ι}_{h_{0}}, \dot{Ι}_{e_{1}}, \dot{Ι}_{f_{1}}, \dot{Ι}_{g_{1}}, \dot{Ι}_{h_{1}}, \dot{Ι}_{e_{2}}, \dot{Ι}_{f_{2}}, \dot{Ι}_{g_{2}}, \dot{Ι}_{h_{2}}, \dot{U}_{e_{0}}, \dot{U}_{f_{0}}, \dot{U}_{g_{0}}, \dot{U}_{h_{0}}, \dot{U}_{e_{1}}, \dot{U}_{f_{1}}, \dot{U}_{g_{1}}, \dot{U}_{h_{1}}, \dot{U}_{e_{2}}, \dot{U}_{f_{2}}, \dot{U}_{g_{2}}, \dot{U}_{h_{2}}$ 分别为同杆四回线序电流分量、序电压分量;下标e0,e1,e2表示零、正、负序;下标f0,f1,f2,g0,g1,g2,h0,h1,h2表示各环流模分量的零、正、负序。

根据对各序分量的分析,e序分量其序电流除了流经同杆四回线,还流经线路外系统;f,g,h序分量电流只流经线路而不流经外系统,即当发生故障时同杆四回线的负荷电流对环流模分量没有影响[7]。

因此,本文可利用所提出的同杆四回线模变换分析方法,对线路两端的电压和电流信息进行相模变换,提取各环流模分量,以实现故障分析与计算。

2 线路参数自适应故障测距方程

图3为一同杆四回线故障模型,线路全长为l,故障发生在距离M端d处。利用线路两端的相电压及相电流的同步采样值uM(k),uN(k),iM(k),iN(k),基于全波傅里叶算法提取相应的工频相电压相量 $\dot{U}_{Μ Ρ}$ 和 $\dot{U}_{Ν Ρ}$ 以及相电流相量 $\dot{Ι}_{Μ Ρ}$ 和 $\dot{Ι}_{Ν Ρ}$ ,应用式(3)将相分量电压和电流转化为序分量电压 $\dot{U}_{Μ i}$ 和 $\dot{U}_{Ν i}$ 以及序分量电流 $\dot{Ι}_{Μ i}$ 和 $\dot{Ι}_{Ν i}$ 。在此基础上,仅利用f1,f2,g1,g2,h1,h2环流模分量,即i取 f1,f2,g1,g2,h1,h2,构建基于环流模分量的故障测距频域观测方程。

基于长线方程,分别利用线路M端和N端电压与电流的基频环流模分量,推算出故障点处的相应基频环流模电压分量 $\dot{U}_{Μ f i}, \dot{U}_{Ν f i} (i = f_{1}, f_{2}, g_{1}, g_{2}, h_{1}, h_{2})$ 为:

${\begin{cases} \dot{U}_{Μ f i} (d, γ_{i}, Ζ_{C i}) = \dot{U}_{Μ i} \cosh (γ_{i} d) - \dot{Ι}_{Μ i} Ζ_{C i} \sinh (γ_{i} d) \\ \dot{U}_{Ν f i} (l - d, γ_{i}, Ζ_{C i}) = \dot{U}_{Ν i} \cosh (γ_{i} (l - d)) - \\ \dot{Ι}_{Ν i} Ζ_{C i} \sinh (γ_{i} (l - d)) \end{cases} (4)$

式中:γi为各环流模分量的传播系数;ZCi为各模量波阻抗。

利用 $\dot{U}_{Μ f i} (d, γ_{i}, Ζ_{C i}) = \dot{U}_{Ν f i} (l - d, γ_{i}, Ζ_{C i})$ 的关系,则可构建d,γi和ZCi为待观察量的故障测距方程:

$\begin{array}{l} f_{L o c a, i} (d, γ_{i}, Ζ_{C i}) = \dot{U}_{Μ f i} (d, γ_{i}, Ζ_{C i}) - \\ \dot{U}_{Ν f i} (1 - d, γ_{i}, Ζ_{C i}) = 0 (5) \end{array}$

式中:i=f1,f2,g1,g2,h1,h2。

式(5)中γi和ZCi包含实部与虚部的复数未知量γi,real,γi,imag,ZCi,real和ZCi,imag,且各环流模分量的参数各不相等,故式(5)的未知量实际为13个,将式(5)的实部与虚部联合构建故障测距观测方程,其方程个数仅为12,不足以求解方程中的待求量。而且若对该多维非线性方程进行求解,通常较难保证方程解的精度以及故障测距的准确性。为此,本文提出一种利用故障前电压和电流冗余信息的线路参数自适应原理,避开故障初期暂态电压和电流信息的不稳定性,提高线路参数自适应的准确性。

3 自适应频域观测方程及故障测距方程

利用同杆四回线发生故障前两端的正常稳态运行电压和电流冗余信息,以及全波傅里叶算法提取各回线各相的工频电压和电流相量,然后采用同杆四回线模变换分析方法对电压和电流相分量进行解耦处理,提取各环流模分量的电压和电流,基于长线方程,可得从M端的i模电压和电流相量 $\dot{U}_{n o r m, Μ i}, \dot{Ι}_{n o r m, Μ i}$ 推算至N端相应的i模电压相量 $\dot{U}_{n o r m, Ν i}$ 为:

$\dot{U}_{n o r m, Ν i} = \dot{U}_{n o r m, Μ i} \cosh (γ_{i} l) - \dot{Ι}_{n o r m, Μ i} Ζ_{C i} \sinh (γ_{i} l) (6)$

类似地,从N端的i模电压和电流相量 $\dot{U}_{n o r m, Ν i}, \dot{Ι}_{n o r m, Ν i}$ 推算至M端相应的模电压相量 $\dot{U}_{n o r m, Μ i}$ 为:

$\dot{U}_{n o r m, Μ i} = \dot{U}_{n o r m, Ν i} \cosh (γ_{i} l) - \dot{Ι}_{n o r m, Ν i} Ζ_{C i} \sinh (γ_{i} l) (7)$

在式(6)和式(7)中,各环流模分量的表达式之间相互独立,以i模分量为例,可分别取式(6)和式(7)的实部与虚部,构建含γi,real,γi,imag,ZCi,real,ZCi,imag为待观测量的线路i模分量参数自适应频域观测方程:

${\begin{cases} Re f_{a d a p, Μ i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = 0 \\ Re f_{a d a p, Μ i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = 0 \\ Ι m f_{a d a p, Ν i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = 0 \\ Ι m f_{a d a p, Ν i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = 0 \end{cases} (8)$

式中:

$\begin{array}{l} f_{a d a p, Μ i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = \\ \dot{U}_{n o r m, Μ i} \cosh (γ_{i} l) - \dot{Ι}_{n o r m, Μ i} Ζ_{C i} \sinh (γ_{i} l) - \dot{U}_{n o r m, Ν i} \\ f_{a d a p, Ν i} (γ_{i, r e a l}, γ_{i, i m a g}, Ζ_{C i, r e a l}, Ζ_{C i, i m a g}) = \\ \dot{U}_{n o r m, Ν i} \cosh (γ_{i} l) - \dot{Ι}_{n o r m, Ν i} Ζ_{C i} \sinh (γ_{i} l) - \dot{U}_{n o r m, Μ i} \end{array}$

此参数自适应观测方程待观测量为4,方程数为4,满足方程求解的要求,可利用最小二乘法进行求解。未知量γi与ZCi以同杆四回线的设计参数为最小二乘迭代初值。由于线路的真实参数值是围绕其已知的设计参数附近变化的,故可采用最小二乘法求解方程(8),且迭代求解过程具有较好的收敛性,能够保证同杆四回线的线路参数自适应精度。

通过求解方程(8)即可实现线路各环流模分量参数的自适应,使其成为已知量。于是,利用全波傅里叶算法提取各相线的故障工频电压和电流相量,基于同杆四回线模变换分析方法实现两端故障电压和电流相分量的解耦,提取各环流模分量的故障电压和电流,利用式(5)构建仅含故障距离d为待观测量的同杆四回线频域故障测距观测方程:

式中:i=f1,f2,g1,g2,h1,h2。

此时,式(9)的待观测量个数仅为1,而由各环流模分量构成且分为实部和虚部的方程个数为12,因此,具有较高的冗余度,有利于准确求解方程的待观测量,即故障距离。

4 测距方程的求解

对于式(8)和式(9)的求解,涉及非线性方程求解问题。对于式(8),由于其待观测量为围绕同杆四回线的各环流模分量的模参数设计值变化,迭代初值若采用该设计值,则迭代初值较接近真实值。采用最小二乘法对式(8)进行求解,由于能够得到较接近真实值的迭代初值,故具有较好的收敛性和准确性。而对于式(9),虽然待观测量(即故障距离d)的变化范围为从0至线路全长l,由于其待观测量仅为1个,而方程数有12个,因此同样可采用最小二乘法进行求解,迭代初值可取l/2。若要避免最小二乘法的局部收敛问题,可参考文献[8],先采用具有较高全局收敛性的粒子群优化(PSO)算法对故障距离d进行粗略求解,以该解作为最小二乘法的迭代初值,再求最小二乘解。但由于本文重点不在于非线性方程的求解问题,故直接采用最小二乘法作为故障测距观测方程的求解方法。

5 仿真验证

为了验证本文所提出的同杆四回线故障测距算法的正确性和有效性,采用ATP/EMTP仿真软件,按照500 kV利港电厂至梅里变超高压全线同塔四回交流输电线路参数[9],构建同杆四回线模型,如图3所示。M端系统参数为:系统自阻抗ZS=j59.345 Ω,系统互阻抗ZM=j4.363 Ω,相电源EM=288.63∠-5° kV;N端系统阻抗参数为:系统自阻抗ZS=j67.256 Ω,系统互阻抗ZM=j7.259 Ω,相电源EM=288.63∠0° kV;线路采用JMarti模型,线路全长设为100 km。

表1列出了根据线路设计参数利用ATP/EMTP相关模块计算获得的线路参数设计计算值和自适应的线路参数值。表2列出了线路不同位置不同类型金属性短路的故障测距结果。由表2可得,在金属性故障情况下,故障测距的最大误差为0.044 5 km,相对误差为0.074 2%,可见本文所提出的测距方法具有较高的精度。

由于发生短路故障时通常在故障处具有过渡电阻,因此本文还进行了具有过渡电阻的故障仿真分析验证。设接地电阻为150 Ω,相间电阻为10 Ω,其测距结果见表3。由表3可见,当线路发生非金属性故障时,本文所提出的测距方法的最大误差为0.042 6 km,相对误差为0.071 0%。可见,过渡电阻对本文所提出的故障测距方法的影响很小,该方法具有很好的耐受过渡电阻能力。

注:ⅠAG表示Ⅰ回线A相接地故障;ⅡBG表示Ⅱ回线B相接地故障;ⅠBCG表示Ⅰ回线B和C相接地故障;其余类推。

6 结语

本文所提出的模变换分析方法,解决了同杆四回线之间的复杂耦合关系,实现了基于环流模分量的同杆四回线故障测距频域观测方程的构建。利用故障前的冗余电压和电流信息,消除线路参数不确定性,提高故障测距方程的冗余度,从而提高故障测距算法的精度。利用ATP/EMTP构建同杆四回线模型,通过故障仿真分析验证了本文所提出的故障测距算法的正确性。

摘要：为了消除同杆四回线相间和线间耦合问题及线路参数不确定性对同杆四回线故障测距的影响,提出了适应于同杆四回线故障测距的模变换分析方法。对同杆四回线的电压和电流信息进行解耦处理,提取不受系统阻抗影响的环流模分量,构建基于环流模分量的同杆四回线频域故障测距观测方程;为解决线路参数多变性影响,利用故障前冗余电压和电流信息,构建线路参数自适应的频域观测方程,以获得准确的线路环流模分量的基频参数,从而提出了一种同杆四回线参数自适应的双端故障测距频域算法。利用ATP/EMTP电磁暂态仿真软件,构建同杆四回线JMarti仿真模型,通过全面的仿真分析验证,证明所提出的测距方法能消除同杆四回线相间和线间耦合问题以及线路参数的不确定性影响,具有较高的故障测距精度。

关键词：故障测距,同杆四回线,相模变换,参数自适应

参考文献

[1]孙立山,张晓友,陈学允.平行双回线故障测距算法的研究.电力系统自动化,1999,23(5):28-30.SUN Lishan,ZHANG Xiaoyou,CHEN Xueyun.Research on a new fault location method for parallel transmission lines.Automation of Electric Power Systems,1999,23(5):28-30.

[2]全玉生,王晓蓉,杨敏中,等.工频双端故障测距算法的鲁棒性问题和新算法研究.电力系统自动化,2000,24(10):28-32.QUAN Yusheng,WANG Xiaorong,YANG Minzhong,et al.Two newalgorithms and their robustness for two-terminal fault location on HVtransmissionline.Automation of Electric Power Systems,2000,24(10):28-32.

[3]赵永娴,曹小拐,刘万顺.同杆并架双回线准确参数未知时的故障测距新算法.电力系统自动化,2005,29(4):72-76.ZHAO Yongxian,CAO Xiaoguai,LI U Wanshun.New fault location algorithm for double transmission lines on a same tower.Automation of Electric Power Systems,2005,29(4):72-76.

[4]龚震东,范春菊,郁惟镛,等.一种基于六序网图的同杆双回线故障测距算法.电力系统自动化,2007,31(17):58-63.GONG Zhendong,FAN Chunju,YU Weiyong,et al.A new fault location algorithmfor parallel transmission line based on six sequence network.Automation of Electric Power Systems,2007,31(17):58-63.

[5]龚震东,范春菊,田羽.一种适合于同杆4回线的故障测距方法.电力系统自动化,2007,31(23):70-73.GONG Zhendong,FAN Chunju,TI AN Yu.A fault location algorithm suitable for jointed four transmission lines.Automation of Electric Power Systems,2007,31(23):70-73.

[6]任明珠,邰能灵,袁成,等.基于单端量的同塔并架4回线路故障测距方法.上海交通大学学报,2009,43(8):1228-1232.REN Mingzhu,TAI Nengling,YUAN Cheng,et al.A new fault location algorithmfor jointed four transmission lines based on single-ended data.Journal of Shanghai Jiaotong University,2009,43(8):1228-1232.

[7]XU Peng,WANG Gang,LI Haifeng,et al.Anewphase-mode transformation method for fault analysis of four-parallel transmission lines//Proceedings of Power and Energy Systems Conference:AsiaPES,October12-14,2009,Beijing,China.

[8]梁远升,王钢,李海锋.基于粒子群—最小二乘混合算法的参数自适应故障测距方法.电力系统保护与控制,2009,37(4):16-22.LI ANG Yuansheng,WANG Gang,LI Haifeng.A parameter adaptive fault location scheme based on the combination of particle swarmopti mization algorithmandleast squares method.Power System Protection and Control,2009,37(4):16-22.

自适应信赖域算法篇8

对于无约束优化问题,信赖域算法是非常重要的算法。这类算法的收敛性分析已有许多成果。由于非单调算法比单调算法具有更好的收敛效果[1,2,3],近几年出现了许多非单调信赖域算法的研究。文献[4]首次将非单调技术引入到信赖域算法中,并提出了一个对无约束优化问题具有强收敛性的非单调信赖域算法。文献[5,6]对这一工作进行了进一步的研究,提出了无约束最优化的一类非单调信赖域算法,并证明了算法的全局收敛性和Q-二次收敛性。文献[7]在信赖域算法中引入了非单调线搜索技术。当试探步不成功时,并不重新求解子问题,而采用非单调线搜索,以得到下个迭代点,这样做大大减少了计算量。

但仍有一些问题没有解决,当选取的初始搜索点处于峡谷附近时,利用现有的信赖域算法搜索到的最优解可能是局部最优解。本文提出一类非单调信赖域算法,它是通过修正信赖域算法中的实际下降量,放宽信赖域半径的校正条件,从而放大信赖域半径,即而可能跳出峡谷,使搜索到最优解尽可能是全局最优解。

1 改进的信赖域算法

对于无约束优化问题 $\min_{x \in R^{n}} f (x)$ ,基本的信赖域算法如下,设xk为第k次迭代点,fk=f(xk), gk=ᐁf(xk),Bk为ᐁ2f(xk)的第k次近似,Δk是信赖域半径,则第k次迭代的子问题有如式(1)形式。

${\begin{cases} \min m_{k} (s) = f_{k} + g_{k}^{Τ} s + \frac{1}{2} s^{Τ} B_{k} s \\ s . t . ∥ s ∥ \leq Δ_{k} \end{cases} (1)$

求信赖域子问题式(1)的最优解和近似解dk,计算目标函数的实际下降量Aredk=fk-f(xk+sk)与预测下降量Predk=mk(0)-mk(sk)的比值ρk。如果ρk≥η1,其中η1∈(0,1), 则接受sk, xk+1 = xk+sk,信赖域半径增加或不变;否则信赖域半径减少,求新的sk和ρk。重复以上过程即可求得无约束优化问题的最优解。定义

$f_{l (k)} = \max_{0 \leq j \leq t (k)} {f (x_{k - j})} (2)$

式(2)中t(k)=min{t(k-1)+1,T},T是非负整数,t(0)=0。

下面给出一类新的非单调信赖域算法。对文献[6]算法中的第k次迭代步的实际下降量进行修改,在fl(k)的前面乘以一个参数αk。如果fl(k)≥0,则αk≥1;如果fl(k)<0,则αk<1。在迭代的过程中αk总是趋向于1的,即 $\lim_{k \to \infty} α_{k} = 1$ 。

对信赖域半径的调整依赖于Ared $_{l (k)}^{k}$ =αkfl(k)-f(xk+sk)与Predk的比值,若要求接受条件为ρ $_{l (k)}^{k}$ =Ared $_{l (k)}^{k}$ /Predk≥η1,就接受xk+1=xk+sk。算法步骤如下。

算法1

步1 选初值,取 $\bar{Δ} > 0$ 为信赖域半径上界, x0∈Rn,令 $Δ_{0} \in (0, \bar{Δ}] ‚ 0 < η_{1} < η_{2} < 1 ‚ 0 < r_{1} < 1 < r_{2} ‚ ε \geq 0 ‚ k = 0 ‚ Τ$ 为非负整数,αk满足。

步2 检验终止条件,计算gk,若‖gk‖≤ε,则x*=xk,算法终止。

步3 解子问题式(1),求得sk,利用式(2)求的fl(k)。

步4 计算ρ $_{l (k)}^{k}$ =Ared $_{l (k)}^{k}$ /Predk,其中

$\begin{array}{l} A r e d_{l (k)}^{k} = α_{k} f_{l (k)} - f (x_{k} + s_{k}) ‚ Ρ r e d_{k} = \\ m_{k} (0) - m_{k} (s_{k}) = - g_{k}^{Τ} s_{k} - \frac{1}{2} d_{k}^{Τ} B_{k} s_{k} 。 \end{array}$

步5 校正信赖域半径

$Δ_{k + 1} = {\begin{matrix} r_{1} Δ_{k}, & 如果 ρ_{l (k)}^{k} \leq η_{1} \\ \min (r_{2} Δ_{k}, \bar{Δ}), & 如果 ρ_{l (k)}^{k} \geq η_{2} \\ Δ_{k}, & 否则 \end{matrix} 。$

步6 若ρ $_{l (k)}^{k}$ >η1,则xk+1=xk+sk,否则xk+1=xk,k=k+1,转步2。

2 全局收敛性

作如下定义和假设。

定义1 定义水平集

L(x0)={x∈Rn|f(x)≤f(x0)}。

定义2 Cauchy位移s $_{k}^{c}$ 的表达式为:

$\begin{array}{l} s_{k}^{c} = \\ {\begin{matrix} - \frac{Δ_{k}}{∥ g_{k} ∥} g_{k}, & 如果 g_{k}^{Τ} B_{k} g_{k} \leq 0 \\ - \min {\frac{∥ g_{k} ∥^{2}}{g_{k}^{Τ} B_{k} g_{k}}, \frac{Δ_{k}}{∥ g_{k} ∥}} g_{k}, & 否则 \end{matrix} (3) \end{array}$

假设1 (i)水平集L(x0)是有界的, (ii){fk}是有下界。

引理1 Cauchy位移s $_{k}^{c}$ 带来的mk(s)的下降量(详见文献[8])。

$m_{k} (0) - m_{k} (s_{k}^{c}) \geq \frac{1}{2} ∥ g_{k} ∥ \min {Δ_{k}, \frac{∥ g_{k} ∥}{∥ B_{k} ∥}} (4)$

引理2 假定存在{1,2,…}的无穷子列N0,使得对任意k∈N0, ρk≥η1,则对所有的k∈N0有

$α_{k} f_{l (k)} - f_{k + 1} \geq \frac{1}{2} η_{1} ∥ g_{k} ∥ \min {Δ_{k}, \frac{∥ g_{k} ∥}{∥ B_{k} ∥}}$ (5)

$ρ_{l (k)}^{k} = \frac{α_{k} f_{l (k)} - f_{k + 1}}{Ρ r e d_{k}} \geq \frac{f_{k} - f_{k + 1}}{Ρ r e d_{k}} (6)$

引理3 有界数列必含有收敛子列。

定理1 设在算法1中ε=0,对任意的x0∈Rn,函数f(x)在水平集L(x0)上一阶连续可微。若存在β>0,使得对任意k,有‖Bk‖≤β,且式(1)的近似解sk满足式(5),则 $\lim_{k \to \infty} \inf ∥ g_{k} ∥ = 0$ 。

证明假设结论不成立,则存在ε0>0和正整数k0,使得对任意的k≥k0,有‖gk‖≥ε0。又因为存在β>0,使得对任意的k,有‖Bk‖≤β,则通过引理可以得到,对k≥k0, k∈N0有

$\begin{array}{l} Ρ r e d_{k} \geq \frac{1}{2} ε_{o} \min {Δ_{k}, \frac{ε_{0}}{β}} (7) \\ α_{k} f_{l (k)} - f_{k + 1} \geq \frac{1}{2} η_{1} ε_{0} \min {Δ_{k}, \frac{ε_{0}}{β}} (8) \end{array}$

由于fk有界,则可以得到fl(k)也有界。通过引理3可以得到{fl(k)}中含有收敛子列{fl(ki)},其中i=1,2,3,…。根据文献[5]中的证明方法可得到

$\lim_{i \to \infty} f_{k_{i} + 1} = \lim_{i \to \infty} f_{l (k_{i})} (9)$

由于 $\lim_{k \to \infty} α_{k} = 1 ‚ k_{i} \geq k$ 则 $\lim_{i \to \infty} α_{k_{i}} = 1$ ,因此 $\lim_{i \to \infty} f_{k_{i} + 1} = \lim_{i \to \infty} α_{k_{i}} f_{l (k_{i})}$ 。

所以

$\lim_{i \to \infty} (α_{k_{i}} f_{l (k_{i})} - f_{k_{i} + 1}) = 0 (10)$

由式(8)可以得到

$α_{k_{i}} f_{l (k_{i})} - f_{k_{i} + 1} \geq \frac{1}{2} η_{1} ε_{0} \min {Δ_{k_{i}}, \frac{ε_{0}}{β}} (11)$

则由式(10)和式(11)可得

$\lim_{i \to \infty} \frac{1}{2} η_{1} ε_{0} \min {Δ_{k_{i}}, \frac{ε_{0}}{β}} = 0 (12)$

同时由于η1,ε0,β都是常数,因此

$\lim_{i \to \infty} Δ_{k_{i}} = 0 (13)$

由于函数f(x)在水平集L(x0)上一阶连续可微,根据Taylor展开式我们有

f(xk+sk)=fk+gTksk+

∫ $_{0}^{1}$ sTk(g(xk+τsk)-gk)dτ (14)

当Δk>0充分小时,同时有

$\begin{array}{l} | m_{k} (s_{k}) - f (x_{k} + s_{k}) | = \\ | \frac{1}{2} s_{k}^{Τ} B_{k} s_{k} - \int_{0}^{1} s_{k}^{Τ} (g (x_{k} + τ s_{k}) - g_{k}) d τ | \leq \\ \frac{β}{2} ∥ s_{k} ∥^{2} + o (∥ s_{k} ∥) (15) \end{array}$

因为mk(0)=fk,则有

$\begin{array}{l} | \frac{f_{k} - f_{k + 1}}{Ρ r e d_{k}} - 1 | = \\ | \frac{f (x_{k} + s_{k}) - f_{k} - (m_{k} (0) - m (s_{k}))}{m_{k} (0) - m_{k} (s_{k})} | = \\ | \frac{f (x_{k} + s_{k}) - m (s_{k})}{m_{k} (0) - m_{k} (s_{k})} | (16) \end{array}$

由式(7)、式(15)和式(16)可以得到

$| \frac{f_{k} - f_{k + 1}}{Ρ r e d_{k}} - 1 | \leq \frac{β Δ_{k}^{2} + 0 (∥ Δ_{k} ∥)}{ε_{0} \min {Δ_{k}, ε_{0} / β}} (17)$

由引理可知

$ρ_{l (k)}^{k} = \frac{α_{k} f_{l (k)} - f_{k + 1}}{Ρ r e d_{k}} \geq \frac{f_{k} - f_{k + 1}}{Ρ r e d_{k}} (18)$

令k→∞,有 $\lim_{k \to \infty} \frac{f_{k} - f_{k + 1}}{Ρ r e d_{k}} = 1$ 。由式(17)和式(18)可得到对充分大的k,有ρ $_{l (k)}^{k}$ ≥η2,因此由算法1可以得到,对充分大的k∈N0,有Δk+1≥Δk,则对充分大的ki∈N0,有Δki+1≥Δki,与 $\lim_{i \to \infty} Δ_{k_{i}} = 0$ 矛盾。所以假设不成立,即 $\lim_{k \to \infty} \inf ∥ g_{k} ∥ = 0$ ,因此算法1具有全局收敛性。

3 数值实验

对算法1进行全面的数值试验。所有的程序都用MATLAB写的。在试验中取 $η_{1} = 0.01 ‚ η_{2} = 0.75 ‚ r_{1} = 0.5 ‚ r_{2} = 2.0 ‚ Δ_{0} = \frac{1}{10} ∥ g_{0} ∥ ‚ \bar{Δ} = \frac{1}{5} ∥ g_{0} ∥ ‚ α_{k} = 2^{sgn (f_{l (k)})^{*} (1 / 2^{*} k)}$ 。

若‖gk‖≤10-6,计算终止。同时如果迭代次数超过500次,则计算终止。

例1 wood函数

f = 100(x12-x2)2 + (x1-1)2 + (x3-1)2 +

90(x32-x4)2 + 10.1((x2-1)2 +

(x4-1)2)+19.8(x2-1)(x4-1)。

这个函数在x*=(1,1,1,1)T取得最小值f*=0。初始点为(-3,-1,-3,-1)T。··

具体的数值结果如表1。

例2 GROSEN(广义Rosenbrock函数)

$f (x) = 1 + \sum_{i = 2}^{n} [100 (x_{i} - x_{i - 1}^{2})^{2} + (1 - x_{i - 1})^{2}] 。$

初始点x0=(-1.2,1,-1.2,1,…,1)',这个函数在x*=(1,1,…,1)T取得最小值f*=1。在试验过程中取T=5,数值结果见表2。

通过对上述数值实验结果的观察,该算法是有效的,它能够搜索到最优解,并且迭代步骤和迭代时间都比较的少,具有很强的实用性。

4 结论

本文提出了一种求解无约束优化的非单调信赖域算法。新算法是在现有的非单调信赖域算法的基础上在fl(k)添加了一个参数αk。通过对αk的设定,放宽信赖域半径的校正条件,从而使得搜索到的最优解尽可是全局最优解。在合理的条件下,证明了算法的全局收敛性,并通过数值实验验证了算法的有效性。

参考文献

[1] Grippo L,Lampariello F,Lucidi S.A nommonotone line search tech-nique for Newton’s method.SIAM J Numer Anal,1986;23:707—716

[2] Grippo L,Lampariello F,Lucidi S.A truncated Newton method withnonmonotone line search for unconstrained optimization.J OptimTheory Anal,1989;60:401—419

[3] Panier E R,Tits A L.Avoiding the Maratos effect by means of a non-monotone line search I:general constrained problems.SIAM J Num-er Anal,1991;28:1183—1195

[4] Deng N Y,Xiao Y,Zhou F J.A nonmonotonic trust region algo-rithm.J Optim Theory Appl,1993;75:259—285

[5]柯小伍,韩继业.无约束最优化的一类非单调信赖域算法.中国科学(A),1998;28(6):488—492

[6]李正峰,邓乃扬.一类新的非单调信赖域算法及收敛性.应用数学学报,1999;22(3):458—465

[7]姚升保,施保昌,彭叶辉.一类带线搜索的非单调信赖域算法.数学杂志,2003;23(3):290—294

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【自适应信赖域算法】相关文章：

局部误差的有界约束非线性方程组的非单调信赖域算法04-28