算法的稳定性

算法的稳定性（共8篇）

算法的稳定性 篇1

0 引言

关于边坡的稳定问题涉及到水利工程、采矿工程和许多关系到民生问题,研究边坡的稳定性问题对于工程的稳定性具有重大的意义。我们以前用过的平衡方法出现一个共同难点就是以失效的上条能够被分解为假设的依据。将我们所使用的所有方法的过程总体上可以总结为:却定一个滑面,然后对其剪压静力分析,k为整个滑面的抗剪强度与实际产生的剪应力之比,计算出相应的安全系数k,再通过计算kmin确定其所对应的临界滑面。

1 边坡稳定性分析计算的条分法

对于我们在施工时形成的边坡的问题,若设计的边坡过于陡峭,就容易发生滑坡或塌方,出现事故,设计的边坡过缓,会延长施工时间,增加施工量。在工程实践中,会遇到如何确定边坡坡度,需要对边坡的稳定性进行计算和分析,并计算边坡的合理断面等相关的问题,为了保障临近建筑物的安全和使用,要避免超出建筑界限的规定。

对上坡稳定性计算分析方法中,极限平衡法条分法是一种比较简单、常用的方法,它是把滑动面上的上体进行分解,分成若干个部分,然后对每个部分进行计算分析的一种边坡稳定的方法。它是计算上体外力与内部强度所提的供抗力之间的平衡,通常是在边坡在临界状态下进行的。这是我们对边坡稳定分析时常用的方法之一,而且这种方法适用的范围广,不需要考虑坡面表面是否平整、质体是否均匀。条分法首先假定边坡的斜面是一滑裂面,然后运用条分法,将滑裂面上体分解成若干个垂直上条滑裂面,然后对这些小得滑裂面进行力合力矩分析,通过这种方法的计算,我们就可以推出最危险滑裂面位置及相应的最小安全系数。求出在极限平衡状态下,滑裂面上体稳定的安全系数。

因为土坡稳定的安全系数是用滑裂面的抗滑力矩与滑动力矩之比来定义计算的。计算时,我们假定上坡稳定问题是一个整体计算的问题,滑裂面是个柱体面,在计算中不考虑土条之间的相互作用力。影响边坡稳定的载荷因素主要有:外部载荷、地下水和边坡的自重等;边坡几何形状的主要计算指标有:边坡高度(H)和边坡的坡角(α);岩上体力学性质的主要控制指标有:内摩擦角(ф)和上体的内聚力(c);边坡岩上体的物理力学性质、边坡的几何形状和外部载荷,是影响边坡稳定性的控制变量主要三大类。将滑面上的土体分成若干垂直的土条,就是运用条分法分析边坡的稳定性。根据上图1所示,就可以确定边坡安全系数的公式。

上式中k是滑裂面的安全系数,un表示孔隙压力比,cn代表土壤的内聚力,θn是经过土条中点的半径与水平线的夹角,准n是土条的摩擦角,用bn表示土条的宽度,Wn代表土条的质量,n代表土条编号。

2 基于遗传算法的岩土边破稳定性分析方法

在极限平衡理论基础上,我们运用分析土坡的圆弧滑面法,来计算滑裂面的安全系数。边坡稳定分析是要找出最小安全系数的滑动面,它要对大量不同潜在滑动面进行计算分析。在复杂的设计中,需要控制参数(坡度、内聚力c、摩擦角准等),来得到解决滑裂面的安全系数问题。“Monte Carlo”方法是通过系统的搜索方法,实质上是一种空间随机搜索的方法。遗传算法要求有一个染色体表示,用来对参数空间编码、一个适应度函数用于评价所有染色体、一组遗传操作用于产生新染色体和一组概率用于控制遗传操作。遗传算法已经广泛应用于解决类似边坡稳定性问题的多极值优化问题。主要包括以下几个主要部分:解的编码和译码方式、函数初始种群的产生方法、适应度函数的定义,遗传计算的操作主要包括选择操作、变异操作和交叉操作。

2.1 遗传算法适应度函数的建立

遗传算法在计算的过程中对外部的信息基本不利用,主要是以适应度函数作为计算的依据,在确定的种群中,对个体的适应度值进行计算和搜索。在实际计算的过程中,适应度函数的选取是否恰当,影响着遗传算法的收敛速度和搜索能力。把个体i的适应度函数定义为:Fi=C-ki。

式中:fi为种群中第i个的适应度函数,C是常数,它的选择要保证个体的适应度函数在计算过程中始终正值。

2.2 算法的解的表达

遗传算法是在二进制下的环境下运行的,要将二进制与十进制进行转换。我们采用二进制编码,将它们换为区间[ximin,ximax]上的十进制数的公式为

其中:ximin和ximax是依据先验信息来确定搜索区间的最小值和最大值,Q为二进制的长度,gq为第q个计算基因。

2.3 Monte Carlo的算法选择

我们常说的轮盘赌选择计算方法中,个体被中的概率就遵循Monte Carlo的算法选择,个体被选中的概率与其适应度和种群的平均适应度的比值成正比。依据自然法则,生命力强的物种能够征服弱小的物种这一规律,在物种繁殖操作过程中,旧的物体群体中会“随机”选择符号串生成一个新的计算种群,但选择要依据一定的规则,并非是完全随机的,要基于一个符号串对计算群体的适应度。

2.4 交叉操作

采用单点交叉方法,首先以交叉概率pc从种群中随机选择2个个体p1、p2,在{1,2,Q}内随机选择一个数Cn,Cn代表交叉方式的位置,称为交叉点,然后交换这2个个体在交叉点的基因,得到2个新个体,如图2所示。

2.5 遗传算法的变异操作

依据相关的法规,对种群进行计算,对与个体pi的第j位,在[0,1]范围内随机生成一个数pran,若pran>pm,则保持第j位不变;否则,对第j位进行取反运算,如图3所示。它的主要目的是使得算法能够具有跳出局部极小的应变能力,产生新的操作个体。

如果滑裂面为圆弧形滑移面,边坡稳定的搜索变量要包括滑弧圆心xo,yo坐标和半径r。运用遗传算法来确定边坡最小安全系数的计算方法是:首先却立边坡稳定性分析的力学模型和安全系数计算方法,用如图1的方法确定偏移的角度和上面求安全系数的公式进行计算,其次是确定遗传算法的二进制编码和如何设定参数,计算出边坡稳定性的最小安全系数,用给定边坡的几何图形和力学参数来计算确定滑移面中心和半径的搜索范围。

3 遗传算法的应用举例

如下图4所示,边坡角26.50,水平投影长度40米,边坡高20米,边坡的其他力学参数如表1所示。将遗传算法应用于实际的计算中,我们来研究一个简单的、质地均匀的边坡最小安全系数计算、搜索问题。

上表1中质地均匀边坡的力学参数主要用于边坡稳定性估计,遗传算法运行主要参数如下:变异概率0.05,交叉概率0.85,种群规模200,下表2给出了不同的计算方法搜索得到边坡稳定性德最小安全系数。

在简单的计算等到实际的效果以后,接着计算一个比较复杂的边坡稳定性的计算方法,如图5所示,该岩土边坡主要由2种材料和性能不同的土层组成,边坡的垂直高度为10米,水平投影为8米,边坡倾斜为角51.3°,边坡的顶部有1kN·m-1的均布荷载,通过运用遗传算法,可以得到相应最小安全系数,在图5中给出了运用遗传算法计算和搜索到的临界滑移面的结果和边坡的最小安全系数。

4 小结

本文的目的主要是说明对于复杂的上工边坡,我们可以运用遗传算法将复杂的问题进行分解处理,间接的求出系统的最小安全系数,既快捷又方便。遗传算法主要运用一种基于遗传学原理的方法来计算复杂的工程问题,能够很好的避免局部安全系数的最优解问题。

摘要：非线性优化方法主要缺陷在于当边坡土层为非均质复杂条件时,无法保证搜索到安全系数的全局最小解,而只能搜索到局部极小解。基于遗传算法,建立了搜索岩土边坡稳定性分析最小安全系数和滑移面中心坐标与半径的数值方法。问题的可行解在变量搜索区间内搜索,包括滑弧的圆心坐标和半径。数值模拟结果表明,遗传算法搜索到的边坡稳定最小安全系数与理论解是一致的。

关键词：边坡稳定,遗传算法,滑移面

参考文献

[1]高大钊,袁聚云,主编.土质学与土力学[M].北京:人民交通出版社,2001.

[2]孔祥元.控制测量学[M].武汉:武汉测绘科技大学出版社[M],l998.

[3]李守巨,刘迎曦,王登刚.基于遗传算法的岩体初始应力场反演[J].煤炭学报,2001(1).

[4]王登刚,刘迎曦,李守巨.岩土工程位移反分析的遗传算法[J].岩石力学与工程学报,2000(19).

一类具有时滞的金融系统的稳定性 篇2

关键词 时滞； Hopf 分叉； 金融系统

中图分类号 O175.17 文献标识码 A

1 引 言

金融稳定是经济可持续发展的基础和前提， 亚洲金融危机后， 金融稳定和安全问题引起了全世界的广泛关注和重视. 金融机构和金融市场构成巨大的金融系统， 金融系统是一个开放的复杂系统， 是人造系统. 参考文献[1-3]， 金融系统和生态系统有很多相似之处， 运用生态系统的相关理论可以研究金融系统的相关问题.

2 模型

参考文献

[1] Chant Joha. Financial stability as a policy goal[R]. Canada：Bank of Canada Technical Report No. 95， 2003，9， 3-4.

[2] Crockett， Andrew. The theoey and practice of financial stability[M]. United Kingdom： Conville and Caius College Cambridge， 1997.

[3] 刘淄， 王顺庆. 浸润稳定性与生态稳定性[J]. 生物数学学报， 2009， 26（4）， 657-664.

[4] S RUAN， J WEI. On the zeros of transcendental functions with applications to stability of delay di erential equations with two delays[J]. Dyn. Contin. Discrete Impuls. Syst. Ser. A Math. Anal，2003，10：863-874.

[5] B HASSARD， D KAZARINO， Y WAN. Theory and applications of hopf bifurcation[M]. Cambridge： Cambridge University Press ，1981.

[6] 李立华， 张强. 基于混沌理论的金融系统稳定性研究[J]. 经济数学，2010，27（4）：67-72.

算法的稳定性 篇3

随着国民经济、电力行业的发展,电力系统形成了一个大规模的非线性互联网络,其远距离送电及重负荷运行导致运行点非常接近电压稳态临界点,使电力系统面临电压失稳的问题。电压稳定问题可用暂态和中期仿真来进行分析,但它们不能提供灵敏度信息和系统稳定程度的信息,而静态电压稳定分析因其简单易行且能提供系统电压崩溃预警和防御措施而受到极大的重视和发展。最小奇异值作为静态电压稳定分析指标,在实际电力系统中得到较广泛的应用。文献[1]给出了最小奇异值对系统参数的灵敏度算法;文献[2]结合最小奇异值指标对江苏电网的稳定性做了分析,给出了一种工程上实用的稳定程度判定方法。

本文以最小奇异值作为静态电压稳定裕度指标,并利用模态分析计算电力系统的灵敏度,用于确定薄弱节点的分析,最灵敏的控制变量或扰动就是对系统影响最大的因素。根据稳定裕度和灵敏度信息,为运行人员提供重要的预防手段,从而采取相应的措施来提高系统的电压稳定性。

目前多机电力系统中电压失稳的机理尚不完全清楚,导致目前对于电压崩溃的研究理论尚未完善,但普遍认为,有载变压器的离散调节、PV节点电压以及电容补偿装置等控制变量对电压稳定有较大的影响[3,4,5,6,7,8,9,10,11],利用优化算法对控制变量进行优化,可以有效地提高静态电压稳定裕度,从而改善电压稳定预防控制措施。本文目的是通过综合算法对有载变压器分接头、PV节点电压及无功补偿装置进行优化调整,以电力系统电压稳定分析为研究方向,考虑负荷的静态特性对电压稳定的影响,对最小奇异值与灵敏度在电压稳定分析中的应用作详细的论述。

1 理论基础

文献[3,4]设矩阵A∈Rn×n,利用SVD分解,可以证明存在单位正交矩阵M和V,使得

$\mathit{V}{}^{\text{Τ}}\mathit{A}\mathit{{\rm M}}=\left[\begin{array}{cc}\Lambda & 0\\ 0& 0\end{array}\right](1)$

上式中,Λ=diag(δ1δ2…δr),且有δmax=δ1≥δ2≥…δr=δmin≥0为矩阵A的奇异值,设M的第i列向量ui为矩阵A的第i个奇δi异值的右奇异向量,V的第i列向量vi的矩阵A的第i个奇异值的左奇异向量。

1.1 系统模型

在对电力系统进行静态分析时,极坐标形式的潮流方程为[3]

${\rm P}{}_{Gi}-{\rm P}{}_{Li}=U{}_i{\displaystyle \sum _{j\in i}U}{}_j(G{}_{ij}\cos \theta {}_{ij}+B{}_{ij}\sin \theta {}_{ij})(2)$

$Q{}_{Gi}-Q{}_{Li}=U{}_i{\displaystyle \sum _{j\in i}U}{}_j(G{}_{ij}\sin \theta {}_{ij}-B{}_{ij}\cos \theta {}_{ij})(3)$

其中

$\begin{array}{l}{\rm P}{}_{Li}={\rm P}{}_{Li0}+\lambda {\rm P}{}_{Li0}\kappa {}_{1}Q{}_{Li}=Q{}_{Li0}+\lambda Q{}_{Li0}\kappa {}_2\\ {\rm P}{}_{Gi}={\rm P}{}_{Gi0}+\beta {\displaystyle \sum _{j=1}^{n{}_{pq}}(}{\rm P}{}_{Li}-{\rm P}{}_{Li0})\beta =\frac{{\rm P}{}_{Gi0}}{{\displaystyle \sum _{j=1}^{n{}_{pq}}{\rm P}}{}_{Gj0}}\end{array}$

式中,PGi、QGi分别为发电机的有功、无功出力;PLi、QLi分别代表有功、无功负荷;λ为负荷增长水平,k1、k2分别为负荷增长率;Ui、Uj、θij分别为节点i和j的电压幅值和节点i和j之间的电压相角差;Gij、Bij分别为节点导纳阵第(i,j)个元素的实部和虚部,l为步长,K1、K2、K3为系统常数。在运行点附近将系统的潮流方程(3)、(4)线性化,则可得到修正方程为

$\left[\begin{array}{c}\text{Δ}\mathit{{\rm P}}\\ \text{Δ}\mathit{Q}\end{array}\right]=\left[\begin{array}{c}\mathit{{\rm H}}\mathit{{\rm N}}\\ \mathit{J}\mathit{L}\end{array}\right]\left[\begin{array}{c}\text{Δ}\mathit{\theta }\\ \text{Δ}\mathit{U}/\mathit{U}\end{array}\right](4)$

式中:ΔP、ΔQ分别为节点有功和无功功率的不平衡量子列向量;Δθ、ΔU/U分别为节点电压相角与电压幅值的不平衡量子列向量;H、N、J和L为分块矩阵,其中H和N中的元素分别为节点有功功率对节点电压角度θ和电压幅值U的偏导数,J和L中的元素分别为节点无功功率对节点电压角度θ和电压幅值U的偏导数。

1.2 应用奇异值分析指标

满秩矩阵A的奇异值从数学意义上讲可以解释为对应超椭球平面的半轴长度,A的最小奇异值δn-1是A到秩为n-1的奇异矩阵集合的最小距离[4,5]。用矩阵J表示式(4)中的雅可比矩阵,若J∈A∈Rn×n,对其进行奇异值分解可得

$\mathit{J}=\mathit{V}\mathit{\Lambda }{\rm M}{}^{\text{Τ}}={\displaystyle \sum _{i=1}^n\delta }{}_i\mathit{v}{}_i\mathit{m}{}_i^{\text{Τ}}(5)$

式中:n为雅可比矩阵J的维数;V和U均为n×n阶的正交矩阵;Λ为由奇异值δi组成的对角矩阵;奇异向量vi和ui分别为V和U中δi所对应的列向量。令δmin为最小奇异值,当δmin≠0时,有

$\left[\begin{array}{c}\text{Δ}\mathit{\theta }\\ \text{Δ}\mathit{U}/\mathit{U}\end{array}\right]=\mathit{{\rm M}}\mathit{\Lambda }{}^{-1}\mathit{V}{}^{\text{Τ}}\left[\begin{array}{c}\text{Δ}\mathit{{\rm P}}\\ \text{Δ}\mathit{Q}\end{array}\right]={\displaystyle \sum \delta }{}_i^{-1}\mathit{m}{}_i\mathit{v}{}_i^{\text{Τ}}\left[\begin{array}{c}\text{Δ}\mathit{{\rm P}}\\ \text{Δ}\mathit{Q}\end{array}\right](6)$

由式(7)可知,当一个奇异值几乎为零时,任何小的扰动将会造成状态变量的巨大变化,当系统处于弱稳定状态、接近于电压崩溃点时,系统响应完全由最小奇异值决定。因此雅可比矩阵的最小奇异值的大小表明了电压稳定的相对临近程度。

1.3 优化数学模型

最小奇异值作为静态电压稳定裕度[4],系统网络中最大的最小奇异值与系统中的一些控制变量所处的位置相关,通过对控制变量K进行优化,可使得最小奇异值变大。

在此,目标函数为最大的最小奇异值,即

$\min \left|\delta {}_{\lim }\right|(7)$

等式约束条件为式(4),状态变量的不等式约束为

Umin≤U≤Umax (8)

控制变量的不等式约束条件为

$\{\begin{array}{l}\mathit{U}{}_{G\text{m}\text{i}\text{n}}\le \mathit{U}{}_{\mathit{G}}\le \mathit{U}{}_{\mathit{G}\text{m}\text{a}\text{x}}\\ \mathit{{\rm K}}{}_{n\text{m}\text{i}\text{n}}\le \mathit{{\rm K}}{}_n\le \mathit{{\rm K}}{}_{n\text{m}\text{a}\text{x}}\end{array}(9)$

式(8)中,U、Umin、Umax分别为PQ节点当初电压及其下限与上限值;式(9)中,UG、UGmin、UGmax分别为PV节点当初电压及其下限与上限值,Kn、Knmin、Knmax为变压器分接头当初值及其下限与上限值。

2遗传退火综合法及模态分析在静态电压稳定中的应用

2.1 遗传算法

遗传算法既可以适用于连续性变量也能很好地处理离散变量,能够提供一种求解复杂系统优化问题的框架,对问题的种类有很强的鲁棒性[12,13],但在运行早期个体差异较大,当采用经典的轮盘赌方式选择,后代产生个体数与父个体适应度大小成正比,因此在早期容易使个别好的个体的后代冲斥整个种群,造成早熟;在遗传算法后期,适应度趋向一致,优秀的个体在产生后代时,优势不明显,从而使得个体种群进化停滞不前。

2.2 模拟退火法

模拟退火算法来源于固体退火原理[13,14]。用固体退火模拟组合优化,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法。由模拟退火原理可知,其计算过程简单、通用、鲁棒性强,适用于并行处理,可用于求解复杂的非线性优化问题,但如果降温过程足够缓慢,得到的解的性能会比较好,与此相对的是收敛速度太慢;如果降温过程过快,很可能得不到全局最优解。

2.3 遗传和模拟退火法综合策略

根据两种优化算法的不同特点,可将遗传算法与模拟退火法相结合,构造新的重组策略。在温度高时(遗传算法的前期),适应度相近个体产生的后代概率相近;而当温度不断下降后,拉伸作用加强,使适应度相近个体适应度差异放大,从而使得优秀的个体优势更明显,同时可以确保在全局范围内寻找最优点。此混合策略主要包括编码法则、参数确定、种群初始化、计算适应度、遗传操作、模拟结果等步骤[14,15]。如图1所示。

2.3.1 种群初始化

由文献[12]可知,染色体的长度影响优化算法过程和结果,所以在优化计算中,通过控制变量值的范围与精确度的要求确定染色体的长度,这种编码规则简明有效。

遗传算法和模拟退火都不依赖于初始值,所以随机产生pop_size(pop_size为种群大小)个作为初始种群,为了克服遗传算法陷入局部极值而导致早熟现象出现的可能性增加,本文规定pop_size=η×M(η为1.0～2.0之间的实数),即至少有M个样本,才能使得初始群体在空间集中均匀分布。

2.3.2 温度参数的控制

温度参数是退火算法的关键参数之一,主要包括起始温度的选取、温度的下降方法和停止温度的确定等[13]。模拟退火算法的全局搜索性能也与退火速度密切相关,一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件,本文采用如下所示的降温方式:T(k+1)=αT(k),通过每一温度的迭代和温度的下降,最后满足终止条件而停止。

2.3.3 群体更新的Metropolis准则

采用Metropolis判别准则产生下一代群体中n-1个个体。在父代群和子代群中,分别随机选取个体i和j,i和j竞争进入下一代群体的准则采用Metropolis判别准则[13,14],即i和j被选取的概率为

$p(i)=\{\begin{array}{l}1,f(i)\ge f(j)\\ \exp \left(\frac{f(i)-f(j)}{{\rm T}}\right)\end{array}(10)$

$p(j)=\{\begin{array}{l}0,f(i)\ge f(j)\\ 1-\exp \left(\frac{f(i)-f(j)}{{\rm T}}\right)\end{array}(11)$

其中,f(i)、f(j)分别为i和i的适应度,T为温度值。

2.3.4 遗传算子操作

此过程包含选择、基因重组、变异。初始种群产生后,经过适应度值的计算后,根据代沟ρ(ρ为选择个体占种群个体的比例)采用经典轮盘赌方式选择规模为ρ×pop_size个新的种群用来繁殖子代,再利用精英策略从父代中选择(1-ρ)×pop_size个最优个体补充到子代中,这样可以保证子代的最佳个体绝不比父代最佳个体差。由遗传算法操作可知,基因重组或变异可采用多点操作或单点操作,多点交叉往往会破坏一些好的基因组合,为了将破坏降至最低提高计算效率,本例采用单点法进行重组或变异。

2.4 模态分析法

利用最小奇异值只能知道总体系统的稳定裕度,不能分析每个节点对负荷增加时的灵敏度,但通过模态分析,考虑负荷的增长模式,可以确定节点稳定程度。一方面电压幅值与无功功率强耦合而与有功功率弱耦合, 在求取当前系统灵敏度时,常常不计有功功率的影响, 只考虑无功和电压的关系[16],令有功注入保持不变, 即ΔP=0, 根据式(4)得

ΔQ=(L-JH-1N)ΔU/U (12)

因此得到系统的电压/无功线性化关系化模型

ΔV/V=(L-JH-1N)-1ΔQ (13)

式中,(L-JH-1N)-1为电压/无功灵敏度矩阵,它反映系统的电压与无功之间的变化关系。

从有功和角度的关系入手,另一方面对系统稳定性进行分析,在式(4)中令ΔQ=0则:

Δθ=(-H+NL-1J)-1ΔP (14)

得出系统dθ/dP的灵敏度信息。

通过(9)、(10)式子,可以反应系统中薄弱节点,有利于对系统进行控制。在dU/dQ信息中,它的第i个对角元素是节点i的电压/无功灵敏度。正的灵敏度值表示系统的稳定运行,灵敏度愈小,系统愈稳定,负的灵敏度值表示系统不稳定运行。同样对dθ/dP分析可知,灵敏度值越大,表示该节点对有功的灵敏度大。利用(9)、(10)分析可以较准确地确定功率传输极限,辨识系统电压薄弱点和易发生电压失稳的区域,找出有效的校正控制方式和控制地点。

3 算例仿真

本算例是IEEE 9节点电力系统,其系统结构如图3所示。

本文分别用最小奇异值算法、基于最小奇异值的遗传与退火综合法分别对IEEE 9节点系统,在初始运行方式下以电压稳定裕度为目标函数进行电压稳定分析,以所有PV节点电压、K1、K2、K3分接头为优化参数,PV节点电压是连续优化变量,变压器分接头为离散变量。仿真结果如表1、图4和图5(a)、(b)所示。

由表1得,通过比较两者算法结果,可知当前最小奇异值离最大的最小奇异值(即崩溃点)的稳定裕度,从而为运行人员做出快速的判断。

由图3知,随着运行代数的增加,目标值也逐渐增大,当达到一定代数后,变化减小,稳定裕度值趋向稳定;由于在遗传算法中插入模拟退火法,因此改进了曲线收敛特性,提高收敛速度,可以有效地克服遗传算法“过早收敛”问题,继续向全局最优解方向搜索,提高了电压稳定裕度值。

本文利用模态分析,可以得出系统网络中各节点灵敏度信息指标,作为判断系统节点的薄弱情况,有利于调节控制,预防系统的事故发生。表2、3为IEEE 9节点系统利用模态分析得出的各种灵敏度信息。

由表2得,在dV/dQ信息中,在某运行方式基态时负荷节点都为正值,相对处于稳定状态,相比较各节点对于无功功率的注入稳定程度,负荷节点5最不稳定,应密切关注此点,其它点不稳定程度依次为6、8、7、4、9节点。在极限运行条件下灵敏度值全为负值,说明各节点都处于不稳定状态,按照灵敏度大小排序,不稳定程度依次为5、6、7、4、8、9节点,其中5号节点可能最先失稳,应先对5号节点采取相应的控制方式,以防事故的扩散。由表3可知,对于dθ/dP灵敏度,2号节点对有功功率的注入最为敏感,通过灵敏度排序,可知其它节点在基态与极限运行下相对薄弱程度,从而调节相应的控制措施。综合表2、3可知同时对注入无功功率和有功功率都比较敏感的点,从而做出相应的措施。

4 结束语

本文在静态电压稳定分析的优化数学模型下,考虑了不等式约束条件,使计算更符合实际。通过本文优化算法,可以较准确地找到最大的最小奇异值,有效地提高系统的稳定裕度,不需要额外的投资,经济实用。

本文算法物理概念明确,收敛性好。将模拟退火算法融合到遗传算法,充分考虑了种群竞争优胜劣汰分布程度,有效地改善了寻优能力,并很好地克服了控制变量的离散性与连续性相混合难以处理的问题。对IEEE9节点系统的仿真计算结果表明本方法在提高电压稳定裕度上的有效性。

利用模态分析,可以较准确地找到系统薄弱节点,进一步提供了预防判断措施,从而预防电压稳定事故的发生。

摘要：由于远距离送电及重负荷运行导致电网运行在电压稳定裕度较低的工作点,因此如何改善静态电压稳定预防控制受到广泛的关注。最小奇异值分析法在静态电压稳定研究中得到了广泛的应用,利用最小奇异值作为稳定裕度指标,提出了一种基于最小奇异值的遗传退火综合优化算法,通过优化有载调压变压器和PV节点电压量,改善电压稳定裕度,并在此基础上,利用模态分析,计算灵敏度信息确定电网的薄弱节点。利用IEEE9节点系统,在计算灵敏度时考虑负荷增长模型,用遗传退火综合法对稳定裕度计算,验证了算法的有效性。

算法的稳定性 篇4

移动Ad Hoc网络[1]是一种多跳、自组织、分布式的无线网络, 它不需要集中式的网络管理和基础设施。针对Ad Hoc网络的特点, 国内外学者提出了很多路由协议。相对于单径路由协议而言, 后备路径路由协议更能满足容错、路由可靠性要求, 因而成为该领域的研究热点。

本文讨论将成本函数应用到后备路由选择中, 再结合地理位置预测模型预测链路稳定性来确定主备路由, 利用此算法改进AODV协议。最后通过软件仿真的手段, 论文实现了LS-BPR协议, 并评价了它的路由性能。通过仿真验证算法性能。

2 多路路由算法分析

随着对Ad Hoc网络的研究的不断深入, 单路路由协议的研究己经相对成熟。但是, 简单的单路路由协议还不能满足容错、路由可靠性等更高层次的路由要求。多路路由恰恰是解决这些问题的一个很好的途径。

3 基于成本函数的后备路径路由算法实现

3.1 成本函数中相关参数的定义及计算

在这里提出一种BPR (Backup Path Routing) 算法, 它是引入了成本函数作为后备路径的选择原则。在主路径确定之后, 再通过主路径和所选路径计算成本函数值, 来确定需要的后备路径。

为了能够找到一个路由可靠度的衡量标准, 我们需要一个近似的计算公式, 来对路由有效期进行计算和比较。为此, BPR算法引入了成本函数的概念。给定备份路由对 (λ, λ′) , 当路径长度|λ′|越小;节点相似度L (λ, λ′) 越小;独立子路径R (λ, λ′) 越大时, 备份路由对的路由有效期都会越长, 路径就会越可靠。因此用备份路由对 (λ, λ′) 的成本函数值C (λ, λ′) 的启发式来估算路由可靠度。成本函数值与路由有效期成反比, C (λ, λ′) 的值越小, 备份路由对就越可靠。

定义:假设λ是主路径, λ′是后备路径, L (λ, λ′) 是主备路径对 (λ, λ′) 的链路相似度, R (λ, λ′) 是主备路径对 (λ, λ′) 不相交子路径的数目, |λ′|表示后备路径λ′的总跳数, 则主备路径对的 (λ, λ′) 的成本函数定义为:

由于主路径上节点由于频繁的移动造成无线链路发生断裂时, 由于后备路径与主路径公用节点的数目较少, 所以也就降低了后备路径也同样发生断裂的可能性, 所以最可靠的后备路径就要选择使C (λ, λ′) 值最小的后备路径。

3.2 基于链路稳定性预测的后备路径选择算法研究

基于ARIMA模型分析方法的基本思路是:对于非平稳的时间序列, 用若干次差分使其成为平稳序列, 再用ARMA (p, q) 模型对该平稳序列建模, 之后经反变换得到原序列。并且根据样本自相关函数、偏自相关函数的统计特性来判断随机序列适合哪一模型, 进而确定模型阶数[2]。

为了使用ARIMA模型改善BPR算法的性能, 所以本文提出了基于运动轨迹预测链路稳定性的后备路径路由算法LS-BPR (Link Stability Prediction Algorithm based on Backup Path Routing) 。

LS-BPR算法的基本思想是, 在确定源节点到目的节点的后备路径时, 考虑节点的移动性所带来的链路稳定性的变化和链路的传输延迟, 用链路有效时间来衡量链路稳定性, 利用ARIMA预测模型预测节点移动性, 提前得知下一时刻该节点的地理位置[3], 即能够提前预测节点的运动轨迹, 减少了后备路径在下一时候断开的可能性。通过GPS系统获取节点的地理位置, 形成一段时间序列, 然后利用ARIMA预测模型对地理位置进行预测, 得到下一时刻的地理位置, 从而获取一个节点的运动轨迹。

3.3 下一时刻地理位置的使用

在Qual Net中, 不存在GPS模块, 但是可以通过其他方法获取到节点的地理位置, 如下方法。

节点的地理位置坐标定义为

通过snt/qualnet/5.0/main/node.cpp文件我们知道节点当前地理位置为:

由于Qual Net中只对二维拓扑进行仿真, 那么在实际中, z坐标的值为0。

在snt/qualnet/5.0/include/mobility.h中增加定义了移动节点Mobility Data的所存储的历史地理位置的信息:

4 基于链路稳定性预测的后备路径路由协议仿真与分析

4.1 仿真环境

根据移动自组网在实际中的应用, 本文使用Qual Net进行仿真, 采用以下仿真场景进行仿真分析, 仿真区域是在1500m×1500m的矩形区域, 区域内随机分布35个节点。节点的移动方式采用随机路点移动方式, 符合Random Waypoint模型, 每个节点的移动速度最大值可调节, 设备移动间隔尺寸为1m。发送CBR数据包, 每个包大小为512字节, 网络流量以固定比特率CBR (Constants Bit Rate) 产生, 采用单信道, 带宽为2Mbps, 仿真时间为100s, 每个节点使用相同的无线收发设备, 采用单一增益的全向天线, 仿真比较LS-BPR AODV与AODV的性能。

为了反映不同路由协议在所设置场景下的网络性能, 本文选用平均端到端时延和数据包投递率作为性能指标, 分别从节点最大速度参数变化着手, 研究以下两种性能指标的变化规律:

(1) 数据包投递率 (Packet Delivery Ratio)

分组投递率是成功传递到目的端的数据包数与发送端成功发送的数据包数之比。该指标反映了接收方受网络拓扑变化影响的程度。

(2) 平均端到端时延 (Average End to End Delay)

平均端到端时延是从源节点成功到达目的节点的所有数据分组的端到端时延的平均值。

4.2 仿真结果与性能分析

移动速度:

35个节点的最大移动速度分别为5m/s, 10m/s, 15m/s, 20m/s, 25m/s, 30m/s, 35m/s, 40 m/s时, 移动方向随机, 共发100个数据包, 每个CBR数据包大小为512字节, 暂停时间20秒, 发包率为1包/秒。仿真结果显示当节点移动速度增加时, 两种协议的传输时延都在增大。这是因为节点的运动速度越大, 网络拓扑变化越激烈, 那么路由断裂的可能性大大增加, 路由断裂次数也大大增加, 从而导致数据发送需要的等待时间增长, 传输时延增加。由图可得, 但从图中可以发现LS-BPR AODV受节点最大移动速度的影响相对较小。

仿真结果还显示数据包投递率与最大速度之间的关系。当节点运动速度增加时, LS-BPR AODV与AODV的投递率都在降低。这是因为节点移动速度越大, 网络局部拓扑变化越激烈, 造成路由中断次数增加, 目的节点不可达的现象增多, 从而造成网络的丢包率增加。由图可得, LS-BPR AODV的丢包率要明显低于AODV, 这是因为在前者的路由算法中, 加入了成本函数与地理位置预测算法。LS-BPR AODV偏向于利用丢包率更低的后备路由。同时, 加入地理位置预测后, 能够提前预知链路的断裂, 减少路由中断的次数。通过这两种机制的同时作用, 提升了数据包投递率。

参考文献

[1]陈代武.计算机网络技术[M].北京:北京大学出版社, 2009:290-292.

[2]王黎明, 王连, 杨楠.应用时间序列分析[M].上海:复旦大学出版社, 2008:1-85.

算法的稳定性 篇5

关键词：岩质边坡,失稳方式,BP网络模型,稳定性

边坡系统是一个复杂系统,其稳定性影响因素(如斜坡的外形岩性构造水地震和人为因素)虽部分具有确定性,但大部分具有不确定性、随机性、模糊性、可变性等。它们对不同类型边坡岩体稳定性影响权重是变化的,故边坡稳定性评价是一项复杂的综合评价过程。传统的统计法力学计算可靠性分析不能深刻揭示边坡灾害演化的非线性关系,难以精确解决问题。基于概率理论的可靠性分析方法的实质是用泰勒级数展开并忽略高阶项,以得到简单的解析关系。应用模糊综合评价灰色聚类分析并与数学方法进行综合评价,但是这些方法都忽略了评价指标的作用,有些是相互依赖或相互关联的。近年来发展的神经网络技术突破了以上方法的“瓶颈”限制。此项技术具有自学习、自组织联想记忆能力和良好的容错能力,能进行聚类分析特征[1]提取缺损模式复原等模式信息处理工作,又宜于做模式分类、模式联想等模式识别工作,还具有很强的自适应功能。

1 BP网络基本原理

1.1 BP网络简介

人工神经网络是一种高度的非线性映射处理系统,具有强大的自组织、自学习、自适应和分类计算能力。神经网络按网络结构和学习算法可分为很多种,BP网络是目前运用最为广泛的神经网络模型之一。

BP网络实质上是一种输入到输出的映射,它能够学习大量的输入和输出之间的映射关系,而不需要任何输入和输出之间的精确的数学表达式,只要用已知的模式对BP网络加以训练,网络就有输入输出对之间的映射能力。它实际上是把一组样本输入输出问题变为一个非线性优化问题,使用了优化中最普遍的梯度下降法,用迭代运算求解权值[3]。

1.2 BP网络的改进算法

实际应用发现BP算法在迭代计算过程中存在易陷入局部极小值和收敛速度慢的问题。文中采用附加动量法和自适应学习速率改进BP算法[2],以克服上述两个问题。

附加动量法是在逆传播法的基础上在每一个权值的变化上加上一项正比于前次权值变化的值(动量项),并根据逆传播法来产生新的权值变化。带有附加动量因子的权值调节公式为:

Δwij(t+1)=(1-α)ηδiuj+αΔwij(t) (1)

Δθj(t+1)=(1-α)ηδi+αΔθj(t) (2)

其中,Δwij为权值变化量;Δθj为阈值变化量;δi为误差项;uj为输入变量;η为学习率;t为训练次数;α为动量因子。

附加动量法的实质是将最后一次权值变化的影响,通过一个动量因子来传递。当动量因子的取值为0时,权值的变化根据梯度下降法产生;当动量因子为α=1时,新的权值变化则是最后一次的变化,而依梯度法产生的变化部分被忽略。以此方式,增加了动量项后,促使权值的调节向误差曲面底部的平均方向变化,当网络权值进入误差曲面底部的平坦区时,δi将变得很小,于是Δwij(t+1)≈Δwij(t),从而防止Δwij=0的出现,有助于使网络从误差曲面的局部极小值中跳出。

2 预测的神经网络模型

2.1 岩体边坡稳定性及变形失稳方式的评价指标

存在于大自然的岩质边坡与其稳定性的有关因素概括起来有:地形、岩体、影响因素三大类[4]。并将影响边坡岩体稳定性指标归纳为岩体质量系数、回弹值(实验确定)、结构面发育特征、结构面力学性质、岩体风化作用、坡高、地下水、坡角开挖。

2.1.1 岩体质量系数SRMR

边坡岩体质量综合反映岩体结构完整性、岩石坚硬程度。根据Bieniawski提出的岩体质量评价系统RMR值,进行如下修正得出边坡岩体质量系数SRMR为:

$SR{\rm M}R=\frac{R{\rm M}R}{100}$ (3)

2.1.2 结构面修正系数λ

在边坡岩体稳定性分析中,断层、软弱夹层、泥化夹层、层理及节理等各种结构面对边坡稳定性的工程意义及影响权值一般情况下是不同的,文中建议采用以下取值原则:断层、软弱夹层、泥化夹层,λ=1.0;层面λ=0.7～0.9;节理面λ=0.6。

2.1.3 坡高系数μ

大量的边坡工程统计表明,随着坡高的增大,边坡岩体应力状态逐渐使边坡处于不利的状态。文中采用坡高的修正系数表征边坡体规模对边坡岩体稳定性的影响,坡高修正系数μ为:

μ=0.56+33.9H-1 (4)

其中,H为坡高,m。

2.1.4 坡角开挖影响系数ξ

边坡开挖的方式不同,对边坡岩体的应力分布、岩体结构及完整性的影响程度是不同的,从而对边坡岩体稳定性及工程岩体质量的影响程度也不同,因此,在边坡稳定性分析过程中应考虑不同的开挖方式的影响,有关开挖方法影响系数见表1。

2.2 建立预测的神经网络模型

文中采用BP神经网络模型,用上述的若干个指标为输入变量,以边坡岩体稳定系数和失稳方式为输出变量,通过对大量工程因素与稳定系数及失稳方式的非线性学习模型的分析,然后用这个模型对部分已知工程进行推广预测,对训练网络进行测试,评价学习模型的泛化能力。此网络的第一层即输入层有n个神经元,中间层有2 n+1个神经元,第三层有m个神经元(Kolmogorov定理[5])。文中选取SRMR,λ,μ,ξ,N(回弹值),岩体风化程度,地下水输入神经元。输出层取两个二值神经元,以表示稳定系数和可能的稳定状况。第一个神经元输出稳定状况即稳定(1,0)、较稳定(0,1)、失稳(1,1)。第二个神经元输出失稳方式即顺层或切层滑动(1,0)、风化剥落(0,1)、表层坍塌(1,1)。

2.3模型训练过程及回判结果

由于网络输入输出节点较多,要使它较准确地掌握输入因素与输出因素的非线形关系,就必须有充足的学习样本。在收集和综合分析计算国内大量的各种边坡岩体结构类型和稳定状态资料[6]的基础上,筛选14个工程实例进行网络训练,其余5个实例作为预测样本。通过2 146次迭代计算后,误差达到精度要求。并对神经网络预测的边坡稳定状况和失稳方式与实际边坡稳定状况和失稳方式综合对比分析(见表2),表明预测结果正确可靠,同时说明建立的神经网络模型是合理、可信的。

3结语

对于具体的边坡工程,不同部位的地质条件常常是不尽相同的,文中建立的边坡岩体稳定性评价指标综合反映了边坡岩体质量及其影响稳定性分析的结构特征,对于地质条件变化大的岩质边坡,可以根据岩体特征进行分区建立评价指标,再进行分区稳定性评价。

正是因为人工神经网络性能良好,具有自学习、自组织、强容错性,能够很好地掌握地质体各种信息间复杂的非线性关系,以大量的工程实例为学习的预测基础,可以灵活地选择评价因子,故在地质灾害预测中具有广泛的应用前景。文中建立的预测模型,数据获取方便,准确度高,能够很好地预测边坡的稳定性。

参考文献

[1]徐丽娜.神经网络控制[M].哈尔滨:哈尔滨工业大学出版社,1999.

[2]从爽.面向MATLAB工具箱神经网络理论与应用[M].合肥:中国科技大学出版社,1998.

[3]吴简彤,王建华.神经网络技术及其运用[M].哈尔滨:哈尔滨工业大学出版社,1993.

[4]卢才金,胡厚田,徐建平,等.改进的BP网络在岩质边坡稳定性评判中的应用[J].岩石力学与工程学报,1999,18(3):303-307.

[5]王士同.神经模糊系统及应用[M].北京:北京航空航天大学出版社,1998.

算法的稳定性 篇6

排序算法的稳定性是度量排序算法质量的一个重要指标,指两条关键字相等的记录R、S在排序前与排序后应该保持次序上的先后关系不变。简单选择排序简单易懂,但其稳定性存在争议。大部分常见排序算法在是否满足稳定性方面都有明确的结论。例如,直接插入排序、折半插入排序、冒泡排序、树形选择排序、归并排序、基数排序等都是稳定的排序算法;而希尔排序、快速排序、堆排序等是不稳定的。

文献[1]在选择排序的专题内容中给出的简单选择排序算法是不稳定的,但是进行内部排序方法比较时所有时间复杂度为平方级的简单排序方法都是稳定的。文献[1]指出,选择排序方法本身是一种稳定的排序方法,但经典的简单排序算法却表现出不稳定现象,是由于经典算法采用了交换记录的策略,适当改变该策略就可以得到一个稳定的简单选择排序算法。但是,如何调整经典选择排序的交换策略,文献[1]中并没有给出具体方法。常见程序设计、数据结构以及算法方面的教材中对简单选择排序算法的稳定性问题也都缺乏深入完整的讨论[2,3]。文献[4]指出经典选择排序算法是不稳定的,同时给出了一个改进的简单选择排序算法以保证稳定性。但文献[5]所提方法提高了经典选择排序算法的空间复杂度。本文在不改变简单选择排序时间复杂度和空间复杂度的前提下,对简单选择排序算法进行改进,提出一种稳定的同等复杂度的简单选择排序算法。

1 简单选择排序算法及其性能分析

1.1 经典简单排序算法

设待排序记录数组为R[1...n],对其按照关键字key由小到大进行排序。经典的简单选择排序算法思想为:将排序过程分为n趟,第一趟从R[1]开始,通过n-1次比较,从所有n条记录中选出关键字最小的记录,记为R[IndexOfMin],交换R[1]和R[IndexOfMin];第二趟从R[2]开始,通过n-2次比较,从第2条到最后一条共n-1条记录中选出关键字最小的记录,同样记为R[IndexO-fMin],交换R[2]和R[IndexOfMin];以此类推,上述过程重复n-1趟,完成排序。经典简单选择排序算法C语言伪代码如下:

1.2 简单选择排序算法复杂度分析

简单选择排序过程基本操作分为比较、交换两类。排序过程中,需要进行的记录移动次数较小。当原始记录按照所要求顺序排列时,交换次数为0;当原始记录排序顺序与要求顺序相反时,交换次数最多达到(n-1)次,对应的赋值次数为3(n-1)。就比较次数而言,无论原始序列是何种情况,第1趟排序过程中需要比较n-1次,第2次需比较n-2次;以此类推,第i次需要比较n-i次,最后一趟比较1次。因此,总的比较次数为n*(n-1)/2。由此可知,简单选择排序算法的总时间复杂度为O(n2)。

就空间复杂度而言,由上述简单选择排序伪代码可见,无论待排序记录有多少条,简单选择排序算法只有i、j、IndexOfMin和temp四个辅助变量。因此,简单选择排序算法的空间复杂度是常数阶的,空间复杂度为O(1)。

1.3 稳定性分析

结合实例说明经典简单选择排序算法是不稳定的。假设:将以下序列从小到大排序,3,3*,3* *,2(当中,*用来区分关键字相同的不同记录)。按照经典的简单选择排序,当i=1执行第一次循环时,最小记录为最后一条记录2,它对应的下标IndexOfMin取值为4。此时,将R[1]与R[4]互换得2,3*,3**,3。第二趟和第三趟选择排序不发生任何交换。因此,最后所得有序序列仍然为2,3*,3**,3。可见,两条相等的记录3与3* 在排序前后的顺序发生了改变,经典的简单选择排序算法不稳定。

2 改进的简单选择排序及其性能分析

2.1 改进的简单选择排序算法

为了保证简单选择排序的稳定性,本文方法基本思路如下:找到最小记录R[IndexOfMin]后,不将该元素与无序快首记录(即第i条记录)直接交换,而在第i+1条记录到最小记录之间寻找与R[i]关键字相等的记录。每找到一条就将它与R[i]互换。如此,最多经过n-i次交换,R[i]就成为IndexOfMin之前、离IndexOfMin最近的与无序块首记录关键字相等的记录,而其它记录的相对顺序不发生改变。此时再将R[i]与R[IndexOfMin]交换,则排序算法将保持稳定性。

首先给出改进后的简单选择排序算法的伪代码,结合实例说明其稳定性,并对改进后算法的时间复杂度和空间复杂度进行分析。改进后的简单选择排序算法如下,加粗部分是为了保证算法稳定性而新增的代码。其目的是将无序块首记录后面的、与无序块首记录关键字相等的最后一条记录交换到无序块的首位置,同时保证其它与无序块首记录关键字相等的记录保持次序先后关系上的不变。结合实例说明这一过程。

以序列3,3*,3**,2由小到大排序过程为例说明改进算法的执行过程。第一趟排序过程中,IndexOfMin取值为最小记录2的下标4。此后,改进的算法并未将该记录与无序快首记录交换,而是执行如下交换过程:第1次,3*与3交换,得序列3*,3,3**,2;第2次,3*与3**交换,得序列3**,3,3*,2;最后一次,最小记录与无序块首记录交换,即2与3* * 交换,由此得到记录序列2,3,3*,3**。最后两趟选择排序过程中,记录未发生任何交换,最后所得有序序列为2,3,3*,3**。由此可见,与经典的简单选择排序算法不同,改进后的算法并未改变三条关键字均为3的记录的相对次序。

再如,对记录序列12,15,12*,11,15*,15**,10,15***,9,20,17,15****,111,16,15*****由小到大进行排序。15条记录中记录12出现2次,记录15出现了6次。第一趟排序过程中,IndexOfMin的取值为9,在首记录12与最小记录9交换之前,两者之间的元素12与12*先进行一次交换,从而12*成为了首记录。此后,12*与最小记录9交换得到9,15,12,11,15*,15**,10,15***,12*,20,17,15****,111,16,15*****。第二趟选择排序过程中,最小值为10,Index-OfMin的值为7在15与10交换之前,首先15与15*交换,然后15*与15** 交换,最后15* * 再与10交换。以此类推,最终可得记录序列9,10,11,12,12*,15,15*,15**,15***,15****,15*****,16,17,20,111。由此可见,取值为12或者15的记录在排序前后相对次序未发生改变,满足稳定性的要求。

2.2 改进的简单选择排序算法性能分析

改进的算法只在第一层循环(i对应的循环)内加了一个与第二层循环(j对应的循环)并列的循环。从循环结构嵌套的角度来分析,外层循环执行n-1次,内层的两个循环中,j对应的循环至多执行n-1次,新增的循环也至多执行n-1次,由此可知,整个算法中基本操作的执行次数为(n-1)*[(n-1)+(n-1)],所以改进后的简单选择排序的时间复杂度并未提高。

就具体的基本操作次数而言,改进后的简单选择排序算法需要的基本操作只包括比较和交换两类。当原始记录按照所要求顺序排列时,条件IndexOfMin!=i始终不成立,此时改进后的算法时间性能最优,交换次数为0,比较次数与改进前的简单选择排序算法相同,均为n*(n-1)/2。当原始记录排列顺序恰巧与要求顺序相反时,j所对应的循环下执行的比较次数为n*(n-1)/2;k所对应的循环下每次都判断条件与否的比较次数最多为(n-2)+ (n-3)+…+1=(n-1)*(n-2)/2;最坏情况下每次比较都要发生交换,再加上k所对应循环外的一次交换,最坏情况下交换次数为(n-1)*(n-2)/2 +(n-1)= n*(n-1)/2。由此可见,相比改进前的简单选择排序算法而言,为了保证排序算法的稳定性,改进后算法比较操作和交换操作的次数最多均增加(n-1)*(n-2)/2次。结合上节例2,第一趟选择排序过程中,经典的选择排序算法进行了14次比较和1次交换。而改进后算法在进行14次比较之后IndexOfMin值为8,还需进行7次比较,以判断是否存在k使得R[k].key==R[i].key成立,此时共进行了21次比较,中间过程中两个12交换1次、最小元素9与首元素再交换1次,共2次交换,所以,比较次数和交换次数均有所增加,但如前文所述,改进后算法最大时间复杂度与改进前保持不变,都是O(n2)。

此外,就改进后算法的空间复杂度而言,相比改进前算法,无论待排序记录有多少条,新算法只是引入了一个计数器变量k,所以改进后算法的空间复杂度也保持不变,仍然是常数空间复杂度,即空间复杂度依然是O(1)。

最后,根据简单选择排序算法的改进原理,每趟简单选择排序过程中,最小记录只是与其左侧最后一个与无序块首记录相等的记录发生了交换,交换后该记录仍然位于原本在其前面的、与其关键字相等的记录后面;同时,其它记录的相对次序保持不变。所以改进的简单选择排序算法是稳定的。结合2.1节的两个实例也可说明这一过程。

3 结语

本文对简单选择排序算法的稳定性问题进行了探讨,在对现有研究进行综述的基础上,结合实例指出经典的简单选择排序算法是不稳定的;对经典的简单选择排序算法进行改进,在保持时间复杂度和空间复杂度不变的前提下,提出一个稳定的简单选择排序算法。

摘要：稳定性是度量排序算法质量的一个重要指标。简单选择排序是一种常见的排序算法,但其稳定性存在较大争议。结合实例探讨经典简单选择排序算法稳定性,并进行改进,在时间复杂度和空间复杂度不变的前提下,提出一种稳定的简单选择排序算法。

关键词：算法设计,排序算法,选择排序,算法稳定性

参考文献

[1]严蔚敏.数据结构[M].北京:人民邮电出版社,2011.

[2]宁正元.数据结构[M].北京:中国水利水电出版社,2000.

[3]ROBERT SEDGEWICK,KEVIN WAYNE.算法[M].谢路云,译.北京:人民邮电出版社,2014.

算法的稳定性 篇7

随着电力系统规模的不断扩大以及互联网络的增多,电网的动态特性变得越来越复杂,如何快速有效地进行电力系统的暂态稳定计算也变得更加重要[1,2]。在其计算过程中需要求解描述网络及发电机等系统的高维、非线性的微分-代数方程组,其中较传统的数值计算方法(包括显式龙格库塔和隐式梯形法)已逐渐不能满足当前电力系统的暂态稳定计算的要求。为此,需要寻找新的数值计算方法,以提高暂态稳定计算的收敛精度和计算速度。

近年来,不少研究人员提出了一些新的微分方程的数值计算方法。其中一类著名的算法是辛几何算法[3,4,5,6]。辛几何算法是由我国著名数学家冯康院士针对传统数值计算方法不能保几何结构以及人为耗散等缺点而提出的。由于辛几何算法在解微分方程时具有很优越的效果,因此本文将一种辛RungeKutta-Nystr(O|")m法(辛RKN法)[7]用于电力系统的暂态稳定计算中,通过Matlab的仿真结果验证了该算法具有保辛的优点,即体现了数值的稳定性和准确性。

1 辛Runge-Kutta-Nystr(O|")m法

自从1984年冯康院士采用辛几何的观点提出了计算Hamiltion系统的新方法之后,辛算法的研究已取得了十分丰富的成果,特别是与传统的非辛几何算法相比辛几何算法具有保持系统原来几何结构特征的优点。因此,本文只以显式3级4阶的辛RKN法[7]为例,来进行电力系统暂态稳定性的计算。

对于给定的二阶常微分方程初值问题:

其常用的s级RKN方法可以写成:

相应的Butcher表为:

如果式(2)的系数满足如下条件:

则该式为辛格式。

如果aij=0(i=1,…,s,j=i,…,s),即:

则式(2)中gi仅与gj(j=1,…,i-1)相关,因此式(2)变为显式,由此可知3级4阶辛RKN暂态稳定计算步骤如下:

(1)计算向量;

(2)计算向量g1后,求解代数方程组0=G(g1,k1)得到k1;

(3)计算向量

(4)计算向量g2后,求解代数方程组0=G(g2,k2)得到k2;

(5)计算向量

(6)计算向量g3后,求解代数方程组0=G(g3,k3)得到k3;

(7)求解状态变量

再将xn+1代入代数方程组0=G(xn+1,yn+1)求解得到yn+1。至此,该算法的暂态计算过程基本完成。

2 暂态计算的数学模型

电力系统的暂态稳定计算实质是求解一组非线性方程组和代数方程组:

式(5)中,x通常称为状态变量,y通常称为辅助变量。式(5)中的微分方程组主要是描述电力系统相关元件的动态特性,而代数方程组描述电力网络结构特性。

暂态计算主要是通过式(5)代数方程组的数值及微分方程组的初值,用式(2)所给出的数值计算方法来求解上述微分方程组。这也就是本文所提出的辛RKN方法。在负荷用恒定阻抗表示,发电机用经典模型的情况下,系统中每一台发电机的摇摆方程可以描述为[8]:

式中:,Cij=EiEjBij,Dij=EiEjGij;Mi为第i台发电机的惯性时间常数;Pmi为第i台发电机的机械功率;Gij为收缩导纳矩阵的电导;Bij为收缩导纳矩阵的电纳;Ei为第i台发电机的暂态电动势。

则式(6)可以描述为:(7)

由式(7)可以说明在采用经典模型构造电力系统的情况下,发电机的功角δ和角频率ω是完全可分的,这正好有利于采用该显式辛RKN算法来求解暂态稳定性计算的问题。对于刚性系统,与传统Runge-Kutta法(RK法)相比,该显式的数值积分方法能很好地适应较长过程的暂态稳定计算。

3 仿真计算分析

本文采用IEEE145节点系统[9],暂态稳定计算所采用的是发电机经典模型。发生三相接地短路故障,故障持续时间为0.10 s,整个积分时间为1.5 s。为便于对结果进行对比分析,以步长h=0.001 s时发电机相对功角的计算结果为基准值(此时步长很小,不同数值计算方法的结果基本一样),在不同的积分步长情况下,采用传统4阶RK法与3级4阶辛RKN法进行暂态计算,得到发电机的相对功角,与步长h=0.001 s得到的相对功角进行误差比较分析,得到误差曲线。

图1是步长h=0.03 s时RK法与辛RKN方法的相对功角误差曲线。从图1可以看出:在相同步长情况下,辛RKN方法的计算精度比传统RK法的计算精度更好。

为了进一步检验上述结论,分别采用步长h=0.04 s、h=0.05 s、h=0.06 s时,仿真电力系统暂态稳定计算,从而得出辛RKN与传统RK方法的误差曲线。其误差曲线图分别为图2、图3、图4。

从图1～图4可以看出,随着步长的逐步增大,辛RKN方法所计算的发电机之间功角的相对误差的增长幅度比传统同阶的RK方法所计算的功角误差要小得多。由此可以预测随着步长逐渐适当的增大时,传统RK方法计算所得到的功角误差曲线越来越偏离正确值,最后,甚至会出现不稳定的情况。因此可以得出,辛RKN算法在步长允许增大的情况下,仍然具有较好的计算精度。这也从另外一个方面说明了辛RKN算法具有长时间稳定进行数值计算的优点[10]。

为了更进一步阐述辛RKN方法的计算效率,本文在采取适当增大步长的情况下,计算辛RKN方法所耗时间,并将其与传统同阶的RK方法进行比较,其结果见表1。

由表1可以明显看出:3级4阶辛RKN法明显具有步长的优势。例如辛RKN在步长h=0.05 s时所用的计算时间几乎是传统同阶RK法在步长h=0.07 s时所用的时间。且随着步长的逐步增大(比如在步长h=0.12 s辛RKN所用时间比h=0.14 s时RK法所用时间还少),这种优势就更加的明显。因此,将该辛几何算法应用在电力系统暂态稳定计算中,具有无可比拟的优势,这也体现了辛算法的强大生命力。

4 结论

本文将辛Runge-Kutta-Nystr(O|")m法成功地应用在电力系统暂态稳定性计算中。通过仿真计算,得出采用该种算法时系统发电机的相对功角曲线和不同步长情况下的CPU计算时间。并将其与传统同阶的Runge-Kutta法相比,无论是计算精度还是计算速度,辛Runge-Kutta-Nystr(O|")m法都具有显著的优势。同时,对于高阶的辛几何算法,在采用较大步长情况下,仍然具有较好的结果。另外,对于一个s级的辛RKN方法,在求解下一步时,需要在s个时间点上同时求解,这就解决了暂态稳定计算过程中相邻积分步间的变量耦合关系,即在相邻时间点上不存在相互“等待”的问题,体现了该算法内在的时间并行特性。

参考文献

[1]樊冬梅.超导储能提高电力系统暂态稳定性理论探讨[J].电网与清洁能源,2010,26(3):20-24.

[2]都伟杰,张俊芳,刘鹏,等.基于MATLAB的电力系统暂态稳定性仿真研究[J].电网与清洁能源,2009,25(1):17-20.

[3]冯康,秦孟兆.哈密尔顿系统的辛几何算法[M].杭州:浙江科学技术出版社,2002.

[4]FENG K,QIN M Z.Hamiltonian Algorithms for Hamiltonian Dynamical Systems[J].Progress in Natural Science,1991,1 (2):105-116.

[5]秦孟兆.辛几何及计算哈密顿力学[J].力学与实践,1990, 12(6):1-20.

[6]Sun G.Construetion of High Order Symplectic Runge-Kutta Methods[J].Journal of Computational Mathematics, 1993,11(3):250-260.

[7]徐松,候晓荣.三级四阶显式R-K-N格式的完全构造[J]. ??系统科学与数学,2009,29(9):1211-1221.

[8]张汉雄,李丹,罗志远.基于辛RKN算法的电力系统暂态稳定性计算[J].陕西电力,2010,38(10):19-22.

[9]Vittal V.Transient Stability Test Systems for Direct Stability Methods[J].IEEE Transactions on Power Systems,1992,7 (1 ):37-43.

算法的稳定性 篇8

传感器的精确度在工业生产中也同样占据着不可忽视的地位。由于部分压力传感器是由半导体材料构成,因此具有灵敏度高及动态响应快等诸多优点; 但也由于半导体的特殊性质,这种传感器容易受温度影响,产生温漂,导致传感器的稳定性和精确性降低,所以要对其进行温度补偿。目前对于压力传感器的温度补偿方法有很多,但补偿精度都不是很高［1，2］。

近年来随着人工神经网络的发展,其应用范围也越来越广泛,BP神经网络是一种具有连续传递函数的多层前馈人工神经网络,被广泛应用在各行各业中。BP神经网络可以应用在压力传感器的温度补偿模型当中,但是由于它的收敛速度慢且容易早熟,所以笔者提出了一种采用遗传算法( Genetic Algorithm,GA) 优化的BP神经网络, 通过调整其权值和阈值使传感器具有较好的收敛性和稳定性。

1 BP神经网络1

1. 1结构

BP神经网络的训练方法是误差反向传播算法,并以均方误差最小化为目标不断修改网络的权值和阈值,最终达到高精度的拟合数据。从整个框架来看BP神经网络( 图1) 可分为输入层、隐含层和输出层,而隐含层可以含有多层神经元。通过已取得的成果可以发现,BP神经网络只需含有3层结构就可以实现任意的非线性映射,因此笔者选择三层BP神经网络为研究对象［3］。

BP算法是一种梯度下降算法。假设输入层神经元I =[I1,I2,…,Ii],隐含层神经元S =[s1, s2,…,sk],输出层神经元O =[o1,o2,…,oj],Wk，i1表示输入层第i个神经元与隐含层第k个神经元之间的连接权值,Wj2,k表示隐含层第k个神经元与输出层第j个神经元之间的权值,f1和f2分别为隐含层和输出层的激发函数,bsk1和baj2分别为隐含层和输出层的阈值,Wk，i1、Wj,k2、bsk1、baj2的取值都在( - 1,1) 。

由此可得隐含层第一个神经元x11=f1[(I1×W11,1+I2×W11,2+…+Ii×W11,i)+b1si],输出层第一个神经元a1=f2[(x11×W11,1+x12×W11,2+…+x1k×W11,k)+b2a1]。

1. 2特点

BP神经网络具有误差逆向传播的特点。当S维指标向量通过各层神经元最终得到输出值A后,把输出值和期望值E进行对比,即可得到期望与实际输出的均方差M = ∑( A - E)2/ N,其中N为输入样本个数。若M小于预定要求,则进入逆向过程［4］,具体流程如图2所示。

2 GA-BP神经网络

GA是通过模拟进化过程来搜索最优解的方法,是通过编码生成初始群种的一种算法,可采用GA算法来训练神经网络。具体步骤如下:

a. 当神经网络规模较大时,为了简化遗传操作,可采用实数编码方法,即把染色体的一个基因位直接用实数表示,如此便可以使染色体的长度减少,省去编码解码的繁琐。把编码串的一系列权值和阈值按照一定的顺序连接起来,形成数组, 作为遗传算法的一个染色体。采用三层BP神经网络,设输入层、输出层和隐含层的神经元个数分别为i、j和k,网络隐含层和输出层对应的权值和阈值分别为W1、W2、B1、B2,可得编码长度为i × k + k × j + k + j,如此便构成了一个完整的染色体［5］,最终在权值和阈值的相应范围内产生S个染色体就构成了初始种群。

b.采用评级函数作为遗传的依据。BP神经网络的评价准则就是M值越小越好,故将M的倒数作为评级函数,当该值最大时BP神经网络的权值和阈值即得到了最大改善。公式,其中f(i)是第i条染色体的评级值,Mi是第i条染色体的网络权值和阈值[6~8]。

c. 执行遗传操作。遗传操作的选择方法为排序,即首先把求得的评级值由小到大从1 ~ M排列,然后通过个体评级值的大小按照评级比例的选择法计算每个染色体的选择概率,采用单点交叉和均匀变异方法,最终找出最优评级值的染色体,然后按照上述方法反复计算,直到最终满足条件为止。

d. 通过遗传运算得到评级值最优的一系列权值和阈值。

e. 执行BP神经网络。

3 GA-BP神经网络算法在压力传感器中的应用

3.1传感器的标定数据

在实际应用中,压力传感器的输出Up与被测压力和温度呈非线性关系。隐含层有4个神经元,输出层有两个神经元。以S17-30A型压力传感器为实验对象,选取3个温度T进行压力标定, 详见表1,其中Up为压力传感器输出信号,Ut为温度传感器输出,γ 为电源波动,p为输入压力。

通过对表1中的数据进行处理得到,传感器随温度变化的波动 α = 22. 00% ,可见温度对传感器的影响非常大,需要对其进行补偿。

3. 2建立学习样本库

由于表1中的数据比较大,而且单位不同,并且神经网络的隐含层需要采用S型函数来激活［9，10］,所以需要对表1中的数据进行归一化处理,公式为:

其中,xi、xmin和xmax分别代表任意值、最小值和最大值。归一化后的数据见表2。

3. 3结果分析

采用Matlab语言编制训练程序,经过训练后的修正值见表3,可得被测压力p( k Pa) 的最大相对波动 α' = 1. 21% 。

采用GA-BP神经网络的补偿结果见表4,可得被测压力p( k Pa) 的最大相对波动 α″ =0. 84% 。

通过上述计算得到了原始标定、BP神经网络算法补偿后和GA-BP神经网络算法补偿后的最大相对波动值分别为22. 00% 、1. 21% 和0. 84% 。 可见,通过BP神经网络算法补偿后的压力传感器其工作稳定性有显著提高; 而采用GA-BP神经网络算法补偿后的压力传感器,其稳定性得到了进一步升华,并且GA-BP神经网络算法的收敛次数明显减少,时间缩短了近2 /3。

4结束语

由于部分压力传感器受半导体材料的限制, 使得其在实际应用过程中很容易产生温漂,影响了测量精确度和稳定性,所以有必要对其进行温度补偿,而通常的温度补偿方法不仅收敛速度慢而且成本也比较高。在此,笔者以S17-30A型压力传感器为标定样本,将BP神经网络和GA算法结合,并把结合后的GA-BP神经网络算法应用于标定过程,取得了良好的效果,压力传感器运行稳定,波动较小。证实GA-BP神经网络算法对压力传感器有着很好的温度补偿效果,提高了其测量精确度。

摘要：通过对BP神经网络的分析,提出一种采用遗传算法(GA)优化的GA-BP神经网络,通过调整其权值和阈值使传感器具有较好的收敛性和稳定性。最终通过实验仿真得出:GA-BP神经网络算法对压力传感器温度补偿具有显著的改善效果,提高了传感器的测量精确度和稳定性。