（电子科学与技术专业论文）基于蚁群克隆遗传算法的配电网重构研究.pdf

m st h e s i s ： s e a r c hf o rd i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o nb a s e do n a n tc o l o n yc l o n a lg e n e t i c a l g o r i t h m s p e c i a l t y ：e l e c t r o n i cs c i e n c ea n dt e c h n o l o g y m a s t e rd e g r e es t u d e n t ：l u oj i n w e n s u p e r v i s o r ：a s s o c i a t ep r o f w a n gj i s c h o o lo fl n f o r m m i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a ，h u n a n ， c h i n a m a y2 0 1 0 9删础 舯删-9m 1 舢7 川-肿y 作者签名：受鳞垫 日期：韭年三月盟日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盟导师签名缬期：旦生年二月旦日 摘要 配电是电力系统的一个重要组成部分，配电网重构是在满足辐射 状负荷需求的情况下，通过变换刀闸的组合状态来达到降低网损、消 除过载、提高系统可靠性、提高配电质量及经济效益等目的。本文从 中心算法入手，讨论了在不同的目标函数下的配电网重构问题。 首先，通过对应用于配电网重构的大量算法进行分析，确立了将 蚁群算法( a c a ) 和克隆遗传算法( c g a ) 融合，形成蚁群克隆遗传算法 ( a c c g a ) 。该算法能弥补两个单一算法的缺点，同时发挥克隆遗传 算法的全局性及蚁群算法的正反馈性特点，能有效控制遗传进化的方 向。 其次，以降低网损为目标，将克隆遗传算法应用于配电网重构中。 根据配电网络及算法的特点，对配电网络的树状拓扑及潮流计算方法 进行了简化，对算法的编码、初始种群、遗传算子、初始信息素的产 生、信息素更新等方面进行优化改进，分别以i e e e 3 3 和i e e e 6 9 为案例 验证该算法的可行性。 再次，分析配电网络的可靠性、评估指标及其计算，采用系统平 均停电频率( s a i f i ) 和系统平均停电时间( s a i d i ) 为综合目标，对 配电网络进行提高可靠性的重构。对r t s b u s 2 和b u s 4 进行算例分析， 进一步验证了蚁群克隆遗传算法在配电网重构中的有效性。 最后，设计了一套配电网重构的实验装置，在这个平台上分别实 现了上述两种目标函数的配电网络重构。 关键词：配电网重构；克隆遗传算法；蚁群算法；网损；可靠性 a b s t r a c t d i s t r i b u t i o nn e t w o r ki sa ni m p o r t a n tp a r to fp o w e rs y s t e m u n d e r c o n d i t i o n so fm e e t i n gr a d i a ll o a dn e t w o r k ，d i s t r i b u t i o nn e t w o r k r e c o n f i g u r a t i o ni st oc h a n g et h ec o m b i n a t i o no fs t a t e s w i t c hi no r d e rt o a c h i e v el o w e rl o s s ，e l i m i n a t eo v e r l o a d ，i m p r o v es y s t e mr e l i a b i l i t ya n d p o w e rq u a l i t ya n de c o n o m i cb e n e f i t s s t a r t i n gf r o mt h ec o r ea l g o r i t h m ， t h ea r t i c l ed i s c u s s e dt h ed i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o nu n d e r d i f f e r e n to b je c t i v ef u n c t i o n s f i r s to fa l l ，a f t e ra n a l y z i n gal a r g en u m b e ro fa l g o r i t h m su s e df o r d i s t r i b u t i o nn e t w o r kr e c o n s t r u c t i o n ，a n tc o l o n yc l o n a lg e n e t i ca l g o r i t h m ( a c c g a ) ，w h i c hf u s e sa n tc o l o n ya l g o r i t h m ( a c a ) a n dc l o n a lg e n e t i c a l g o r i t h m ( c g a ) ，i se s t a b l i s h e d t h ea l g o r i t h mc a nc o m p e n s a t ef o rt h e s h o r t c o m i n g so ft h et w os i n g l ea l g o r i t h m s ，a l s od e v e l o pt h eg l o b a lo f c l o n a lg e n e t i ca l g o r i t h ma n dt h ep o s i t i v ef e e d b a c ko fa n tc o l o n y a l g o r i t h m ，s oi tc a ne f f e c t i v e l yc o n t r o lt h ed i r e c t i o no fg e n e t i ce v o l u t i o n s e c o n d ，a n tc o l o n yc l o n a lg e n e t i ca l g o r i t h mi sa p p l i e d t od i s t r i b u t i o n n e t w o r kr e c o n f i g u r a t i o nw i t hav i e wt or e d u c i n gt h el o s s a c c o r d i n gt o t h ec h a r a c t e r i s t i c so fd i s t r i b u t i o nn e t w o r ka n dt h ea l g o r i t h m ，w es i m p l i f y t h et r e et o p o l o g yo fd i s t r i b u t i o nn e t w o r ka n df l o wc a l c u l a t i o nm e t h o d s ， o p t i m i z et h ee n c o d i n g ，t h ei n i t i a lp o p u l a t i o n ，g e n e t i co p e r a t o r s ，t h ei n i t i a l p h e r o m o n e ，p h e r o m o n eu p d a t ee t c i e e e 3 3 a n di e e e 6 9c a s e sa r e r e s p e c t i v e l yu s e dt ov e r i f yt h ea l g o r i t h mf e a s i b l e t h i r d ，t h ea r t i c l ea n a l y z e st h er e l i a b i l i t y , a s s e s s m e n ti n d i c e sa n d c a l c u l a t i o no fd i s t i l b u t i o nn e t w o r k d i s t r i b u t i o nn e t w o r ki sr e c o n s t r u c t e d t oi m p r o v et h es y s t e mr e l i a b i l i t y , u s i n gt h es y s t e ma v e r a g ei n t e r r u p t i o n f r e q u e n c y ( s a i f i ) a n ds y s t e ma v e r a g ei n t e r r u p t i o nd u r a t i o n ( s a i d i ) a s i t sc o m p r e h e n s i v eg o a l t h er t s - b u s 2a n db u s 4i sa st h ee x a m p l et o f u r t h e rp r o v et h a ta n tc o l o n yc l o n a lg e n e t i ca l g o r i t h mi se f f e c t i v ei n d i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o n a t l a s t ， a e x p e r i m e n t a l d e v i c ef o rd i s t r i b u t i o nn e t w o r k r e c o n f i g u r a t i o ni sd e s i g n e d ，t h r o u g hw h i c hw er e s p e c t i v e l yr e a l i z e dt h e r e c o n f i g u r a t i o nb a s e d o na b o v et w oo b je c t i v ef u n c t i o n s k e yw o r d s ：d i s t r i b u t i o nn e t w o r kr e c o n f i g u r a t i o n ，c l o n a lg e n e t i c a l g o r i t h m ，a n tc o l o n ya l g o r i t h m ，n e t w o r kl o s s ，r e l i a b i l i t y i i i i l l 2 ：! 2 1 3 研究现状及其发展趋势3 1 3 1 传统方法4 1 3 2 人工智能优化方法4 1 4 本文的主要工作6 第二章蚁群克隆遗传算法8 2 1 克隆遗传算法8 2 1 1 遗传算法的基本原理8 2 1 2 克隆遗传算法的基本原理9 2 1 3 克隆遗传算子9 2 1 4 克隆遗传算法特点。l o 2 2 蚁群算法1 0 2 2 1 蚁群算法的基本原理一1 0 2 2 2 蚁群算法的数学模型。l l 2 2 3 蚁群算法的参数分析。1 3 2 2 4 蚁群算法的特点及改进1 4 2 3 蚁群克隆遗传算法1 4 2 3 1 蚁群克隆遗传算法的基本原理1 4 2 3 2 构建蚁群克隆遗传算法的原因。1 5 2 3 3 蚁群克隆遗传算法的操作步骤16 2 4 本章小结。1 7 第三章基于降低网损的配电网重构1 8 3 1 总体结构框图18 3 2 配电网络结构1 9 3 2 1 拓扑结构1 9 3 2 2 结构简化2 0 3 2 3 拓扑分析一2l 3 4 3 4 3 适应度函数3 0 3 4 4 克隆遗传算子一3 0 3 4 5 初始信息素的生成及更新3 2 3 4 6a c c g a 变异概率选择3 3 3 4 7 结束条件。3 4 3 5 排除不可行解模块3 4 3 5 1 双环网3 5 3 5 2 三环网3 5 3 5 3 排除不可行解3 6 3 6 算例分析3 8 3 6 1 算例l 3 9 3 6 2 算例2 4 l 3 7 本章小结4 4 第四章基于提高系统可靠性的配电网重构4 5 4 1 配电系统可靠性4 5 4 1 1 可靠性定义。4 5 4 1 2 国内外研究4 6 4 2 可靠性指标4 6 4 2 1 负荷点的可靠性指标4 6 4 2 2 系统的可靠性指标一4 7 4 3 以提高系统可靠性为目标的配电网重构4 8 4 3 1 数学模型4 8 4 3 2 可靠性计算一4 9 4 - 3 3 算法流程51 4 4 算例分析5 3 4 4 1 算例l 5 3 4 4 2 算例2 5 4 4 5 本章小结5 5 第五章配电网重构的硬件设计5 6 5 。l 系统设计5 6 5 2 下位机模块设计5 6 5 3 上位机模块设计5 8 5 3 1 配电网络实现模块5 8 5 3 2 操作界面5 8 5 4 本章小结。6 0 第六章总结与展望6 1 6 1 总l 砉6 l 6 2 展望6l 参考文献。6 3 附勇匙6 8 附录ai e e e 标准3 3 节点单电源配电系统6 8 附录bi e e e 标准6 9 节点单电源配电系统7 0 附录ci e e e 配电网可靠性测试系统7 3 附录d 下位机数据采集模块电路7 6 i v 致谢7 7 攻读硕士学位期间的主要研究成果7 8 i 。一 硕士学位论文第一章绪论 第一章绪论 配电系统是电力系统的最后一个环节，联系整个电力系统与用户，是向用户 供电的重要环节，其电能质量和可靠性是电力系统的关键。特别是在一些大中城 市，重要的用户较多，可靠性要求相对高。然而，因为配电网络的电压等级相对 较低，功率损耗相对较大，这势必对配电网的经济运行造成影响。当前经济发展 异常迅速，供电需求及质量越来越高。因此，通过配电网络重构来使配电系统更 经济、更安全和更可靠的运行将带来很大的社会效益和经济效益。 本文主要研究配电网络重构的问题。本章对该课题选题的背景、研究的目的 以及研究的意义进行了论述，并且详细介绍了目前有关配电网络重构的研究状况 以及发展趋势。 1 1 选题背景 从我国的电力建设来看，历来重视发电，轻视输电和配电，在电网的投入上 存在不足。根据发达国家的经验，发电资产通常小于输、配电资产，输电和配电 的资产与发电资产之间的比例为4 0 ：6 0 ，而我国仅占3 5 ：6 5 。以当前的发展速度和 状况来看，电网“瓶颈 仍极大可能存在。电力系统中大约有5 - - - 1 3 的电 能因为线路损失浪费在配电系统中。故而，研究如何减少配电系统中的线路损 失是一项及其重要的工作。 一般说来，减少配电系统中线路损失的方法有五种，为安装电容器，引入更 高电压等级，负荷平衡，更换线路，网络重构。为考虑可靠性、经济性方面，更 换线路、引入更高电压等级、安装电容器很少作为减少线路损失的方法。但是网 络重构能够利用网络中已存在的设备来使线路损失减少，使系统安全性提高， 所以它是一个非常重要的解决手段。配电系统的每条馈线的负荷都是工业负荷、 商业负荷、居民负荷等类型的组合状态。它们有各自的日负荷变化曲线，使得各 馈线负荷的峰值在不同时刻出现。正常运行条件下，通过网络重构可以将部分负 荷从重负荷馈线转移至轻负荷的馈线上，从而使线路损失减少和馈线上电压的分 布质量提高。配电网络重构是配电系统正常运行的重要优化手段，是配电系统自 动化过程中的一个不可或缺的部分。 现在，配电网多采用放射网状结构，对故障反映比较敏感，大多数用户停电 是由配电系统发生故障引起的，如何充分挖掘配电网的潜力已经被人们广泛关 注。 配电系统的开关有两类：一类是联络开关，这类开关在系统正常运行时处于 硕士学位论文第一章绪论 断开状态；另外一类是常闭开关，这类开关在系统正常运行时处于闭合状态。因 为配电系统具有开环运行、闭环设计的特点，所以，当联络开关闭合时，必须要 将相应的常闭开关断开。配电网的重构问题实际上是配网结构的优化问题。通过 改变开关状态变换配网的结构，从而达到使各馈线之间的负荷相互进行转移而且 分配合理，使系统在发生故障时恢复供电的能力得到加强，从而达到减少负荷点 的停电时间和停电次数，进一步减少系统的平均停电持续时间和平均停电频率， 最终使配电系统可靠性得到大大加强的目的心1 。本质上说，配网重构是一个非线 性的混合整数规划问题。 在这种背景下，本文展开了对配电网重构问题的研究。 1 2 研究的现实意义 1 2 1 配电网重构的概念 配电网络重构是近十几年来一个备受关注的研究课题。按照电压等级不同， 配电网分为低压配电1 网( 3 8 0 2 2 0 v ) 、中压配电网( 3 l o k v ) 以及高压配电网( 3 5 1 l o k v ) 。本文讨论的是城市l o k v 配电网，属于第二类。 配电网络为环形结构，开环运行。为满足电网的开环运行，在配电系统的各 馈线上会装设一些分段开关，而在各馈线之间则装设一个或者多个联络开关。配 电网络具有网络复杂、线路长、电压低、网络损耗大等特点。为了保证供电的可 靠性，在电网运行过程中，需要把一段线路中的负荷通过开关的变换转移到不同 的电源上供电，电荷转移的这个过程就是配电网络重构。而重构的目的则是消除 线路的过载情况、降低配网的有功网络损耗以及改善节点的电压质量等。 1 2 2 配电网重构研究的意义 在我国，中低压配电网电压低、过负荷、可靠性差的现象可能会越来越严重， 给人民生活和城市的经济发展带来的不良影响会越来越大。加快配电网络重构， 既可以降低电网损耗、提高电网质量以及可靠性、确保电网的运行安全，而且也 可以提高电力企业的经济效益、适应市场经济发展的要求。 配电网重构的意义有： ( 1 ) 整合以前各种算法的优点，对网络结构进行最优化，以达到减小网络损 耗，节约能量的目的。 ( 2 ) 合理分配各馈线间负荷，避免过载情况发生，使电网的安全性及供电质 量得到提高。这样，系统就能均衡负荷，使甩负荷的情况减少，从而得到更多的 2 硕士学位论文第一章绪论 电费收入，提高经济效益。 ( 3 ) 提高供电可靠性。通过对配网的优化，可以加快故障的隔离、尽快恢复 供电、明显减少停电次数，从而达到提高整个配电系统的供电可靠性。 ( 4 ) 通过对配网进行重构，开发出一套智能化管理系统，可以减少人工费用， 提高效率。 1 3 研究现状及其发展趋势 配电网主要研究的内容包括计算网损的潮流计算，网络结构简化、建模及识 别，状态估计与规划，搜索算法的优化等。 在正常运行时，配电网的联络开关断开，使系统保持“树状 运行的状态， 但它的存在又使得系统整体成“环状”结构，这是唯一的。反过来，由联络开关 连接而成的“环状结构来确定系统的“树状”运行状态却不是惟一的，存在着 多种不同的解，即多种不同的组合。而组合情况不同导致对应的潮流分布不同， 该网络结构下的线路损耗也不尽相同。所以，我们希望在这些组合，找到一种组 合，配电网络按照这一组合方式运行时，某一个目标函数达到最优。此外，最优 的运行方式也会随着负荷的变化而变化。 最优配电网重构技术由b a c k 和m e r l i n 于1 9 7 5 年首先提出【3 】，此后不断有研 究者提出了多种方法。 按目标函数划分，网络重构有如下几种分类： ( 1 ) 以系统有功损耗最小为目标函数 4 1 。 ( 2 ) 以负荷平衡率为目标函数【5 】。 ( 3 ) 以提高电压质量为目标函数【6 1 。 ( 4 ) 在故障情况下以最快时间、最大范围恢复用户供电为目标函数【7 】。 另外，还有综合了以上的两个或多个目标函数多目标的网络重构算法，各目 标函数占用不同的比例，用来满足综合需求【8 一。 按中心优化算法划分，目前求解配电网重构的算法主要有以下几种分类： ( 1 ) 传统方法：分支定界法1 4 、单回路优化法【l o 】、最优流模式算法【1 1 1 、支路 交换法【5 , 1 2 。 ( 2 ) 人工智能优化方法：粒子群优化算法 t 3 , t 4 , 1 5 1 、人工神经网络法【1 6 , 1 7 1 、 禁忌算法 1 8 , 1 9 1 、模拟退火法 2 0 2 1 1 、模糊系统口2 】、遗传传算法1 2 4 2 5 1 、蚁群算法 【2 6 2 7 2 引、免疫算法【2 9 3 0 3 1 l 等。 3 硕士学位论文 第一章绪论 1 3 1 传统方法 m e r l i n 和b a c k 等人首先在配电网络重构问题中运用数学规划的方法【3 】然 后进一步采用分支定界法 4 1 得出了最好的网络结构。文献【1 0 】阐明了一次只合上 一个、断开一个开关的单回路优化方法。s c i v a n l a r 等人首先提出的支路交换算 法【1 2 j 在文献【1 0 的基础上，进一步提出每次将联络开关中两端点电压差最大的那 个闭合，使电压差大的一侧的负荷移动到电压差小的一侧去。很多研究人员继续 改善了这一算法，比如综合支路交换法和负荷均衡法i s 】。首先由d s h i r m o h a m m a d i 等人提出的最优流模式算法将开关组合问题转化为计算优化潮 流的问题【l 。 1 3 2 人工智能优化方法 ( 1 ) 人工神经网络法a n n 应用人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 进行配电网络重构，主 要是利用a n n 的非线性特点，它能通过训练找到配电网络结构中开关的非线性 关系，从而输出对应的开关状态。 m a k a s h e m 等人【l6 】将以工业、商业和民用三类负荷水平为样本的输入，以 不同开关状态下的负荷模式为样本输出，实现电压稳定为目标的配电网络重构。 文献 1 7 】以配电网负荷作为输入，网损最小时的开关状态作为输出，实现配电网 络的重构。 a n n 的缺点在于需要花费大量的时间来训练样本。 ( 2 ) 模拟退火s a 在人工智能优化算法中，s a 最早被引入求解配电网重构问题。s a 算法具有 较好的局部搜索能力，易跳出局部最优解，一般可以得到全局最优或全局次优解， 缺点是收敛的关键在于初始解，即初始温度及退火方案的选取。 文献 2 0 】提出了利用模拟退火算法、克隆遗传算法各自的优点，在c g a 遗 传操作的过程中插入退火方案，既提高了重构速度，又避免了早熟收敛，且有效 保证了解空间的可行性和完备性。文献 2 1 】将s a 进行局部搜索，应用于门阵列 的布局优化，提高了全局搜索能力及搜索速度。 ( 3 ) 遗传算法g a 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 来源于适者生存的自然规律和生物遗传学。 将一个群体( 种群) 中的所有个体( 染色体) 作为研究对象，利用随机搜索技术，对 参数空间进行编码，然后高效地搜索求解解空间的过程就是遗传算法的基本过 程。它是上世纪6 0 年代，由美国m i c h i g a n 大学的h o l l a n d 教授提出来的。 4 硕士学位论文 第一章绪论 在配电网络重构问题上，k n a r a 等人【2 4 】第一次将其描述成一个 混合整数规划问题，采用简单遗传算法配电网络进行编码、遗传算子的设置及 操作，最后完成了重构。文献 2 5 】采用了改进的染色体编码策略，即相邻开关在 染色体中相邻以及构成同一环路的开关在同一基因块内的编码方法，极大地提高 了有效候选解的比例。采用了单点移位和令基因块为整个染色体的p g a 基因移 位操作和修正的p g a 基因突变操作，消除了常规遗传算法中对可行性解破坏严 重的双亲交叉算子的作用，从而有效的避免了常规算法的缺陷。 ( 4 ) 蚁群算法a a 通过观察蚂蚁的觅食习性，意大利人m d o r i g o 等人发现了蚁群算法。而在 模拟蚂蚁的觅食习惯后，将其特性加以提炼、改造，构造出人工蚂蚁。蚁群算法 就是按人工蚂蚁的习性进行觅食的算法，是一种基于种群寻优的启发式搜索算 法，具有相互协作及正反馈性，已被证实在求解大规模组合优化问题上是非常有 效的。 文献【2 6 】提出一种用最小生成树的方法来表示解，避开了配电网络结构的有 效性检查，使搜索在可行解域内进行，而且利用蚁群算法本身的并行性搜索，搜 索效率进一步得以提高。文献 2 7 1 j 嗵_ 过修改蚁群算法的信息素，使其适用于配电 网络优化，另外还根据重构中开关的动作求取近似网络损耗，从而得到一种实用 的大规模网络的优化方法。文献 2 8 通过将蚂蚁的信息素构造信息熵来指导粒子 的运动方向，调节粒子收敛速度，有效地防止了局部收敛的产生。 ( 5 ) 粒子群算法p s 0 美国普渡大学的k e n n e d y 和e b e r h a r t 在1 9 9 5 年根据鸟类和鱼群的社会行为 提出了粒子群优化算法( p s o ) 【1 3 1 。在初始化阶段，粒子在解空间追随最优的粒子 进行随机搜索，通过迭代的方法找到最优解。每次迭代后，粒子通过跟踪两个极 值来完成对自己的更新。p s o 具有实现简单，调整的参数少等优点。 文献 1 4 】把粒子群算法( p s o ) 和克隆遗传算法相结合，提出了粒子群克隆遗 传算法，构建了p s o 变异算子，使整个搜索过程在随机完成的同时又带有一定 方向性，朝着个体及群体最优点进化，在提高速度的同时保证全局收敛。文献 1 5 指出由于粒子速度降低而失去继续搜索可行解的能力而导致了早熟，提出一种基 于种群速度动态改变惯性权重的粒子群算法，该算法以种群粒子的平均速度为信 息，动态改变惯性权重，避免了粒子速度过早接近。 ( 6 ) 禁忌搜索算法t s 禁忌搜索算法t s ( t a b us e a r c h ) 是局部领域算法的推广。其主要特点是采用 禁忌技术，禁止重复以前的工作。用一个禁忌表记录已经经历过的局部最优点， 在下次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以避免陷入局 硕士学位论文第一章绪论 部邻域搜索时导致过早收敛的困境。 文献 18 】按照环路上的开关进行编码，应用禁忌搜索策略，将环路上的开关 依次放入禁忌表中，不断更新表中内容，完成配电网络的重构，该算法能有效收 敛。文献 1 9 1 在配电网络重构中应用禁忌搜索，能有效提高计算效率，并且找到 全局最优解。 ( 7 ) 其他智能算法 文献 2 9 】以负荷平衡为评价的标准，将免疫算法应用于配电网络重构，将被 优化问题对应抗原，解作为抗体，亲和力的大小对应解的优劣。算例证明，它能 在较快的时间内找到全局最优。文献【3 0 提出运用免疫系统的免疫机制、动量系 数自动调整的特点来构造自适应因子，且能根据负荷的曲线图智能化的分区段， 使系统能实现动态的无功优化，达到最优控制。文献 3 1 提出将免疫算法与克隆 遗传算法融合，在克隆遗传算法的基础上，利用高频变异进行接种疫苗和免疫选 择，在算法的前期能均匀地搜索解空间，后期对配网进行重构，提高了算法的全 局收敛性及收敛速度。 文献 2 2 】提出将模糊策略融入遗传算法中，对遗传操作的交叉概率和变异概 率进行模糊控制，有效克服了简单遗传算法带来的早熟收敛。文献 2 3 提出将配 电网络规划分为基于时间和空间维度的配电网络，对负荷动态的变化采用模糊综 合评价的方法。 1 4 本文的主要工作 配电网重构问题已经成为很多学者研究的课题，取得了很多成绩，重构问题 不断得到改进和优化，但仍存在一些问题。本文主要内容有： ( 1 ) 在分析克隆遗传算法和蚁群算法的基本原理、优缺点及应用的基础上， 提出把克隆遗传算法和蚁群算法融合成蚁群克隆遗传算法，分析蚁群克隆遗传算 法的原理、实现流程和主要特性。 ( 2 ) 结合配电网络的运行特点简化树状拓扑结构，建立相应的配网模型，着 重介绍了应用蚁群克隆遗传算法时的前推回代法进行潮流计算。 ( 3 ) 研究蚁群克隆遗传算法在降低网损的配电网重构中的应用。结合具体特 点，对蚁群克隆遗传算法的编码、遗传算子、初始信息素的产生、信息素更新等 方面进行优化改进；在重构过程中采用有效性判断模块，排除产生的不可行解； 以网络损耗最小作为目标函数，分别对i e e e 3 3 和i e e e 6 9 节点进行案例分析， 验证该算法的可行性。 ( 4 ) 分析配网的可靠性、评估指标及其计算，以提高系统可靠性为目标，应 6 硕士学位论文第一章绪论 用蚁群克隆遗传算法进行配电网重构，对r t s b u s 2 和b u s 4 进行算例分析，进 一步验证了蚁群克隆遗传算法在配电网重构中的有效性。 ( 5 ) 本文最后还将以降低网损为目标的配电网络重构和以提高系统可靠性 的配电网络为模型，建立了配电网络重构的硬件部分，能模拟配电网络的重构过 程，并对重构结果进行分析。 本文后继各章节安排如下： 第二章介绍蚁群克隆遗传算法的基本原理，第三章分析基于降低网损的配电 网重构，第四 的硬件设计， ( 3 ) 效率通常低于其他传统的优化方法； ( 4 ) 易出现早熟收敛； ( 5 ) 算法的可信度、精度、复杂性等没有有效的定量分析方法。 鉴于此，人们对算法的改进作了大量的工作，得出了很多有价值的结论。有 8 硕士学位论文第二章蚁群克隆遗传算法 学者将自适应的思想引入g a ，构成自适应遗传算法( a g a ) 。自适应遗传算法具 有更好的鲁棒性和更高的计算效率。最初使用二进制编码方式，操作简单，但对 基因比较多的组合优化问题易造成“组合爆炸”于是有学者提出通过改进编码 策略【圳来减少组合状态，譬如改用整数编码【3 5 】或格雷编码【3 6 】，能有效提高求解 效率。另外，还有学者提出对遗传操作( 如选择、交叉、变异操作等) 进行改进， 如文献【3 6 中引入了进化策略，a 个父代产生旯个子代，参与竞争后取代父代， 文献 1 4 1 中采用粒子群来构造变异算子，使其按个体最优及种群最优的方向进 化。对交叉概率、变异概率也进行了一些改进，文献 2 2 】提出将模糊策略融入遗 传算法中，对遗传操作的交叉概率和变异概率进行模糊控制，有效克服了简单遗 传算法带来的早熟收敛。遗传算法的一个主要缺陷是“早熟收敛 ，为了避免“早 熟 现象，人们设计新的遗传算子、对控制参数进行改进等等。文献【3 7 】将蚁群 算法的思想引入到遗传算法中，并通过马尔可夫方法验证了其收敛性。 2 1 - 2 克隆遗传算法的基本原理 克隆遗传算法( c l o n a lg e n e t i ca l g o r i t h m ，c g a ) ，又称为单亲遗传算法 ( p a r t h e n og e n e t i ca l g o r i t h m ，p g a ) 。它没有交叉操作，所有遗传操作都作用在一 个个体上。这样的操作简单，计算效率高，且具有全局收敛性。 遗传操作中最主要的是交叉算子。当两个染色体相同时，交叉操作将不能产 生新的染色体。因此，基本遗传算法的初始染色体必须具有广泛的多样性，且在 迭代中也要一直保持下去，直至收敛于全局最优解。如果在中途失去了多样性， 则交叉操作将无法进行而引起“早熟”。 而c g a 没有交叉算子，它的所有操作都在一个染色体上进行，与染色体的多 样性没有关系，即使所有个体都相同也能开始遗传操作。 2 1 3 克隆遗传算子 克隆遗传算子主要包括基因突变算子和基因重组算子，基因重组算子又分基 因倒位算子、基因换位算子和基因移位算子等【3 引。 ( 1 ) 基因倒位算子：按某一概率将染色体的某一( 几) 个子串中的基因依次首 尾交换，随机选取子串的位置、长度。基因倒位也有单点倒位和多点倒位两种。 ( 2 ) 基因换位算子：按某一概率交换染色体中某两个( 串) 位置上的基因，该 位置是随机产生的。基因换位有单点换位和多点换位两种。 ( 3 ) 基因移位算子：将一条染色体看作一个环，按某一概率将个( 些) 基因 依次前移或后移，该基因( 串) 是随机的。基因移位有单点移位和多点移位两种。 ( 4 ) 基因突变算子：按某一概率使一条染色体中的某一( 几) 个基因改变状态， 9 硕士学位论文 第二章蚁群克隆遗传算法 取其它值，随机选取突变位置。它分单点突变和多点突变两种。 2 1 4 克隆遗传算法特点 ( 1 ) 对序号编码方式和实数编码策略均可适用。 ( 2 ) 所有操作在一个染色体上进行，简单易行。 ( 3 ) 种群个体不要求多样性。 ( 4 ) 不存在“早熟收敛现象。但如果个体失去了多样性，算法就只能从一 个点开始进行搜索，使搜索效率下降而发生“准早熟 。所以尽量选择多于一个 个体的种群。 ( 5 ) 约束优化问题容易在遗传操作过程中处理。 近十多年来，已经有学者将克隆遗传算法用于配电网重构啪14 3 1 巩3 9 1 。 2 2 蚁群算法 上世纪9 0 年代，欧洲学者d o r i g o m a c r o 等人通过模拟蚂蚁寻找食物路径的 集体行为，提出了蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) ，它是一种启发式仿生进 化算法。该算法最早被用于解决旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，后 来又用于解决作业安排调度问题( j o b s h o p s c h e d u l i n g p r o b l e m ，j s p ) 和二次分配 问题( q u a d r a t i c a s s i g n m e n t p r o b l e m ，q a p ) 等复杂优化问题。但是蚁群算法在运行 时，搜索时间长、收敛速度慢、易限于局部最优解，成为推广中的瓶颈。 2 2 1 蚁群算法的基本原理 研究发现，蚂蚁在寻觅食物的过程中总是能找到从栖息地到食源的一条最短 路经。在寻找的过程中，蚂蚁之间通过释放一种体外激素来传递信息，它们能感 知路径上外激素的存在和强弱，并且选择激素强的路径前进，这样相互协作，来 寻找到食源的最短路径。蚁群的这种行为属于信息的正反馈现象：当某一条路径 将越来越 群的这种 障碍物的 戈d 绕过 b 点， 硕士学位论文第二章蚁群克隆遗传算法 一只蚂蚁走过后留在路径上的信息素为1 。为简单起见，设信息素停留时间为l s 。 ( 1 ) t = 0 时，由于路径a c 、a d 、b c 、b d 上均没有信息素存在，位于a 和b 的蚂蚁以相同的概率选择a c 、a d 、b c 、b d ，如图2 1 ( b ) 所示。 ( 2 ) t = l 时，在路径a c b 上的信息素是路径a d b 上信息素的二倍。因为路 径a d b 的长度是路径a c b 的二倍，相同时间信息素挥发的要多些。将有3 0 只 蚂蚁由a 和b 到达c ，有2 0 只蚂蚁由a 和b 到达d ，如图2 1 ( c ) 所示。 ( 3 ) t = n 时，蚂蚁将以越来越大的概率选择路径a c b ，最终所有蚂蚁选择路 径a c b ，找到由a n t 到s o u r c e 的最短路径，图2 1 ( d ) 所示。 由上述过程可知，蚂蚁之间这种交换信息的过程是一个正反馈过程。 c ( a ) 初始状态 s o u r c e dc s o u r c e d ( b ) t = 0 ，蚂蚁以相同概率选择路径 s o u r c e dcd ( c ) t = l ，更多蚂蚁选择较短路径( d ) t = n ，几乎所有蚂蚁选择较短路径 图2 - 1 蚁群算法原理图【4 0 】 我们在上述蚂蚁觅食的过程上进行简化，构造出人工蚂蚁。它保留了自然蚂 蚁的正反馈性，而且人工蚂蚁的对以前的觅食过程具有一定的记忆能力，并不是 完全盲目的选择下一条路径。 2 2 2 蚁群算法的数学模型 为了更好的叙述，以旅行商问题为例来说明蚁群算法的具体实现过程。 ( 1 ) 初始化 设各路径上的初始信息素相同，( 0 ) - - r 。( f 。为一个很小常数) 。在f 时刻蚂 硕士学位论文 第二章蚁群克隆遗传算法 蚁七由城市i 转到j 的概率群由式( 2 一1 ) 决定。 嘭( ，) ：j 揣，j f 与f 相连的城市( 2 - 1 )嘭( ，) = 艺五丽吖训叩日琏州坝兀1 10 ，否则 r l 表示边( f ，歹) 的能见度( 取= 1 吒) ，口为蚂蚁在运动过程中以往积累信息的 重要性，为启发信息在蚂蚁选择路径时的相对重要性。 ( 2 ) 评价 t = n 时，