（电力系统及其自动化专业论文）遗传算法在配电网故障诊断中的应用研究.pdf

硕士论文 遗传算法在配电同故障诊断中的应用研究 a b s t r a c t f a u l ts e c t i o n d i a g n o s i s o fd i s t r i b u t i o nn e t w o r ki st h ek e r n e lt e c h n o l o g yi n d i s t r i b u t i o na u t o m a t i o na n di ti n c l u d e sd i s t r i b u t i o nn e t w o r kf a u l t l o c a t i o na n d i s o l a t i o na n dr e s t o r a t i o n r e c o n f i g u r a t i o n t h et h e o r y a n d a p p l i c a t i o n o fg e n e t i c a l g o r i t h mi nf a u l ts e c t i o nd i a g n o s i so fd i s t r i b u t i o nn e t w o r kh a sb e e ns y s t e m a t i c a l l y s t u d i e di nt h i sp a p e r , w h i c hi n c l u d e s ：b a s i cc o n c e p ta n dt h ed e v e l o p i n gs i t u a t i o ni n a p p l i c a t i o nf i e l do f f a u l ts e c t i o nd i a g n o s i sh a v eb e e ns u m m a r i z e d ；c o r r e l a t i v et h e o r y o fg ah a sb e e ni n t r o d u c e d ，a n da ni m p r o v e dg a w h i c hc o n t a i n sc o n v e r g e n tf a e t o r h a sb e e nd i s c u s s e d ；b a s e do nt h et w ot y p i c a ld i s t r i b u t i o nn e t w o r kc o n f i g u r a t i o n sn o d e d e n o t e dn e t w o r km e t h o dh a sb e e na d v a n c e d ；t h e nn e t w o r kc o m p o n e n t sh a v eb e e n c l a s s i f i e di n i n c o m i n g l i n ec i r c u i tb r e a k e r sa n ds w i t c h e sa n d1 i n e s t h r e e t y p e s ； n e t w o r k t o p o l o g yp a r t i t i o ni nn o n - f a u l ts t a t ea n d f a u l ts e c t i o ni d e n t i f y i n gh a v eb e e n r e a l i z e da n ds i m u l a t i o nr e s u l t sh a v eb e e np r e s e n t e d ；a c c o r d i n gt o t h e t o p o l o g y p a r t i t i o nr e s u l t a n dc u r r e n to f f - l i m i ts i g n a lg ah a sb e e na p p l i e di nn e t w o r kf a u l t s e c t i o nd i a g n o s i s ；n e t w o r km a t h e m a t i c a lm o d e la n df i t n e s sf u n c t i o na n di m p r o v e d g aa n dp o w e rf l o wc a l c u l a t i o nm e t h o da r ea n a l y z e di nt h ep a p e r ；s o m ei m p o r t a n t c o n c l u s i o n sa r eg i v e ni ns i m u l a t i o nt e s t so fi e e et h r e ef e e d e r ss y s t e ma n da c t u a l s e v e nf e e d e r sd i s t r i b u t i o ns y s t e m ；t h er e s u l t so fs i m u l a t i o ns h o wt h a tt h i sm e t h o dh a s h i g hf a u l t t o l e r a n c ep e r f o r m a n c ea n di t i se f f e c t i v e ；t h es o f t w a r eo fd i s t r i b u t i o n n e t w o r kf a u l ts e c t i o nd i a g n o s i sh a sb e e nd e s i g n e da n ds o m ef l o wc h a r t so fi m p o r t a n t f u n c t i o nm o d u l e sa r eg i v e ni nt h i sp a p e r k e yw o r d s ：d i s t r i b u t i o n n e t w o r kg e n e t i c a l g o r i t h mt o p o l o g yp a r t i t i o n f a u l ts e c t i o na n di s o l a t i o ns e r v i c er e s t o r a t i o n r e c o n f i g u r a t i o n p o w e rf l o wc a l c u l a t i o n 1 1 y6 2 4 g 7 5 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 槲年1 月i ；日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 2 * 牟年月1 1 日 硕士论文遗传算法在配电网故障诊断中的应用研究 1 绪论 1 1 课题研究背景及意义 配电网是电力系统中二次降压变电所低压侧直接或降压后向用户供电的网 络，是高压输电线路和低压用户之间的关键环节【“。随着现代社会和经济的快速 发展，中国配电网络结构和硬件设施的不断完善，电力用户对供电可靠性的要求 也越来越高。 配电网的故障一般可分为两类：瞬时性故障和永久性故障。据有关统计资料 显示，在架空配电系统中，瞬时性故障约占6 1 ，永久性故障约占3 9 ，而这 3 9 的永久性故障中约有三分之一是由瞬时性故障引起。对于瞬时性故障，只要 能短时断电。使电弧通道有足够的去游离时间就能消除故障，当再接通电源时就 可以恢复正常供电，其危害程度相对较轻；对于永久性故障，将引起开关跳闸， 如不采取措施将造成全线停电，影响较大。因此，当配网发生故障后应尽快故障 定位并有效隔离故障区域，快速恢复对用户的供电。 电力系统由于运行、维护、绝缘老化等原因，发生故障是不可避免的。为了 快速监测及消除故障，确保系统安全稳定运行。增强供电可靠性和连续性，实现 配电网络的故障定位以及快速故障恢复等，就需要一个优质的配电网故障诊断系 统。另外由于现有的一些故障诊断方法存在种种不足，难以取得令人满意的结果， 因此配电网故障诊断方法的改进迫在眉睫。 国家电力公司明确提出供电可靠性要达到9 9 9 6 的目标，配电自动化是实 现这一目标的重要保证，而实现故障诊断是配电自动化的关键技术之一。配电网 自动化程度的提高使得如何充分利用s c a d a 系统采集的数据资源，辅以智能软 件，自动处理故障报警信息、判断故障位置，为调度人员提供故障诊断结果，对 保证系统安全运行、提高供电可靠性是非常有意义的研究课题。 1 2 配电自动化系统 配电自动化( d a ，d i s t r i b u t i o na u t o m a t i o n ) 这一术语是2 0 世纪9 0 年代由 美国提出的。通常把从变电、配电到用电过程的监视、控制和管理的综合自动化 系统称为配电管理系统( d m s ，d i s t r i b u t i o nm a n a g e m e n t s y s t e m ) 1 - 3 1 。其内容包 括配电网数据采集和监控( s c a d a ) 、地理信息系统( g i s ) 、网络分析和优化、 工作管理系统、需方管理( d s m ) 和调度员培训模拟系统等。 目前，配电自动化系统有广义与狭义两种定义。广义上，d a 指利用先进的 电子技术、计算机网络和通信技术实现对配电网正常运行时的控制、监测和故障 时的快速处理，以及配电的生产管理、设备管理等的自动化，其包括配电网数据 采集和监控、配电地理信息系统和需方管理。狭义上，d a 指配电网故障的自动 硕士论文遗传算法在配电网故障诊断中的应用研究 化处理，包括故障检测、故障定位、隔离和非故障区的供电恢复整个过程，它由 变电站自动化( s a ) 、馈线自动化( f a ) 及相应的配电网通信等实现。 配电自动化系统是配电管理系统最主要的内容，两者的涵盖关系如图1 1 所 示。 r 进线监视 f 配极一系统 嚣娶黧波蚴鲋化 f 配电自动化 地理信息系统 。变电站巡检与无功补偿 。m 。j 。，。l 需方管理 篓雾募篓茎霁萎自动化 d m 81 网络分析和优化。惩力抄表与计费目动化 l 工作管理系统 l 调度员培训模拟系统 图1 1 配电自动化系统和配电管理系统的涵盖关系 配电s c a d a 系统中进线监视一般完成对配电网进线变电站的开关位置、母 线e r k , 、线路电流、有功和无功功率以及电度量的监视。开闭所和配电变电站自 动化完成对配网中1 0 k v 开闭所，小区变的开关位置，保护动作信息，小电流接 地选线情况，母线电压，线路电流，有功和无功功率以及电度量的远方监视、开 关远方控制、变压器远方有载调压等。馈线自动化是指在正常情况下，远方实时 监视馈线分段开关与联络开关的状态和馈线电流、电压情况，并实现线路开关的 远方合闸和分闸操作；在故障时获取故障记录，并自动判别和隔离馈线故障区段 以及恢复对非故障区域供电。变压器巡检系指对配电网中箱式变、台变的参数远 方监视和补偿电容器的自动投切和远方投切等。 地理信息系统主要包括设备管理、用户信息系统、实时数据信息与g i s 相结 合以便操作和管理人员进行动态分析及停电管理系统等。其中设备管理是将变电 站、馈线、开关等设备的技术数据反映在地理背景图上。用户信息系统借助g i s 对大量用户信息进行处理，便于迅速判断故障的影响范围，另外用电量和负荷的 统计信息还可作为网络潮流分析的依据。停电管理系统是指在接到停电投诉后， g i s 迅速查明故障地点和影响范围，选择合理的操作顺序和路径，显示处理过程 进展，并自动将有关信息转给用户投诉电话应答系统。 d s m 实际上是电力的供需双方共同对用电市场进行管理，以达到提高供电 可靠性，减少能源消耗及供需双方的费用支出的目的。其内容包括负荷监控、管 理和远方抄表、计费自动化两方面。负荷监控和管理是根据用户的用电量、分时 电价、天气预报以及建筑物内的供暖特性等进行综合分析，确定最优运行和负荷 控制计划，对集中负荷及部分工厂用电负荷进行监视、管理和控制，并通过合理 硕士论文 遗传算法在配电同故障诊断中的应用研究 的电价结构引导用户转移负荷，达到削峰填谷的目的，使电网负荷变化趋于平缓。 远方抄表与计费自动化是通过各种通信手段读取远方用户电表数据，并将其传至 控制中心，自动生成电费报表和曲线等。 配电自动化是电力系统现代化的必然趋势，其主要任务f ”】： a ) 在正常运行情况下，通过监视配网运行工况，优化配网运行方式； b ) 当配网发生故障或异常运行时，迅速查出故障区段及异常情况，快速隔 离故障区段，及时恢复非故障区域用户的供电，缩短对用户的停电时间，减少停 电面积： c ) 根据配网电压合理控制无功负荷和电压水平，改善供电质量，达到经济 运行的目的； d ) 合理控制用电负荷，从而提高设备利用率； e ) 自动抄表计费，保证抄表计费的及时和准确，提高了企业的经济效益和 工作效率，弗可为用户提供自动化的用电信息服务等。 1 3 配电网故障诊断研究现状 电力系统故障诊断是从技术上提高电网安全可靠运行的重要手段。准确的故 障判断能减少维修人员巡线检查的时间，加快线路的恢复，减少因停电造成的经 济损失。电力系统故障诊断一般分为发送电设备故障诊断和电力网络故障诊断两 类。电力网络的故障诊断涉及输电网和配电网等。 迄今为止，国内外提出了许多电力系统故障诊断的方法，主要有以下四种： 逻辑处理方法h 0 , 1 1 】，专家系统方法【1 2 1 ”，人工神经元网络方法【1 6 - 1 9 1 和基于优化技 术的方法【2 0 _ 2 “。在高压、超高压的输电领域故障诊断的研究已相当深入，并且己 取得了令人满意的结果；而对低压配电领域故障诊断的研究相对较少。由于输电 网络与配电网络有共同点，使得配电网故障诊断的研究可以借鉴输电网络故障诊 断的一些经验和做法：同时又由于两者的众多不同，故障诊断方法不能直接移植， 还必须做些细致的转化工作。 1 3 1 配电网故障定位与隔离 传统上配电网采用逐条拉闸停电的方法查询故障线路，在选出故障线路后派 人沿线寻找具体的故障点，这种停电选线的方法工作量大，且造成生产困难。随 着城网改造项目的开展，f t u 等监控终端大量用于配电网中，为提高配电自动 化、保障供电可靠性提供了前提。故障发生后，利用户外开关处的柱上f t u 提 供的故障过流信息实现配电网快速、准确的故障定位，为隔离故障及恢复供电提 供前提条件。 基于s c a d a 系统实现配电网故障定位和隔离的算法主要有两大类：一类是 硕士论文遗传算法在配电网故障诊断中的应用研究 以图论知识为基础，根据配电网的拓扑结构进行故障定位田珊j ，如矩阵算法、传 递函数算法和拓扑辨识等；另一类是以人工智能方法为基础【2 ”，如采用神经网 络、遗传算法和模式识别算法等。 文【2 3 】首次提出了适用于各种配电网故障区段判断的矩阵算法，针对配电网 络结构获得网络描述矩阵，在发生故障时根据安放于馈线分段开关处和主变电所 的r t u 上报的过电流信息生成故障信息矩阵，通过两者的异或运算得到故障判 断矩阵，经规格化处理后确定故障区段。从解决双电源及多电源并列供电系统等 复杂配网的故障定位问题及提高算法计算效率入手，文1 3 2 1 提出了基于现场监控 终端的故障定位优化矩阵算法，该算法以矩阵分析为基础，采用分线路存储技术 并以矩阵问有效元素的直接运算代替矩阵计算，改善了系统的存储效率和算法的 工作量，与优化前矩阵算法相比，扩大了算法的适用范围及提高了算法的计算效 率。文 3 3 1 将配电网故障定位矩阵算法中电网结构简化为以开关作节点的网络， 应用电工网络图论原理建立节点的邻接矩阵和节点信息矩阵，讨论了一种基于 f t u 的馈线网络故障区段判断矩阵及算法，并通过算例验证了方法的正确性。 文 3 4 1 针对多电源复杂配电网提出了一种故障定位的新算法，根据有向连接关系 确定的不对称网络描述矩阵和考虑了方向的故障电流进行对比即可判定故障区 间，该算法无需进行矩阵相乘的繁琐运算，且当电源数增加时，程序设计简单无 需进行规格化调整，并具有良好的实时性。在分析了前述算法的不足后，文 3 6 1 提出了解决问题的新统一矩阵算法，并通过实例证明了算法的有效性。 文 2 6 1 阐述了应用于配电网故障定位的传递函数法原理，给出了单相和三相 配电线路接地故障定位的传递函数公式，并分析了依据传递函数波形的频率、相 位和幅值特征进行故障定位的判据，从理论公式的数值计算和实际线路仿真两方 面论证了判据的可靠性和有效性。文【4 l 】以三相配电网线路在不换位情况下的接 地故障检测为研究对象，对传递函数法作了改进，从而扩展了其在配网接地故障 定位中的应用范围。在原有传递函数法的基础上，文 4 2 提出了根据频域波形特 性与配电线路结构关系的配电网接地故障定位的分支故障信息法，该方法利用数 字信号处理提取线路接地故障分支的故障信息作为接地故障定位的判据，并通过 仿真计算实例，结合实际理论分析证实了本方法的有效性。文 4 3 通过实验室线 路模拟试验及结果分析进一步论证了传递函数法在配电网接地故障定位中的有 效性，为其实际应用进行了试验性的准备工作。 基于拓扑辨识的配电网故障定位算法将配电网络的拓扑描述矩阵分解成不 含区域和只含区域的矩阵描述方式，有效地解决了配电网故障区段判断，且适应 多变的网络结构【4 4 】。针对配电网规模的不断扩大，电源点及t 接点的增多，文 【2 5 ，4 5 1 提出了基于分层拓扑模型的配电网故障定位优化算法，利用对分法计算某 硕士论文 遗传算法在配电网故障诊断中的应用研究 一区间中间层顶点故障信息状态组合情况，以确定故障所属区间实现故障定位。 文【4 6 】针对变结构耗散网络理论的故障定位算法存在无谓扩大故障切除区域的 问题，通过引入虚拟开关概念进行建模，实现配电网的快速故障定位，算例分析 表明该改进算法对特殊形式隔离开关的操作灵活实用。 人工智能在配电网故障诊断中的应用是基于建模和信号处理的智能知识诊 断技术。其中专家系统发展最早，文4 7 ，4 8 建立了基于g i s 的配电网故障定位专 家系统，基本思想是专家系统利用g i s 形成网络拓扑，根据用户的故障电话信息 检索知识库，确定可能的故障节点，推理机对故障节点进行动态搜索、回溯推理 形成多个故障序列，再根据关键用户的信息和故障序列的交集确定故障区域。针 对故障电流判别法的不足，文【5 0 首次提出基于遗传算法的配电网故障定位和隔 离算法，由于遗传算法的强鲁棒性，该算法在进行全局寻优求解时具有高容错性 能，适用于网络拓扑的多变方式，开放性强。文 2 9 ，5 2 分别对遗传操作和故障分 级式判别法作了改进，使算法性能更优、且具有在线应用的潜力。文 2 7 运用粗 糙集理论研究了因保护和断路器误动或拒动、通信装置的故障等原因造成的不完 备警报信号模式下的配网故障诊断新方法。 此外，多种人工智能方法的组合应用于配电网故障定位也是一发展趋势。文 5 3 】创造性的提出了基于多值神经逻辑网络冗余纠错和前馈神经网络组合的配 网故障定位原理和实现方法。文【2 8 科哿粗糙集理论和遗传算法相结合，形成数据 挖掘模型来处理实时输入信息畸变时的配电网故障定位，仿真测试表明该算法比 前馈神经网络故障定位算法具有更高的容错性能。文【5 5 】论述了一种适用于不同 配电网络结构的故障定位混和算法，该算法由模糊推理算法和基于启发式规则的 专家系统算法两种子算法组成，大大缩短了故障定位与隔离的时间。 1 3 2 配电网故障恢复 配电网故障恢复用数学语言描述是一个多目标、多阶段的混和非线性多约束 优化问题，解决该类问题的关键是如何确定最优的搜索方向5 7 。6 0 1 。故障恢复有硬 件和软件两种实现方式。硬件实现是由分段开关预置的动作序列进行故障恢复， 具体实现时无法考虑优化策略，拓扑通用性差，仅适用于简单配电网络。配电网 发展的趋势是基于f t u 的远方集中控制方式，这有利于故障恢复软件的实现。 配电网故障恢复模式大致可以划分为三种恢复模式【5 7 】： a ) 早期的故障恢复模式 在自动化水平较低的早期，故障恢复主要依靠装设在配电线路上的故障指示 器。故障发生后，工作人员依靠故障指示器找到故障位置，利用柱上开关设备手 动隔离故障区，人工恢复非故障区的供电。这种早期模式自动化水平较低，故障 处理时间较长。 硕士论文遗传算法在配电网故障诊断中的应用研究 b ) 配电自动化的故障恢复模式 这种模式( d a 模式) 主要依靠装设在配电网中的分断器、重合器及柱上开 关等具有一定智能的硬件设备，通过开关功能和保护时间配合，实现故障的自动 诊断、隔离和恢复。这种恢复模式的特点是依赖于配电网的早期规划、配网结构 及配电设备的自动化程度，但一般只适用于简单结线网络，而且不能考虑实际负 荷水平和网络运行约束。 c ) 配电管理系统的故障恢复模式 这种模式( d m s 模式) 主要应用配置在配电控制中心的故障恢复软件实现 故障检测、隔离和供电恢复。当配电网中发生故障时，d m s 的故障恢复软件根 据f t u 采集并经过通信系统传送到配电控制中心s c a d a 实时数据库中的故障 信息进行逻辑推理，判断故障位置，并且确定隔离故障和恢复供电的操作步骤， 然后以操作序列的形式提交s c a d a 系统，手动或自动执行。这种恢复模式的特 点是适用于任意结构的配电网络，可以处理一些特殊情况( 如多重故障) ，可以 考虑实际负荷水平和网络约束，但与设备可靠性和软件功能等有着密切的关系。 d a 模式与d m s 模式在不同的条件下各有优缺点。然而随着通信技术及计 算机技术的发展，d m s 模式必将获得更广泛的应用。d m s 模式是自动化发展的 必然，它运用智能软件控制配电网的故障恢复，能够从全局规划和考虑配电网的 恢复进程，适用于各种复杂的配电网络。 国内外关于故障恢复软件实现的研究可分为两类。一类依据配电网故障恢复 问题中的启发性知识、专家经验或优化策略，有效地缩小恢复决策的搜索范围， 在较短的时间内得到满足约束条件的最优或次最优解，例如：文 5 8 ，6 1 ，6 2 】的启 发式搜索方法，文【6 3 】的神经网络方法，文【6 4 ，6 5 的优化算法等；该类方法可以 在较短的时间内获得故障恢复的可行解，但其执行局部最优的搜索策略缺乏处理 多目标冲突的有效方法。无法保证得到全局最优解。另一类 5 9 , 6 6 , 6 7 1 采用快速搜索 技术构造满足基本约束条件的可能解集。再依据优化目标评价出最优解作为恢复 决策方案；目前尚缺乏解集构造快速、有效的算法，同时解集评价中如何综合考 虑多目标及其之间的协调尚需深入研究。 综上所述，配电网故障诊断的传统算法和智能算法相比较，各有优缺点。传 统优化法虽然不能从理论上保证全局最优，但其计算速度较快，同时需要依靠大 量的专家系统知识作为支撑，实现困难。智能算法从理论上讲能达到全局最优 但其计算时间有时过长，实用性能相对较差，但随着智能化技术的不断提高，实 用算法的不断改进，其性能也会逐渐提高，是实际应用的必然发展趋势。 1 4 本文完成的主要工作 论文在上述背景下对配电网故障诊断方法进行了研究，针对目前故障诊断存 6 硕士论文 遗传算法在配电网故障诊断中的应用研究 在的主要问题，在智能算法的改进及实现等方面作了研究和探讨。主要工作包括 以下几个方面： a ) 在广泛阅读了电力系统故障诊断算法相关著作和论文的基础上，系统地 研究了其基本理论。确定论文以配电网为对象进行故障定位、隔离和恢复系统的 研究。 b ) 论述了配电自动化系统和配电管理系统的涵盖关系，指出配电网故障诊 断在其中的重要地位和作用。给出配电网故障定位、隔离和恢复重构的基本概念， 分析了故障定位算法及故障恢复三种模式，并总结了配电网故障诊断的发展及研 究现状。 c ) 就遗传算法的发展及特点，算法的基本操作流程和数学机理进行了深入 分析，并对算法的收敛性作了定性论述。通过研究g a 算子的改进和控制参数的 自适应动态调整，提出一种引入收敛因子的改进自适应调整遗传算法。 d ) 根据配电网基本元件组成和两种典型的配电网络结构，讨论了配电网图 的表示和树的表示两种常用表示方法，并提出了采用节点表示配电网络模型的简 化描述方法。综合考虑配电网快速拓扑分析的要求，将配电网基本组成元件归纳 为进线断路器、开关和线路三类进行描述。在此基础上，以迸线断路器作为拓扑 搜索起点，依据拓扑分区的基本原则，实现了配电网非故障拓扑分区和故障区域 的快速识别，对两种典型配电网结构进行了拓扑分析仿真。 e ) 利用配电网拓扑分区结果及f t u 的电流越限信号将g a 应用于配电网故 障定位与隔离系统中，完成了故障定位与隔离系统的原理分析及算法实现。为了 有效加快算法的搜索过程，对遗传操作及控制参数等作了改进，使之更加适合解 决配电系统故障定位问题。对某实际七馈线6 0 节点配电系统进行算法仿真测试， 结果表明遗传算法的寻优过程满足故障定位的要求，该方法具有较高的容错性， 优于传统的故障电流判别法，具有实用意义。 f ) 结合系统实例讨论了故障恢复的数学模型及目标函数和约束条件的数学 表述。针对辐射状配电网的特点采用前推回代法完成配电网的潮流计算。在实现 遗传算法故障恢复流程中提出了染色体基因分块编码方法、适应度函数的构造改 进、约束条件和目标函数的模糊化及实现等。最后分别用三馈线和七馈线系统对 故障恢复算法程序进行系统仿真，得出故障恢复重构改进g a 的若干结论。 g ) 完成配电网故障诊断系统软件的总体结构设计及实现，就七大模块的主 要功能及具体内容进行了深入分析，并分别给出主要模块的程序流程。 硕士论文遗传算法在配电网故障诊断中的应用研究 2 遗传算法及其在故障诊断中的应用 遗传算法( g a ，g e n e t i c a l g o r i t h m ) 是由美国m i c h i g a n 大学的j o h n h o l l a n d 教授创建的。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体 遗传学说。其基本思想是模拟自然界遗传机制和生物进化论，根据所求问题的目 标函数信息形成一种过程搜索最优解的算法 6 8 , 6 9 】。 2 1g a 的发展及特点 2 1 1g a 的发展 早在2 0 世纪5 0 年代和6 0 年代，少数几个计算机科学家独立地进行了“人 工进化系统”的研究，其出发点是进化的思想可以发展成为许多工程问题的优化 工具【6 9 4 3 1 。2 0 世纪6 0 年代，j o h nh o l l a n d 教授和他的数位博士受生物模拟技术 的启发，认识到自然遗传可以转化为人工遗传算法。1 9 6 2 年j o h nh o l l a n d 提出了 利用群体进化模拟适应性系统的思想，引进了群体、适应值、选择、交叉、变异 等基本概念。1 9 6 7 年，j d b a g e l y 在其博士论文中首次提出了“遗传算法”的概 念。1 9 7 5 年，h o l l a n d 编著了自然与人工系统中的适应性行为( a d a p t a t i o n i n n a t u r a la n da r t i f i c i a ls y s t e m ) ，系统地阐述了遗传算法的基本理论和方法，提出 了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。同年， d e j o n g 在其博士论文中首次把遗传算法应用于函数优化问题，对遗传算法的机 理与参数进行了较为系统地研究，并建立了著名的五函数测试平台，其中包括非 凸函数、连续函数、随机函数和高维函数，把模式理论和函数优化结合起来，定 义了遗传算法性能评价的标准。2 0 世纪8 0 年代初，h o l l a n d 教授实现了第一个 基于遗传算法的机器学习系统分类器系统( c s ，c l a s s i f i e rs y s t e m ) ，开创了 基于遗传算法的机器学习的新概念。1 9 8 9 年，d a v i dg o l d b e r g 编著了搜索、优 化和机器学习中的遗传算法( g e n e t i ca l g o r i t h m si ns e a r c ho p t i m i z a t i o na n d m a c h i n e l e a r n i n g ) ，全面系统地总结了当时关于遗传算法的研究成果，结合大量 的实例，完整的论述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础。 1 9 9 2 年，j o h nr k o z a 出版了专著遗传编程( g e n e t i cp r o g r a m m i n g ) ，提出了 遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号 处理等方面。同年，m i c h a l e w i c z 出版了一本很有影响力的著作“g e n e t i c a l g o r i t h m s + d a t as t r u c t u r e s = e v o l u t i o np r o g r a m s ”，对遗传算法应用于最优化问 题起到了推波助澜的作用。t 9 9 4 年该书再版发行。2 0 世纪8 0 年代中期遗传算法 进入了蓬勃发展时期，有关遗传算法的会议相继召开。1 9 8 5 年，在美国卡耐基梅 隆大学召开第一届国际遗传算法会议i c g a 8 5 。与之平行进行的国际会议很多， 硕士论文 遗传算法在配电网故障诊断中的应用研究 其中i n t e r n a t i o n a lc o n f e f e n c eo ne v o l u t i o n a r yp r o g r a m m i n g 和i e e ei n t e r n a t i o n a l c o n f e r e n c eo ne v o l u t i o n a r yc o m p u t a t i o n 也分别召开了6 届和4 届。2 0 世纪9 0 年 代以后，人们比较重视遗传算法的一些基本问题，d ej o n g 称为“重访基本假设”， 这方面的研究内容主要有：表示和形态发生学，拉马克算子等的弓i 入，非随机配 对和物种形成，分散的、高度并行的模型，自适应系统。共同进化系统等。 g a 在应用研究方面的长处主要得益于其求解的有效性、现有仿真环境下易 于实现、可扩充性和易于与其它方法相结合，可以预料在不远的将来，随着理论 研究的不断深入和应用领域的不断拓广，遗传算法将取得长足的发展。 2 1 2g a 的特点 遗传算法是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的 产生与进化过程。它通过模拟达尔文“优胜劣汰、适者生存”的原理激励好的结 构：通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好 的结构 7 们。作为一种随机的优化搜索方法，遗传算法有着其鲜明的特点： a ) 遗传算法操作的是待求问题变量的编码，而不是变量本身，目标函数解 释为编码化个体的适应值，因而具有良好的可操作性与简单性。 b ) 遗传算法使用概率规则而不是确定性规则指导搜索，只需利用目标的取 值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连 续多峰函数的优化以及无解析表达式的目标函数优化，具有很强的鲁棒性。 c ) 遗传算法通过控制种群中相对少的个体。能处理各代中大量的模式。若 每一代对个个体进行操作，基于模式定理，可得出每次遗传有效保留的模式 为o ( n 3 ) 的估计，即是说实际上处理了大约o ( n 3 ) 个模式。这体现了遗传算法的 隐含并行性，同时搜索解空间中许多点而不是一个点，因而能够快速全局收敛。 隐含并行性是g a 优于其它方法的关键所在。 d ) 遗传算法在变量空间中进行寻优，种群在遗传因子的作用下，同时对空 间中不同的区域进行充分搜索，从而构成一个不断优化的种群序列。g a 通过保 持在解空间不同区域中各个点的搜索，而不是盲目地穷举或试探，故能以很大概 率找到优化问题的全局晟优解。 2 2g a 的基本原理 利用遗传算法求解问题时，每个可能的解都被编码成一个染色体，若干个体 构成种群。算法开始时，随机产生一些个体( 即初始解) ，根据预定的目标函数 对个体进行评价，给出适应度值，基于此值选择个体用来复制下一代，选择操作 体现了适者生存、优胜劣汰的原理，选择出来的个体经过交叉和变异算子进行再 组合生成新一代种群。新个体由于继承了上一代的一些优良性状，因而在性能上 9 硕士论文遗传算法在配电网故障诊断中的应用研究 优于上一代，逐步朝着更优解的方向进化。 通常我们把h o l l a n d 所提出的算法称为标准遗传算法( c a n o n i c a lg e n e t i c a l g o r i t h m ) ，简称g a 、c g a 或s g a ，而将其他的“g a 类”算法称为g a s ( g e n e t i c a l g o r i t h m s ) 。经过多年的发展，g a s 在理论上和实际应用中都取得了很大的发 展，但在本质上，这些方法同g a 是相似的。 标准遗传算法的基本过程如图2 1 所示。 图2 i 标准遗传算法的基本流程图 2 2 1g a 的操作过程 2 2 1 1 编码 遗传算法求解问题时，首先确定问题的目标函数和变量，并对变量进行编码。 遗传操作算子在迭代过程中直接对串进行操作。因此编码的策略或方法对于遗传 操作，尤其是对于交叉操作的功能有很大的影响。 通常通过以下三个规范来评估编码策略：完备性、健全性和非冗余性。完备 性要求问题空间中的所有解都能用g a 空间的染色体表示：健全性要求g a 空间 l o 硕士论文 遗传算法在配电网故障诊断中的应用研究 的染色体能对应于所有问题空间中的候选解；非冗余性要求染色体和候选解一一 对应。在g a 中，问题空间是指由g a 表现型个体所组成的空间；g a 空间是指 由基因型个体所组成的空间。由于上述规则在实际应用中难以把握，一般采用 d e j o n g 提出的编码原理，主要包括2 条规则：a ) 有意义积木块编码规则，即所 定义的编码应当易于生成与所求问题相关的短距和低阶的积木块；b ) 最小字符 集编码规则，即所定义的编码应采用最小字符集以使问题得到自然的表示和描 述。规则a ) 是基于模式定理和积木块假设。从应用角度看，把握与应用问题空 间相对应的积木块的编码结构是十分困难的，在使用中应该使码串相关，并使相 关位置之间的距离最短。 编码方式可分为二进制编码和实数编码，即十进制编码。 采用二迸制编码方式，其优点在于它与计算机码制相一致，适于计算机应用； 编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理 进行理论分析；表示的变量范围大，适合表示离散变量，对于连续变量只要群体 总数取足够多，就能满足精度。其缺点在于对于一些连续函数的优化问题，由于 遗传算法的随机特性使得其局部搜索能力较差；对于一些多维、高精度要求的连 续函数优化，二进制编码存在连续函数离散化时的映射误差，个体编码串较短时， 可能达不到精度要求；而个体编码串的长度较长时，虽然能提高精度，但会使算 法的搜索空间急剧扩大。 利用实数进行编码，表示问题解的数字串会比用二进制表示的数字串短，相 应的遗传操作算子的计算量也会减小，所需的计算时间也相对降低；同时在优化 过程中不用对参数进行编码和译码，相应地就不存在解的精度问题。 综上所述，采用实数编码l l - - 进制编码工作量小，不存在编码、译码造成的 解的误差；而采用二进制编码便于计算机的操作。具体使用何种编码方式，要根 据实际的优化问题确定，考虑变量编码表示方便及遗传操作简便等问题。 2 2 1 2 遗传操作 遗传操作是模拟生物基因的操作，它的任务是根据个体的适应度对其施加一 定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可 使问题的解逐代优化，逼近最优解。 遗传操作包括三个基本遗传算子：选择、交叉和变异。选择和交叉基本完成 了遗传算法的大部分搜索功能，变异增加了遗传算法找到接近最优解的能力。 a ) 选择 选择是指从群体中选择优良个体并淘汰劣质个体的操作。它建立在适应度评 估的基础上，适应度越大的个体，被选择的可能性就越大，选择出来的个体放入 配对库( m a t i n gp 0 0 1 ) 中。 硕士论文 遗传算法在配电网故障诊断中的应用研究 目前常用的选择方法有以下几种： 轮盘赌方法( r o u l e t t e w h e e l m o d e l ) ：又称为适应度比例法，是目前遗传算法 中最基本也是最常用的选择方法。设种群的大小为，个体的适应度为：，则 个体i 被选择的概率尸c ，为： ， 只，= z z , , ( 2 1 ) ，j = 1 从式( 2 1 ) 看出，概率只反映了个体f 的适应度值在整个种群适应度总和中 所占的比例，如前所述，个体的适应度值越大，被选中的概率就越高，体现了“适 者生存，不适者被淘汰”这一自然选择原理。被选中的个体放入配对库中，随机 地进行配对，以进行交叉操作。 最佳个体保留机制( e l i t i s tm o d e l ) ：把种群中适应度最高的个体不进行配对 交叉而直接复制到下一代。这样做的好处是保证了进化过程中某一代的最优解不 被交叉和变异操作所破坏。但这也带来了弊端：局部最优的遗传基因会急速增加 而使进化停滞于局部最优解，也就是说，这种方法影响了遗传算法的全局搜索能 力。因此，最佳个体保留机制通常不单独使用。 期望值法( e x p e c t e dv a l u em o d e l ) ：是对轮盘赌方法的改进。当种群规模不 大时，使用轮盘赌方法进行选择操作，在选择过程中存在的随机性可能会产生较 大的随机误差，使适应度高的个体被淘汰。为避免这种情况的出现，引入了期望 值法： 1 ) 计算个体应被选中进行交叉操作的期望值： 一 ，卫 m = ，厂= ，l n ( 2 2 ) j = l 2 ) 按期望值m 的整数部分安排个体被选中的次数； 3 ) 对期望值m 的小数部分可按确定方法、轮盘赌方法、贝努利实验方法进 行选择，直至选满为止。 竞争法( t o u r n a m e n t s e l e c t i o n ) ：个体的选择公式为厶= m a x f , ，厂 ，即随机 地选取两个个体，对其适应值进行比较，大的被选中，小的被自然淘汰；如果两 个个体的适应值相同，则任意选取其中一个。被选中的个体放入配对库中，重复 此过程，直到配对库中包含个个体为止。这种方法既保证了配对库中的个体 在解空间有较好的分散性，同时又保证了加入配对库中的个体具有较大的适应 值。 窗i z l 方法( w i n d o w i n gm e t h o d ) ：首先求出目前种群中适应值最小的个体， 令其适应度值为o 。让种群中的每个个体适应值都减去q 后作为其新的适应值， 再用轮盘赌法形成配对库。采用这种方法，个体入选配对库的概率虽不与其适应 硕士论文遗传算法在配电网故障诊断中的应用研究 值直接成正比，但关系比较大，与种群中个体最大和最小适应值之差以及个体的 分散程度有关。 排挤方法( c r o w d i n g m o d e l ) ：在自然界中，当一种群中的个体大量繁殖生存 时，为争夺有限的生存资源，群体中个体之间的竞争压力必然加剧，因此个体的 寿命和出生率也因此降低。基于这种机制，d ej o n g 提出了排挤选择方法。采用 该方法时，新生成的予代将替代或排挤相似的旧父代个体。该方法可提高群体的 多样性。在采用覆盖种群模式的情况下( 代沟g = 0 1 ) ，排挤方法可描述如下： 1 ) 设定参数c f ( c r o w d i n gf a c t o r y ) ； 2 ) 从种群中随机地挑选c f 个个体组成个体集( 新的个体不包括在内) ； 3 ) 从这个体集中淘汰一个个体，该个体与新个体的海明距离最短。 每种选择方法对g a 的在线和离线性能的影响各不相同。在具体使用时，应 根据问题求解特点采用合适的方法或把它们组合使用。 b ) 交叉 交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通 过交叉操作能够在下一代产生新的个体，遗传算法的搜索能力得以飞跃性的提 高。交叉是g a 获取新优良个体的最重要手段。 根据交叉率只在配对库中随机地选取两个个体，并随机确定交叉位置进行交 叉操作。交叉操作分为以下几种： 一点交叉( o n e p o i n tc r o s s o v e r ) ：在个体串中随机地选定一个交叉点，两个 个体在该点前或后进行部分互换，以产生新的个体。交叉过程如图2 2 所示。 父个体1 ：1 l o o l l i 0 0 1 0 銮墨 ，子个体1 ：1 1 0 0 1 1 1 0 1 1 父个体2 ：0 0 0 1 0 i1 0 11子个体2 ：0 0 0 1 0 1 0 0 1 0 图2 2 一点交叉示意图 两点交叉( t w o - p o i n tc r o s s o v e r ) ：与一点交叉类似，随机地产生两个交叉点。 多点交叉( m u l t i p o i n tc r o s s o v e r ) ：是两点交叉的推广。 均匀交叉( u n i f o r mc r o s s o v e r ) ：将每个点作为潜在的交叉点，随机地产生与 个体等长的0 、l 掩码，通过掩码决定新个体的基因如何继承父个体基因。当掩 码样本为0 时，父代的两个个体相应位互换生成两个新个体的相应位；当掩码样 本为l 时，父代