通用算法（精选九篇）
通用算法 篇1
自然语言信息隐藏技术利用自然语言处理技术对文本内容进行分析,得到文章中可以替换的文字片段,如单词、句子等,通过改写或替换文字片段进行信息隐藏。根据操纵的语言单位不同,可以分为基于词汇的信息隐藏、基于句法的信息隐藏和基于语义的信息隐藏。
以自然语言为内容的信息交换是人们交流信息的主要方式,文本文档根据其应用需求不同,对信息隐藏方案的性能要求也不尽相同。如军事部门、政府机关、国家安全部门以及一些商业机构对文本的安全性要求较高。通过在文本中嵌入数字指纹,可以在机密泄漏后追踪泄密者。而在电子书籍、通讯稿、新闻稿等文本载体中嵌入数字水印可以提供版权保护。在电子商务,数字图书馆等领域,文档在拷贝分发过程中需要确定其内容是否被篡改或伪造,这时可以通过嵌入脆性水印来进行数据完整性认证和版权验证。
1 现有文本信息隐藏算法分析
通过对现有自然语言信息隐藏算法的分析,其存在如下问题:
(1)隐藏容量。
在进行秘密信息嵌入时,根据载体文本的篇幅长短以及行文风格不同,文本能够为信息隐藏技术提供的隐藏空间也不一样。如在版权保护领域,通讯稿、新闻稿等篇幅较短的文本,一般能够提供的隐藏空间非常有限,而且容易被攻击者找到从而破坏水印信息。而且篇幅较长的小说中,为防止局部内容的抄袭,需要在文章中多个地方重复嵌入水印信息,来提供版权保护。但现有的文本信息隐藏算法还无法提供足够的隐藏容量来满足不同的应用需求。
如现有的基于同义词替换的文本信息隐藏算法,需要用到同义词词库。而目前还没有完全适合信息隐藏算法的大型同义词库。同义词库中同义词集太少,导致同义词替换算法的隐藏容量无法满足嵌入要求。因此,迫切需要建立全面、权威的同义词库来提高隐藏容量。
而现有的句法变换信息隐藏算法,在文本中嵌入一个字符,按照ASCII编码方式,一个字符占8个二进制bit位。以文献[18]中的句法变换方法为例,将可变换句子分为“标识句”和“水印句”。如果一个“水印句”只承载一个比特的信息,嵌入一个字符至少需要16个句子。若将该技术应用于版权保护,需要在文本中嵌入作者信息,以30个字符为例,文本中至少需要480个可变换的句子。于是,在新闻稿件,短篇小说等篇幅较小的文本中嵌入作者信息就变得不现实。
(2)隐藏算法的通用性。
如使用同义词替换算法在文学著作中嵌入秘密信息,由于词语的使用存在少许差异,所以对原文的表达力会造成影响,容易被察觉,从而使秘密信息的隐蔽性得不到保证。再如,对于网络小说在网络中传播等攻击普遍存在的应用场景,文本在传递过程中会被大量且多次修改,如果采用简单的从左向右向文本中嵌入秘密信息,对于文本的简单修改,就有可能打乱秘密信息的同步信息,比如将原先的秘密信息由“01000100”,改变为“1000100”,从而导致提取出的秘密信息完全失去意义。
2 自然语言信息隐藏抽象算法
2.1 载体单元的概念
目前的自然语言信息隐藏算法只是使用文本中某一种文字片段进行信息隐藏,而其它文字片段并没有得到有效利用。如基于同义词替换的信息隐藏算法只使用文本中可以替换的同义词。基于句法变换的信息隐藏算法只使用文本中可以变换的句子。从根本上讲,无论单词还是句子都是文本的一个语义单元,只是大小不同而已。对于隐藏编码而言,这些文字片段都是承载秘密信息比特位的语义单位。如果将多种变换方法应用到同一个信息隐藏算法中,则可以极大地提高隐藏容量。而且多种文字片段混合使用,也提高了隐藏算法的鲁棒性,使得攻击者针对某一类变换方法的攻击成功率大大降低。
为抹去不同自然语言处理技术的不同,实现多种自然语言处理技术的协同工作,提出载体单元的概念。载体单元的定义如下:
对于特定自然语言处理技术,将可以做语义不变替换的文字片段称为载体单元。
载体单元作为一个抽象概念,对不同的自然语言处理技术具有不同的意义。例如对于同义词替换技术,载体单元即具有同义词的词语;对于句式变换技术,载体单元即可以进行句式变换的句子。这样无论在信息隐藏中使用何种自然语言处理技术,均可以将其可处理的文本统一作为载体单元。
由于载体单元是一个抽象概念,所以在程序中以接口的形式定义它。其属性列表如表1所示。
2.2 算法的分离
以载体单元的概念为纽带,可以进一步将自然语言信息隐藏算法分离为载体操纵算法和隐藏编码算法。现有的自然语言处理技术,主要关注与对于文本进行变换,没有关注隐藏编码,将隐藏编码算法单独分离出来,有利于实现鲁棒性和隐蔽性更好的隐藏方案,有利于提高系统的扩展性,同时也有利于代码的复用。
2.2.1 载体操纵算法的定义
对于载体操纵算法,需要完成以下功能:
(1)分析文本功能。对于给定文本片段c┃ ┃┃┃┃ C,扫描得到c中的对应类型的载体单元,同时对载体单元进行可行变换,将变换结果存储在载体单元Ti的中,将找到的载体单元加入载体单元集合S。并标识在该片段中嵌入信息是否可能会和其他载体操纵算法冲突。即S=Traverse(C)过程的和Transform过程,不同的是,对于特定载体操纵算法未必可以得到S集合的全部,通常只能得到S的一个子集,并且具体实现中,如果两个载体操纵算法在同一个片段中嵌入信息,则可能存在冲突。
(2)嵌入功能。对于给定载体单元和需要嵌入的具体bit,如果是该载体操纵算法对应的载体单元,使用载体单元中定义的可用于替换的文本片段替换文本片段中的相应内容,使之表示给定bit。即Embed ding(Si,Ti,Mg,Pi,ComputeBit,K)。
(3)提取功能。对于给定的载体单元,如果是该载体操纵算法对应的载体单元,分析该载体单元目前表示的bit;并确定在嵌入过程中是否由于当前载体操纵对文本的修改,导致该文本片段中已经不存在其他类型的载体单元。即M1=Extracting(S″,ComputeBit,K)的一个子过程,该过程只处理一个载体单元,并得到对应比特。
2.2.2 隐藏编码算法的定义
对于隐藏编码算法,需要完成以下功能:
(1)确定Ti中每个文本表示的bit。对于已有的载体单元集合S,确定集合中每个元素对应的集合T中的每个元素的bit,将得到的bit串,由对应载体单元记录,即ComputeBit过程。
(2)分组载体单元。确定S中每个元素对应嵌入Mg的哪个分组,即Blocking过程,由对应载体单元记录结果,即pi。
(3)重排序Mg。按照S中每个元素的pi值,将秘密信息进行重新排序,并对空白的位置补充无效字符,使得载体单元集合中第i个元素和秘密信息中第i个分组对应。该过程是为嵌入过程的算法复杂度考虑,即在嵌入过程中,只需顺序地嵌入重新排列后的bit串,不需要再在原有bit串中查找。
(4)恢复M1顺序。与c过程相反,本过程将M1,按照已有载体单元集合中每个载体单元pi的值,恢复其原始顺序,即Recover过程。
(5)编码过程。即对给定秘密信息进行编码和分组,具体过程视不同的编码算法而定。该过程即Encode过程。
(6)解码过程,对于已经提取得到的bit串,按照解码算法将之复原为原始秘密信息的二进制序列,具体过程视不同编码算法而定。即Decode过程。
2.3 抽象算法的设计
2.3.1 嵌入算法
在载体单元、载体操纵和隐藏编码3个接口之下。提出的通用信息隐藏算法可以描述如下:
嵌入信息时,先利用载体操纵算法对文本进行分析,得到文本中所有载体单元,然后对载体单元进行预变换,得到每个载体单元对应的同义集合。然后利用隐藏编码算法对载体单元集合中所有元素进行编码,通过密钥选择对应编码的同义单元来嵌入秘密信息。
提取信息是嵌入的逆过程。提取时,也需要先利用载体操纵算法对含密文本进行分析,得到文本中所有载体单元,然后进行预变换,获得载体单元对应的同义集合。然后利用隐藏编码算法对载体单元进行编码,通过密钥选择载体单元,并获取载体单元对应的比特来还原秘密信息。
对于嵌入过程描述中需要使用到的符号定义如下:
C为原始文本;K为密钥;S为原始文本中提取出来的载体单元集合,类似的S中第i个元素表示为Si;Ti为可以替换第i个载体单元的文本的集合;M为需要嵌入的秘密信息;Mg为分组并编码后的M,由若干个分组组成;Pi为第i个载体单元需要对应嵌入Mg的第几个分组。
抽象嵌入过程描述如下:
(1)分析文本。S=Traverse(C),S={S0,S1,…,Sn}。即使用某种或者某几种自然语言处理技术分析文本,得到C中所有的载体单元。S中各元素可能是不同类型的载体单元,例如S0对应文本中一个可以替换为其同义词的词语,而Si对应的却是文本中的一个可变换句式的句子。
(2)生成所有可行变换。Ti=Transform(Si),T={S
(3)确定Ti中每个文本表示的bit。ComputeBit(Ti,S
(4)分组载体单元。考虑到分组编码的需求,需要对载体单元进行分组。Pi=Blocking(Si,K),Pi∈N*。该函数返回值为载体单元Si需要对应嵌入Mg的第几个分组。具体应用中,对于不需要分组的算法,则将每组包含的载体单元数量设置为1。基于鲁棒性考虑,分组与载体单元在原文中顺序无关。分组的目的是把秘密信息的比特顺序和实际嵌入的顺序打乱。如果将M顺序的嵌入到S中,秘密信息集中在文本的首部,攻击者可能通过篡改或统计分析等手段破坏或破解秘密信息,所以鲁棒性较差。
(5)分组并编码秘密信息。Mg=Encoding(M,K)。对于秘密信息M进行编码和分组。
(6)嵌入。Embed ding(Si,Ti,Mg,Pi,ComputeBit,K),作为最终嵌入过程就是将Mg的第Pi个分组嵌入到Si中,也就是使用Ti中Compute(Ti,S
(7)生成含密载体。即将嵌入秘密信息后的文本输出。
2.3.2 提取算法
对于该过程描述中需要用到的符号定义如下:
C′为嵌入了秘密信息的文件,即含密文本;K为密钥;S′为含密文本中提取出来的载体单元集合,类似的S′中第i个元素表示为S′i;T′i为可以替换第i个载体单元的文本的集合;M为秘密信息,类似的M1,M2等为对于M的变换形式;P′i为第i个载体单元需要对应嵌入的秘密信息的第几位。
则秘密信息的提取过程可以描述如下:
(1)分析文本。S′=Traverse(C′),S′={S′0,S′1,…,S′m}。即使用嵌入秘密信息时使用的自然语言处理技术分析文本,得到C′中所有的载体单元。
(2)生成所有可行变换。Ti=Transform(S′i),T′i={S
(3)提取。M1=Extracting(S′,ComputeBit,K)。这一步从C′中初步提取,得到bit串M1。此处的ComputeBit与嵌入时使用的ComputeBit函数相同。
(4)分组载体单元。P′i=Blocking(S′i,K),P′i∈N*该过程与嵌入过程类似,是对S′分组。
(5)恢复秘密信息顺序。M2=Recover(M1,Blocking)即将提取出来的M1恢复到原始的顺序。
(6)解码。M3=Decoding(M2,K)。该过程是对M2解码,得到的M3即提取得到的秘密信息。
3 自然语言信息隐藏平台实现
在提出的自然语言信息隐藏抽象算法框架下,设计并实现了一个信息隐藏通用平台。该平台的结构如图1所示,最上层是展示层,负责嵌入秘密信息后载体文本的可视化展示,编码方案展示以及提取后的秘密信息解码结果展示。
核心模块是中间层的“自然语言信息隐藏系统框架”,它只是一个通用的信息嵌入和提取的系统框架。框架向下定义了载体操纵算法接口和隐藏编码算法接口。通过框架设计将载体操纵部分和隐藏编码部分进行了分工。展示层定义了两部分内容:一个是内部算法的API接口,由展示层控制系统框架进行运转,并了解其工作过程;另一个是数据可视化接口,在界面上直观地显示嵌入、提取效果。下层的“载体操纵插件”和“隐藏编码插件”都以插件方式设计。并生成动态链接库到指定目录,框架运行时即可自动识别所有插件。
目前本原型系统实现的载体操纵插件包括:英文绝对同义词替换插件、英文相对同义词替换插件、英文句法变换插件、中文绝对同义词插件、中文句式变换插件。隐藏编码插件包括随机编码插件、扩频编码插件和F5编码插件。
4 实验
为验证文中提出的信息隐藏抽象算法,从网络上收集了1 000篇英文语料,构建了测试语料库。这1 000篇英文语料涵盖了人文社会、自然科学、新闻、综合4大类。使用的自然语言处理工具包括:Lingpipe,Stanford Lexicalized Parser。其中Lingpipe使用其单词歧义消解(Word Sense Disambiguation)功能,Stanford Lexicalized Parser使用其语法解析功能。
4.1 隐藏容量
图2是对一个20 kB的英文文本,分别使用英文绝对同义词替换隐藏方法、英文相对同义词替换隐藏方法、英文句式变换隐藏方法和文中的信息隐藏抽象算法对其进行载体分析,所获得的载体单元数量。由图2可以看出,在使用载体单元的概念后,可以将所有可变换的语言单元结合到一个编码算法中。极大地提高了信息隐藏算法的隐藏容量。
4.2 通用性
由于不同算法在隐蔽性、鲁棒性和隐藏容量上的不同性能,对于特定的应用,就可以灵活选择不同插件,构建隐藏方案。
5 结束语
通过对现有自然语言信息隐藏算法进行分析,发现现有隐藏算法的隐藏容量不足,算法的通用性较差。无法满足实际应用的多样性需求。为获得容量足够大且载体单元覆盖面足够广的隐藏算法,提出了一种自然语言信息隐藏抽象算法。通过定义载体单元、载体操纵和隐藏编码三个抽象接口。对现有自然语言信息隐藏算法进行了抽象化处理。通过对这三个抽象接口的实例化,设计并实现了一个自然语言信息隐藏平台。最后通过实验证明,文中提出的信息隐藏抽象算法的隐藏容量有了极大提高,而且也极高了隐藏编码算法的通用性。
摘要：自然语言信息隐藏技术是近年来信息安全领域的一个研究热点。文中通过对现有自然语言信息隐藏算法进行分析,发现现有算法普遍存在隐藏容量不足,无法通用于多种应用场景的问题。为获得容量足够大且通用性好的隐藏方案,提出了一种自然语言信息隐藏通用抽象算法。该抽象算法以载体单元的概念为纽带,将自然语言信息隐藏算法分离为载体操纵算法和隐藏编码算法,继而实现了对现有算法的抽象。该抽象算法可以实现多种载体操纵算法的协同使用,最大程度地利用文本内容,有效提高了隐藏容量,同时由于可以针对不同的应用场景灵活搭配不同的嵌入方案,解决了通用性问题。最后通过实验证明该抽象算法的通用性。
通用算法 篇2
求解作业排序问题的通用混合遗传算法研究
车间作业排序理论是生产管理与组合优化领域的重要研究方向,由于其固有的计算复杂性(NP-Hard),一般无法利用经典方法求出最优解.本文针对一般作业排序问题,将遗传算法与启发式方法相结合,建立了一种混合算法框架,利用遗传算法改进启发式方法的求解性能,同时利用启发式方法引导遗传搜索过程,以提高其搜索效率.通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明,该方法对不同类型的.排序问题均具有相当满意的求解效果.
作 者：周泓 姬彬 作者单位：北京航空航天大学经济管理学院,刊 名：系统工程理论与实践 ISTIC EI PKU英文刊名：SYSTEMS ENGINEERING――THEORY & PRACTICE年，卷(期)：200121(12)分类号：O223 C931.1关键词：作业排序 遗传算法 启发式
通用算法 篇3
关键词：支持向量机；SVM；PRP-SVM；CGM-OC-SVM
中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)15-30814-02
A Algorithm of SVM for any Kernel
TAO Mei, Wushour·Silamu
(School of Information and Engineering Xinjiang University，Wulumuqi 830046, China)
Abstract: Taking support vector machines (SVM) and the traditional statistics classification method as the research object, introduces the classification method theory of SVM algorithms，and based on PRP-SVM，then puts forward the orthogonal adjustment conjugate gradient iteration algorithm of support vector machines (CGM-OC-SVM), meanwhile the CGM-OC-SVM algorithm is carried out by the C programming language，and doing a graphic simulation using Matlab.
Key words: Support vector machine; SVM; PRP-SVM; CGM-OC-SVM
1 引言
数据挖掘中，数据的分类与回归问题是其重要的研究对象。常用于分类和回归的方法，如Bayes 分类、Logistic 回归、神经元网络等在实现机器学习时，都是基于经验风险最小化原则的。然而，一般在有限样本的情况下，经验风险最小不一定意味着期望风险最小，在有些情况下会出现“过学习”和推广性不好等情况，得到的实验结果并不是很理想。
Vapnik 于上世纪90年代初提出的支持向量机（SVM），是数据挖掘中的一项新技术。它是在统计学习理论的基础上，借助于最优化方法解决机器学习问题的新工具。该算法是一个凸优化问题，即局部最优解就是全局最优解，这是其他学习算法所不及的。SVM 基于结构风险最小化原则，能很好地解决有限数量样本的高维模型构造和“过学习”问题，具有良好的推广性和较好的分类精确性，已被应用于人脸识别、医疗诊断等方面。
尽管SVM 的应用领域很广，但其理论研究还相对滞后，其中就包括算法本身改进和算法的实际应用。支持向量机分类器最终可以转化为解决一个二次规划问题，目前的研究大都集中于如何在训练数据较多的情况下来解决这个二次规划问题。现基于改进共轭梯度迭代PRP-SVM 算法的基础，提出一种对任何SVM 核通用的正交校正共轭梯度迭代支持向量机算法（CGM-OC-SVM），并通过程序实现此算法，利用Matlab进行算法结果的图形模拟。
2 支持向量机（SVM）
SVM与传统统计学的大样本量研究方向不同，它最大的特点是遵循“结构风险最小化原则”，尽量提高学习机的泛化能力，即由有限的训练样本集获得小的误差的特性，保证对独立的测试集有小的误差，从而解决了有限样本的“过学习”问题（即机器复杂性越高，则置信范围越大，导致真实风险与经验风险可能的差别越大）。目前，该技术已应用到手写体识别、人脸识别、指纹识别、语音识别、数据挖掘等领域。
SVM的核心理论包括：(1)VC维理论，不仅要使机器学习的经验误差最小，而且应该最小化函数集的VC维，从而控制学习机的结构误差，使SVM分类器具有较强的泛化能力；(2)引入最优超平面概念，使函数的VC维上届达到最小，而最优超平面问题可以转化为二次规划问题；(3)核空间理论，通过非线性映射将输入空间映射到高维特征空间，使低维输入空间线性不可分问题转化为高维特征向量空间线性可分问题，并通过核函数绕过高维空间，使计算在低维输入空间进行，从而不需知道非线性映射的具体形式。
2.1 线性SVM最优分界面
2.1.1 线性可分情况
假定训练数据为 个观测样本(x1,y1),(x2,y2)…(xn,yn),xi∈Rp,yi∈{+1,-1}，则存在超平面(w·x)+b=0线性可分，使训练点中的正类输入和负类输入分别位于该超平面的两侧，或者说存在参数对(w,b)，使得yi=sgn((w·xi)+b),i=1,…,n这样的超平面通常不止一个，因此，我们的目的是要找到一个最优分类超平面，使分类面经验风险最小（即错分最少），并且推广能力最大（即空白最大）。如图1中(a)、(b)所示：
图1 2-class分类
SVM问题的数学表示为：
2.1.2 线性不可分情况
2.2 非线性SVM最优分界面
在很多情况下，数据是线性完全不可分的，这就属于非线性划分问题。我们可以通过非线性映射将向量x映射到一个高维特征空间Z，在这个高维特征空间中构造最优平面或推广的最优分类超平面。即通过函数Φ:Rn→Z将所有样本点映射到高维空间，将原来的xi·xj变为Φ(xi)·Φ(yi)形式，记核函数K(xi,xj)=Φ(xi)·Φ(yi)。常见的满足Mercer条件的核函数有多项式核函数K(xi,xj)=[(xixj)+1]d和高斯径向基核函数（即RBF核）
该策略的主要思想是对N分类问题构建N个支持向量机，每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面w·b+b距离最大的那个支持向量机决定。
2.3.3 层次策略
该策略的主要思想是对N分类问题构建若干个支持向量机，且它们之间是有层次地连接成一个有向无环图的结构，分类结果根据图经过的若干个支持向量机的判别得到。
3 算法模拟
CGM-OC-SVM算法是用C语言编写的，并选择RBF核作为核函数，现应用该算法分别对平面上两点和多点训练样本点进行分类训练、算法模拟。
(1)设x,y平面上的2个训练样本点为α=(1,1),b=(2,3)
假设训练集为S={(a,-1),(b,1)}，其中a是-1类点，b是+1类点。取核参数δ=1，惩罚参数C=2时，采用改进的CGM-OC-SVM算法求解得α*=(1,1)，设定x,y平面上的一点为k=(x,y)，分类函数为：，
内层迭代次数为1，外层迭代次数为1。利用Matlab分别作其三维、二维模拟图，见图3(a)和(b)。
图3
(2)设x，y平面上的5个训练样本点为a=(3,1),b=(4,2),c=(8,0.3),d=(2,3),e=(3,4)
假定训练集为S={(a,-1),(b,-1),(c,-1),(d,1),(e,1)}，其中a,b,c是-1类点，d,e是+1类点。取核参数δ=1，惩罚参数C=2时，采用改进的CGM-OC-SVM算法求解得α*=(0.801222,0.799457,0.799498,1.200462,1.20044)，设定x,y平面上的一点为k=(x,y)，分类函数为：
内层迭代次数为1，外层迭代次数为1。利用Matlab分别作其三维、二维模拟图，见图4(a)和(b)。
图4
4 结束语
由于支持向量机是建立在统计学习理论的VC维理论和结构风险最小原理的基础上，根据有限样本在学习精度和学习能力之间寻求最佳折衷，因此具有最好的推广能力。提出的CGM-OC-SVM算法改进了PRP-SVM算法只能选择多项式核函数的缺点，具有通用性。
参考文献：
[1] 邓乃扬, 田英杰. 数据挖掘中的新方法——支持向量机[M]. 北京：科学出版社,2004.
[2] 张学工. 关于统计学习理论与支持向量机[J]. 自动化学报，2000,26(1).
[3] 黄琼英. 支持向量机多类分类算法的研究与应用[D]. 河北：河北工业大学，2005.
[4] E.Osuna, R.Freund, and F.Girosi Support Vector Machines: Training and Applications A.I. Memo 1602, MIT Artificial Intelligence Laboratory, 1997.
[5] Zhang Ling, Zhang Bo. Relationship between Support Vector Set and Kernel Functions in SVM, J.Comput.Sci.&Technol,2002,17(5):549.
[6] O Chapelle，V Vapnik et al.Choosing Multiple Parameters for Support Vector Machine[J]. Machine Learning,2002,46:131-159.
配电网故障区间判断的通用矩阵算法 篇4
对配电网故障进行准确诊断和定位、迅速隔离故障并恢复非故障区域供电是馈线自动化的主要功能。随着城乡电网改造及其DAS的普遍开展,配网中大量使用FTU等现场监控终端,在断路器、分段开关和联络开关上一般都装有FTU用来采集线路信息从而上传给控制中心,同时接收控制中心指令操纵断路器、分段开关和联络开关动作,为迅速、准确地实现馈线自动化功能奠定了基础。随着分布式发电技术的发展,我国配电网运行方式已不再是单一的单电源辐射状网络。为了适应配电网这一发展需求,已有文献利用过热弧搜索[1],优化算法[2]以及矩阵算法等方法对多电源并列供电配电网进行故障定位。其中,矩阵算法因其简明直观、计算量小等特点,应用更为广泛。
文献[3]的统一矩阵算法需要矩阵相乘和进行大量规格化处理,只适合单电源树状网络,不能判断馈线末端故障。文献[4]的简单矩阵算法不需要进行大量的规格化处理,但也不能判断馈线末端故障。文献[5]对文献[3]进行了改进,克服了不能判断馈线末端故障的弊端。但是文献[3~5]都不适用于环状运行网络。文献[6]也不适合馈线末端故障,且需要矩阵相乘和规格化处理,计算速度慢。文献[7]和文献[8]的算法不适用于馈线末端故障。文献[9]和[10]能解决馈线末端故障问题,但它们和文献[8]一样在解决同一环网上的多重故障问题时会产生漏判现象,比如判断图2的故障情况时就只能判断出一个故障,而漏掉另外两个故障。以上对故障定位所作的大量研究中所得到的方法都存在着某种缺陷,所以本文在以上各算法的优缺点的基础上提出一种通用的矩阵算法,可以解决各种类型的故障问题。方法简单、直观,有较强的实用性。
1 通用算法的原理
1.1 概述
由于配电网网络庞大,结构复杂,如果把整个配电网看作一个整体来进行故障定位,其工作量很大,所以这里采用分区分层的办法。首先以常开型联络开关为分界点把配电网络分成许多小区。然后把各个小区内的断路器,分段开关和常闭型联络开关当作节点进行编号,节点编号必须包含节点的属性即节点属于哪个小区,这样当网络发生故障时就可以根据上传故障信息的FTU的编号很快判断出发生故障的小区,然后就可以只对故障小区的配网进行研究,而不考虑其它网络,这样大大缩小了网络的规模,加快计算速度。确定故障小区后,对小区内的馈线规定一个正方向,按照节点之间的有向连接关系形成网络描述矩阵。然后再根据FTU上传的故障信息对网络描述矩阵进行修正形成故障判断矩阵。无须对故障判断矩阵进行规格化处理就可以直接判断故障发生的位置。
1.2 形成网络描述矩阵D
首先给故障小区网络假定一个正方向,正方向的制定原则是:对于单电源网络,线路功率的流出方向即为馈线的正方向;对于多电源网络,先假定该网络由某一个电源供电,由这个电源向全网供电的功率流出方向即为网络的正方向。然后根据各节点的编号和节点之间的有向连接关系构造网络描述矩阵D。若节点i和节点j之间存在一条馈线且该馈线的正方向是由节点i指向节点j,则对应的网络描述矩阵D中的元素dij=1,而dji=-1,第i行的其它元素置0。
1.3 生成故障判断矩阵P
参考文献[6],充分利用配电网的结构特点,在馈线终端单元(FTU)装置中设置1、-1和0三种工作模式。在1模式下,节点i流过故障电流且过流方向和所选网络正方向相同,节点i的FTU向控制中心发送故障信息1;在-1模式下,节点i流过故障电流但过流方向和所选网络正方向相反,节点i的FTU向控制中心发送故障信息-1;在0模式下,节点i没有故障电流,节点i的FTU不向控制中心发送故障信息。节点i的FTU处于工作模式1时,置矩阵D中的元素dii为1;处于工作模式-1时置矩阵D中对应元素dii为-1;处于工作模式0时置矩阵D中对应元素dii为0。这样便可生成故障判断矩阵P。
1.4 故障诊断原则
由故障判断矩阵就可以判断出故障区段,其具体的判断原则如下:
(1)当配电网的故障发生在节点i和节点j之间时,其判别条件有两条。条件一:pii=1,对所有pij=1的j(j≠i),都有pjj=0或-1。条件二:pii=-1,对所有pij=-1的j(j≠i),都有pjj=0。满足上述条件中的任一条就可以判断节点i和节点j之间发生了故障。
(2)当故障发生在末端i时,其判别条件是:pii=1,对于所有的pij(j≠i),都不等于1。末端故障定位原理的物理意义是:当某点i流过故障电流,且若以这点为起点并不存在其它连接到该点上的点(如存在,则dij=1(j≠i)),那么末端i必然发生故障。
2 算例分析
2.1 简单网络
如图1所示为一个有A、B和C三电源供电的网络,它们之间由常开型联络开关相连,形成开环运行。首先以常开型联络开关为分界点把此配电网分成A区,B区和C区。分别对每个小区的节点(测控点)进行编号,如图所示,节点编号包含有自己的小区属性,例如2A就表示此节点是A区的2号节点。当网络发生故障时,一些测控点会向控制中心上传故障信息,控制中心通过这些上传故障信息的测控点的编号就可以判断出发生故障的小区。假设现在控制中心得到的故障信息来自B区,那么首先确定是B区发生了故障,然后就只对B区的三个节点进行分析,而不去考虑A区和C区,这样需要分析的节点只有三个,形成的网络矩阵和判断矩阵也都只是3×3的矩阵,矩阵规模小,运算量很小。如果不进行分区,对整个网络的节点进行分析,则需要分析14个节点(包括常开型联络开关),形成14×14的矩阵,矩阵规模很大,计算速度慢。所以首先对配网进行分区对快速故障定位起了重大作用。
判断出是B区发生故障后,对B区网络规定一个正方向,以电源B进行供电时功率的流出方向为网络的正方向,然后形成B区的网络描述矩阵
如果是节点2B和3B之间发生故障,那么节点1B和2B的FTU处于1工作模式,根据故障信息对网络描述矩阵D进行修正,令d11和d22都等于1,这样得到的故障判断矩阵为
观察矩阵P的元素:p22=1、p23=1、p33=0,根据故障判断原则(1),可判断是节点2B和3B之间发生了故障,判断准确。
如果是节点3B和与其相连的常开型联络开关之间发生故障,此种情况为馈线末端发生故障,那么节点1B、2B和3B的FTU处于1工作模式,根据故障信息对网络描述矩阵D进行修正,令d11、d22和d33都等于1,这样得到的故障判断矩阵为
观察矩阵P的元素:p33=1,对于所有的p3j(j≠3)都不等于1,根据判断原则(2),可以判断出故障发生在3B末端,判断准确。
2.2 复杂网络
图2为三电源并列供电模式下发生三重故障的配电网络,为了不失一般性,图中有意打乱了编号顺序。设故障点为K1,K2,K3。
首先此网络中没有常开型联络开关,所以可以不用再分区,把此网络看成一个整体进行分析。此网络属于多电源闭环供电网络,假设由电源A向全网供电,则功率流出的方向即为网络的正方向。按照图中的编号,根据节点间的有向连接关系形成网络描述矩阵为
然后根据故障信息来修正网络描述矩阵形成故障判断矩阵。此时网络中节点6和2的FTU处于1工作模式,则令d22=1、d66=1。节点1、3、4和8的FTU处于-1工作模式,则令d11=-1、d33=-1、d44=-1、d88=-1。最后得故障判断矩阵为
观察矩阵P中元素可知有三组元素:p22=1、p27=1、p77=0,p11=-1、p15=-1、p55=0和p44=-1、p49=-1、p99=0满足判定原则1,所以可知节点2和7之间,1和5之间,还有4和9之间发生了故障,即判断出了三个故障点K1,K2和K3,没有产生漏判现象。
3 结论
本文针对原有矩阵算法在配电网故障定位应用中存在的各种不足,提出了一种通用矩阵算法。该算法不仅适用于树状、辐射状网络和开环运行环状网络故障,还适用于环状运行网络故障,而且不仅能解决单电源单一故障问题,还能解决馈线末端故障问题和多电源环网多重故障问题。本算法采用先对配电网进行分区的思想使故障定位更为迅速,而且此方法的判断原理简单,不需要矩阵相乘也不需要烦琐的规格化处理,运算量小,运算速度快,对配电网运行工况的变化有很强的适应性。
参考文献
[1]江道灼,张锋,张怡.基于配电监控终端的配网故障区域判断和隔离[J].继电器,2002,30(9):21-24.JIANG Dao-zhuo,ZHANG Feng,ZHANG Yi.Fault Sections Detection and Isolation in Distribution System Based on FTU[J].Realy,2002,30(9):21-24.
[2]卫志农,何桦,郑玉平.配电网故障区间定位的高级遗传算法[J].中国电机工程学报,2002,22(4):127-130.WEI Zhi-nong,HE Hua,ZHENG Yu-ping.A Refined Genetic Algorithm for the Fault Sections Location[J].Proceedings of the CSEE,2002,22(4):127-130.
[3]刘健,倪建立,杜宇.配电网故障区段判断和隔离的统一矩阵算法[J].电力系统自动化,1999,23(1):31-33.LIU Jian,NI Jian-li,DU Yu.An Unified Matrix Algorithm for Fault Section Detection and Isolation in Distribution System[J].Automation of Electric Power Systems,1999,23(1):31-33.
[4]黄力.配电网故障定位的简单矩阵算法[J].湖北电力,2005,29(5):1-3.HUANG Li.A Simple Matrix Algorithm for Fault Detection in Distribution System[J].Hubei Electricity,2005,29(5):1-3.
[5]刘会家,王峥,陈玮.配电网故障定位统一矩阵算法的改进[J].三峡大学学报,2002,24(4):308-310.LIU Hui-jia,WANG Zheng,CHEN Wei.To Improve Unified Matrix Algorithm for Fault Detection in Distribution System[J].Journal of Three Gorges University,2002,24(4):308-310.
[6]刘耀湘,乐秀璠,顾欣欣.配电网故障区段判断和隔离的综合矩阵算法[J].电力自动化设备,2006,26(3):38-40.LIU Yao-xiang,LE Xiu-fan,GU Xin-xin.Synthesis Matrix Algorithm for Fault Section Detection and Isolation in Distribution System[J].Electric Power Automation Equipment,2006,26(3):38-40.
[7]王飞,孙莹.配电网故障定位的改进矩阵算法[J].电力系统自动化,2003,27(24):45-46,49.WANG Fei,SUN Ying.An Improved Matrix Algorithm for Fault Location in Distribution Network of Power Systems[J].Automation of Electric Power Systems,2003,27(24):45-46,49.
[8]卫志农,何桦,郑玉平.配电网故障区间定位的一种新算法[J].电力系统自动化,2001,25(14):48-50.WEI Zhi-nong,HE Hua,ZHENG Yu-ping.A Novel Algorithm for Fault Location in Power Distribution[J].Automation of Electric Power Systems,2001,25(14):48-50.
[9]蒋秀洁,熊信银,吴耀武,等.改进矩阵算法及其在配电网故障定位中的应用[J].电网技术,2004,28(19):60-63.JIANG Xiu-jie,XIONG Xin-yin,WU Yao-wu,et al.Improved Matrix Algorithm and Its Application in Fault Location of Distribution Network[J].Power System Technology,2004,28(19):60-63.
通用试卷库组卷策略及算法研究 篇5
随着教育教学改革的不断深入，教考分离、试卷规范化、标准化的呼声越来越高，如何满足这些新需求成了教育工作者潜心研讨的问题。而伴随着国家对教育发展投入的力度不断加大和全社会信息化水平的不断提高，采用计算机信息管理系统来解决教考分离、试卷规范化和标准化的问题是一种行之有效的办法。它既可以减轻人员的重复劳动，提高工作效率，更是各学校实现考务自动化，管理数字化、信息化的标志。在通用组卷的基本运行系统中，组卷需要考虑的问题如下：
1.1 检测相容性
因为题库是有限资源，因此用户对组卷的要求可能会与题库不相容(相矛盾)，题库不能同时满足有些组卷要求，这样就无法组成所要求的试卷。检测相容性就是对用户组卷要求的评判，从而可以及早发现不合理的组卷要求。
1.2 控制一份试卷中相同知识点的题目
被称作相同知识点(考察点)的题目包括两种，一种情况是两道试题题型相同，虽然字面表达不同或者计算参数不同，但是解题所用的方法完全相同;第二种情况是题型不同，但是考察同一内容，在一份试卷中不允许出现有重复知识点的试题。
1.3 组卷方法
组卷是该系统的核心。组卷问题实际上可以被看作一个复杂的组合优化问题。一般的题库都采取带着某种启发式的随机搜索策略进行逐题选取，然而由于组卷要求之间的彼此约束关系，到最后经常难以找到满足要求的试题，这必然影响试题搜索效率。
2 算法探究
智能组卷对提高考试质量有重要作用，目前，在计算机网络技术迅速发展的基础上组卷系统发展迅速，智能组卷的方法主要包括随机选取法、回溯试探法和遗传算法。
2.1 随机选取法
随机抽取法是根据用户提交的组卷要求，使用随机函数自动抽取若干试题构成状态类型，再从题库中随机抽取一道试题加入试卷中，如此反复进行，直到生成试卷或者再也无法从试题库中再取出符合要求的题目为止。
其中搜索过程包括随机选取状态分量，按状态分量随机从题库中抽取题目两步。通常，在进行第一步时，抽取多少个题目就需要随机抽取相应数量的状态分量，而产生每个状态分量又需要根据状态数纵向随机进行搜索，但是按照这个方式抽取的这些题目的状态通常很难满足用户的需求。通常情况下，如果随机产生N个数，只要次数足够多，那么各数出现的几率是相近的。但是，在实际组卷过程中，无论是难度、章节还是题型，都具有不同的分布状态，也就是说，在随机选取状态分量的同时，就应该判断它是否能满足组卷需求，如果不能满足需求则要重新生成一个新的状态分量。这样随机抽取的状态分量在后期会出现很大的冲突，遇到一次冲突，就需要重新生成新的状态分量，因此效率很低。这种方法比较容易实现，对于单道试题抽取速度快，而对于整张试卷而言，其成功率较低，重题率较高，花费时间较长。
2.2 回溯试探法
回溯试探法是将随机选取法产生的每一状态类型记录下来，当搜索失败时释放上次记录的状态类型，然后再依据一定的规律变换一种新的状态类型进行试探，通过不断地回溯试探直到试卷生成完毕或退回出发点为止。
在运用回溯试探法进行搜索的过程中，从上到下进行搜索，如果在某个节点上不能满足控制指标的要求，则进行回溯。这个过程需要不断进行重复，直到找到满足条件的解。这种方法是对随机选取法的改进，保存了搜索的历史状态。当搜索到某个节点不能满足要求时，则对状态进行更新继续下一个搜索。这样的状态更新时有一个很大的空间。从理论上讲，回溯试探法可以在理论上遍历每一种可能的状态组成，但是当试题量比较大时，状态类型的变换就成为一个巨大的数字。因此，该方法只适用于状态类型和试卷总体量都比较少的题库。
2.3 遗传算法
遗传算法(GA)是一种全局优化算法，它是对自然现象或过程进行模拟而形成的，是通过模拟达尔文的自然选择学说和自然界的生物进化过程而形成的一种计算模型[3]。遗传算法具有自适应全局寻优和智能搜索的功能，其收敛性也相当好，能有效解决较大计算量的问题，而这些特点都是处理试卷库自动组卷中存在的问题所必需的。因此，遗传算法能很好地满足考试自动组卷的要求。作为一种新型的模拟生物进化过程的随机化搜索、优化方法，遗传算法在近几十年来在组合优化问题中显示了良好的性能和效果。
2.3.1 概述
遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，每一代根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群[4]。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。
2.3.2 一般原理
用户在进行自动组卷时会会试卷的质量提出很多方面的要求，包括知识点、题型比例、总体量、平均难度等，自动组卷应该在最大程度上满足用户的要求。通常来说，利用遗传算法进行组卷的基本原理包括[5]：在组卷之前，应该先为自动组卷过程建立控制指标相应的状态空间。状态空间的每一行由某一试题的控制指标构成，如题号、题型、难度、知识点等，而且这些属性指标都进行编码用二进制形式表示每一列式题库中的某一指标的全部取值。在进行具体出题时，测试方可能不会用到所有的指标，因此可以将状态空间包含的个体表示为考方要求的控制指标和考方不要求的控制指标。因为试题库中的每一道试题在建库时都输入了相应的属性指标，因此产生了试题模型。
3 组卷策略及算法实现
通过对以上算法的基本操作过程的认识，并且对它们的优缺点进行了详细比较，当作为高校日程考试的组卷策略时，算法和结果都相对简单的随机选取法更能满足实际需求。同时，为了克服随机选取法的不足，在制定组卷策略时，要通过对知识点和难度的合理分配，首先随机产生决策表，这样可以在很大程度上缩小随机抽题的范围，从而可以提高抽题速度[6]。其次，根据决策表，从题库中随机逐道抽取试题。因为所论述的组卷系统只是应用于高校的课程考试，而非资格考试，因此在随机抽取试题的过程中，当抽取单道试题失败时，可以对抽题条件进行适当放宽(比如扩大分值范围，调整难度级别)以重新抽取试题，从而提高试题抽取的成功率。在组卷失败后，采用回溯算法的原理，通过控制一定的回溯次数，重新计算知识点和难度，生成决策表，再次抽取试题，从而可以避免回溯算法的大量的回溯试探。这样不仅提高了组卷成功率，也保证了组卷速度。
在组卷过程中还应考虑以下因素：
(1）判断试题是否超范围
首先将试题范围中各知识点放入一维数组中。然后再判断该试题的知识点是否超范围。设定判断函数公式为scope(x),其中x为试题范围,函数返回值T或者F表示判断结果“是”或“否”。对于未超出知识点范围的试题，随机产生决策表，缩小随机抽题的范围。
(2）判断分值
分值包括总分值、各题型分值等，可以由系统默认(总分100分，各题型按照一定比例设定)或者由用户指定。抽题过程判断已选中试题分值是否大于设定分值。
(3）试卷难度
生成试卷的难度系数为各试题难度系数的平均值。
(4）试题区分度
由该道题的学生答题情况决定。通过得分率求差法，用公式D=PH-PL来计算。
(5）判断试题知识点是否均匀
根据知识点范围和知识点出现情况设定为二维数组，知识点分区不区分题型，出现情况包含出现次数和累计分值两部分。
(6）判断试题的最近曝光度
设定n字段栈S1～SN。每输出一套试卷，该试卷中试题的曝光度字段进行进栈算法操作。由用户设定临界次数值，若在该值的抽题次数内该题未被抽中，则进行退栈算法(tp和tb值相等的情况除外)。优先抽取栈值较小的试题，若栈满，则放弃抽取该试题。
4 结语
重点介绍了常用的组卷算法，并对一种自动组卷方法的策略和算法进行了分析。这种算法既拥有随机抽取法的速度快、算法相对简单的优点，又借鉴了回溯算法求解的基本思想，从而能够在抽取试题时取得很高的组卷成功率。
参考文献
[1]刘彬,糜长军,李勇.智能组卷系统试题库结构的研究[J].信息技术,2002,(3):2-4.
[2]戴亚非,李晓明,唐朔飞.计算机自动组卷算法分析[J].小型微型计算机系统,1995,16(9):51-55.
[3]陈国良,王熙发.遗传算法及其应用[M].北京:人民邮电出版社,2001:1-400.
[4]路平,王敏娟,万昆.试题库自动组卷中选题策略研究[J].江汉大学学报(自然科学),2003,31(4).
[5]刘彬,金涛,陈大平.遗传算法在试题组卷中的应用[J].燕山大学学报,2002,26(3):193-195.
靶标角点自动匹配世界坐标通用算法 篇6
为了提高相机标定的自动化水平,角点的自动识别和定位是其中的关键环节。目前常用角点提取算法:1)根据图像边缘特征,由边缘夹角或曲率来判断是否为角点[1];2)利用图像的灰度信息,如Susan算法;3)利用图像的灰度变化率,如Harris算法[1,2]得到的是无序角点集,4)利用支持向量机[3],小波变换[4]等复杂算法。上述算法提取出的角点均为无序角点集,为了进一步完成标定算法必须实现角点的物象匹配。针对目前各种样式X型标定模板(如图1所示),提出了一种自动定位角点的通用算法。可以快速实现角点世界坐标和像素坐标的匹配。
1 角点匹配世界坐标算法评价准则
成像模型关联坐标系包括世界坐标系(Xw,Yw,Zw),相机坐标系(Xc,Yc,Zc),图像物理坐标系(x,y),图像像素坐标系(U,V)。分析上述通用成像模型(如图2所示)得到如下成像公式[6]:
其中:(u′,v′),(u,v)分别为(x′,y′)和(x,y)对应的图像的实际坐标和图像的理想坐标;k1与k2为径向畸变系数,(u0,v0)为图像中心坐标。A为相机内部参数矩阵,R,T分别为旋转矩阵和平移矩阵。上述成像模型在数学上是三维空间到二维平面的中心投影,该模型是一个退化的射影变换[7]。
令H=A[R T],称H为射影变换矩阵。由射影变换性质可知:1)角点在投影后分布形状出现几何形变。2)射影变换保持点共线性质,由于镜头径向畸变的影响,角点的共线特性会受较大干扰(图3所示)。
因此要稳定的实现角点的定位,算法必须有效的抗拒射影变换矩阵带来的几何形变和镜头径向畸变。文献[8]提出由中心角点出发,以图像x与y方向的动态增量dx与dy,来预测和递推其它角点无法有效抗拒射影变换矩阵带来的几何形变。文献[9]应用平行线共灭点的原理,先确定中心格四角点,作直线求灭点,后由灭点与角点的距离来排序,依次确定其他栅格线上角点。由于径向畸变的存在会导致共灭点的求取不稳定甚至是无法获得共灭点。文献[10]利用凸包算法分层识别角点,如果镜头出现枕型畸变,凸点和凹点会出现误识别,导致角点定位失败。
2 匹配世界坐标通用算法
2.1 霍夫变换
由霍夫变换原理可知:直角坐标系中的每一个点(x,y)对应参数空间(θ,ρ)中的一条直线,可以表示为:ρ=xcosθ+ysinθ,θ∈[0,π]。图4为畸变投影点在θ取样步长为1°时θ-ρ坐标系中的投影图。在可分投影区间[θ1,θ2]内,ρ值出现明显的聚类现象。聚类最明显的角度称为最佳投影角θ0(如图5(a)所示)。
为了验证可分投影区间能够有效对抗径向畸变,仿真试验中分别取k1=k2=1,k1=k2=5,k1=k2=10(如图5所示),径向畸变的增大对可分投影区间影响不大,不会导致投影区间减小或消失。在实际情况下,镜头的畸变远远小于k1=k2=10,证明了在角点行分类或列分类过程中,极坐标投影变换可以有效抵抗镜头镜像畸变带来的影响。
2.2 最佳投影角搜索和二次分类
由图5可知,在可分投影区间里,角点出现很明显的聚类现象。在最佳投影角方向,角点的ρ值稳定聚类,因此搜寻最佳投影角,对于角点稳定分类至关重要。
假设已知待匹配模板角点行数R,列数C,通过下述算法寻找最佳列分类投影角。在列分类投影角方向,角点聚类类别数为R。第i角点在θ方向的ρ表示为ρ(i,θ)。最佳投影角搜索算法步骤:
1)任意θ方向:ρmax(θ)=max(ρ(i,θ)),i∈[1,N=R×C],ρmin(θ)=min(ρ(i,θ)),i∈[1,N=R×C]。
2)任意θ方向,区间划分有两种方式(步骤3中按照给定的阈值自动选择其中一种区间划分方式):
(a)分ρ(θ)为C个区间,各个区间为
(b)分ρ(θ)为R个区间,各个区间为
记各个区间的中值为Mid(j)。
3)求各个区间的标准差D(θ,j),“区间方差和”D(θ)=∑C-1j=1D(θ,j)。则Dmin(θ)=D(θ0),在最佳投影方向θ0,D(θ)取得最小值。因此只要找到Dmin(θ)即可确定θ0(如图6所示)。若在步骤2)中选择第一种区间划分方式获得的θ0为最佳列投影角θ0c,否则为最佳行投影角θ0r。
发生上述投影几何形变时,会使行可分投影区间(图7中(a)所示)或列可分投影区间(图7中(b)所示)变窄,甚至不可分。为了消除这种现象,这里设定阈值thread=ρmax(θ0),如果Dmin(θ)
4)对最佳投影角θ0c或θ0r的ρ值利用K—means算法进行自动聚类,为了确保算法准确稳定聚类,以Mid(j)为各类的初始聚类中心进行聚类。取各类均值,按大小排序完成行(列)分类。
5)对各类内角点计算l=(X2+Y2),对l按照大小排序完成列(行)分类。至此可以全部确定全部角点的行列值,实现角点和世界坐标的完全匹配。
3 测试与分析
输入:模板角点行数r,模板角点列数c,所有角点的像素坐标mn(u,v),n表示第n个角点,n∈[1,r×c]。
输出:mn(i,j)完成行列分类的所有角点。i为角点行值j为列值。
在焊缝跟踪项目中,该匹配算法作为独立的算法模块嵌入系统(如图8所示),测试结果如下:
(1.Board information input:numbers and interval(mm)of corners’row and column;2.Matching explanatory chart;3.Matching table)
1)镜头畸变较小情况下各个姿态下模板角点匹配世界坐标(Computar工业镜头,12 mm焦距,感光元件CCD 640×480,靶标为7行11列)。
2)镜头畸变较大情况下各个姿态下模板角点匹配世界坐标(普通USB摄像镜头,感光元件CMOS320×240,靶标为7行11列)。
分析表1数据:算法实时性高,算法时间30 ms左右;算法准确选择区间划分方式(r/c),在最佳投影角方向,完成对角点行列确定;实现角点和世界坐标的完全匹配。
4 结论
针对各种类型靶标,提出一种角点匹配世界坐标的通用算法。该算法与模板样式无关,在已知角点像素坐标和行列数的情况下,可稳定准确的实现角点行列识别,完成与世界坐标的匹配。
通过上述原理分析和表1数据验证:
1)算法稳定性:通过2.1和2.2分析可知该算法可以有效的抵制投影变换导致的几何形变和镜头的径向畸变。保证了在各种拍摄角度和镜头畸变严重时算法可稳定实现。
2)算法实时性:算法仅对角点进行了投影变换,相比对图像做霍夫变换大大减少了运算量。
3)算法通用性:与靶标样式无关,输入量只需要提取到角点的像素坐标和X靶标的行列数,即可自动完成角点匹配世界坐标。对圆点模板,栅格模板同样适用。
4)算法独立性:可以形成独立的角点匹配世界坐标模块,有效提高标定自动化水平。
参考文献
[1]白瑞林,李杜,赵晶晶,等.一种实用的x型靶标亚像素角点提取方法[J].光学技术,2010,36(4):561-565.BAI Rui-lin,LI Du,ZHAO Jing-jing,et al.A practical method for detection of sub-pixel corners for X-target[J].OPTICAI.TECHNIQUE,2010,36(4):561-565.
[2]赵万金,龚声蓉,刘纯平,等.一种自适应的Harris角点检测算法[J].计算机工程,2008,34(10):212-214.ZHAO Wan-jin,GONG Sheng-rong,LIU Chun-ping,et al.Adaptive Harris Corner Detection Algorithm[J].Computer Engineering,2008,34(10):212-214.
[3]GAO Xin-ting,Sattar F,VenKateswarlu R.Multiscale Corner Detection of Gray Level Images Based on Log-Gabor Wavelet Transform[J].Circuits and Systems for Video Technology(S1051-8215),2007,17(7):868-875.
[4]Minakshi Banerjee,Malay K Kundu,Pabitra Mitra.Corner Detection Using Support Vector Machines[C]//17th International Conference on Pattern Recognition,USA,2004:819-822.
[5]张毓晋.图像工程[M].北京:清华大学出版社,2007.ZHANG Yu-jin.Image Engineering[M].Beijing:Tsinghua University Press,2007.
[6]ZHANG Z Y.A flexible new technique for camera calibration[R].Technical Report MSR-TR-98-71,Microsoft Research,1999.
[7]吴福朝.计算机视觉中的数学方法[M].北京:科学出版社,2008.WU Fu-zhao.Mathematical Methods in Computer Vision[M].Beijing:Science Press,2008.
[8]王忠石,徐心和.棋盘格模版的自动识别与定位[J].中国图象图形学报,2007,12(4):618-622.WANG Zhong-shi,XU Xin-he.Auto-recognition and auto-location of the checkerboard pattern corner[J].Journal of Image and Graphics,2007,12(4):618-622.
[9]刘群根.基于梯度与对称度提取棋盘格角点及角点递推定位[J].测控技术,2008,27(1):7-9.LIU Qun-gen.Extracting checker board corners based on gradient&symmetry and locating with Iteration[J].Measurement&Control Technology,2008,27(1):7-9.
多媒体播放器通用算法设计与实现 篇7
在许多商业软件的设计中,需要提供对多媒体信息的支持。单纯实现多媒体的播放方法很多,可以利用暴风影音、Real One、PPS网络电视等成熟的多媒体播放器进行实现。然而,在很多情况下,自主设计的软件需要实现对多媒体播放器的控制,比如播放控制、界面控制等等,这就要求用户必须进行自主开发多媒体播放软件。
提出了多媒体播放器功能模型,设计了通用算法,并进行了实验,效果良好,有一定推广应用价值。
2播放器功能模型
播放器功能实现模型如图1所示。其中,标题栏用于显示播放器名称;视频播放区用于实现视频播放;播放控制区用于实现多媒体播放控制,包括、播放、暂停等;文件搜索区用于实现媒体文件搜索;视频播放列表区配合文件搜索区能够完成将指定目录下的所有视频文件进行显示。
在此模型中,标题栏设计、视频播放、播放控制等均比较容易实现,在多种文献中均有所涉及,在此不再进行重复。重点对视频播放大小的自动控制以及视频文件搜索两项内容进行讲解。
3视频播放大小自动控制算法
3.1算法提出
视频播放页面太小,不适合用户观看,视频页面太大,显示器无法进行全部显示,因此视频播放页面的大小必须能够跟随显示器大小(分辨率)而变化,有些视频控件,比如Active Movie,可以通过全屏播放功能来进行实现,但是若加上视频播放列表区等附属显示之后,就必须考虑全屏页面的大小。为此,提出视频播放大小自动控制算法,成功解决了上述问题。
3.2变量定义
对照图1所示,变量定义如下:
(x0,y0)表示视频控件原始大小,(x1,y1)表示视频控件调整之后大小,(x2,y2)表示对话框大小,(w,h)表示显示器分辨率,b Max表示是否进行最大化显示。h1表示标题栏高度,h2表示视频播放列表区高度,h3表示视频播放控制区高度,w1表示视频播放列表区宽度。
3.3算法实现
在VC++环境下,算法实现如下:
4视频文件搜索算法
4.1算法提出
根据功能模型要求,播放器要能够实现对指定目录下视频文件的搜索和显示。如果单纯实现对某个目录下视频文件的搜索比较简单,但是如果该目录下还有多重目录,则实现比较困难,针对后者设计了视频文件搜索算法,能够实现对一级目录或者多级目录自动搜索和显示。
4.2算法实现
Dir表示视频目录,Str Ary用于存放搜索结果,基于VC++环境,采用嵌套的思想,实现视频文件自动搜索算法如下:
void findfile(CString Dir,CString Array&Str Ary){//Dir表示被搜索目录//Str Ary用于存储搜索到得视频文件目录CFile Find file Find;BOOL b Ret=TRUE;CString strdir;strdir=Dir+_T("\*.*");if(file Find.Find File(strdir,0)){while(b Ret){
5实验分析
5.1实验条件
根据播放器功能模型,选取参数h1=30,h2=70,w1=245,编程环境为VC++6.0。
5.2实验结果
实验结果如图2所示。
通过实验,播放器能够实现对多种格式的视频文件播放,双击播放区时,可以实现视频全屏播放,再次双击播放区时,可以退出全屏播放,正常进行显示,更改显示器分辨率时,上述功能依然能够正常实现。浏览不同目录时,视频播放列表可以实时更新,显示最新视频文件目录。
5.3结果分析
通过实验结果充分说明,视频播放大小自动控制算法能够根据不同显示器分辨率,自动调整视频正常显示大小以及全屏显示大小,视频文件搜索算法可以对多层次的目录进行自动搜索,达到了设计目的。
6结语
视频播放器设计中重点和难点的内容是视频显示大小,提出的视频播放器模型及视频大小自动控制算法和视频文件自动搜索算法具有很强的通用性,具有一定的推广应用价值。
摘要：设计了一种多媒体播放器模型,提出了播放器模型中的视频播放大小自动控制算法和视频文件自动搜索算法,并进行了实验。实验结果显示,算法效果良好,具有一定的推广应用价值。
通用算法 篇8
配电网具有与输电网不同的特点,如结构呈辐射状、有时含有少量环网(弱环网),以及支路参数的r/x值较大等[1]。这些特点使得配电网潮流计算对算法的收敛性要求较高,而且在算法中需要充分利用辐射状及弱环网的结构特点来提高计算效率。回路电流法是各种配电网潮流算法中收敛性较好的算法之一,它根据电源、负荷、线路电容等对地支路形成的回路列出回路电压方程组,对形成的回路阻抗矩阵进行LU分解,然后迭代计算各回路的电流及各节点电压。通过一定的节点编号优化方法,可以利用稀疏技术简化回路阻抗矩阵的LU分解。文献[2]提出的“直接潮流算法”是最早的回路电流法,文献[3]对文献[2]中的节点编号方法进行了改进,提出了对对角线元素和相邻元素进行优化的计算方法,但是这些方法还存在如下缺点:
(1)在节点编号过程中需要向配电网插入零阻抗的虚拟支路形成等价的二叉树网络,以确定负荷节点的编号[2,3,4],在加大算法复杂度的同时改变了原有的网络结构;
(2)对回路阻抗矩阵进行LU分解时只有部分元素利用了优化算法,而且没有进一步利用同一行元素的相同因子进行优化计算;
(3)计算有弱环网的配网潮流时需要修改回路阻抗矩阵,使得受修改影响的部分元素不能利用优化算法,而且环网的解裂节点必须含有负荷[2],限制了回路电流法在环网潮流计算中的应用。
本文在传统的回路电流法基础上,首先针对辐射状配电网提出一种新的节点编号方法,不需要添加额外的虚拟支路就能形成优化的节点编号,不仅降低了编号的复杂性,而且还可以保持编号后的辐射状网络与原有网络结构相同,方便了通用潮流算法的设计。其次,充分利用根据优化编号形成的回路阻抗矩阵的稀疏性质,将优化的LU分解算法扩展到U矩阵的所有元素,并通过预先计算行元素分解需要使用的相同系数,进一步加快了LU分解速度。
传统回路电流法只能处理含有弱环的配电网,无法计算含有PV节点的配电网。文献[5]虽然提出了可以计算含有环网和PV节点的配电网潮流算法,但它采用的前推回代计算方法收敛性有时较差[6],而若以传统的回路电流法来替代前推回代算法,则插入的虚拟支路会在由文献[5]方法形成的节点导纳矩阵中产生无穷大导纳元素,使得利用传统回路电流法难以形成配电网潮流通用算法。本文在改进回路电流法的基础上,结合文献[5]中将环网和PV节点解裂形成辐射状网络的方法,形成配电网潮流的通用算法。
1 回路电流法的改进
1.1 基本回路电流法
在辐射状配电网络中,如果把负荷表示为恒定阻抗,则馈线根节点和各个负荷节点之间可以形成一系列回路,根据基尔霍夫电压定律列出n个回路的电压方程:
式中:VS为根节点电压;对角线元素Z(k,k)为回路k的回路阻抗;非对角元素Z(i,j)为回路i和回路j的互阻抗;Ik为回路k的电流。将式(1)写为矩阵形式:
其中的对称矩阵Z称为回路阻抗矩阵。对Z进行LU分解后,通过求解上述方程(2)得到各回路电流,进而求出各负荷节点电压。根据求出的节点电压重新计算负荷的等值阻抗,然后修改回路阻抗矩阵中的对角元素值,再次求解式(2),如此反复迭代,直至负荷节点电压的两次计算结果之差小于收敛精度为止。
1.2 节点编号方法的改进
虽然式(2)中的回路阻抗矩阵是一个满阵,但由于回路互阻抗总数量不可能超过分支节点数,因此矩阵中含有很多相同元素。采用一定的节点编号优化方法,可以生成具有“稀疏”性质的回路阻抗矩阵,即相同的元素尽量聚集在一起[4],这样,LU分解时可以跳过部分相同元素,减少需要计算的元素数量。文献[2]向辐射状的配电网络中插入零阻抗的虚拟支路形成二叉树,然后对二叉树上的各负荷节点编号。文献[3]虽然对文献[2]的编号方法进行了简化,但本质上还是需要向配电网加入虚拟支路形成等价的二叉树网络。
本文提出新的节点编号方法,无须增加虚拟支路就可以形成优化的节点编号。该方法只需要对与回路对应的负荷节点进行编号,同时为每个节点记录如下的信息:
1)从某节点向辐射网末端搜索得到的负荷节点数目,记为n Load。
2)某节点下的起始负荷编号(s Id)和结束负荷编号(e Id)。s Id等于该节点下负荷节点的最小编号,e Id等于该节点下负荷节点最大编号加1,区间[s Id,e Id)为其下负荷节点编号的范围。
本文提出的负荷节点编号方法具体如下:设负荷节点数目为n,则根节点的s Id为0,e Id为n,得到各节点的n Load值后,从根节点开始向末端进行搜索。假设当前搜索节点为m,如果m为负荷节点,则将该负荷节点编号为s Id[m],并按n Load值对m的子节点升序排序为mS0,mS1,mS2,,mSc,子节点mSi的s Id和e Id按式(3)计算,如果m为负荷节点则式中的s Index=s Id[m]+1,否则s Index=s Id[m]。
继续搜索子节点mS0,mS1,mS2,,mSc,根据上述方法确定各负荷节点的编号,直至辐射网的末端。
以图1的9节点辐射状配电网络为例,m0为根节点,共有m2,m3,m4,m6,m7,m8 6个负荷节点。根据本文提出的负荷节点编号方法,各个节点的n Load,s Id,e Id值如表1所示,负荷节点编号如表2。
按负荷节点编号列出回路电压方程式(1)(编号为i的负荷节点对应第i条回路),并对回路阻抗矩阵Z进行LU分解得到上三角矩阵U。如果Z中第k行的第i列到第j列元素相同,则从第0行到第k-1行的第i列到第j列元素相同,因此在分解得到的U矩阵中,第k行第i列到第j列的元素也相同。这样,在U和Z中各行有相同的元素排列,计算U的行元素时只需要计算相邻相同元素的第一个元素,然后通过查询节点的e Id值,跳过其他相同元素,找到下一个不同元素。LU分解算法流程图如图2所示。
1.3 U矩阵元素计算方法的改进
在对回路阻抗矩阵Z进行LU分解时,本文把对其中部分元素的优化算法扩展到整个U矩阵元素的计算中,减少了不必要的重复计算。
设s为0到i-2之间使得Zsi=Zs,i-1的最大值。根据上节设计的节点编号方法可知Uti=Ut,i-1(t=s-1,s-2,…,0),因此式(4)可简化为:
上述算法可以应用于U矩阵所有元素的计算中,而且在进行行元素计算时可以预先计算行相关系数,大大减少了不必要的计算量,进一步加快了回路电流法的计算速度。
2 配电网潮流通用算法设计
热电联产机组的投运为配电网引入了PV节点,而有些配电网还可能含有少量的环网(弱环网)[5,7]。因此需要有既可以求解辐射状配电网潮流,又可以求解含有弱环网甚至有PV节点的配电网潮流的通用算法。文献[2]提出把环网上的负荷节点解环,并采取修改回路阻抗矩阵的方法来解决环网问题,但是修改后的矩阵“稀疏”性质遭到破坏,对部分元素无法利用优化算法,而且文献[2]也没有提出如何解决含有PV节点的配电网潮流计算问题。本文根据文献[5]中的基于前推回代法的潮流算法,提出应用改进的回路电流法计算含有PV节点和弱环的配电网潮流通用算法。
配电网中电压为|Vh|、功率为Ph的PV节点,可以转换为具有-Ph+j0的负荷以及0+j Qh的注入功率的PQ节点[5,7](如图5)。环网可以在解裂节点处分解为具有符号相反的两个注入功率Pr+j Qr和-(Pr+j Qr)的节点[5,7,8](如图6)。
转换和解裂后的网络为一个辐射状网络,节点分为三类:1)PV节点转换得到的PQ节点;2)环网解裂节点;3)其他节点。根据叠加原理,辐射状网络的潮流将由负荷产生的潮流和注入功率产生的潮流叠加得到,前者可以通过改进回路电流法计算得到,后者可以通过求解节点电压方程式(6)得到:
由于第3)类节点的注入功率为0,根据Kron变换[5],可以得到式(7):
其中:Va和Ia为转换后的PQ节点的电压和注入电流;Vb和Ib对应注入功率为Pr+j Qr的环网解裂点的电压和注入电流;Vc与Ic对应注入功率为-(Pr+j Qr)的环网解裂点的电压和注入电流,且Ic=-Ib。由式(7)得到式(8):
其中:ΔVbc=ΔVb-ΔVc;Z11=Zaa;Z12=Z21=Zab-Zac;Z22=Zbb+Zcc-Zbc-Zcb。通过式(8)可以计算得到注入功率差值ΔQ、ΔP。
通用潮流算法的主要步骤如下:
1)将PV节点转换为PQ节点并解裂环网,转换和解裂后的节点注入功率初始值设为0。将所有负荷等价为标么电压值1.0 pu下的导纳,并将松弛节点接地,生成式(6),进而得到方程式(8)。
2)不考虑只含有注入功率的负荷节点,应用前述的改进节点编号方法对负荷节点进行编号,生成回路电压方程(2)。
3)采用改进的回路电流法计算解裂后形成的辐射网潮流,得到各支路电流,进而由根节点向末端推算各节点电压。
4)计算转换后的PQ节点电压与标准电压的差值ΔVa以及环网解裂点电压与标准电压的差值ΔVbc,根据式(8)计算得到ΔQ、ΔP,与原有注入功率叠加得到Q(k+1)=Q(k)+ΔQ,P(k+1)=P(k)+ΔP。
5)考虑只含有注入功率的负荷节点,采用改进的节点编号法对负荷节点重新进行编号,并再次生成回路电压方程(2)。
6)重复步骤2)与3)。如果重新计算出的PQ节点(转换后的)和环网解裂点电压与标准电压差值满足收敛精度要求,则计算终止。
由于回路电流法将负荷功率为0的节点的电压始终锁定为0,因此上述算法在初次计算辐射网潮流时不考虑只含有注入功率的负荷节点。在初次计算后,注入功率变为非0值,再考虑只含有注入功率的负荷节点。
3 算例分析
本文以PG&E的69节点辐射状配电网[5,9]以及对其修改后的网络为例进行验算,基准电压为12.66k V。三个测试网络如下:
(1)PG&E的69节点辐射网,如图7中实线连接而成的网络所示。
(2)在(1)的基础上添加图7中虚线所示的支路,形成弱环网。
(3)在(2)基础上,于节点10,20,50,90上添加200 k W的发电机,电压为1.0 pu。
分别采用文献[2]的传统回路电流法和文献[5]基于前推回代的配网潮流算法以及本文提出的基于改进回路电流法的配网潮流通用算法,对三个测试网进行潮流计算,收敛精度取为0.000 1。迭代次数与计算时间的比较如表3所示。
由表3结果可以看出,传统的回路电流法计算速度比前推回代法慢一个数量级,当配电网中存在弱环网时,计算速度会进一步下降,并且传统的回路电流法无法计算含有多个PV节点的配电网潮流。本文提出的改进回路电流法的计算速度接近前推回代法,不仅能计算含有弱环和PV节点的配电网潮流,而且保持了回路电流法收敛性好的特点。
4 总结
本文提出的改进回路电流法解决了原有回路电流法编号复杂的问题,提高了计算效率;在对回路阻抗矩阵进行LU分解时,可以对所有元素进行优化计算,并通过预先计算行元素分解时使用的系数,进一步加快回路方程的求解过程。通过改进回路电流法形成了可以计算含有PV节点和环网的配电网潮流通用算法,该算法可以完全利用回路阻抗矩阵的稀疏性质优化计算,而且环网的解裂点不须是负荷节点,便于环网解裂算法的实现。算例分析表明,该算法不仅保持了回路电流法良好的收敛性,而且比传统回路电流法的计算效率有大幅度提高。
参考文献
[1]张学松,柳焯,于尔铿,等.配电网潮流算法比较研究[J].电网技术,1998,22(4):45-49.ZHANG Xue-song,LIU Zhuo,YU Er-keng,et al.A comparison of power flow calculation methods for distribution network[J].Power System Technology,1998,22(4):45-49.
[2]Goswami S K,Basu S K.Direct solution of distribution systems[J].IEE Proceedings Part C,1991,138(1):78-88.
[3]Wang Shou-xiang,Liu Yu-tian,Ruan Tong-jun.Distribution power flow based on loop-impedance equations[J].Energy Management and Power Delivery,1998,2(2):728-731.
[4]王守相,王成山.配电系统节点优化编号方案比较[J].电力系统自动化,2003,27(8):54-58.WANG Shou-xiang,WANG Cheng-shan.Comparative study of optimal node indexing schemes for distribution system[J].Automation of Electric Power Systems,2003,27(8):54-58.
[5]Haque M H.A general load flow method for distribution systems[J].Electrical Power System Research,2000,54(1):47-54.
[6]吴文传,张伯明.配网潮流回路分析法[J].中国电机工程学报,2004,24(3):67-71.WU Wen-chuan,ZHANG Bo-ming.Study on loop analysis theorem of distribution system power flow[J].Proceedings of the CSEE,2004,24(3):67-71.
[7]Luo G X,Semlyen A.Efficient load flow for large weakly meshed networks[J].IEEE Transactions on Power Systems,1990,5(4):1309-1316.
[8]Haque M H.Efficient load flow method for distribution systems with radial or mesh configuration[J].IEE Proceedings on Generation,Transmission and Distribution,1996,143(1):33-38.
通用算法 篇9
配电网是电力系统电能发、变、送、配中最后向用户供电的环节。随着人民物质文化生活水平的不断提高,用户对供电质量和供电可靠性的要求也越来越高,甚至不能忍受供电瞬时中断[1]。
为快速判断故障点,文献[2]提出了故障定位的统一矩阵算法,其故障判断矩阵需要将网络描述矩阵和故障信息矩阵相乘后再进行规格化处理,运算量大;且该文只对单一电源的故障定位做了分析,对于双电源或多电源网络的情况没有加以考虑。文献[3]提出了支路矩阵算法,其对故障的定位采取分支路判断,由故障判断矩阵的元素数依次从该支路首节点排序到故障节点,不能直接判断出故障两端节点号。文献[4]提出的矩阵算法仅限于单一故障下的故障定位,且需要故障信息辅助矩阵来实现故障的定位。文献[5]在文献[4]和文献[1]的基础上提出了一种新型的配电网故障定位算法,此法解决了多电源多故障的定位问题,但其在多电源多故障定位时须根据不同的电源设定不同的正方向,否则会漏判,这引起部分不可避免的重复运算,运算量较大。文献[6]在馈线终端单元(FTU)装置中设置三种工作模式,0,1,-1,将故障电流的方向考虑进判断矩阵,故障判断一次到位,但此法在构造网络描述矩阵D时,在两关联节点正方向时记对应元素为1,反方向时记为-1,描述矩阵的形成不够简单。文献[6]需要矩阵相乘及辅助矩阵,运算量大。文献[7]在多电源多故障定位时须根据不同的电源设定不同的正方向,否则会漏判。文献[8]运用配网归一化负荷矩阵进行过热弧搜索以有效地解决配电网络故障区段的判断和隔离问题。本文在文献[5]和[9]的基础提出了一种改进的通用矩阵算法,该法故障描述矩阵形成简单,故障判断一次到位,判断原理清晰,计算量小。
1 改进通用算法的原理
1.1 概述
本算法的物理基础是:配电网中绝大多数故障是由短路引起的,当配电网中某一区域发生短路故障时,线路的一侧或两侧会有短路电流流过,由于馈线终端设备(FTU)等现场监控终端越来越多地得到应用[10],短路电流被馈线终端FTU检测到并实时将故障信息传送给配网控制中心的SCADA系统,SCADA系统根据收到的故障信息修改网络描述矩阵D以得到故障判断矩阵P,再运用故障判据快速判断出故障区域,并由SCADA发送跳闸命令隔离故障区域。对于单电源网络,馈线的正方向即为功率的正方向,对多电源网络,需假定功率流向的正方向,以便网络描述矩阵的形成和故障电流正负向的判断。由于SCADA系统中进行矩阵算法只需要知道各节点是否有故障电流,故FTU的整定值不需按不同地点的而设定不同值。故障区段位于最后一个经历了故障电流的节点和第一个未经历故障电流或经过负向(与假定正方向不同)电流的节点之间。
1.2 网络描述矩阵D
首先以常开型联络开关为分界点对配电网进行分区[11],仅选择含有故障信息的区间进行运算。将该区间中的断路器、分段开关和联络开关当作节点进行编号,设定正方向:对于单电源网络,线路功率的流出方向即为馈线的正方向;对于多电源网络,假定该网络只由其中某一个电源供电及假定电源向全网供电的功率流出方向即为馈线的正方向[1]。根据各节点的有向连接构造描述矩阵D,如有n个节点的配电网,则须构造一个n×n的方阵,若节点i和节点j间存在一条馈线且该馈线的正方向由节点i指向节点j,则记dij=1,否则置0,由于改进算法描述矩阵只涉及节点的正向连接性,在此记为单向描述原理。
单向描述原理:
本方法相对于文献[9]的改进之处便体现在网络描述矩阵构建上,在文献[9]中,网络描述矩阵由1,0,-1三种元素组成,此算法涉及到节点的正、负向连接,记为双向描述原理。
双向描述原理:
文献[9]对同一馈线的两节点构造描述矩阵时计及反方向的连接关系,即增加了-1的元素,而本法则去掉描述矩阵中的反方向关联节点的计数,在形成网络矩阵时更快速,矩阵的稀疏性更强。
1.3 故障判断矩阵P
利用配电网的结构特点,在馈线终端FTU中设置0,1,-1三种工作模式[9],其中模式0为节点工作正常,不向控制中心发送故障信息;模式1为节点出现故障电流且该电流方向与假定功率正方向一致,模式-1为节点出现故障电流且该电流方向与假定功率正方向相反。根据FTU传送给SCADA的故障信息改写网络描述矩阵,形成故障判断矩阵。判断矩阵原理:
1.4 故障定位判据
由故障判断矩阵就可以判断出故障区段,其具体的判断原则如下。
判据(1)。当配电网的故障发生在节点i和节点j之间时,其判断条件有两条。
条件一:pii=1,对所有pij=1的j(j≠i),都有pjj=0或-1。
条件二:pii=-1,对所有pji=1的j(j≠i),都有pjj=0。满足任一条就可以判断节点i和节点j之间发生了故障。
判据(2)。末端故障判断条件是:pii=1,所有的pij(j≠i)都等于0。
2 算例分析
2.1 算例一双电源网络
双电源网络示例如图1,首先为各测控点编号,为不失一般性,故意将编号打乱。然后假定该网络仅有电源A供电,则电流正方向如图长箭头所示,再根据规定的正方向和各节点的连接性形成网络描述矩阵D。由单向描述原理可得:
根据故障电流信息修改描述矩阵形成判断矩阵P,图1中短路点和假定的正方向已知,由判断矩阵原理可得:节点2,6流过正向故障电流,故p22,p66=1,节点1,5流过反向故障电流,故p11,p55=-1,其余元素不变。
故障判断:由1.4节中判定原则
p22=1,p24=1,p44=0,则符合条件一,节点2,4之间馈线发生故障(即K1);
p33=1,p3j=0(j=1,2,4,5,6,7),则符合判据(2),节点3发生末端故障(即K3);
P66=1,p63=1,p33=1,不符合条件一,故节点3,6间正常;
p11=-1,p71=1,p77=0,则符合条件二,故节点1,7之间馈线故障(即K2);
p55=-1,p15=1,p11=-1,不符合条件二,故节点1,5间正常。
算法总结及对比:此算例和文献[5]中算例结构一致,只是编号不同,本文假设只有电源A供电,根据原理一形成网络描述矩阵D,再根据原理三形成故障判断矩阵P,最后直接运用判据判断故障区域,过程如图2;文献[5]首先假设只有A电源供电,形成描述矩阵DA和故障判断矩阵PA,由判据判断出节点2、4间故障K1,节点3末端故障K3;再假设只有B电源供电,形成网络描述矩阵DB和故障判断矩阵PB,判断出节点1、7间故障K2和节点3末端故障K3,最后统计出故障区域K1、K2、K3,如图3。
由图1知文献[5]结果和本法判定结果一致,但因其判断矩阵不计及反向过电流,使得故障定位判断时须将电源A和电源B分别假定为唯一电源来做一次判定,否则会漏判,这相当于做了两次故障判断,不仅是过程繁复,还可能出现同一故障被重复判定,如两次都判定出节点3末端故障。本方法故障判断一次到位,省去了文献[5]中各电源均需假设一次正方向再判断一次的反复过程。
2.2 算例二多电源网络
多电源多故障网络如图4,和图1的判定方法相同,假定电源A为网络唯一供电电源,则电流规定正方向为途中长箭头所示,根据节点连接的方向性形成网络描述矩阵D,由单向描述原理可得:
根据故障电流信息修改描述矩阵形成判断矩阵,图4短路点和假定的正方向已知,由双向描述原理:节点2,6流过正向故障电流,故p22,p66=1,节点1,3,4,8流过反向故障电流,故p11,p33,p44,p88=-1,其余元素不变。
故障判断:由判据(1)中判定原则
p22=1,p27=1,p77=0,则符合条件一,节点2,7之间馈线发生故障(即K1);
p66=1,p62=1,p22=1,不符合条件一,节点6,2之间正常;
p11=-1,p51=1,p55=0,则符合条件二,故节点1,5之间馈线故障(即K2);
P33=-1,p13=1,p11=-1,不符合条件二,故节点1,3间正常;
P44=-1,p94=1,p99=0,则符合条件二,故节点4,9之间馈线故障(即K3);
P88=-1,p48=1,p44=-1,不符合条件二,故节点4,8间正常。
该判定结果和图中故障区域一致,无漏判,无错判。
算法总结及对比。该算例和文献[9]算例一致,本法过程如图2;文献[9]中对网络描述矩阵的形成考虑了两相连节点间的负向性,这使得矩阵中出现-1的元素,矩阵的稀疏性不如本算法强。为进一步说明此方法对文献[9]的改进,现将文献[9]的网络描述矩阵形成过程分为两步讨论,由双向描述原理:第一步将各关联节点的正方向性形成描述矩阵,第二步将各关联节点负方向关联性添加到描述矩阵中,过程如下:
再根据节点故障电流信息修改网络描述矩阵D2,形成故障判断矩阵P,运用判据判定故障区域,如图5。
对比算例一中本文过程图可知,本法在网络描述矩阵的形成过程中减少了对节点负向连接性的考虑,即不需要形成网络描述矩阵D2,直接运用矩阵D1形成判断矩阵P,再运用判据判定故障区域即可,简化了描述矩阵形成过程,节省了时间。
3 结论
通过对现有矩阵算法的分析,针对已有方法的一些不足之处,提出了一种改进的通用矩阵算法,此法不仅适用于单电源单一故障,还适用于多电源多故障并列发生及线路末端故障判断的情况,且其原理清晰,算法精简,对复杂多变的配电网运行有很强的实用性。
参考文献
[1]蒋秀洁,熊信银,吴耀武,等.改进矩阵算法及其在配电网故障定位中的应用[J].电网技术,2004,28(19):60-63.JIANG Xiu-jie,XIONG Xin-yin,WU Yao-wu,et al.Improved matrix algorithm and its application in fault location of distribution network[J].Power System Technology,2004,28(19):60-63.
[2]刘健,倪建立,杜宇.配电网故障区段判断和隔离的统一矩阵算法[J].电力系统自动化,1999,23(1):31-33.LIU Jian,NI Jian-li,DU Yu.An unified matrix algorithm for fault section detection and isolation in distribution system[J].Automation of Electric Power Systems,1999,23(1):31-33.
[3]许奎.配电网故障区域判断的支路矩阵算法[J].现代电力,2009,26(1):49-51.XU Kui.Branch matrix algorithm to identify fault sections in distribution system[J].Modern Electric Power,2009,26(1):49-51.
[4]卫志农,何桦,郑玉平.配电网故障区间定位的高级遗传算法[J].中国电机工程学报,2002,22(4):127-130.WEI Zhi-nong,HE Hua,ZHENG Yu-ping.A refined genetic algorithm for the fault sections location[J].Proceedings of the CSEE,2002,22(4):127-130.
[5]冯小华,苏小三.基于矩阵算法的配电网故障定位及其改进[J].电气应用,2007,26(1):124-127.FENG Xiao-hua,SU Xiao-san.Fault location of the distribution network based on improved matrix algorithm[J].Electrotechnical Application,2007,26(1):124-127.
[6]黄力.配电网故障定位的简单矩阵算法[J].湖北电力,2005,29(5):1-3.HUANG Li.A simple matrix algorithm for fault detection in distribution system[J].Hubei Electricity,2005,29(5):1-3.
[7]许奎,张雪松,杨波.配电网故障定位的改进通用矩阵算法[J].继电器,2007,35(3):6-8.XU Kui,ZHANG Xue-song,YANG Bo.An improved general matrix algorithm for distribution system faultlocating[J].Relay,2007,35(3):6-8.
[8]江道灼,张锋,张怡.基于配电监控终端的配网故障区域判断和隔离[J].继电器,2002,30(9):21-24,57.JIANG Dao-zhuo,ZHANG Feng,ZHANG Yi.Fault sections detection and isolation in distribution system based on FTU[J].Relay,2002,30(9):21-24,57.
[9]马强,张利民,刘皓明.配电网故障区间判断的通用矩阵算法[J].电力系统保护与控制,2009,37(5):14-17.MA Qiang,ZHANG Li-min,LIU Hao-ming.General matrix algorithm for fault section detection in distribution system[J].Power System Protection and Control,2009,3(5):14-17.
[10]齐郑,高玉华,杨以涵.配电网单相接地故障区段定位矩阵算法的研究[J].电力系统保护与控制,2010,38(20):159-163.QI Zheng,GAO Yu-hua,YANG Yi-han.Research on matrix-based algorithm for single-phase-to-earth fault section location in distribution grid[J].Power System Protection and Control,2010,38(20):159-163.
【通用算法】相关文章：
国外新颖优化算法——花斑鬣狗算法09-10
《算法案例：秦九韶算法》教学教案04-09
国外新型智能优化算法——松鼠觅食算法09-25
评估算法04-30
选课算法05-07
光流算法05-09
表决算法05-14
姿态算法05-16
弹性算法05-16
变换算法05-19