潮流追踪迭代算法
第21卷第11期2001年11月中国电机工程学报
P roceedings of the CSEE
Vol.21No.11Nov.2001
n2001Chin.Soc.for Elec.Eng.
文章编号:0258-8013(2001)11-0038-05
潮流追踪迭代算法
李卫东1,孙辉1,武亚光2
(1.大连理工大学电气工程与应用电子技术系,辽宁大连116023;
2.辽宁省电力公司调度通讯中心,辽宁沈阳110006)
AN ITERATIVE LOAD FLOW TRAC ING METHOD
LI We-i dong1,SUN Hui1,WU Ya-guang2
(1.Department of Electrical and Electronics Engineering,Dalian University of Technology,Dalian116023,China;
2.Liaoning Electric Pow er Dispatch and Communication Centre CH N,Shenyang110006,China)
ABSTRAC T:Based on t he thoroughly analysis of the power flow mechanism,a fast and accurate power flow tr acing method is proposed.T he power losses are allocated according to the pro-po rtion o f complex power when tr acing power flow,so the ac-tiv e and r eactive pow er are traced in the same time.T he diff-i culty that accur ate tracing results can not be gain in some cases could overcome for the active and reactive po wer flow tr acing are car ried on iteratively in the algor ithm.T he distribution of bus voltag e is made full use of,as the ang le and magnitude of t he bus voltage are used as level to trace activ e and reactive power respectively.As a result,the research of buses and trans-mission elements can be avoid and the computation speed can be enhanced notably.T he tracing results are accurate,for t he ac-tiv e and reactiv e pow er are traced in the same time.T he pro-posed method is directly perceived through the senses,fast and accurate in computation,so the method can be accepted easily by electric power company.Case study shows that t he view-po int in the paper is correct and the proposed method is valid and feasible.
KEY WORDS:tansmission open access;pow er flow tr acing;it-erative method;losses allocation
摘要:该文在对潮流流动机理进行深入分析的基础上,提出了一种新的快速准确潮流追踪算法。在潮流追踪过程中,考虑了有功与无功功率之间的影响,是完全意义上的有功和无功功率追踪。算法中采用了有功功率与无功功率追踪的迭代进行方式,从而克服了在有功与无功功率通路不同的情况下无法进行准确追踪的困难。由于充分利用了电压分布的特点,将节点电压的幅值和角度作为水平位分别对有功和无功功率进行追踪,在确定节点追踪顺序中避免了对节点和线路的搜索,可显著提高计算速度。因为该算法中同时对有功和无功功率进行追踪,故计算结果准确。该算法直观、清晰,计算快速、准确。数字算例表明,文中的观点是正确的,所提出的迭代算法是有效的。
关键词:输电系统开放;潮流追踪;迭代算法;损耗分摊
中图分类号:T M731文献标识码:A
1引言
在确定输电费用的过程中,潮流追踪是输电费用分摊等分析的基础,故对其算法的研究成为一个热点,提出了很多方法[1-5]。
由于负荷功率因数的不同、系统参数的不同和FACTS等设备的存在,此等因素均会导致负荷功率在输电元件中分布的功率因数不同,且无功功率可产生有功功率损耗,而有功功率亦可产生无功功率损耗,所以不考虑二者之间的影响来进行损耗分摊是不准确的。
本文将对潮流追踪问题及潮流流动机理进行详尽的分析和研究。
2潮流流动机理分析
图1所示系统中1、2节点为负荷节点,3节点为功率输入点。节点负荷功率的表示方式为
S1= P1+j Q1, S21=P21+j Q21。
如果P1>0、Q1>0,则
S c21= S21+$
S21= S1+$ S21
式中$
S21为输电元件L21的功率损耗。
因$
S21是完全由
S1引起的,故该损耗应由 S1承担。
如果P2>0、Q2>0,则
因$ S 32是由3部分组成: S 1所引起的功率损耗, S 2所引起的功率损耗和$ S 21所引起的功率损耗。这里,$ S 32中由于输送$ S 21所引起的功率损耗,应由 S 1承担。
图2所示为环型网络,其中1、2节点为负荷节点,3节点为功率输入点。假定功率由节点3流向节点1和2,而对输电元件1-2,其功率的传输情况主要有以下两种,其余情况的处理请参见文[6]
。
图1 3母线系统Fig.1 A 3bus
system
图2 3母线环型网络
Fig.2 A 3bus system with loop
2.1 有功与无功功率流向相同
如果P 12、P c
12、Q 12和Q c
12均大于零,即有功与无功功率流向相同,则问题很简单,只需从节点2开始逆流追踪,便可计算出损耗的分摊情况,从而得知各点的负荷功率在输电元件中的分布。
2.2 有功与无功功率流向相反
假定:P 12>0、P c 12>0,而Q 12<0、Q c 12<0,则此时输电元件1-2的功率损耗为
$ S 12=
P 212+Q 2
12
U 22
(R 12+j X 12)=$P 12+j $Q 12=P 212U 22(R 12+j X 12)+Q 2
12U 22(R 12+j X 12)=$S 12P +$S 12Q =$P 12P +j $Q 12P +$P 12Q +j $Q 12Q
式中 U 2为节点2电压幅值;R 12和X 12为输电元
件1-2的电阻和电抗。
由上式可看出,输电元件1-2的功率损耗可分为2部分:1由P 12产生,为$ S 12P ,即$P 12P +j $Q 12P ;o由Q 12产生,为$ S 12Q ,即$P 12Q +j $Q 12Q 。其中,$ S 12P 由节点2的负荷承担,$ S 12Q 由节点1的负荷承担。
从图2可看出,功率P 2的一部分是从节点3经
输电元件3-1和1-2而来,而功率Q 1的一部分是从节点3经输电元件3-2和2-1而来。因此,功率损耗$P 12Q 是从节点3经输电元件3-1和1-2提供而来,与引起该损耗的无功功率Q 2的走向相反;$Q 12P 亦是如此。
通过以上分析可知:对无功功率引起的有功功率损耗的供给是经有功通路完成的,而对有功功率引起的无功功率损耗的供给是经无功通路完成的。当有功流动通路与无功流动通路不相同时,供给方与损耗方的流动路径亦不同,故采用有功与无功功率分开单独进行追踪的方式所得到的计算结果是不
准确的;而通过追踪电流来进行功率追踪[4],将有功功率和无功功率引起的损耗混在一起,其计算结果也是不准确的。
3 潮流追踪原理
已提出的潮流追踪算法中,或是需要对矩阵求逆[1],或是需要先对潮流有向图进行一遍消去过
程,以确定追踪的节点顺序[2,3,5]。随着系统规模的增加,这些算法的计算量将显著增加。
观察图3所示的潮流有向图,如果从节点5开始逆流追踪,可到达节点3,完成对输电元件3-5的功率分配追踪。如果输电元件3-5的前面还有串联支路,则可一直追踪下去。在完成对输电元件3-5的功率分配追踪后,由节点3再逆流追踪会出现问题,因为这时节点3的另一条出线3-4的功率组成还不明确,故无法继续向上追踪。因此,应由节点4向上追踪,完成对输电元件3-4的功率分配追踪。待将节点3所有功率输出元件追踪完毕,明确节点3的输出功率的组成与归属后,方可由节点3向上进行追踪。
图3 潮流有向图
Fig.3 Load f low graph for analysis
由上面的分析可以看出,潮流追踪的一个关键问题是如何确定用来指引追踪方向的水平位,即确定潮流有向图中节点追踪的顺序。图3中的一组节
39
第11期 李卫东等: 利用节点电压搜索定位的潮流追踪迭代算法
点追踪顺序为{4,5,3,1,2}(节点追踪顺序可能不止一组)。为解决该问题,需明确以下命题:
命题1 一般情况下,在输电网中节点电压幅值的下降方向和无功功率流动方向是一致的[6]
;
命题2 一般情况下,在输电网中节点电压角度的下降方向和有功功率流动方向是一致的[6]。
根据以上2命题,可得出以下结论:
可利用节点电压幅值作为等位线对无功功率进行追踪;可利用节点电压角度作为等位线对有功功率进行追踪。
4 潮流追踪算法及一些问题的处理
4.1 有功通路与无功通路相同时的算法流程根据第2节中的分析,以节点电压角度和幅值分别对有功和无功功率进行追踪是十分简便和快捷的。由于有功和无功的通路相同,故利用电压角度或幅值即可进行追踪,以下的论述以电压幅值进行。从负荷节点逆流追踪的具体步骤如下:
(1)潮流计算,对节点电压幅值由小到大进行排序;
(2)按所得到的排序对每个节点进行3步处理,(a)将所有出线功率进行整理、合并,明确该节点出线功率的组成与归属。(b)将出线功率与该节点负荷利用按比例分摊原则[1,2]在该节点所有进线中进行分配,从而得到该节点所有进线末端的功率组成与归属。(c)对该节点的每条进线根据上面计算出的该线路末端功率的组成与归属,根据损耗分摊原则,将该线路的功率损耗进行分配,从而得到该线路首端的功率组成与归属;
(3)结束
在计算过程中,应做好数据结果的归纳与整理,在将所有的节点处理完成后,即可回答诸如某一负荷的功率由哪些发电机提供;经过哪些输电元件;在这些输电元件中输送功率的数量;该负荷应承担多少损耗等问题。
4.2 有功通路与无功通路不相同时的迭代算法
当潮流有向图中的有功与无功通路不相同时,利用上节所提出的步骤进行计算会遇到困难。如图4所示,假设节点1是无功功率分点,而节点3是有功功率分点,那么在进行潮流追踪如有功功率追踪时,对节点3经输电元件3-2、2-1和1-4向上追踪,会遇到输电元件3-2和2-1中无功功率的组成与归
属不详而无法进行损耗分摊的困难。对无功功率由
节点1向上进行追踪也是如此。即:当潮流中的有功与无功通路不相同时,即使采用考虑有功、无功相互影响的损耗分摊原则,也无法直接进行准确的潮流追踪。对该种情况,可采用如下的迭代方法解决此问题。
图4 网络功率分析示意图
Fig.4 A network for explanation
(1)潮流计算,对节点电压幅值和角度由小到大进行排序;
(2)利用4.1节提出的追踪步骤对有功功率进行追踪。由于此时输电元件中无功功率的组成与归属不详,故在进行损耗分摊时,不计无功功率的影响;
(3)重复以下2步迭代过程,直至2次迭代结果之差的绝对值小于给定的精度值时结束。
1利用4.1提出的追踪步骤对无功功率进行追踪,线路中有功功率的组成与归属采用上一次迭代的结果;
o利用4.1节提出的追踪步骤对有功功率进行追踪,线路中无功功率的组成与归属采用上一次迭代的结果。
在迭代方法(3)中进行损耗分摊时,采用了文[7]中所提出的损耗分摊原则。
5 算例
5.1 4-bus 算例
利用本文提出的潮流追踪算法对图5中4节点网络2种运行方式的潮流进行追踪。其中方式1的有功功率通路与无功功率通路相同,方式2的有功功率通路与无功功率通路不同。分析2种方式的电压与功率,可看出节点电压幅值的下降方向和无功功率的流动方向是一致的,而节点电压角度的下降方向和有功功率流动方向是一致的。用有功功率通路与无功功率通路相同时的潮流追踪方法对方式1进行追踪,然后用潮流追踪迭代算法对方式1进行追踪时,其收敛条件是线路功率归属2次计算结果差值的绝对值,收敛精度是10-6
,迭代一次收敛,结果与有功、无功通路相同时的潮流追踪方法的结果
40 中 国 电 机 工 程 学 报 第21卷
相同,这说明所提出的潮流追踪迭代算法在原理上是正确的;用潮流追踪迭代算法对方式2进行追踪,迭代2次收敛,说明该迭代算法是有效的,2种运行方式的潮流分布数据示于表1、2中,潮流追踪结果如表3、4
所示。
图5 数字算例网络
Fig.5 The example system
从潮流分布看,在方式2中,节点2是有功功率分点,看上去似乎节点3和节点4的负荷不应对线
路2-3的有功功率损耗负责,但由于节点3是无功功率分点,节点3和节点4的部分无功功率是由节点1经线路1-2、2-3而来,这部分无功功率在流经线路2-3时引起了有功功率损耗,故节点3和节点4
的负荷应分摊线路2-3有功功率损耗的一部分。同理,节点3和节点4的负荷也应分摊线路1-2的有功功率损耗的一部分。此结论从表3和表4中可得到印证。
如果按照不考虑有功与无功功率相互影响的追踪方法进行潮流追踪,由于节点2是有功功率分点,其结果必然是节点3、4的负荷不对线路1-2和2-3的有功功率损耗负责。而由于节点3、4的无功功率负荷有一部分是经线路1-2和2-3而来,因此其结果明显是不合理的。
表1 2种运行方式的电压分布(标么值)
Table1The voltages of two operating patterns(in pu)
节点
12
3
4
方式1幅值/角度 1.05000/0.0 1.03892/-0.97082 1.04077/-0.93262 1.03816/-1.13943方式2
幅值/角度
1.05000/0.0
1.04024/-0.93298
1.03847/-0.53792
1.03586/-0.74566
表2 2种运行方式的功率分布(标么值)
Tab.2 The line power flows of two operating patterns(in pu)
线路
1-2
1-3
2-3
3-4
方式1首端功率 1.26057+j0.42154 1.45032+j 0.533430.04585+j0.104300.20014+j 0.10097末端功率 1.25416+j0.39592 1.44599+j 0.505280.04584+j0.104080.20000+j 0.10000方式2
首端功率u 1.19888+j0.349210.90973+j 0.79463-0.40694+j0.126590.20014+j 0.10098末端功率
1.19323+j0.32659
0.90708+j 0.77743
-0.40677+j0.12356
0.20000+j 0.10000
表3 线路功率分属各个节点负荷的值(标么值)
Tab.3 C ontribution of the users to the line power flow(in pu)
线路
节点
2
3
4
运行方式1
运行方式2
1-21-3
2-33-41-21-3
2-33-4
首端负荷
1.21780+j0.353010.03666+j0.051330.00611+j0.01721末端负荷 1.21144+j0.327580.03662+j0.051140.00611+j0.01719首端负荷0.00000+j0.00000 1.24334+j0.404320.20698+j0.12911末端负荷0.00000+j0.00000 1.23929+j0.378040.20669+j0.12723首端负荷0.00000+j0.000000.03929+j0.078050.00655+j0.02624末端负荷0.00000+j0.000000.03928+j0.077870.00655+j0.02621首端负荷0.00000+j0.000000.00000+j0.000000.20014+j0.10097末端负荷0.00000+j0.000000.00000+j0.000000.20000+j0.09999首端负荷 1.19876+j0.222140.00011+j0.110410.00000+j0.01387末端负荷 1.19323+j0.200000.00000+j0.109960.00000+j0.01386首端负荷0.40769+j0.005010.30157+j0.700530.20044+j0.08909末端负荷0.40692+j0.000000.30000+j0.690290.20014+j0.08713首端负荷0.40692+j0.002760.00001+j0.109960.00000+j0.01386末端负荷0.40677+j0.000000.00000+j0.109710.00000+j0.01385首端负荷0.00000+j0.000000.00000+j0.000000.20014+j0.10098末端负荷
0.00000+j0.00000
0.00000+j0.00000
0.20000+j0.10000
41
第11期 李卫东等: 利用节点电压搜索定位的潮流追踪迭代算法
表4每条线路功率损耗中各个节点负荷应分摊的值(标么值)
Tab.4The losses of transmission lines allocating to the users(in pu)
线路
节点
234
运行方式1运行方式21-20.00636+j0.025430.00005+j0.000190.00001+j0.00002 1-30.00000+j0.000000.00404+j0.026280.00029+j0.00188 2-30.00000+j0.000000.00001+j0.000180.00000+j0.00003 3-40.00000+j0.000000.00000+j0.000000.00014+j0.00097 1-20.00553+j0.022140.00011+j0.000450.00000+j0.00001 1-30.00077+j0.005010.00157+j0.010230.00030+j0.00196 2-30.00015+j0.002760.00001+j0.000250.00000+j0.00001 3-40.00000+j0.000000.00000+j0.000000.00014+j0.00098
5.230-bus算例
为了进一步检验所提出算法的收敛性,在此以一30-bus系统进行试算。该系统有30个节点,由30条线路构成。试算时选择了一些特殊的运行方式,且其有功通路与无功通路均不同。在其中的一种运行方式中,一对有功功率与无功功率流在7条线路中交叉。利用所提的迭代追踪算法对该系统进行追踪时,迭代3次即可收敛,且精度达到10-8。
6结论
本文对潮流追踪问题进行了深入的研究,通过理论分析和数字算例结果可得出以下几点结论:
(1)对潮流流动机理的分析表明,准确地追踪无功功率是十分必要的。而单独进行有功和无功功率追踪并不是完全意义上的有功、无功功率追踪。进行损耗分摊时应考虑有功与无功功率之间的相互影响,忽略无功功率的影响或追踪有功(无功)功率,只按有功(无功)功率比例进行有功(无功)功率损耗分摊计算方式,在有功与无功功率通路不同的情况下是不准确的;
(2)根据所提出的2个命题,明确了可将节点电压的幅值和角度作为水平位分别对有功和无功功率进行追踪,这样在确定节点追踪顺序时可避免对节点和线路的搜索,以提高计算速度;
(3)指出了当有功功率通路和无功功率通路不相同时,即使利用考虑有功、无功相互影响的损耗分摊原则,也无法直接进行准确的潮流追踪。而利用本文提出的潮流追踪迭代算法,则可完全解决该问题;
(4)数字算例证明了所提观点和迭代算法的正确性。当有功与无功通路不同时,迭代算法最多只需迭代3次即可收敛到10-8精度,说明该算法是十分有效的;
(5)由于直接利用节点电压所蕴含的信息进行追踪,可节省确定追踪顺序的工作量,减少计算时间,尤其是对大规模系统,节约效果将更加显著。
参考文献:
[1]Bialek J.Traci ng the fl ow of electricity[J].IEE Proc.-Gener.
Transm.Distrib.1996,143(4):313-320.
[2]Kirschen D S,Allan R N,Strbac G.Contri butions of individual
generators to loads and flow s[J].IEEE T rans on Pow er Systems.
1997,PWRS-12(1):52-60.
[3]王锡凡,郏斌,王秀丽.电力市场过网费的潮流分析基础)))输
电设备利用份额问题[J].中国电力,1998,31(7):31-34.
[4]Kirschen D S,Allan R N,Strbac G.Tracing Active and reactive
pow er betw een generators and loads using real and imaginary cur-rents[J].IEEE T rans.on Power Sys tems.1999,PWRS-14
(4):1312-1319.
[5]孙洪波,常宝波,周家启.网损分摊决策研究[J].电力系统自动
化,1999,23(2):59-62.
收稿日期:2000-09-20;改回日期:2001-04-06。
作者简介:
李卫东(1964-),博士,教授,从事电力系统分析方面的教学与科研工作。目前的研究领域是电力市场分析、配电自动化及人工智能在电力系统中的应用;
孙辉(1964-),博士生,副教授,从事电力系统分析方面的教学与科研工作。目前的研究领域是电力市场分析、配电自动化及电能质量分析与改善;
武亚光(1963-),博士生,高级工程师,长期从事电网调度运行工作。目前的研究领域是电力市场技术支持系统的开发与研制及组织电力市场的试运行工作。
(责任编辑喻银凤)
42中国电机工程学报第21卷
迭代最近点算法综述
迭代最近点算法综述 摘要：三维点集配准问题是计算机技术中的一个极其重要的问题，作为解决三维点集配准问题的一个应用较为广泛的算法，ICP算法得到了研究者的关注，本文以一种全新的思路从配准元素的选择、配准策略的确定和误差函数的求解等3个方面对三维点集配准的ICP算法的各种改进和优化进行了分类和总结。 关键词：三维点集；迭代最近点；配准 1引言 在计算机应用领域，三维点集配准是一个非常重要的中间步骤，它在表面重建、三维物体识别、相机定位等问题中有着极其重要的应用[1]。对于三维点集配准问题，研究者提出了很多解决方案，如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等，这些算法各有特色，在许多特定的情况下能够解决配准的问题。但是应用最广泛的，影响最大的还是由Besl和Mckay在1992年提出的迭代最近点算法[2]（Iterative Closest Point，ICP），它是基于纯粹几何模型的三维物体对准算法，由于它的强大功能以及高的精确度，很快就成为了曲面配准中的主流算法。 随着ICP算法的广泛应用，许多研究者对ICP算法做了详细的研究，分析了该算法的缺陷和特点，提出了许多有价值的改进，推动了这一重要算法的发展。本文着眼于ICP算法的发展历程，详细介绍了ICP算法的基本原理，总结其发展和改进的过程，对于该算法的各个阶段的发展和变化做了简单的论述。 2ICP算法原理 2.1ICP算法原理 ICP算法主要用于三维物体的配准问题，可以理解为：给定两个来至不同坐标系的三维数据点集，找出两个点集的空间变换，以便它们能进行空间匹配。假定用{}表示空间第一个点集，第二个点集的对齐匹配变换为使下式的目标函数最小[3]。 ICP算法的实质是基于最小二乘法的最优匹配算法，它重复进行“确定对应关系点集—计算最优刚体变换”的过程，直到某个表示正确匹配的收敛准则得到满足。ICP 算法的母的是找到目标点集与参考点之间的旋转R和平移T变换，使得两匹配数据中间满足某种程度 度量准则下的最优匹配。假设目标点集P的坐标为{}及参考点集Q的坐标为
聚类分析K-means算法综述
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
各种聚类算法的比较
各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类
1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解
迭代算法
算法设计之迭代法 军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A，B两人的位置，规定在前面的数大于后面的数，则是A>B，B>A交替出现。但现在假设军中有一个胆小鬼，同时大家又都很照顾他，每次冲锋都是让他跟在后面，每当前面的人占据一个新的位置，就把位置交给他，然后其他人再往前占领新的位置。也就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B（即执行B = A操作），然后A 再前进占领新的位置，B再跟上……直到占领所有的阵地，前进结束。像这种两个数一前一后逐步向某个位置逼近的方法称之为迭代法。 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下三个方面的工作： 一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 最经典的迭代算法是欧几里德算法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a, b) = gcd(b, a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 。假设d是a,b的一个公约数，则有 d% a==0, d%b==0，而r = a - kb，因此d%r==0 ，因此d是(b, a mod b)的公约数 同理，假设d 是(b, a mod b)的公约数，则 d%b==0 , d%r==0 ，但是a = kb +r ，因此d也是(a,b)的公约数。 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。 欧几里德算法就是根据这个原理来做的，欧几里德算法又叫辗转相除法，它是一个反复迭代执行，直到余数等于0停止的步骤，这实际上是一个循环结构。其算法用C语言描述为： int Gcd_2(int a, int b)// 欧几里德算法求a, b的最大公约数 { if (a<=0 || b<=0) //预防错误 return 0; int temp; while (b > 0) //b总是表示较小的那个数，若不是则交换a，b的值 { temp = a % b; //迭代关系式
基于迭代近点算法的地图拼接方法研究
基于迭代近点算法的地图拼接方法研究
基于迭代最近点算法的地图拼接方法研究
毕业设计（论文）原创性声明和使用授权说明 原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：日期：
学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 涉密论文按学校规定处理。 作者签名：日期：年月日 导师签名：日期：年月日
基于RRT的运动规划算法综述
基于RRT的运动规划算法综述 1.介绍 在过去的十多年中，机器人的运动规划问题已经收到了大量的关注，因为机器人开始成为现代工业和日常生活的重要组成部分。最早的运动规划的问题只是考虑如何移动一架钢琴从一个房间到另一个房间而没有碰撞任何物体。早期的算法则关注研究一个最完备的运动规划算法（完备性指如果存在这么一条规划的路径，那么算法一定能够在有限时间找到它），例如用一个多边形表示机器人，其他的多边形表示障碍物体，然后转化为一个代数问题去求解。但是这些算法遇到了计算的复杂性问题，他们有一个指数时间的复杂度。在1979年，Reif则证明了钢琴搬运工问题的运动规划是一个PSPACE-hard问题[1]。所以这种完备的规划算法无法应用在实际中。 在实际应用中的运动规划算法有胞分法[2]，势场法[3]，路径图法[4]等。这些算法在参数设置的比较好的时候，可以保证规划的完备性，在复杂环境中也可以保证花费的时间上限。然而，这些算法在实际应用中有许多缺点。例如在高维空间中这些算法就无法使用，像胞分法会使得计算量过大。势场法会陷入局部极小值，导致规划失败[5],[6]。 基于采样的运动规划算法是最近十几年提出的一种算法，并且已经吸引了极大的关注。概括的讲，基于采样的运动规划算法一般是连接一系列从无障碍的空间中随机采样的点，试图建立一条从初始状态到目标状态的路径。与最完备的运动规划算法相反，基于采样的方法通过避免在状态空间中显式地构造障碍物来提供大量的计算节省。即使这些算法没有实现完整性，但是它们是概率完备，这意味着规划算法不能返回解的概率随着样本的数量趋近无穷而衰减到零[7]，并且这个下降速率是指数型的。 快速扩展随机树(Rapidly-exploring Random Trees，RRT)算法，是近十几年得到广泛发展与应用的基于采样的运动规划算法，它由美国爱荷华州立大学的Steven M. LaValle 教授在1998年提出，他一直从事RRT算法的改进和应用研究，他的相关工作奠定了RRT算法的基础。RRT算法是一种在多维空间中有效率的规划方法。原始的RRT算法是通过一个初始点作为根节点，通过随机采样，增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域，便可以在随机树中找到一条由树节点组成的从初始点到目标点的路径。 快速扩展随机树（RRT）也是一种数据结构和算法，其设计用途是用来有效搜索高维非凸空间，可应用于路径规划、虚拟现实等研究。RRT是一种基于概率采样的搜索方法，它采用一种特殊的增量方式进行构造，这种方式能迅速缩短一个随机状态点与树的期望距离。该方法的特点是能够快速有效的搜索高维空间，通过状态空间的随机采样点，把搜索导向空白区域，从而寻找到一条从起始点到目标点的规划路径。它通过对状态空间中的采样点进行碰撞检测，避免了对空间的建模，能够有效的解决高维空间和复杂约束的路径规划问题。RRT 算法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划问题[8]。与其他的随机路径规划方法相比，RRT算法更适用于非完整约束和多自由度的系统中[9]。 相比于最原始的RRT算法的一些缺点，又提出了许多改进的RRT算法，例如：（1）基于概率P的RRT 为了加快随机树到达目标点的速度，简单的改进方法是：在随机树每次的生长过程中，根据随机概率（0.0到1.0的随机值p）来选择生长方向是目标点还是随机点。2001年，LaValle
基于特征光流的角点匹配快速算法
第33卷第4期 光电工程V ol.33, No.4 2006年4月 Opto-Electronic Engineering April, 2006 文章编号：1003-501X(2006)04-0085-04 基于特征光流的角点匹配快速算法 杨常清，王孝通，李博，金良安 ( 海军大连舰艇学院航海系，辽宁大连 116018 ) 摘要：为了解决视频序列点匹配过程中的实时性和误匹配问题，本文提出了一种基于特征光流技术的快速角点匹配方法。该方法通过多分辨率策略，求出特征光流场概略运动矢量，然后依据匹配准则做相应特征点匹配处理，得到的精确运动矢量用作下一步的光流场计算。这样，既消除了误匹配点，又克服了光流计算的迭代负担。实验结果表明，算法正确匹配率达到98%以上，平均处理帧率24，能够满足系统实时性要求。 关键词：运动估计；点匹配；特征光流；实时性；多分辨率 中图分类号：TN941.1 文献标识码：A Fast point matching method based on feature optical flow YANG Chang-qing，WANG Xiao-tong，LI Bo，JIN Liang-an (Department of Navigation, Dalian Naval Academy, Dalian 116018, China ) Abstract：To solve the general point correspondence problem in motion estimation, a new fast point matching algorithm based on feature optical flow is proposed. This algorithm calculates cursory motion vector of feature optical flow with multi-resolution tactic, and then do feature point matching by the matching criterion. The obtained precision motion vector is used in the next optical flow calculation. The algorithm can avoid wrong matching and solve the problem of operation load. The experiments show that this algorithm has the right matching rate 98% and process rate 24 frame/second on average. Key words：Motion estimation; Point matching; Feature optical flow; Real-time; Multi-resolution 引言 特征点(角点)匹配是视频序列运动估计常用算法之一。所谓点匹配，就是在两个2D或3D的点集之间找到几何映射和对应关系。然而，由于噪声、出格点(Outliers)以及非刚性映射的存在，使得角点匹配难以满足系统要求。为此，人们进行了广泛的研究。文献[1]提出通过最小化两个点集之间的Hausdorff距离，来寻找它们之间的仿射变换，这种方法虽然可以排除大量的出格点，但对噪声很敏感。由Ranade最早提出的松弛标记法[2]已广泛应用于点匹配问题中，但这种方法没有考虑一对一匹配的约束，文献[3]在松弛标记框架下应用了确定性退火算法的形式，但是也仅考虑了单向的匹配约束。文献[4]提出了一个同时处理空间映射和对应关系的目标函数，通过最小化目标函数来求解点匹配问题。但是这些方法在排除出格点的同时都不能保证点集之间一一对应。迭代最近点算法(ICP)[5]是通过最小化一点与另一点集中的最近点之间的距离，来求解它们之间的空间变换。文献[6]在ICP的基础上提出共线性以及特征提取等策略实现两个点集的配准。通过求取最小化函数或者穷举算法来实现匹配，都不能保证算法的实时性。 本文为了提高点匹配的鲁棒性和实时性，提出了一种基于特征光流的点匹配算法。该算法首先采用多分辨率策略，求解出特征光流场概略运动矢量，然后根据特征空间匹配策略做相应特征点匹配处理，将得 收稿日期：2005-03-22；收到修改稿日期：2005-08-22 基金项目：“十五”国防预研课题 作者简介：杨常清(1976-)，男(汉族)，辽宁丹东人，博士生，主要从事电子稳像、图像处理研究。E-mail: changqing527@https://www.wendangku.net/doc/715131652.html,