全局最优搜索

2024-11-15

全局最优搜索（精选6篇）

全局最优搜索篇1

0 引言

简要说来，模糊聚类问题就是：给定一些样本，要求根据样本的某些特征把这些样本进行聚类，并且可以根据某个样本对于某个类或者多个类的隶属程度而在聚类过程中把这个样本归入某一个类或多个类。在硬聚类中每一个样本只能属于某一个确定的类。

为方便对模糊聚类问题进行数学描述，在一个s维的空间中描述这些样本，s表示这些样本所据以聚类的特征的数目。所以，可以把模糊聚类描述成一个非线性的问题。

取J(W,Z)的极小值：

约束条件：

此处，n表示被聚类的样本(数据点)的数目;c表示样本集被划分成c个子集且有2≤c≤n;m是平滑参数，又称加权指数，m>1，尽管从数学角度看m的出现不太自然，但如果不对隶属度加权，从硬聚类目标函数推广到模糊聚类目标函数将是无效的;xi∈Rs,l≤i≤n,Rs是数据点的特征空间;zj是未知的聚类中心，且zj∈Rs,l≤j≤c，‖·‖表示xi和聚类中心zj的Euclid距离;Z=[z1,z2,…zc]是一个s×c的矩阵;W{wij]是一个n×c的矩阵。

如果矩阵W已知，问题就演化成寻找聚类中心Z。寻找聚类中心是比较简单的，并且它的全局最小值总是可以求得的。如果已知聚类中心Z，那么，在求得W之后，就很容易解决全局解的问题。

在求解模糊聚类问题时，模糊C-均值算法是应用最为广泛的一种算法。模糊C-均值算法是先选择一个初始值，然后算法不断迭代，计算当前聚类中心和Z之间的距离，以及当前W和给定W之间的距离。当连续两次计算出的W或Z之间的距离小于预先给定的阈值时，算法停止。前人已经证明算法是收敛的[4]。然而，算法也可能陷入模糊聚类问题的某个局部极小值或者鞍点而停止迭代。这是因为当J(W，)和J(,Z)都是凸函数时，函数J(W,Z)是非凸的。算法停止在某个局部极小值意味着所得到的解还可以进一步改进。本文提出的Tabu搜索算法就是搜索模糊C-均值算法可能找不到的全局最优解。

Tabu搜索是一种搜索局部最优解之外的解空间的一种引导式的局部启发式搜索过程。Glover[1]引进这种算法主要是为了解决组合数学方面的问题。Hansen[2]用别的名字描述它的基本思想：“急剧上升，平缓下降”。自此，Tabu搜索算法被成功地应用在商店的货物流通、建筑设计[3]等方面。

1 Tabu搜索算法

给定一组zj,j=1,2，…c，可以利用下述公式计算全局最优解：

上述公式是求解令J(W,Z)的偏导为0的W而得到的，并且考虑到W可能为零阵。模糊C-均值算法利用(4)式求得所给定聚类中心值的权值。给定权值wij和聚类中心zj，即可求解目标函数J(W,Z):

由此可知，对于任意给定的一组聚类中心zj，都对应着目标函数的一个特定的值。所以，可以利用这种新的搜索算法来形成聚类中心zj，并会产生一个目标函数的值J(W,Z)。可以比较三种类型的聚类中心和它们所对应的目标函数的值。

给定权值wij，就可以用下述的公式计算最优聚类中心：

上述公式是求解令J(W,Z)的偏导为0而得到Z。当m=1(硬聚类)时，(6)式为聚类中心。FCM算法利用(6)式在已知隶属度矩阵的前提下求得聚类中心。所以，可以利用Tabu搜索技术结合(6)式和wij的值计算聚类中心zj。实践证明，利用zj求wij比利用wij求zj效率要高。

分别用zt、zu、zb表示可能解矩阵、当前模式矩阵、最优中心矩阵。Jt、Ju、Jb分别表示相应的目标函数值。对当前中心zu不断进行操作，通过后面将要叙述的位移产生可能的聚类中心。在算法进行过程中，需要保存最优聚类中心zb，并相应地对目标函数值Jt、Ju、Jb进行操作。

因为是进行Tabu搜索，因此必须分离这些位移并存储在Tabu列表中。位移定义如下：

其中，ztj是第j个可能的中心;zuj是第j个当前中心;d∈Rs是dj方向的随机向量，d=(di),di=0，-1，+1。经观察得知，当越来越接近问题的解时，需要以非常小的步幅来进行迭代。可以用如下算法求方向乘子α。

算法描述如下：

Step1：初始化：令zu为可能的中心，Ju为相应的目标函数值，zb=zu，且有Jb=Ju，分别为Tabu列表长度(NTLM)、概率阈值(P)、可能解的数目(NH)、每个中心的最大迭代次数(I-MAX)赋值。方向乘子α=1，迭代计数器β=0.75，令k=1,NTL=0,l=1;

Step2：利用可能的中心zu，固定所有中心，并通过产生NH个邻近的点z1,z2,…z NH来移动中心zul，并求相应的目标函数J1,J2,…JNH的值。

Step3:

(1)对Jti,i=1,2,…NH进行非降序排序，排好序后，将它们标记为：Jt[1],…Jt[NH]，显然Jt[1]≤Jt[2]≤…≤Jt[NH]，若Jt[1]≤Jb，则k=k+l;

(2)如果用来产生z[1]的方向不是Tabu的，或者即使是Tabu的，但是Jt[1]≤Jb，则令zul=z[1]且Ju=Jt[1]，跳转到Step4。否则，产生u～U(0,1)(此处，U(0,1)是一个(0,1)之间的函数)，如果Jb≤Jt[1]≤Ju且u>P，则令Ju=Jt[1]，zul=z[1]跳转到Step4，否则，跳转到Step3的(4);

(3)重复进行Step3的(2)，计算zt[2],…zt[NH]，直到选中一个邻近的点，跳转到Step4;

(4)若k>IMAX，跳到Step5，否则跳转到Step2选择新的邻近点集。

Step4：如果Tabu列表中不存在产生zul的方向向量，则将此方向向量添加到列表末尾，令NTL=NTL+1。若NTL=NTLM+1，则删除列表头，并令NTL=NTL-1。若Jb>Ju，令Jb=Ju,Zb=Zu，跳转到Step2。

Step5：若l1，则令l=1，跳转到Step2，否则，算法停止(Zb是最优中心，Jb是相应的最优解)。

说明：Pb:样本序号，Iter:Tabu搜索的迭代次数，C-means:FCM的目标函数值，Tabu:Tabu搜索的目标函数值，Dev:Tabu搜索的目标函数值和FCM的目标函数值的相对误差，AV:平均迭代次数和平均相对误差。

2 算法的参数

Tabu搜索算法的各个参数都会对算法的过程产生不同程度的影响。Tabu搜索算法的参数描述如下：

Tabu列表大小(NTLM):Tabu列表中有搜索的历史记录，这是Tabu搜索算法最明显的特征。算法假定没有存储最后的NTL位移，因此，没有修正倒数第二个解。NTLM是可以存储在列表中的最大位移的数，因此，NTLM的值越大，搜索的存储能力越强。

概率阈值(P)：可以利用概率阈值来检测Tabu位移和优于当前解的位移，从而更接近于最优解。可能解的数目(NH)：在Tabu搜索中，研究NH个可能的解来决定下一步将要进行的位移。因此，NH的值越大，就需要检测更多的邻近点;反之，则需要检测较少的邻近点。

每个中心的非优化位移的数目(IMAX)：这个参数决定在对下一个可能的中心进行操作前允许进行多少次非优化的位移。通过实验可以看出，当靠近最优解时，花在检测给定中心上的时间会减少，因此，最好采用变化的参数IMAX。

所以，可以从某个值IMAX开始，直至中心不再更优时，利用因子β减小IMAX的值直至小于1，这和算法停止的判定标准是一致的。

每个中心的非优化位移的最大数目的减小因子(β)：如上所述，如果进行了IMAX个非优化位移，就可以确定下一个中心。当所有的中心都确定后，利用因子减小IMAX的值(0<β<1)。显而易见，β的值越小，IMAX的值下降到1以下的速度越快，算法就可以通过越少的可能的中心点求得最优解，但是，所求得的最优解与实际最优解的误差会越大。

说明:C:聚类类别数,N:待聚类样本数目,Set:数据集编号**.m:模糊加权指数(m为1时为硬聚类)。

方向乘子(α)：α是一个标量，表示在特定方向上找到可能解的步长。α必须为正数，且值越大，邻近点与当前解的距离越大。当越来越接近最优解时，α的值是可以变小的。

经实验验证，可得到参数的经验性取值：

NTLM:1/15*可能性方向的总数;或是(3n-1)/15(n是待聚类样本数目);

NH:0.1*可能性方向的总数;

α：对每个中心进行操作时，对α初始化为1，并使用减小因子0.8;

IMAX：初始化为40，在处理完所有中心后使用减小因子0.75;

β：0.75。

3 数据实验

采用如下数据集：有[-5,5]之间的随机数xi,i=1,2…n。分别在m=1.2,1.5,2.0,3.0,5.0,n=10,50,100,c=3,4,s=2,3,5的情况下对算法进行实验验证。表一、二是实验的结果，表三是总结性的结果。从表中的结果可以看出，Tabu搜索算法比FCM算法的性能要好。在图一～图四中可以看出，当m的值更小，待聚类样本数、样本维数更少，以及聚类类别数更多时，算法的优势更加明显。只有极少数情况下，FCM算法得到的聚类中心要更接近实际的中心。但是，当Tabu搜索进行的时间长一些后，依然会得到和FCM同样的解，这是因为这两种算法都得到了全局最优解，即是说FCM算法没有陷入局部极值点或鞍点。

4 结束语

在本文中提出了一种求解模糊聚类问题全局最优解的Tabu搜索算法。经过多次数据试验，证明Tabu搜索算法在搜索全局最优解时是很有效的。

摘要：模糊聚类问题由于其非凸性而成为一个难以解决的数学问题。在解决模糊聚类问题时,会出现很多局部极小值和鞍点。因此,启发式的模糊C-均值算法是应用最为广泛的算法,其缺点是很容易陷入局部极小值。本文提出了一种搜索模糊聚类全局最优解的Tabu搜索算法,并比较这种新算法和模糊C-均值算法的性能。经过多次数据试验,证明Tabu搜索算法在搜索全局最优解时是很有效的。

关键词：模糊聚类,模糊C-均值算法,Tabu搜索技术,全局最优值

参考文献

[1]J.C.Dunn.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J].J.Cyber-net,1974.

[2]J.C.Bezdek.Fuzzy mathematics in pattern classification,Ph.D.Dissertation,Departm-Ent of Applied Mathematics.Cornel[J]l University,Ithaca,New York,1973.

[3]M.A.Ismail and S.Z.Selim.Fuzzy C-means:Optimality of solutions and effective termination of the algorithm[J].Pattern Recognition,1986.

[4]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.

[5]李安贵等.模糊数学及其应用[M].北京:冶金工业出版社,2006.

全局最优搜索篇2

本文提出一种基于局部扫描法与P&O相结合的全局最优MPPT算法,该方法在系统启动后先采用固定大步长进行一次全局扫描来寻找全局最大功率点,当扫描结束后使系统运行于全局最大功率点附近,然后启动变步长P&O算法变步长扫描,找到精确的最大功率点。该方法解决了传统的单峰值算法导致光伏阵列不能持续工作在系统最大输出功率点的问题,能使光伏阵列运行在系统全局最大功率点。

1 局部阴影下的光伏输出特性

图1 为光伏阵列有/无阴影输出特性示意图。本文针对光伏阵列在有/无阴影输出的特性进行研究,假设初始时刻光伏阵列表面无阴影,在运行过程中出现阴影,其输出特性的变化规律为:1)在正常情况下光伏阵列只有1个峰值点,当出现局部阴影后,光伏阵列输出功率将会减小,系统会出现2 个或2 个以上的峰值;2)光伏阵列从无阴影到出现阴影过程中,其输出特性曲线上的全局最大功率点可能向电压减小的方向移动,或仍在原最大功率点对应的电压附近;3)当光伏阵列输出呈现多峰特性时,一般情况下,各个局部峰值点呈阶梯状,即在全局MPP点左右两边,局部MPP点逐次减小,距离全局最大功率点越远,局部最大功率点的功率越小。特殊情况下会在2个较大局部峰值点之间存在一个较小峰值点。

当光伏阵列出现如图1中所示的局部阴影下多峰输出特性时,传统的MPPT算法可能会失效。基于以上输出特性规律,本文提出了局部扫描法与P&O相结合的全局最优MPPT算法。

2 全局MPPT算法设计

2.1 系统启动阶段

在系统启动阶段,有2种方案。

1)一般在全局最优MPPT算法中,默认系统启动时光伏阵列输出为单峰值,故采用传统的MPPT启动,当阴影出现后,再使能全局MPPT算法。但是,系统在实际启动之前无法确定光伏阵列输出处于单峰值还是多峰值状态,所以本方法中系统启动后先进行一次全局扫描来寻找全局最大功率点。由于全局扫描范围较大,为减小功率损失,先采用固定大步长扫描,扫描结束后使系统运行于全局最大功率点附近,然后启动变步长P&O算法变步长扫描,找到较精确的最大功率点。

2)若系统启动时光伏阵列表面无局部阴影,则测量此时的开路电压,并以0.9 倍的开路电压为参考电压,启动变步长P&O算法,此时无需进行全局MPPT扫描算法。

2.2 稳定运行阶段

变步长P&O算法:即在传统的P&O算法上增加变步长算法,具体实施方法就是每改变一次搜索方向,步长变为原步长的一半,该方法可以减小在最大功率点附近震荡带来的能量损失。

系统启动后,根据此时的扰动步长可以判定系统是否处于稳定阶段,当扰动步长足够小时,认为系统已稳定运行在全局最大功率点上。

当系统稳定运行后,使能光伏阵列阴影判断功能,此时设定阈值ΔP0。另外,令ΔP=P(t)-P(t-1),其中P(t)和P(t-1)分别为当前功率值和上一次功率值,考虑到系统的响应时间及振荡,故设P(t)和P(t-1)为某一时间段内功率的平均值。若光伏阵列输出功率不发生突变,即| ΔP| < ΔP0时认为光伏阵列无阴影,则继续执行P&O算法;否则认为光伏阵列有阴影,需要启动局部扫描法。

2.3 变步长的P&O算法

1)功率平均值的计算。在P&O算法执行过程中,系统处于稳态,则无需进行频繁的扰动,选取扰动时间间隔为500 ms,而功率计算平均值的时间则为500 ms中后半200 ms。

2)ΔP0的取值。因为P&O算法是在不停地进行扰动,当无局部阴影发生时,采用变步长P&O算法产生功率差值很小;在无阴影条件下,光伏阵列工作在全局最大功率点处时,扰动步长为ΔU,扰动带来的功率变化ΔP与ΔU、最大功率点处电流成比例关系。因此设定ΔPmax= k ·ΔU·Imax,其中k为系数,为防止太容易进入局部阴影扫描,故选取ΔU的最大值。当局部阴影发生时,若对光伏阵列输出功率产生的影响比较小时,也无需启动局部扫描算法,以避免扫描过程中带来的功率损失。

因出现局部阴影后,光伏阵列输出功率变小,最大功率点保持在原工作电压点附近或向电压减小的方向移动,故进入局部扫描算法后,从当前工作电压点处向电压减小的方向扫描,并将当前工作点的功率、电压分别记作Pmax,UPmax。由于扫描范围较大,故扫描的固定步长可以略大于P&O算法中的最大步长。系统不断向电压减小的方向进行扫描,直到出现新的峰值,若新峰值的功率值大于Pmax,则更新UPmax的值,继续向电压增大的方向进行扫描,若新峰值的功率值小于Pmax,则停止扫描。另外,若搜索到扫描范围的电压下限值Umin,也停止扫描。局部扫描过程不宜太长,故在系统稳定的前提下,减小扰动时间间隔,相应计算P(t)和P(t-1)的平均值时间的减小,扰动时间间隔取为300 ms以内。

3 仿真和实验结果

本文搭建了基于Matlab/Simulink的仿真模型,对全局最优MPPT算法进行了仿真验证。

3.1 基于Matlab的仿真模型

图2为光伏阵列仿真模块。光伏阵列的开路电压、短路电流、最大功率点电压、电流,以及温度、光照强度和每个组件中被遮挡的光伏阵列个数具体见图中给定的参数。其中2个阶跃信号表示光伏阵列第2 块组件与第3 块组件在1 s时突然出现阴影,这样导致光伏阵列输出特性出现多峰现象。PV_3_531模块为S-Function模块,可根据输入条件与当前工作电压,得到光伏阵列对应的输出电流值。其中,用Boost电路控制光伏阵列的输出电压,寻找光伏阵列的全局最大功率点。Boost电路的输入端接光伏阵列,输出端接直流电压源,作为稳定的母线电压。

3.2 Matlab仿真结果

1)仿真条件。在光照度为1 000 W/m2时系统启动,输出单峰特性曲线。在1 s时第2个与第3 个组件都有4 个阵列出现阴影。因为6 k W逆变器的MPPT最低电压为200 V,最高电压为500V,故设置P—V曲线的扫描范围为220~480 V。

2)仿真过程。1系统启动后从0.9 倍的开路电压处开始进行P&O算法,算法初始步长为20V,寻找最大功率点并保存;2当P&O算法的步长足够小时,认为光伏阵列已稳定运行于最大功率点,启动功率判断功能,在功率发生突变时执行步长为20 V的局部扫描法,寻找全局最大功率点并保存,若功率没有发生突变,继续执行P&O算法;3在1 s功率发生突变,启动局部扫描法;4启动局部扫描法扰动结束后,参考电压给定为全局最大功率点处电压,执行P&O算法,算法初始步长为20 V;5返回步骤3。

3)仿真结果。图3 为仿真过程中,全局最优MPPT算法给定的参考电压变化过程。正常情况时,光伏阵列输出特性如曲线1所示,系统运行于最大功率点O。曲线2为出现局部阴影时的光伏输出特性。

图4、图5分别为全局最优MPPT算法过程中光伏阵列输出电压、功率变化仿真波形图。

系统启动后开始进行P&O算法,经过t1时间,系统扫描到最大功率点O,此时输出功率大约为6.2 k W。t2=1 s时出现局部阴影,光伏阵列输出电压不变,电流减小,输出功率降为4.4 k W左右,光伏阵列工作于A点。随后启动局部扫描法,将A点记为功率最大点Pmax,并从A点开始向电压减小的方向进行扰动扫描。扫描到局部功率最大B点后,由于B点功率小于A点,继续向电压减小的方向扫描,但由于B点左边没有功率减小的局部峰值点,故需扫描到MPPT的电压下限Umin处时停止扫描,然后回到记录中的最大功率点A后附近扫描,由于C点功率为4.42 k W,并且右边没有功率减小的局部峰值点,t3时刻将C点的电压作为参考电压,启动P&O算法,使光伏阵列工作在C点左右,等待下次功率突变的发生。此时光伏阵列输出最大功率为4.42 k W。至此,此种全局最优MPPT算法已完成,其工作点依次为O→A→B→A→C。

3.3 实验装置及结果

为验证本文的算法,搭建了功率为6 k W的单相光伏并网逆变器,图6 为用毛毯遮住部分电池组件。装置的主要参数为:PV输入功率6 k W,升压电感0.22 m H,Boost IGBT型号IKW40N65H5,Boost二极管型号APT30DQ120BG,母线DC-link315 V/1 000 μF。

图7、图8分别为全局最优MPPT算法过程中光伏阵列输出电压、功率变化实际瞬态波形图。

图7和图8是系统开始无阴影时工作电压、输出功率分别约520 V,6 000 W,在150 s时用毛毯遮住部分电池组件,在270 s时移去毛毯后系统电压、功率的动态变化波形。从图中可以看出:在出现阴影的情况下,系统立即对光伏输出特性曲线不断的扫描,当扫描结束后使系统运行于全局最大功率点附近,这样减少系统能量的损失,与仿真及理论分析相符。

图9为光伏模拟器模拟当光伏组件有2个峰值时光伏阵列全局最大输出功率点时波形图。

从图9 可以看出,当系统存在2 个局部最大功率点时,通过本文提出的算法能很快找到全局最大功率点,如图9中圆点所示。通过同样的方法,当系统存在2个及2个以上的局部最大功率点时也能通过比较找到全局最大功率点。

4 结论

本文提出一种新的基于局部扫描法与P&O相结合的全局最优MPPT算法,通过仿真与实验说明了采用全局最优MPPT算法的过程,该算法有以下优点:

1)相较于全局MPPT扫描算法,此算法扫描范围较小,减少了扫描过程中功率的损失;

2)此算法避免了短路电流的在线测量,而开路电压值也只需在开机前读取即可;

3)结合传统的P&O算法,不需要在无阴影的情况下对光伏输出特性曲线不断的扫描,从而减少了功率损失,同时有利于系统的稳定运行。

摘要：针对光伏阵列出现多个局部功率峰值时,传统的MPPT算法导致系统工作在某个局部最大功率点的问题,提出一种新的基于局部扫描法与P&O相结合的全局最优MPPT算法,该方法在系统启动后先采用固定大步长进行全局扫描来找到全局最大功率点,当系统运行在全局最大功率点附近时,然后采用变步长P&O算法变步长扫描来找到精确的最大功率点。基于Matlab/Simulink的仿真模型,对全局最优MPPT算法进行了仿真验证;并搭建一个功率为6 k W的实验平台验证当系统出现多个峰值时的效果。仿真和实验结果验证了所提出的全局最优MPPT算法在光伏阵列出现多峰值时具有很好的MPPT效果。

关键词：光伏阵列,全局优化,最大功率点跟踪,算法

参考文献

[1]Kjaer S B.Evaluation of the Hill Climbing and the Incremen-tal Conductance Maximum Power Point Trackers for Photovol-taic Power Systems[J].IEEE Transactions on Energy Conver-sion,2012,27(4):922-929.

[2]Ji Y H,Jung D Y,Kim J G,et al.A Real Maximum PowerPoint Tracking Method for Mismatching Compensation in PVArray Under Partially Shaded Conditions[J].IEEE Transac-tions on Power Electronics,2011,26(4):1001-1009.

[3]张兴,曹仁贤.太阳能光伏并网发电及其逆变控制[M].北京:机械工业出版社,2011.

[4]Hiren Patel,Vivek Agarwal.Maximum Power Point TrackingScheme for PV Systems Operating Under Partially ShadedConditions[J].IEEE Transactions on Industrial Electronics,2008,55(4):1689-1698.

全局最优搜索篇3

HEV的能量管理策略对燃油经济性有决定性的影响。因此, 为了提高HEV的燃油经济性, 各国的研究人员提出了多种优化方法, 如基于规则的控制策略、模糊控制策略[1-2]、动态规划[3-5]、等效燃油消耗最小[6]、极小值原理[7-9]等。基于规则的控制策略、模糊控制策略和等效燃油消耗最小策略计算速度快, 能够实时运行。动态规划是全局优化算法, 计算量很大, 不具有实时性, 但可以从所得的结果中总结出一些用于实时控制的规则, 还可以作为其他控制策略的参考。

为了得到串联HEV能量管理策略的全局最优解, 本文采用分段函数拟合了发电机组的最优工作曲线。把电池组的工作区间限制在一个较小的范围, 并假定开路电压和内阻为常数。在给定工况下, 采用庞特里亚金极小值原理算法求解, 在很短的时间内就得到了全局最优解。因而, 该方法具有实时化的潜力[7，10]。

1混合动力汽车建模

为了研究串联HEV的能量管理策略, 需要建立动力总成和各个能量源的数学模型。为简化计算, 忽略了动力传动部件的效率损失。

1.1动力总成模型

串联HEV动力总成的模型如图1所示, 发动机和发电机直接相连组成发电机组。动力总成工作模式如下:1发动机带动发电机发电, 直接给电动机供电;2发电机给电动机供电, 同时给电池充电;3发电机给电池充电;4再生制动时, 电动机工作在发电状态, 把车辆的动能转化为电能给电池充电;5再生制动的能量和发电机的输出能量同时充入电池。图1中, 箭头表示能量的流向, 带双箭头的线段表示能量可双向流动。Pgen (t) 为发电机组的输出功率, Preq (t) 为车辆的需求功率 (驱动时为正, 制动时为负) , Pbatt (t) 为电池的输出功率 (放电时为正, 充电时为负) 。动力总成的功率平衡关系为

在给定工况下, Preq (t) 由仿真软件计算得到, 即Preq (t) 是已知的。

1.2发电机组模型

对于串联HEV, 发动机和车轮之间没有直接的机械连接, 发动机转速可以不依赖车速独立控制。因此, 发动机可以工作在给定功率输出的最高效率处, 即发动机可以沿最优工作线运行[11]。然后, 用分段函数对最优工作曲线进行拟合, 发电机组最优工作曲线和拟合线如图2所示。

图2中发电机组的拟合曲线可表示为

式中为发电机组输出功率为Pgen时的耗油率, g/s;P0为两条拟合线段连接处的功率, P0=24kW;Pgen, min、Pgen, max分别为发电机组的最小、最大输出功率;a1、b1、a2、b2为拟合系数, a1=0.1935, b1=0.0752, a2=1.9988, b2=0.1091。

1.3电池模型

电量保持型混合动力汽车的电池SOC在一个很窄的范围内。这时, 可近似认为电池的端电压和内阻为常值[9]。仿真中设电池SOC工作区间为0.5~0.7, 在该区间内电池工作效率较高, 且近似认为电池的端电压和内阻为常值。

根据电池的电路模型可得电池的输出功率:

式中, Uoc为开路电压;R0为等效电阻。

由式 (3) 得电池输出功率为Pbatt (t) 时的电流:

2能量管理问题模型

2.1性能指标函数

能量管理策略优化的目的是使整个工况的燃油消耗最小。因此, 性能指标用每一时刻的燃油消耗的总和来表示, 并使其达到最小:

式中, Te、ωe分别为发动机的转速和转矩;D为可行域;表示沿最优工作曲线输出功率为Pgen (t) 时的耗油率;tf为仿真工况的结束时间。

2.2状态方程

电池的SOC为系统的状态变量, 其变化过程可表示为

对式 (6) 求导即得系统的状态方程:

d (SOC (t) ) /dt=-UocIbatt (t) (7)

电池是辅助能量源, 对发电机组输出功率起 “削峰填谷”的作用, 从一个较长的时期来看, 驱动车辆的所有能量最终都来自发动机。因此, 为了评估能量管理策略的燃油经济性, 要求电池SOC的末态值等于初始值, 即

SOC (tf) -SOC (t0) =0 (8)

实际计算时, 取

式中, ε为一个非常小的正数。

2.3约束条件

仿真计算时, 在考虑了发动机与发电机的转速与转矩约束后, 最终得到发电机组的功率约束:

电池组的输出功率Pbatt (t) 应满足下面两个公式[11]:

3庞特里亚金极小值原理

满足庞特里亚金极小值原理的条件是必要条件, 而非充分条件。在实际应用中, 可根据系统的物理意义进行判断。如果求解的系统具有唯一的最优解, 且根据极小值原理只能求出一个极值解, 则该解就是最优解[11]。混合动力汽车的能量管理显然具有这样的特点, 因此, 可以采用极小值原理求出最优解。

3.1哈密顿函数

根据式 (5) 、式 (6) , 取哈密顿函数:

式中, λ (t) 为协态变量。

综合式 (2) 、式 (4) 、式 (13) , 哈密顿函数可化为

3.2协态方程

由哈密顿函数可得到协态方程:

式中, λ (t) 为常数。

3.3最优解计算

在每一时刻, 求解使哈密顿函数取极小值的控制量Pbatt (t) , 即

在每一时刻, 通过式 (17) 求取的P*batt (t) 就是该时刻的最优控制量。选择λ (0) , 从给定的SOC (t0) 开始, 电池组状态SOC (t) 通过对状态方程 (式 (7) ) 积分得到。对工况的仿真结束时, 如果满足式 (9) , 则本次循环采用的λ (0) 就是所要求的协态变量值, 且该次循环中计算出的各个时刻的发电机组和电池组需要承担的功率即为给定工况的最优解。反之, 则调整λ (0) 重新计算。λ (0) 的调整采用最优化算法中的二分法, 仿真计算的流程如图3所示。

4仿真结果

以ADVISOR中的串联HEV为基础, 采用镍氢电池组, 车辆参数如表1所示。采用UDDS工况进行仿真, UDDS工况曲线如图4所示。利用仿真软件提取整个工况的需求功率, 在MAT- LAB中编写程序进行仿真, 采用MATLAB优化工具箱中的fminbnd () 函数来计算使哈密顿函数取极小值的控制量, 即电池组输出功率。

仿真得到的百公里油耗为5.576L, 协态初始值λ (0) 的选取对电池组末端荷电状态的影响如图5所示, 当取电池组始末端的荷电状态变化小于0.1%时, 计算得λ (0) =-0.0746。发电机组和电池组的输出功率如图6所示。电池组荷电状态的变化如图7所示。在普通的个人计算机上, 仿真计算花费的时间为52.9s。

5结语

建立了串联HEV的发电机组和电池组的简化数学模型。在给定工况下, 以最小油耗为性能指标, 采用庞特里亚金极小值原理算法计算了发电机组和电池组分别需要承担的输出功率。该方法把全局优化问题转化为一个瞬时优化问题, 通过迭代运算, 找到能够使电池组保持电量平衡的协态变量λ (0) 。同时, 还可得到需求功率在发电机组和电池组之间的分配, 且计算量小、计算速度快。结合工况识别技术[12], 有望得到可实时运行的能量管理策略。

参考文献

[1]彭涛, 陈全世.并联混合动力电动汽车的模糊能量管理策略[J].中国机械工程, 2003, 14 (9) :797-800.Peng Tao, Chen Quanshi.A Fuzzy Energy Management Strategy for Parallel Hybrid Electric Vehicles[J].China Mechanical Engineering, 2003, 14 (9) :797-800.

[2]殷承良, 浦金欢, 张建武.并联混合动力汽车的模糊转矩控制策略[J].上海交通大学学报, 2006, 40 (1) :157-162.Yin Chengliang, Pu Jinhuan, Zhang Jianwu.The Fuzzy Torque Control Strategy for Parallel Hybrid Electric Vehicles[J].Journal of Shanghai Jiao Tong University, 2006, 40 (1) :157-162.

[3]Brahma A, Guezennec Y, Rizzoni G.Optimal Energy Management in Series Hybrid Electric Vehicles[C]//Proceedings of 2000 American Control Conference.Chicago, 2000:60-64.

[4]申彩英, 夏超英.基于改进型动态规划算法的串联混合动力汽车控制策略[J].控制理论与应用, 2011, 28 (3) :427-432.Shen Caiying, Xia Chaoying.Control Strategy of Series Hybrid Electric Vehicle Based on Improved Dynamic Programming[J].Control Theory&Applications, 2011, 28 (3) :427-432.

[5]林歆悠, 孙冬野, 秦大同, 等.混联式混合动力客车全局优化控制策略研究[J].中国机械工程, 2011, 22 (18) :2259-2263.Lin Xinyou, Sun Dongye, Qin Datong, et al.Development of Power-balancing Global Optimization Control Strategy for a Series-parallel Hybrid Electric City Bus[J].China Mechanical Engineering, 2011, 22 (18) :2259-2263.

[6]Paganelli G.Equivalent Consumption Minimization Strategy for Parallel Hybrid Powertrains[C]//IEEE55th Vehicul Technology Conference.Birmingham, 2002:2076-2081.

[7]Lorenzo S, Giorgio R.Optimal Control of Power Split for a Hybrid Electric Refuse Vehicle[C]//2008 American Control Conference, ACC.Seattle, WA, USA, 2008:4498-4503.

[8]Delprat S, Lauber J, Guerra T M, et al.Control of a Parallel Hybrid Powertrain:Optimal Control[J].IEEE Transactions on Vehicular Technology, 2004, 53 (3) :872-881.

[9]Namwook K, Sukwon C, Huei P.Optimal Control of Hybrid Electric Vehicles Based on Pontryagin’s Minimum Principle[J].IEEE Transactions on Control Systems Technology, 2011, 19 (5) :1279-1287.

[10]Delprat S, Guerra T M.Optimal Control of a Parallel Powertrain:From Global Optimization to Real Time Control Strategy[C]//IEEE 55th Vehicular Technology Conference.Birmingham, 2002:2082-2088.

[11]Lorenzo S, Simona O, Giorgio R.A Comparative Analysis of Energy Management Strategies for Hybrid Electric Vehicles[J].Journal of Dynamic Systems, Measurement and Control, 2011, 133 (3) :1-9.

全局最优搜索篇4

全局最优化在许多领域有广泛的应用, 如计算机科学, 经济管理, 资源管理, 工程设计, 生物工程等.自70年代以来有关全局最优化的新的理论及计算方法层出不穷.人们已提出的有效全局优化方法可以分成两类:确定性方法, 如打洞函数法[3,4,5,10], 填充函数法[1,2]等.不确定方法, 又称随机类方法, 如模拟退火算法[11], 遗传算法[12]等.因此, 研究全局最优化方法, 既具有十分重要的理论意义, 又具有广泛的直接应用前景.

填充函数法最早是由西安交通大学的葛仁傅教授在文章[1]中首先提出的, 它的基本思想是:在目标函数f (x) 的当前的局部极小点x*1处构造填充函数P (x) , 如果P (x) 的一个极小点 $\bar{x}$ 在比x*1所在盆谷更低的盆谷中, 则以 $\bar{x}$ 为初始点极小化f (x) 可得到f (x) 的比x*1更低的极小点x*2, 再用x*2代替x*1可找到更低的极小值点.重复以上过程, 在一定条件下结束.最终可以找到f (x) 的全局极小点x*g.

文献[7,8,9]针对两个参数不易调节的问题利用文献[1]的定义加以修改, 构造出了单参数的填充函数.文中是在以上文献的基础上给出的一种有效的单参数填充函数.

本文的结构如下:第2节是预备知识, 给出填充函数的定义以及一些假设条件;第3节给出一个单参数的填充函数, 通过证明它的性质说明所给的函数是一个填充函数;第4节给出填充函数的算法, 并用数值试验结果来说明算法的有效性和可行性;第5节给出结论.

2 预备知识

我们考虑如下无约束最优化问题:

${\begin{cases} \min f (x), \\ s . t x \in R^{n} . \end{cases} (2.1)$

首先我们做如下假设:

假设1f (x) 在Rn上连续可微, f (x) 的局部极小点个数可以有无限个, 但其局部极小值个数只有有限个.

假设2f (x) 是一个强制函数, 即当x→+∞时, 有f (x) →+∞.

显然, 由假设2可知, 存在这样一个强紧集Ω⊂Rn, 它的内部包含f (x) 的所有极小点.为方便起见, 设Ω被一些常数ci, di, i=1, …, n所确定, 特别, 不妨令Ω={ (x1, …, xn) |ci≤xi≤di, i=1, …, n}, 这里ci, di, i=1, …, n是常数.所以, 原极小化问题等价于如下的极小化问题:

${\begin{cases} \min f (x), \\ s . t x \in Ω . \end{cases} (2.2)$

接下来我们介绍几个概念.

定义2.1 一个连通区域B*称为f (x) 在孤立局部极小点x*的盆谷, 是指x*∈B*, 而且从B*内任一点出发, f (x) 的最速下降轨迹一定趋向于x*, 但从B*外的任一点出发, f (x) 的最速下降轨迹一定不趋向于x*.类似地, 称B*为f (x) 的孤立局部极大点x*处的山丘, 若B*为-f (x) 在x*处的盆.

如果f (x) 的两个局部极小点x*1和x*2处的函数值满足f (x*1) ≤f (x*2) , 称x*1处的盆比x*2处的盆低;否则称x*1处的盆比x*2处的盆高.显然有这样的结论:如果B*是x*的盆谷, 那么对∀x∈B*且x≠x*, 有f (x) >f (x*) .

定义2.2 设x*是f (x) 的一个局部极小点, x*处的简单盆S*是一个含于B*内的一个连通区域, 对∀x∈S*且x≠x*, 不等式 (x-x*) T∇f (x) >0成立, 类似地可以定义简单山丘.

定义2.3F (x, q) 称为极小化问题 (2.1) 的对应于局部极小点x*处一个填充函数, 如果F (x, q) 满足如下性质:

(1) x*是F (x, q) 的一个严格局部极大点;

(2) ∇F (x, q) ≠0, 当x∈S1时, S1={x|f (x) ≥f (x*) , x∈Ω＼x*};

(3) 如果x*不是f (x) 的一个全局极小点, 且S2={x|f (x) <f (x*) , x∈Ω}≠Ø, 那么存在一个点 $\bar{x}$ ∈S2是F (x, q) 的一个局部极小点.

3 填充函数的构造及其性质

我们构造在f (x) 当前局部极小点x*处的填充函数的形式如下:

F (x, q) =-ln (f (x) -f (x*) +1) -q (x-x*) 2. (3.1)

这里, x*是f (x) 当前局部极小点, q>0且足够大.

对任意的x∈Ω, 令d (x) =x-x*;L1=max∇f (x) , 其中x∈Ω;D=minf (x) -f (x*) , 其中x∉S1, S1是x*包含的简单盆.

下面我们将证明F (x, q) 满足定义2.3.

定理3.1 假设x*是函数f (x) 的一个局部极小点, 则x*一定是F (x, q) 的一个严格局部极大点.

证明因为x*是函数f (x) 的一个局部极小点, 所以存在x*的一个领域N (x*, δ) (δ>0) 使得对任意的x∈N (x*, δ) 都有f (x) ≥f (x*) .故, 对任意的x∈N (x*, δ) /{x*}都有

F (x, q) =-ln (f (x) -f (x*) +1) -q (x-x*) 2<0=F (x*, q) . (3.1)

所以, x*是函数F (x, q) 的一个严格局部极大点.

定理3.2 对任意的d∈Ω, 且f (x) >f (x*) , 若dT∇f (x) ≥0, dT (x-x*) >0, 或dT∇f (x) >0, dT (x-x*) ≥0, 那么, d都是F (x, q) 在x*处的一个下降方向.特别沿x-x*方向, F (x, q) 是下降的.

证明由 (3.1) 可知:

$\begin{array}{l} d^{Τ} \nabla F (x, q) \\ = - d^{Τ} (\frac{\nabla f (x)}{f (x) - f (x^{*})} + 2 q | x - x^{*} |) \\ = - (\frac{d^{Τ} \nabla f (x)}{f (x) - f (x^{*})} + 2 q d^{Τ} (x - x^{*})) . (3.2) \end{array}$

由定理2的条件可得:dT∇F (x, q) <0, 故d是F (x, q) 在x*处的下降方向.特别地, 当x∈S1时, F (x, q) 沿方向x-x*是下降的, 则S1变成F (x, q) 的一个山丘.

定理3.3 若f (x) >f (x*) , 且dT∇f (x) <0, dT (x-x*) >0时, 有

$q > \frac{- d^{Τ} \nabla f (x)}{2 d^{Τ} (x - x^{*}) (f (x) - f (x^{*}))} = a (x), (3.3)$

则d是F (x, q) 在x*处的下降方向, 特别在x-x*方向成立.

证明只需要证明dT∇F (x, q) <0即可.由 (3.2) 可知, 要使dT∇F (x, q) <0, 只要 $\frac{d^{Τ} \nabla f (x)}{f (x) - f (x^{*})} + 2 q d^{Τ} (x - x^{*}) > 0$ 即可.在题设条件下, 只要 (3.3) 式成立, 就有dT∇F (x, q) <0, 故d是F (x, q) 在x*处的下降方向, 特别在x-x*方向成立.即当 $q > \frac{L_{1}}{D}$ 时, d是F (x, q) 在x*处的下降方向.

定理3.2和定理3.3说明, 在f (x) 的一个极小点x*1的盆S2中, 只要S2比S1高, 即f (x) >f (x*) , 则至少沿方向x-x*, x∈S2, F (x, q) 总是下降的, 所以F (x, q) 在S2中不可能有任何极小点或鞍点, 即∇F (x, q) ≠0.

定理3.4 若f (x) >f (x*) , 且dT∇f (x) <0, dT (x-x*) >0时, 有q<a (x) , 则d是F (x, q) 在x*处的一个上升方向.

证明仿定理3.3的证明可得, 在给定的条件下有dT∇F (x, q) >0.

定理3.5 当 $\frac{L_{1}}{D} < q < a (x) (3.4)$

时, F (x, q) 在比S1低的盆中必有极小点或鞍点.

证明由定理3.3和定理3.4, 可得定理3.5.此外, 在比x*的盆S1低的盆S2中, 当f (x) -f (x*) →0+时, a (x) →+∞, 这时 (3.3) 式右侧趋于正无穷大.这个性质保证, 不管q多大, (3.4) 式都成立, 同时也保证了全局极小点不会丢失.

4 算法和数值试验

求解问题 (2.1) 全局最优解的新的单参数填充函数算法[6]如下:

步0.选取M>0作为q的终止值.选取方向ei, i=1, …, k0和整数k0≥2n, 这里n是变量的个数.选取一个初始点x $_{1}^{0}$ ∈Ω.令k∶=1.

步1.从初始点x $_{k}^{0}$ 出发, 用局部极小化方法得到目标函数f (x) 的一个局部极小点, 记为:x*k.取一个初始参数q∶=q0, 令i=1, δ>0 (δ可适当选取) .

步2.令F (x, q) =-ln (f (x) -f (x*) +1) -q (x-x*) 2. (4.1)

步3.令 $\bar{x}_{k}^{*} = x_{k}^{*} + δ e_{i}$ .如果 $f (\bar{x}_{k}^{*}) < f (x_{k}^{*})$ , 则令 $x_{k + 1}^{0} ∶ = \bar{x}_{k}^{*}, k ∶ = k + 1$ 转步1.

步4.以 $\bar{x}_{k}^{*}$ 为初始点, 用局部极小化方法解极小化问题 (4.1) , 令 $\bar{x}$ q, x*k为所得极小点, 如果 $\bar{x}$ q, x*k∈int Ω, 则令 $x_{k + 1}^{0} ∶ = \bar{x}_{q, x_{k}^{*}}, k ∶ = k + 1$ 转步1;如果 $\bar{x}$ q, x*k∈∂Ω, 则转步5.

步5.如果q<M, 则令i∶=1, 增加q, 转步4.否则, q:=q0, 转步6.

步6.如果i<k0, 令i∶=i+1, 转步3.否则, 停止, x*k已经是极小化问题的一个全局极小点.

我们验算如下算例:

以下算例的局部极小值点都是在Matlab 7.0的工具箱fmincon, Windows XP, Celeron (R) CPU 2.80 GHZ上得到的.每个算例的数值结果都分别用表格给出, 在运算或绘制的表格中我们用到如下记号:

ei, i=1, …, n:其第i个元素为1, 其它元素为0.

k:表示极小化问题 (2.1) 的局部极小化过程的次数.

q:表示用于寻找第k+1个局部极小值点的参数.

x $_{k}^{0}$ :表示原极小化问题 (2.1) 的第k次极小化过程的初始点.

x*k:表示原极小化问题 (2.1) 的第k个极小值点.

f (x*k) :表示原极小化问题 (2.1) 的第k个极小值点处的函数值.

time:表示算法停止时所占用CPU的时间.

数值试验结果如下:

算例1 Goldstein-Price问题

我们取Ω={-3≤xi≤3|i=1, 2}.以 (1, 1) 为初始点, 用上述算法得到全局极小值点为x*= (0.0000, -1.0000) ;对应的全局极小值为f (x*) =3.0000.

算例2 Three-Hump Camel-back问题

f (x) =2x $_{1}^{2}$ -1.05x $_{1}^{4}$ +x $_{1}^{6}$ /6-x1x2+x $_{2}^{2}$ .

我们取Ω={-3≤xi≤3|i=1, 2}.以 (2, 2) 为初始点, 用上述算法得到全局极小值点为x*=1.0e-005 (-0.4384, 0.1846) ;对应的全局极小值为f (x*) =4.9931e-011.

算例3 Six-Hump Camel-back问题

f (x) =4x $_{1}^{2}$ -2.1x $_{1}^{4}$ +x $_{1}^{6}$ /3-x1x2-4x $_{2}^{2}$ +4x $_{2}^{4}$ .

我们取Ω={-3≤xi≤3|i=1, 2}.以 (0, 0) 为初始点, 用上述算法得到全局极小值点为x*= (0.0898, 0.7127) ;对应的全局极小值为f (x*) =-1.0316.

5 结论

本文给出了一个单参数的填充函数, 这个填充函数是满足定义2.3的, 并给出了相应的算法, 并且数值试验表明了这个算法的可行性和有效性.

参考文献

[1]R.P.Ge.A filled function method for finding aglobal minimizer of a function of several varia-bles[J].Mathematical Programming 46 (1990) 191-204.

[2]R.P.Ge, Y.F.Qin.The global convexizedfilled functions for globally optimization[J].Applied Mathematics and Computation 35 (1990) 131-158.

[3]Levy, A.V.and Montalvo, A..The tunnelingalgorithm for the global minimization of func-tions[J].SLAM J.Sci.&Stat.Comput., 1985, 6 (1) , 15-29.

[4]Yao, T..Dynamic Tunneling Algorithm forGlobal Optimization[J].IEEE Transactions onSystems, Man, and Cybernetics, 1989, 19 (5) , 1222-1230.

[5]Barben, J., Protopopescu, V.and Reister, D..TRUST:A deterministic algorithm for globaloptimization[J].Science 276 (1997) , 1094-1097.

[6]吴至友.全局优化的几种确定性方法[D].上海大学, (2003) 70-91.

[7]王忠, 王永军.用于全局优化的一种有效的单参填充函数[J].Journal of Inner MongoliaNormal University (Natural Science Edition) 35 (2006) 308-312.

[8]You-lin Shang, Ding-guo Pu, Ai-ping Jiang.Finding global minimizer with one-parameterfilled function on unconstrained global optimi-zation[J].Applied Mathematics and Computa-tion 191 (2007) 176-182.

[9]Xian Liu.Two new classes of filled functions[J].Applied Mathematics and Computation149 (2004) 577-588.

[10]Cetin, B.C., Barben, J.and Burdick, J.W..Terminal Repeller Unconstrained SubenergyTunneling (TRUST) for Fast Global Optimi-zation[J].Journal of Optimization Theory andApplications, 1993, 77 (1) , 97-126.

[11]VAPNIK VLADIMIR N.The nature of sta-tistical learning theory[M].New York:Springer-Verlag, 1995.

全局最优搜索篇5

关键词：非线性整数规划,严格路径连通域,填充函数,填充函数法,全局极小点

离散全局优化广泛应用于如排序、物流的供应链及工业设计等领域。在过去的整数规划中, 人们大多局限于线性整数规划的研究, 对非线性整数规划的研究甚少。求解线性整数规划有许多的算法, 如分枝定界法、割平面法等, 但非线性整数规划问题则较困难。对于连续的非线性全局优化问题, 人们已找到了许多种确定性算法, 如填充函数法[1,2], 打洞函数法[3]。对于非线性离散全局优化问题, 最初是把非线性整数规划“连续化”[4], 随后的许多在文献[4]的基础上给出了离散全局优化问题的填充函数定义, 并给出了填充函数。但把离散问题连续化有许多弊病。一般地, 连续情形的填充函数的第3个定义条件在离散的情形不适用。文献[5,6,7,8]中提出了一套求解离散全局优化问题的填充函数法。本文在文献[4]中定义的填充函数的基础上, 构造一个新的填充函数, 详细讨论了其理论性质, 并给出了相应的算法。

求解全局优化问题有2个困难要解决, 一是如何从一个局部解出发找到更好的局部解;二是如何判定一个局部解是全局解。本文探讨第一个问题。

1 基本知识

考虑下列离散全局最优化问题:

(P) :min{f (x) :x∈X⊂Zn}。

这里f:Zn→R, Zn是Rn中的整点集, X是Zn的一个子集。事实上, 令f (x) =∞, x∈Zn＼X, 则上述问题等价于:min{f (x) :x∈Zn}。

定义1 序列{xi} $_{i = - 1}^{u}$ 在X上如果满足x-1=x*, xu=x**;对于所有i, xi∈X;如果i≠j, 那么xi≠xj;并且对于所有的i, 有‖x0-x*‖=‖xi+1-xi‖=‖x**-xu-1‖=1, 则序列{xi} $_{i = - 1}^{u}$ 被称为一个连接不同点x*和x**的离散路径。如果x*和x**之间在X中存在一条离散路径, 那么称它们是连通的。进一步, 如果在X中任意两点都是连通的, 那么称X为连通集。另外, 对于所有的i, 如果‖xi-x*‖<‖xi+1-x*‖, 那么该序列称为严格离散路径。如果x*和x*之间在X中存在一条严格离散路径, 那么称它们是严格连通的。

定义2 d={±ei:i=1, 2, …, n}称为Zn中的坐标轴方向集, 这里ei是第i个单位向量, 即该向量的第i分量为1, 其余分量为0的向量。

定义3 如果x∈Zn, 则集合N (x) ={x, x±ei:i=1, 2, …, n}称为点x的离散邻域。

定义4 如果当x∈X∩N (x*) 时, 有f (x) ≥f (x*) , 那么称点x∈X为f在X上的离散局部极小点。如果当x∈X时, 有f (x) ≥f (x*) , 那么称点x∈X为f在X上的离散全局极小点。

引理假设x, x*∈X, 如果存在i∈{1, 2, …, n}使得x±ei∈X, 那么存在d∈D, 使得‖x+d-x*‖>‖x-x*‖。

定义5 给定 (P) 的一个局小点x*, 如函数p (x) 满足下列条件, 则称其为f (x) 在x处的离散填充函数:

1) :x*是p (x) 在X上的离散严格局大点。

2) :设x∈X, 且f (x) ≥f (x*) , x≠x*, 则x一定不是问题 (P) 的局小点。

3) :设x*是 (P) 的局小点, 但不是全局极小点。设x*1是 (P) 的另一极小点, 且 f (x*1) <f (x*) , 则存在一条连通路径, 使得x*1是在此连通路径上的p (x) 的极小点。

2 一个新的离散填充函数及其性质

问题 (P) 提出一个新的离散填充函数。假定x*是问题 (P) 的一个当前局小点, 则我们给出在x*处的填充函数如下:

$p (x) = \frac{r + \min (0, f (x) - f (x^{*}) + r)}{1 + ∥ x - x^{*} ∥}$ , 这里参数r>0。

将证明p (x) 当参数r>0在满足适当的条件下是一个符合在第2节定义的离散填充函数。

定理1 给定 (P) 的一个局小点x*。若r>0适当小, 则x*是p (x) 在X上的离散严格局大点。

证因为x*为 (P) 的局小点, 则∃x*的一个领域N (x*) , 使得

f (x*+d) ≥f (x*) , 对∀x*+d∈X∩N (x*) , d∈D。

故若 $0 < r < \underset{f (x_{1}) \neq f (x_{2}), x_{1}, x_{2} \in X}{\min | f (x_{1}) - f (x_{2}) |}$ ,

则对∀x*+d∈X∩N (x*) , 有

$f (x^{*} + d) - f (x^{*}) + r \geq 0 ‚ p (x^{*} + d) = \frac{1}{2} r < r = p (x^{*})$ , 故x*是p (x) 在X的离散严格局大点。

定理2 设x∈X, 且f (x) ≥f (x*) , x≠x*。若r>0适当小, 则x一定不是问题 (P) 的局小点。

证设x∈X, x≠x*, f (x) ≥f (x*) 。考虑下列二种情形:

情形Ι 存在di0∈D, 使得x+di0∈X, 且f (x+di0) <f (x*) 。

设 $0 < r \leq \frac{1}{2} \underset{x_{1}, x_{2} \in X, f (x_{1}) \neq f (x_{2})}{\min | f (x_{1}) - f (x_{2}) |}$ , 则2r+f (x+di0) -f (x*) ≤0。

$∴ p (x + d_{i_{0}}) = \frac{2 r + f (x + d_{i_{0}}) - f (x^{*})}{1 + ∥ x - x^{*} + d_{i_{0}} ∥} \leq 0 < \frac{r}{1 + (x - x^{*})} = p (x)$ 。

故在这种情况下, x不是p (x) 的局小点。

情形Ⅱ 若对∀x+d∈X, d∈D有

f (x+d) ≥f (x*) ,

则由引理知, ∃di0∈D, 使得‖x+di0-x*‖>‖x-x*‖。

$∴ p (x + d_{i_{0}}) = \frac{r}{1 + ∥ x + d_{i_{0}} - x^{*} ∥} < \frac{r}{1 + ∥ x - x^{*} ∥} = p (x)$ , 从而x不是p (x) 的局小点。

综合上述二种情况知:x一定不是问题 (P) 的局小点。

定理3

(1) 若f (x1) , f (x2) ≥f (x*) , ‖x1-x*‖>‖x2-x*‖>0, 则p (x1) <p (x2) 。

(2) 若f (x2) ≥f (x*) >f (x1) , ‖x1-x*‖> ‖x2-x*‖>0, 则p (x1) <p (x2) 。

证明较易, 故省略.

定理4 设x*是 (P) 的局小点, 但不是全局极小点。设x*1是 (P) 的另一极小点, 且f (x*1) < f (x*) , 则存在一条连通路径, 使得x*1是在此连通路径上的p (x) 的极小点。

证在X中选择一条路径{xi} $_{i = a}^{μ + 1}$ , 使得x0=x*, xμ=x*1, xμ+1=x*1+d, d由以后决定, d∈D, 且 ‖x0-x1‖=‖x1-x2‖=…=‖xi-1-xi‖=…=‖x*1+d-x*1‖=1。

‖xi+1-x*‖>‖xi-x*‖=1, i=0, 1, 2, …, μ-1。

不失一般性, 假定对i=0, 1, 2, …, μ-1有f (xi) ≥f (x*) 。

(不然, 若∃i0, 使得f (xi0) <f (x*) , 取x0=xi0。若有其他点, 可类似处理) 。

则易证p (x) 在x*到xμ-1的路径上单调下降。

由x*1是 (p) 的极小点, 且根据引理, 可选取d∈D使‖x*1-x*+d‖>‖x*1-x*‖, f (x*1+d) ≥f (x*1) 。取r满足 $0 < r \leq \frac{1}{2} \underset{x_{1}, x_{2} \in X, f (x_{1}) \neq f (x_{2})}{\min | f (x_{1}) - f (x_{2}) |}$ , 则

$p (x_{1}^{*}) = \frac{2 r + f (x_{1}^{*}) - f (x^{*})}{1 + ∥ x_{1}^{*} - x^{*} ∥} \leq 0$ 。

于是对i=0, 1, 2, …, μ-1, p (x*) ≤p (xi) 。

对于点x*1 + d, 考虑下列2中情况:

(1) 若f (x*1+d) ≥f (x*) , 则 $p (x_{1}^{*} + d) = \frac{r}{1 + ∥ x_{1}^{*} - x^{*} + d ∥} > 0$ 。于是p (x*) ≤p (x*+d) 。

(2) 若f (x*1+d) <f (x*) , 则 $p (x_{1}^{*} + d) = \frac{2 r + f (x_{1}^{*} + d) - f (x^{*})}{1 + ∥ x_{1}^{*} - x^{*} + d ∥} \leq 0$ , 由 $∥ x_{1}^{*} - x^{*} + d ∥ > ∥ x_{1}^{*} - x^{*} ∥ ‚ p (x_{1}^{*}) = \frac{2 r + f (x_{1}^{*}) - f (x^{*})}{1 + ∥ x_{1}^{*} - x^{*} ∥} \leq 0$ , 知p (x*1 ) ≤p (x*1 + d) 。

综上所述, 有p (x*1) ≤p (xi) , (i=0, 1, …, μ-1, μ, μ+1) ,

∴ x*1 为x*至x*1+d路径上的p (x) 的极小点。

3 填充函数算法及数值试验

填充函数算法由2个算法。第一个算法用于极小化问题 (P) (见文献[8] 中算法1) , 第二个算法即下列算法, 用于极小化问题填充函数。

算法2:

(1) 给定ε=1×10-8作为极小化问题 (P) 的可接受的终止参数;令D={±ei, i=1, 2, 3, …, n};任选初始点x $_{0}^{(0)}$ ∈X。

(2) 从x $_{0}^{(0)}$ 出发, 利用离散下降算法求的 (P) 的离散布局极小点.令k=0, r=1。

(3) 置x $_{k}^{(0) i}$ =x*k+di, di∈D, i=1, 2, …, 2n, i=1。

(4) 令x=x $_{k}^{(0) i}$ 。

(5) 如果f (x) <f (x*k) , 则以x为初始点, 利用离散下降算法的 (P) 的离散局部极小点x*k+1, 使得f (x*k+1) <f (x*k) 。令k=k+1。转步 (3) 。

(6) 令D0={d∈D:x+d∈X}。如果存在d∈D0, 使得f (x+d) <f (x*k) , 则以x+d* 为初始点 (这里d*=argmind∈D0{f (x+d) }) , 利用算法1求的 (P) 的离散局部极小点x*k+1, 使得f (x*k+1) <f (x*k) 。令k=k+1, 转步 (3) 。

(7) 令D1={d∈D0:‖x+d-x*k‖>‖x- x*k‖}。如果D1=∅转步 (9) 。

(8) 令D2={d∈D1:f (x+d) <f (x) , p (x+d, x*k) <p (x, x*k) }。如果D2≠∅, 则令d*=argmind∈D2{f (x+d) +p (x+d, x*k) };否则, 令d*=argmind∈D1{p (x+d, x*k) }。令x=x+d*转步 (6) 。

(9) 如果i<2n, 则令i=i+1。转步 (4) 。

令 $r = \frac{r}{10}$ 。如果r≥e, 则转步 (3) ;否则, 算法不能找到更好的离散局部极小点, 算法终止x*k作为离散全局极小点。

算例1

minf (x) =g (x) h (x) ,

s.t.xi=0.001yi, -2 000<yi<2 000, i=1, 2。

这里yi是整点, 这里

g (x) =1+ (x1+x2+1) 2 (19-14x1+3x $_{1}^{2}$ -14x2+6x1x2+3x $_{2}^{2}$ ) ,

h (x) =30+ (2x1-3x2) 2 (18-32x1+12x $_{1}^{2}$ +48x2-36x1x2+27x $_{2}^{2}$ ) 。

算例2

minf (x) =100 (x2-x $_{1}^{2}$ ) 2+ (1+x1) 2+90 (x4-

x $_{3}^{2}$ ) 2+ (1-x3) 2+10.1[ (x2-1) 2+

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

s.t.-10≤xi≤10, i=1, 2, 3, 4这里xi是整点。

参考文献

[1] Ge R P. A filled function method for finding a global minimizer of a funciton of several variables. Mathematical Programming, 1990;46:191—204

[2]Ge R P, Qin Y F.A class of filled functions for finding global mini-mizers of a function of several variables.Joural of Optimization Theory and Applications, 1987;54:241—252

[3]Levy A V, Montalvo A.The tunnelling algorithm for the global mini-mization of functions.SIAM J Sci statist Comput, 1985;6 (1) :15—29

[4]Ng C K, Zhang L S, Li D, et al.Discrete filled function method for discrete global optimization.Computational Optimization and Applica-tion, 2005;31 (1) :87—115

[5] Ng C K, Li D, Zhang L S. Discrete global descent method for discrete global optimization and nonlinear integer programming, Journal of Global Optimization, 2007;37 (3) :357—379

[6]Shang Y L, Zhang L S.A filled function method for finding a global minimizer on global integer optimization.J of Computational and Ap-plied Mathematics, 2005;181:200—210

[7]Yang Y J, Liang Y M.Anewdiscrete filled function algorithm for dis-crete global optimization.Journal of Computational and Applied Math-ematics, 2007;202:280—291

全局最优搜索篇6

故障测距能为查找输电线路故障点提供重要依据,对电力系统尽快恢复供电具有重要意义[1,2,3,4,5,6,7,8,9]。长期以来,研究人员提出了多种故障点定位算法,主要是针对单相接地故障的,而较少对相间短路包括两相接地故障点定位方法开展研究。在高压和超高压输电系统中,两相接地故障占全部故障的20%左右,虽然几率远小于单相接地故障,但进一步完善其故障点定位方法仍然有其必要性[10]。

现有的输电线路故障故障测距方法可分为单端测距[10,11,12]和双端测距[13]2类。单端故障测距法只用线路一端的电压、电流测量值,容易获得,具有简单、方便、快速、易于实现的特点,目前仍占有重要地位。单端故障测距法又可进一步分为2种:一是利用工频量,二是利用暂态行波[3,4]。后者虽然测距精度较高,不受过渡电阻、系统运行方式等因素的影响,但存在测距死区,当故障位置距测量点很近或故障初始角接近0°时测距将失败。并且行波法对采样率要求很高,需要专门的录波装置,造成硬件成本的增加。工频法只需较低的采样率,可以结合在现有的录波器或保护装置中,具有较高的工程应用价值。目前基于工频量的单端测距方法多数基于集中参数模型,而高压长输电线上分布电容对测距精度的影响不能忽略,当故障点距测量点较远时,不考虑分布电容会带来较大的测距误差。

因此,本文提出了一种基于电压、电流最小相位差全局搜索的两相接地短路故障单端测距方法,其依据是:线路发生两相接地故障时,由于过渡电阻基本为纯阻性,使得故障点处残压与流过故障支路的电流同相,根据这一特征实施两相接地短路条件下的故障定位。

1 两相接地故障算法原理

为不失一般性,假设输电线为均匀传输线,线路参数恒定,以图1所示假设B、C两相经过渡电阻接地故障为例,介绍比相式单端故障定位算法的基本原理。图中L为输电线长度,x为故障点到M端的距离,R为相间过渡电阻,Rg为两相对地过渡电阻,IBF、ICF为故障口B、C两相对地电流,UB、UC为故障点处两故障相B、C相的残压。

由图1可知,故障处满足如下关系:

将式(1)中的序分量转换为以A相为参考相的序分量,则有:

其中,a=ej120°为旋转因子。

在实际线路故障中,R为实数,则Ud相对于-j(IAF1-IAF2)的相位为0。由于IAF1-IAF2不可测,可以用保护所在侧故障端口处以p为基准相计算得到的i序网中的故障分量电流IFmg1-p-IFmg2-p估算IAF1-IAF2。设在故障后某序网中,保护所在侧故障端口处以p为基准相的i序网中电流分布系数为CMi-p,则IAF1-IAF2=(IFmg1-p-IFmg2-p)/CMi-p,在这里p相就是指A相,代入式(1)有:

即Ud相对于-j(IFmg1-p-IFmg2-p)/CMi-p的相位为0,记作:

为了应用式(3)进行测距,可以采用全局一维搜索的方法,对全线路的电压、电流分布进行估算,找出其中相位差最小的电压与电流,其对应的距离即为故障距离。为了精确地考虑分布电容的影响,采用贝瑞隆模型计算全线的电压分布。

下面以BC两相接地短路故障为例阐述本算法的流程。由于线路一端(假设为M端)的三相电压UMA、UMB、UMC和三相电流IMA、IMB、IMC可以测得,通过Karrenbauer相模变换,将三相电压、电流变换到αβ0坐标系,即:

在估算线路上距离M端x处的电压时,根据图1可列出以下电压方程[14]:

其中,i=α,,β,0,代表各模量号,Uxi为输电线路上距M端x处电压的模分量。假设线路单位长度的各模电阻、电感、电容、电导可分别表示为Ri、Li、Ci、Gi,则为输电线路每公里的各模传播系数,为输电线路各模波阻抗。其中,α、β模分量的各个元件参数可用正序参数代入,0模参数用零序参数代入。

在应用搜索法时,按一定步长在[0,L]范围内进行搜索,找到满足式(3)的电压,对应的x即为故障距离。当搜索距离为x时,将M处的各模分量分别代入式(6),得到该处的模电压和电流:

通过相模反变换可得到x处的三相电压和三相电流:

即可以得到UBx、UCx。

因此,BC两相接地短路测距公式为:

其中,i代表各序分量,x为故障点距离,p为非故障相别。

在近似计算中,CMi-p可看作是实数,则可以认为故障点处Udx与-j(IFmg1-p-IFmg2-p)同相位,在此令φx=arg{Udx/[-j(IFmg1-p-IFmg2-p)]}。因此,在逐点搜索的过程中,(IFmg1-p-IFmg2-p)与Udx相位差绝对值最小的点,即min|φ|x对应的x即为所求故障距离。

2 仿真验证

为验证本算法的正确性,采用EMTDC建立图2所示的500 kV、350 km2机模型,进行了大量的仿真试验。其中线路采用平武线(平顶山—武汉)参数。系统中各参数如下:ZMS1=(0.2534+j20.046)Ω,ZNS1=(2.82+j40.092)Ω,ZMS0=(0.1121+j6.723)Ω,ZNS0=(0.224+j12.546)Ω,X1=0.278 3Ω/km,R1=0.027Ω/km,C1=0.012 7μF/km,X0=0.649 4Ω/km,R0=0.194 8Ω/km,C0=0.009μF/km。仿真中,原始采样率为每周期96点,采用butterworth低通滤波器模拟保护装置中的前置低通滤波环节。低通滤波器的输出经全周Fourier差分算法处理后形成各个相量,用于测距算法。为证明算法能普遍应用于录波装置和继电保护装置,在利用Fourier算法前采样率降为每周期24点。

图3给出了一个计算实例,用于说明搜索过程中相位变化的单调性。当距M侧330 km处发生BC两相金属接地(过渡电阻为0.05Ω)短路时,根据贝瑞隆线路模型,以0.1km为步长估算出线路上各点的故障相电压、电流,进而计算其相对保护所在侧故障端口处负序电流的相位差,仿真结果见图3。为使保护线路末端短路时也能可靠定位,搜索的距离可适当大于线路实际长度,这里采用350 km。

由图3(a)可见,在搜索距离由0~350 km的过程中,该相位差从正值单调变化到负值,这就验证了上述关于相位随距离单调变化的观点。

由图3(b)可见,在x=299.933 3 km处,相位差绝对值陡降为最小,在其他位置基本保持平稳变化,这就验证了算法的有效性和测距结果的唯一性。

在算法的实际应用中,通过平移数据窗得到12个点(半个周期)的测距结果后进行平滑处理,可进一步提高测距结果的稳定性。

通过改变系统参数、故障点位置、过渡电阻的大小等多个影响测距精度的因素,充分考察了比相式算法的测距结果。由于篇幅有限,下面从大量的仿真实例中分类给出几种有代表性的仿真结果。

采用文献[15-16]提供的2种典型算法与本文提出的算法进行对比。文献[15]对单端测距算法进行了较全面的考察,其中之一为故障电流相位修正法,将其记为算法1,具体计算公式见文献[15];文献[16]提出了一种基于单侧信息的故障测距修正算法,将其记为算法2,具体计算公式见文献[16]。

表1给出了不同故障点发生两相接地短路时算法1、算法2和本文算法的测距效果对比。误差定义为:(测得距离-实际距离)/线路总长度×100%。由表1中数据可见,基于集中参数模型算法的测距误差与故障距离呈正比,这是由于模型忽略了线路分布电容。本测距算法采用分布参数模型,从而消除了分布电容带来的误差,测距精度达到实际工程应用的要求。

表1同时也证明了基于分布参数线路模型的算法的测距精度高于基于集中参数模型的算法,通过比较3种算法发现,比相式算法的精度最高。

表2给出了BC两相接地短路时,在相间过渡电阻和对地过渡电阻不同组合下,本算法测得的故障距离结果。从表中可以发现测距的精度与对地过渡电阻无关,仅与相间过渡电阻有关,随着相间过渡电阻的增大,测距的精度跟着降低。即使在相间过渡电阻为100Ω的高阻情况下,测距误差也在0.5%左右,能满足工程需要。

表3给出了故障距离为100 m、相间过渡电阻为1Ω、在不同故障发生角时的测距结果。由表3可见,故障发生角基本不影响定位精度。

3 结论

【全局最优搜索】推荐阅读：

全局最优05-26

全局信息05-14

全局故障05-25

全局策略11-10

全局安全11-16

全局信息安全07-07

全局阈值分割07-31