（电气工程专业论文）基于智能优化算法的配电网网架优化研究.pdf

华北电力大学硕士学位论文摘要 摘要 配电网网架优化是一个多目标、多阶段、离散的，非线性、受约束的混合整数规划 问题。长期以来，各国学者对这一问题做了大量的研究，形成了很多算法。常规的 数学方法难以处理这样复杂的问题，因此，近年来国内外学者将智能算法引入配电 网网络规划。本文分析了配电网络优化规划的研究现状，对配电网规划采用的模型 进行总结，研究了近年来新兴的几种智能优化方法的搜索效率和收敛特性；并采用 蚁群算法和禁忌蚊群混合算法应用于配电网网架优化中，通过算例证明了该方法的 可行性和有效性。 关键词：配电网，网架优化，智能算法 a b s i r a c 。i s t n j c t u r co p t i m i z a t i o no ft h ed i s t r i b u t i o nn e t w o r k 鲥di sam u l t i - t a r g e t ，m u l t i t a r g e t ， m u l t i - s t e p ，d i s c r e t e ，n o n l i n e a ra n dc o n s t r a i n e dh y b r i di n t e g r a lp r o g r a m m i n gp r o b l e m s c h o l a r so ft h ew o r l dh a v ed o n eag o o dd e a lo fs t u d yt ot h i sq u e s t i o nf o ral o n gt i m ea n d m a n ya l g o r i t h m sh a v eb e e nf o r m e d i ti sd i f f i c u l tt od e a lw i t ht h i sc o m p l e xq u e s t i o nb yu s i n g t r a d i t i o n a lm a t h e m a t i c a lm e t h o d i nr e c e n ty e a r s ，i n t e l l i g e ma l g o r i t h m sb e c o m ew i d e l y a c c e p t e di nt h i sf i e l d i nt h i sp a p e r c u r r e n tr e s e a r c ho fs 1 1 1 l c n i r eo p t i m i z a t i o na n dm o d e l so f d i s t r i b u t i o nn e t w o r kg r i di si n t r o d u c e d ；t h es e a r c he f f i c i e n c ya n dc o n v e r g e n c ep r o p e r t yo f s e v e r a le m e r g i n gi n t e l l i g e n to p t i m i z a t i o nm e t h o d sa r ea n a l y z e d t h i sp a p e ri n t r o d u c e sa n t a l g o d t h ma n dt s a c oh y b r i da l g o r i t h mf o rd i s t r i b u t i o nn e t w o r kp l a n n i n ga n da l le x a m p l e s h o w st h ee f f e c t i v e n e s so f t h eb o m a l g o r i t h m s y a n gp u ( h i g hv o l t a g ee n g i n e e r i n g ) d i r e c t e db yp r o f p e n g y o n g l o n g k e yw o r d s ：e l e c t r i c a ln e t w o r k ，s t r u c t u r eo p t i m i z a t i o n ，i n t e l l i g e n ta l g o r i t h m 2 声明 本人郑重声明：此处所提交的工程硕士学位论文基于智能优化算法的配电网网架 优化研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作 和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期： 槛鸯 号邵 华北r 乜力大学硕上学位论义 第一章绪论 在现代电力系统中，大型的发电厂往往远离负荷中心，发电厂发出的电能，一 般要通过高压或超高压输电网络输送到负荷中心，然后在负荷中心由电压等级较低 的网络把电能分配到不同电压等级的用户。这种在电力网络中主要起分配电能作用 的网络就成为配电网络i ij 。 配电网按电压等级来分类，可以分为高压配电网( 3 5 1 1 0 k v ) 、中压配电网 ( 6 一i o k v ) 、低压配电网( 2 2 0 - 3 8 0 v ) ；按供电区的功能来分，可以分为城市配电网、 农村配电网和工厂配电网等。 配电网络因主要供给一个地区的用电，因而又称为地方供电网。相对于区域电 力网来说，它的电压等级和供电范围均要小一些，但它在结构上的最大特点是作为 电力网的末端而直接与用户相连，敏锐的反映着用户在安全、优质、经济等方面的 用电要求。 1 1 课题研究的目的和意义 电力工业是国民经济的重要部门之一。随着现代工业和农业的不断发展及人民 生活水平的日益提高，社会对电力的需求量越来越大。为了满足日益增大的电力需 求，必须不断扩大电力系统的规模，电力系统面临着日益繁重的规划任务。由于电 力工业的发展水平不仅对国民经济的其它部门会产生巨大的影响，而且一次能源消 耗和投资的数量也是相当巨大，所以合理地进行电力系统规划不仅可以获得巨大的 社会效益，也可以获得巨大的经济效益j 。 从2 0 世纪8 0 年代中期开始的城市电网规划工作到近几年来力度较大的城乡电 网改造，人们已经逐步认识到通过电网规划，寻求最佳电网投资决策和网络新建改 造方案的重要意义。用电网规划来指导电网的建设发展，可以保证资金的有效利用 和网络的长期最优发展；可以为电网的安全稳定运行及经营管理奠定基础：可以为 建立统一、开放的电力市场服务；也可以保证电网及电力工业的发展与国民经济的 发展及城乡建设协调一致。同时，人们还认识到应该对电网规划问题进行研究，以 期最大限度的提高规划质量，具有较大的现实意义和历史意义。 如上所述，城市电网规划工作十分重要，但到目前为止，仍缺乏能满足上述要 求的规划万法，而且在城市电网规划中所采用的方法也不是很完善。因此，对城市 电网优化规划方法的研究具有较大的现实意义。 1 2 城市电网规划研究概况 对一个地区来说，根据负荷预测的结果，确定了变电所容量、个数和所址以后， i 牛北i 乜力大学硕上学位论文 就已解决了高压配电网规划的“布点”问题，余下的问题就是变电所之间及其与电 源之间如何“连线”的问题，即网架结构优化问题。 1 2 1 网架规划的特点 网架规划问题具有下列特剧2 】： ( 1 ) 离散性：线路都是按整数的回路架设的，所以规划决策的取值必须是离 散的、或整数的。 ( 2 ) 动态性：网架规划不仅要满足规划年限内的经济、技术等性能指标要求。 而且要考虑到网络的今后发展以及今后网络性能指标的实现问题。 ( 3 ) 非线性：线路电气参数与线路功率及网损等等费用的关系是非线性的。 ( 4 ) 多目标性：规划方案不仅要满足经济、技术上的要求，还必须考虑社会、 政治及环境的因素，这些因素常常是相互冲突和矛盾的。 ( 5 ) 不确定性：负荷预计、设备有效度及水力条件等均存在显著的不确定性。 因此，从数学上讲，网架规划是一个动态、多目标、不确定性、非线性、整数 规划问题。 1 2 2 我国配电网的发展现状 与世界其它发达国家相比，我国的配电系统发展起步较晚，发展水平较低，建 设相对落后。城市配电网，特别是老的城市配电网。已或多或少滞后于城市的经济 发展，成为制约城市发展的瓶颈。我国电网投资不到电源投资的一半，而且配电网 投资又小于输电网投资。与发达国家相比，我国的配电网建设相对落后。 目前，我国城市配电网的发展还存在一些普遍性问题。如网架结构薄弱；电力 设备陈旧，事故率高；线路过载：可靠性差，电压质量低等。 具体可归纳为以下几点： 1 ) 中压配电网的网架结构薄弱； 2 ) 城市配电网技术落后，网络自动化水平低； 3 ) 线路损耗率较高，电压合格率普遍较低； 4 ) 电网供电可靠性低，电网规划不合理。 1 3 网架规划研究现状 在配电网规划方法研究中国内外已经取得了许多成就，现以规划模型和规划方 法为线索，对配电网规划研究的国内外现状进行综述。 2 毕北电力大学硕上学位论文 1 3 1 配电网规划采用的模型 a 单阶段模型 单阶段模型是一种假定负荷在规划水平年内不变的静态模型，它无需考虑配电 设备在规划期内投入的具体时间。通常，这种优化模型又可以分为四类：单馈线模 型( i n d i v i d u a lf e e d e r sm o d e l s ) 、系统一馈线模型( s y s t e m f e e d e r sm o d e l s ) 、两阶段模 型( s u b s t m i o n t h e n f e e d e r sm o d e l s ) 、变电站馈线模型( s u b s t a t i o n f e e d e r sm o d e l s ) 。 单馈线模型主要进行单个馈线的设计。文献【3 】建立了农村配电网的单馈线模 型，并用线性规划法和非线性规划法来进行求解。 系统馈线模型 4 - 6 1 是在变电站、负荷分布和供应点己知的情况下，确定变电站 之间的最优连接馈线并使总费用最小。通常情况下，这种模型在数学上可以表示为 一个混合o 1 整数规划问题。该模型将费用分为反映馈线投资的固定费用和反映网 络损耗的变化费用，并对变化费用部分作了线性化处理。模型的求解可以采用分支 定界法、基于固定费用的运输算法和网流法。 两阶段模型i _ 7 l 将配电网规划分解为变电站规划和馈线系统规划两个阶段，并通 过它们的相互协调确定配电设备的投入。其中，变电站模型采用0 1 整数规划模型， 馈线系统模型采用运输模型。m a s u d 于1 9 7 4 年最早提出了上述模型，该文首先用 0 1 整数规划的模型来优化变电站的容量，然后利用一个线性规划模型来优化变电 站间的负荷转移，通过变电站间的负荷转移来考虑馈线网络。 变电站馈线模型i s i o 是在系统一馈线模型中加入反映变电站决策的0 1 变量后 形成的模型，它能够同时确定变电站的容量、馈线的安装、馈线的潮流和变电站的 负荷。h i n d i 和b r a m e l l e 于1 9 7 7 年最早提出上述模型，并采用分支定界法求解。但 目标函数中没有包含变电站的损失费用。g o n e n 和f o o t e i g l 提出了一种改进的模型发 展了混合整数规划在单阶段配电网规划的应用。可以解决变电站的最优定位问题、 变电站变压器的最优容量选择问题、已存在变电站的最优扩展规划问题、变电站间 以及变电站与负荷中心间的负荷转移问题、配电网络的最优路径和最优馈线段尺寸 问题、配电网络的馈线更换问题等。 w i l l s ，n o r t h c o t e g r e e n 和r a m i r e z r o s a d a 分别对上述模型从规划方案的综合效 益、处理大规模问题的能力、对负荷预测误差的敏感程度以及改善的实际水平四个 方面进行了测试“2 l 。结果表明，变电站馈线模型在规划方案的综合效益和对负荷 预测误差的敏感程度上是最好的。 b 多阶段规划 多阶段规划是一种考虑负荷在规划水平年内变化的动态模型。多阶段模型需要 同时决定在规划期间内每一个设备的投入时间，以保证规划结果在整个规划期间内 牛北电力大学硕上学位论文 是最优的，同时多阶段模型不是单阶段模型的简单叠加，仅仅将单阶段模型中的变 量和参数替换为带时间下标的时间变量和参数是不够的。对于多阶段模型，必须建 立相互联系的时变决策量的清晰模型，或者称为逻辑性约束。本质上，配电网规划 的多阶段模型属于动态规划范畴。为了简化多阶段模型的求解，通常将多阶段模型 分解为单阶段模型进行求解【i 引，即：首先根据最终规划年的负荷水平进行规划，以 确定在规划期内所有待建设备；然后分别对每一个规划中间年，以前一个规划年的 网络为初始网架，根据所规划当年的负荷水平应用单阶段规划模型进行扩展规划， 并确定设备。由于设备的决策不是同时进行的，因此上述过程被称为伪动态规划。 1 9 8 4 年，e 1 k a d y 1 4 】将整个网络分为若干个子网分别进行规划，并把固定费用、 可变费用和损失费用表示成与时间相关的费用项。然而，该文中的分区规划与不分 区而直接进行配电网整体规划并不相同。 1 9 8 6 1 9 9 1 年，g o n e n 和r a m i r c z r o s a d a 对规划模型进行了改进m 。6 】增加了对 电压降落约束和辐射状网络约束条件。 纵观上述的多阶段模型，可以发现，建立在混合整数线性规划基础上的多阶 段模型的求解己经变得相当困难。无论是s u n 的两阶段法e l k a d y 的网络解藕法， 还是g a m i r e z r o s a d a 的伪动态规划法，都是通过将动态模型分解为静态模型来解决 的，因而在不同程度上牺牲了问题的最优性。即使g o n e n 和r a m i r e z r o s a d a 提出了 完全动态的模型【。7 l ，但是他们的模型仅仅局限于较小的系统，对于实际规模的配电 网规划问题，需要人们积极探索更加有效的算法。 c 不确定规划模型 传统的配电网规划优化方法是通过选择其中一个预想环境( 被认为实现概率最 大的一个) ，采用该环境下己“确定”的规划参数，求得满足该环境约束的、相对经 济指标最优的确定性方案【i s 】。这一类规划方法缺乏必要的适应性，其数学上的最优 方案往往由于未来的不确定性因素而使该“最优方案”失去了其最优的意义。事实 上，配电网规划确实涉及大量的不确定性。未来负荷增长大小和位置的不确定性、 配电网的扩展费用的不确定性等【9 j 。因此，在进行配电网规划时必须考虑这些不确 定性因素对规划结果的影响。 d 模型的简化 由于配电网规划所具有的多目标性、不确定性、非线性、动态性和整数性等特 点，使得配电网规划成为一个非常复杂的、大规模的组合最优问题。因此，无论是 应用数学规划方法还是启发式方法，都必须对求解模型作一定程度的简化。归纳起 来，主要分为以下几个方面： 1 ) 只考虑单阶段配电网规划，而不考虑动态的多阶段配电网规划。 4 华北电力大学颂上学位论文 2 ) 只考虑以费用为目标的单目标配电网规划。而不考虑多目标配电网规划。或 者即使考虑多个目标，但是通过把其它目标归算为费用指标，实现多目标配电网规 划向单目标配电网规划的转化。 3 ) 对模型的非线性进行线性化近似。概括起来，线性化主要分为两类：对目标 函数的线性化近似和对约束条件的线性化近似。 4 ) 减少目标函数的费用项【2 。系统的费用主要包括变电站的固定费用项和变化 费用项、馈线的固定费用项和变化费用项等四项费用1 2 1j 。 5 ) 减少约束条件数f l 卯。在配电网规划中，通常考虑的约束条件有：k i r c h h o f f 第 一定律；k i r c h h o f f 第二定律；设备的容量约束，包括变电站容量约束和馈线容量约 束；电压降约束；辐射状网络约束；可靠性约束。 6 ) 采用解耦方法。主要包括问题的解耦和配电网络的解耦。常用的问题解耦方 法有：采用b e n d e r s 分解法将配电网规划问题分解成投资子问题和运行子问题，将 配电网规划分解为变电站规划和馈线系统规划两个阶段，将多阶段配电网规划问题 分解成多个单阶段配电网规划子问题，分别求解各子问题并进行相互协调。常用的 配电网络解耦方法主要是将整个配电网电网络按照变电站解耦成几个子网，然后分 别规划并进行相互协调。 7 ) 只考虑确定性的配电网规划。而不考虑配电网规划不确定性。 1 3 2 配电网规划优化方法 配电网规划的数学规划方法包括确定性方法和不确定性方法。其中，确定性方 法又包括线性规划法、非线性规划法、动态规划法、网流规划法，而不确定方法有 模糊规划法、场景分析法、风险度估计法等。配电网规划的启发式方法包括传统启 发式方法、启发式专家系统和现代启发式方法。 a 配电网数学规划优化方法 1 ) 线性规划法 在众多的数学规划方法中，线性规划法是研究最早，也是最为成熟的一种数学 优化方法，它在配电网规划中的应用几乎涵盖了配电网规划早、中期的所有研宄 p - 2 6 j 。线性规划法又分为运输模型、线性规划、整数规划、混合整数规划等。 运输模型是最为简单的一种线性规划法。由于模型简单，共求解算法也最为有 效【5 】。然而，运输模型的一个严重缺陷是运输费用必须严格表达为线性化费用，而 用严格线性化费用模型来代替实际的非线性化费用模型是不准确的。运输模型另一 个严重缺陷是它不满足许多约束条件。 不带整数变量的线性规划是传统的、狭义的线性规划法。它的模型虽然较运输 华北电力大学硕上学位论文 模型复杂，但其求解算法也比较成熟【3 j 无论是采用线性规划的运输模型还是不带整数变量的纯线性规划模型，都无法 考虑到配电网规划的离散性，而整数规划则弥补了这方面的缺陷。在求解整数规划 问题时，由于整数规划的离散特征，解的数目是有限的，并且随整数约束变量数目 的增加而呈组合性的增加，因此，通过显式的方法枚举所有解的方案通常是不现实 的整数规划的常用方法是分支定界法，它是一种把隐式枚举和显式枚举有效结合 起来的整数规划方法，它的有效性依赖于它的枚举逻辑的有效性。 由于整数规划和混合整数规划在求解方法上并无太大差别，加之配电网规划中 大量连续变量的存在，因此采用纯整数规划模型进行配电网规划的文献非常少，绝 大数文献采用混合整数规划模型。 前面已经谈到，配电网规划是一个非常复杂的非线性规划问题。由于配电网规 划问题的非可微性。直接应用非线性规划算法来求解该问题非常困难，因此，这方 面的文献也比较少【2 7 圳j 。 除了直接应用非线性规划算法来求解配电网规划问题，一些文献还采用了动态 规划法【3 2 。3 5 】和网流规划法【3 们。 2 ) 不确定性规划 目前，在配电网规划中考虑不确定性主要有三种方法。 第一种方法是采用模糊数学理论【3 3 8 1 。文献【3 7 h 3 8 】对配电网规划问题建立了 相应的模糊线性规划模型，并相应发展了直流模糊潮流和交流模糊潮流。文献 3 9 】 建立了以模糊供电总成本最小为优化目标，通过计算电网故障状态下的模糊电量不 足期望值计算模糊缺电成本，最后利用遗传算法产生动态优化解。文献 4 0 】、f 4 1 】 采用盲数模型在合理的考虑多种不确定信息基础上进行了电网规划，达到了理想效 果。 第二种方法是场景分析法【4 2 1 。场景分析法并不直接对配电网规划中的不确定性 因素进行建模，而是将未来规划年的环境预想为多种可能的确定性场景，然后在不 同的场景下进行确定性的常规配电网规划，考虑对各种场景都具有较高适应性的配 电网规划方案为最优的柔性方案。 第三种方法是风险评估法【4 3 m 1 。这种方法是通过对可能出现的不确定性情形进 行评估和考虑，确定各个方案的风险率，然后进行确定性的电网规划，从而得到最 优的柔性扩展方案。 b 配电网启发式规划优化方法 以上分析了数学规划方法在配电网规划中的应用，我们可以发现，非线性规划 方法的局限性使得建立在非线性费用函数和非线性约束条件上的配电网规划模型 6 华北屯力大学硕上学位论文 往往得不到有效的解，而混合整数线性规划模型既弥补了运输模型和不带整数变量 的纯线性规划模型过于简化的特点，又避免了非线性规划的“非鲁棒性”，因而成 为求解配电网规划问题较理想的数学规划方法。但是，即使是这种最为理想的数学 规划方法，当进行实际的配电网规划时，由于变量的数日和约束条件很多，也会变 得非常困难，更不用说再在配电网规划中加入其它方面的考虑，如不确定性等。针 对以上数学规划方法的不足，启发式算法的特点就更为突出，它综合考虑了规划效 率和规划效果两个指标。在实践过程中，许多启发式方法，特别是现代启发式方法 常常能给出令人满意的、高质量的解1 4 钉。启发式方法的优点是直观、灵活、计算速 度快，便于规划人员在规划过程中参与具体的决策，通过规划人员过去的经验和常 用的配电网规划启发式规则，并借助于数学规划方法，得出符合工程实际的规划方 案。 1 ) 传统的启发式方法 传统的启发式方法通常基于系统某一性能指标对可行路径上线路参数的灵敏 度，根据一定的原则，逐步迭代直到满足要求的方案为止。这种方法在配电网规划 中的应用主要是结合“支路交换”( b r a n c he x c h a n g e ) 技术进行的。所谓支路交换是 指：对辐射状配电网，通过添加一条支路来形成一个环，然后断开另一条支路以恢 复其辐射状网络结构。重复该过程，直到任意支路交换均不能使目标函数减小为止。 1 9 9 0 年，a o k i 等提出求解单阶段规划问题近似最优解的支路交换法【4 6 l 。在该文中， 将约束条件简化为一系列线性方程，其求解是通过单纯形表和主导点操作来完成， 以决定使目标函数最优的最灵敏的支路交换。 文献 4 7 1 提出了单阶段配电网规划问题的多阶段支路交换算法，以提高算法效 率。 文献 4 8 卜【5 2 】提出了通过采用分解协调的方法，n 年的配电网规划问题被分解 为n 个单年的规划问题来求解。 1 9 9 7 年，g o s w a m i 对n a r a ，a o k i 等人的支路交换算法作了改进，将支路交换分 为两个阶段：区内支路交换和区间支路交换【5 2 】。其中，区内支路交换决定每个变电站 的最优网络结构，区间支路交换决定每个变电站的最优供电区域。 文献【5 l 】提出了一种动态支路交换算法，用于求解多年配电网规划问题。算法 分为两步：第一步，建立一组经济、技术士几可行的网络扩展方案；第二步，对多 年扩展规划，决定这些方案的最优顺序。 分析以上的支路交换法可以看出该方法有一定的局限性：一是应用在单阶段规 划中l ”j ，在添加一条支路形成环时，几乎环外所有的支路都参与交换，计算量大。 二是应用在多阶段规划中f 4 9 巧引，n 年的配电网规划问题被分解为n 个单年的规划问 7 华北屯力大学硕上学位论文 题来求解，但是并没有建立一个统一的目标函数求解，而是在各阶段规划方案中采 用某种协调策略进行处理，实际上属于伪动态规划。 2 ) 专家式启发方法 启发式专家系统可以看作是传统启发式方法的发展，它与传统启发式方法的区 别是在规划过程中引入了规划专家的经验，并便于规划人员参与到具体的规划决策 中去。值得指出的是，专家系统不是用来代替规划人员的，而是利用存放在知识库 中的指示和数据库中的基础数据，并通过推理机的推理，给规划人员提供相对较优 的规划方案，而最终的规划方案的选择是由规划人员作出的。 文献 5 3 】【5 6 】研究了基于专家系统的变电站定位和馈线结构问题。该专家系统 首先建立了规则库，变电站位置通过定位分配的方法确定。规划中还包括了变电站 选点、馈线走向选择的实际物理约束。 1 9 9 6 年，l o 和n a s h i d 在总结前人研究基础上，提出了一个交互式专家系统， 用予配电网规划的最优设计晡刀。专家系统被分为三部分：变电站的最优定位、确定 最优馈线分布和确定最优馈线类型。 3 ) 随机规划方法( 现代启发式方法) 随机规划方法，又称现代启发式方法，它包括人工神经网络a n n ( a r t i f i c i a l n e u r a ln e t w o r k ) 、模拟退火法s a ( s i m u l a t e da n n e a l i n g ) 、遗传算法g a ( g e n e f i c a l g o r i t h m ) 、进化规划e p ( e v o t u d o n a r yp r o g r a m m i n g ) ，t a b u 搜索t s ( t a b us e a r c h ) 、蚁 群最优法a c o ( a n tc o l o n yo p t i m i z a t i o n ) ，粒子群算法p s o 等。现代启发式方法是 一种通用的优化算法。它的另外一个重要特点是所有这些方法均能实现并行计算。 由于现代启发式方法在求解组合最优问题时表现出的卓越性能，在过去的二十年 中，它受到前所未有的关注。 综上所述，目前网架优化规划方法分为数学优化方法和启发式方法两类。 数学优化方法就是将电网规划问题用数学优化模型进行描述，然后通过一定的 算法求解。从而获得满足系统要求的最优规划方案。这种方法由于考虑了电网的决 策变量与运行变量等之间的相互关系，并将实际规划问题采用优化方法求解，因而 在理论上更严格些并保证了方案的最优性。但由予电网规划问题属于大规模的组合 数学问题。计算时间长、占用计算机内存大，对于实际的大规模系统求解困难很大。 因此，优化方法在建立模型时不得不对具体问题作大量简化。 传统的启发式方法是以直观分析为依据的算法，通常基于系统某一性能指标对 可行路径上一些线路参数的灵敏度，根据一定的原则，逐步迭代直到得到满足要求 的方案为止。这种方法直观、灵活、计算时间短，便于人工参与决策且能给出符合 工程实际的较优解。缺点是难以选择既容易计算又能真正反映规划问题实质的性能 s 毕北电力大学硕上学位论文 指标，并且当网络规模大时，指标对于一组方案都差别不大，难以优化选择。专家 启发式方法目前还不成熟，有待进一步研究。基于生物学、人工智能的现代启发式 算法与传统方法存在很大的区别：( 1 ) 传统方法以1 个解为迭代的初始值，而现代 启发式算法以l 组解为初值；( 2 ) 传统算法搜索策略为确定性的，而现代启发式算 法的搜索策略是结构化和随机化的：( 3 ) 现代启发式算法仅用到优化目标函数值的 信息，不必用到目标函数的导数信息，而传统算法大多数需要导数信息；( 4 ) 现代 启发式算法对问题的描述不要求满足可微性、凸性等条件，而传统搜索算法对此有 着较严格的要求；( 5 ) 现代启发式算法具有全局优化性能、鲁棒性强、通用性强且 适于进行并行计算的特点，而传统算法不具有这些优点l ，” 1 4 本文主要研究工作 如前所述，配电网络规划和优化运行是非常复杂的一个大规模、非线性、多目 标、多约束的组合优化难题。本文将蚁群优化算法用于求解配电网网架规划，主要 包含以下几方面下作： l 、简单介绍了智能算法的概况、原理、模型及流程。 2 、建立了目标年的配电网网架的基本数学模型，并对蚁群算法在配电网网架规划 中的应用进行了较为深入的研究。 3 、结合了禁忌搜索算法和蚁群算法两者的优点，提出了一种混合的禁忌搜索蚁群 算法，将其应用于配电网网架规划中，并通过算例证明了其有效性和可行性。 9 华北电力大学硕上学位论文 2 1 遗传算法 第二章智能优化算法介绍 近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人工 智能法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难越来越明显，于 是人们开始致力于研究一些能够处理当前难题的新型算法。1 9 7 5 年，j h o l l a n d 受生 物进化论的启发提出了遗传算法( g e n e t i c a l g o r i t h m s ，简称g a ) 。g a 是基于“适者 生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色 体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变 异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。 目前，随着计算机技术的发展，g a 越来越得到人们的重视，并在机器学习、模式 识别、图像处理、神经网络、优化控制、组合优化等领域得到了广泛的应用。 l 、遗传编码：按照遗传算法的工作流程，当用遗传算法求解问题时，必须在 目标问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码 运算。由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。然而，编码的 策略或方法对于遗传算子，尤其是对交叉和变异算子的功能和设计有很大的影响。 问题编码一般应满足完备性、健全性和非冗余性三个原则，完备性是指问题空间中 的所有点都能成为g a 编码空间中点的表现型；健全性是指g a 编码空间中的染色体 位串必须对应问题空间中的某一潜在解；非冗余性是指染色体和潜在解必须一一对 应。按照遗传算法的模式定理，d el o n g 进一步提出了较为客观明确的编码评估准 则，称之为编码原理。具体可以概述为有意义建筑模块编码规则和最小字符集编码 规则，前者表示编码应当易于生成与所求问题相关的短距和低阶的建筑模块；后者 表示编码应采用最小字符集使问题得到自然、简单的表示和描述。目前的编码方式 有二进制编码、大字符集编码、序列编码、实数编码、树编码以及乱序编码等许多 方式。 2 、评价函数：遗传算法将问题空间表示为染色体位串空间，为了执行适者生 存的原则，必须对个体染色体的适应性进行评价。因此，评价函数( 适应函数f i t n e s s f u n c t i o n ) 就构成了个体的生存环境。根据个体的适应值，就可以决定它在此环境下 的生存能力。若用s 。表示位串空间，s 。上的适应值函数可表示为f ( ) ：s o r + ，其 中r 。表示非负实数集合。对最小值优化问题，一般建立如下适应函数f ( x ) 和目标函 数g ( x ) 的对应关系： 1 0 毕北电力大学硕上学位论文 m 寸百如x 觐；蔷“ 弘t ， 其中，c 。可以是一个输入值或是理论上的最大值，或是到当前所有代或最 近k 代中g ( x ) 的最大值，此时c 。随着进化代数会有变化。对于最大化问题，一般 采用下述方法： 俐= n 耘茗i “ 陋2 ， 其中，c 。i 。既可以是特定的输入值，也可以是当前所有代或最近k 代中g ( x ) 的 最小值。 3 、遗传操作：标准遗传算法的操作一般都包括选择( s e l e c t i o n ，或复制 r e p r o d u c t i o n ) 、交叉( c r o s s o v e r ，或重组r c o m b i n a t i o n ) 和变异( m u t a t i o n ) - - - 种基本形式， 他们构成了遗传算法的核心，是模拟自然选择以及遗传过程中发生的繁殖、交叉和 突变现象的载体 选择：即从当前群体中选择适应值高的个体以生成交配池( m a t i n gp 0 0 1 ) 的过程。 目前，主要有适应值比例选择( f i t n e s s p r o p o r t i o n a t es e l e c t i o n ) ，b o t l z m a n 选择、排序 选择( r a n ks e l e c t i o n ) 、联赛选择( t o u r n a m e n ts e l e c t i o n ) 等形式。为了防止由于选择误差， 或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，d el o n g 提出了精英选择( e l i t i s ts e l e c t i o n o re l i t i s m ) 策略，另外。在机器学习等领域中， h o l l a n d 等专家提出了稳态选择方法( s t e a d y s t a t e s e l e c t i o n l 。 交叉：是进化算法中遗传算法具备的原始性的独有特征。g a 交叉算子是模仿 自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个 体，并生成包含更复杂基因结构的新个体。通常使用的交叉方式有一点交叉、两点 交叉、多点交叉、一致交叉等几种形式。交叉操作般分为以下几个步骤： a 1 从交配池中随机取出要交配的一对个体； b ) 根据染色体长度l ，对要交配的一对个体，随机选取【l ，l - l 】中一个或多个基 因位置作为交叉点； c ) 根据交叉概率p c ( o p c 1 ) 进行交叉操作，配对个体在交叉点处相互交换各 自的部分内容，从而形成新的一对个体。 变异：模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染 色体的结构和物理性状。在遗传算法中，变异算子通过按照变异概率p 。随机反转某 位等位基因的二进制字符值来实现。对于给定的染色体位串s = a i a 。a l ，新个体 j = a l a 2 a l 的具体产生过程如下： 华北电力大学硕上学位论文 眠新= 1 - 乙鬻 l 2 埘 ( 2 3 ) 其中，x 【o ，l 】，是对应于每一个基因位产生的均匀随机变量。为了保证个体变 异后不会与其父体产生太大的差异，变异概率一般取值较小，以保证种群发展的稳 定。 在进化的整个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操 作的作用是第二位的，变异算子仅仅充当背景性的角色( b a c k g r o u n dr o l e ) 针对具 体问题以及为了便于对进化过程实施控制，在标准变异算子的基础上，又引入了其 他类型的变异算子，比如：特定有效位变异、变异概率自适应调整、面向领域知识的 位变异等，使得遗传算法的应用范围和应用效果得到较好的改善。 4 、群体设定以及终止循环的条件 根据模式定理，群体规模对遗传算法的性能影响很大。种群规摸越大，遗传算 子所处理的模式就越多，算法陷入局部解的危险性就越小，因此，从保持种群的多 样性以防止陷入局部解的角度考虑，种群规模应较大。但是，种群过大会带来相应 的问题。一方面，种群越大，个体的适应度评价计算量也会随之增加，从而影响算 法的效率；另一方面，种群过大，随着进化代数的增加，会使少量适应度很高的个 体被大量地复制而生存下来，而大多数个体被淘汰，从而影响个体的竞争。对此问 题。已有一些学者进行了较深入的研究和分析，并得出了一些初步理论分析结果， g o l d b e r g 证明了使用二值编码的遗传算法时，群体中最优个体数目与编码的字符编 码长度的关系，孙艳丰等研究了自然数编码遗传算法的优群体规模。但在大多数情 况下，种群规模的大小是很难进行计算，从理论上讲不同的解题过程应该有不同的 最佳种群规模。 关于g a 迭代过程如何终止，一般采用设定最大代数的方法。首先该方法简单 易行但不准确：其次，可以根据群体的收敛程度来判断，通过计算种群中的基因多 样性测度，即所有基因位的相似性程度来进行控制；第三，根据算法的离线性能和 在线性能的变化判定；最后，在采用精英保留选择策略的情况下，按每代最佳个体 的适应值的变化情况确定。 综上所述，标准遗传算法的基本流程如图2 1 所示： 2 2 禁忌搜索算法 2 2 1 禁忌搜索算法简介 1 2 华北电力大学硕上学位论义 染色体解码 计算目标函数 函数值相适应值映射 适应值调整 三个基本算子 i 选择算子 2 交叉算子 3 变易算子 其他高级算予 确定实际问题参数集 对参数集进行编码 初始化群体p ( f ) 评价群体 初始化群体e ( o 口 群体p ( r + 1 ) 画谪斗互 满足停止准则 i结束 l ln 0 遗传操作 图2 1标准遗传算法的基本流程 禁忌搜索( 1 a b u ) 的思想最早是由g l o v e r 提出，其最重要的思想是标记对应已搜索 到的局部最优解的一些对象，并在下一步的迭代搜索过程中尽量避开这些对象，从而保 证对不同的、有效的搜索路径进行搜索。由于t a b u 算法具有灵活的记忆功能和藐视准 则，且在搜索过程中可以接受劣解，具有较强的“爬山”能力，搜索时能够跳出局部最 优解，转向解空间的其他区域，因此它是一种局部搜索能力很强的全局迭代寻优算法。 图2 2 为t a b u 算法与“爬山法”在寻优机制上的比较。) 【o 为初始解，x i ( i = l 2 ，9 ) 表示 9 步迭代中每步的最优解，n i 0 = 1 ，2 ，9 ) 表示对应x i 的邻域解的集合。首先通过比较) 【o 邻域n o 内诸多候选解中的目标函数值找出最优解x i ，同理找到在以x i 为当前点、n i 为 邻域的最优解x 2 ，“爬山法”陷入局部最小值x 3 ，而t a b u 算法则继续寻优，找到了比 x 3 更优的解x 9 。 华北电力大学硕上学位论文 。i g - i i i f ，、 l a b u 蜘地 图2 2t a b u 算法与爬山法的比较 2 2 2 禁忌搜索的基本原理 考虑最一般优化问题，对于x 中每一个解x ，定义一个邻域n ( x ) ( 由当前解x 所有的移动操作而产生的解的集合定义为解x 的邻域n ( x ) ) ，禁忌搜索算法首先确 定一个初始解x ，初始解x 可以从一个启发式算法中获得或者是从解集合x 中任意 选取。确定初始解后，定义解x 的邻域移动m c x ) ，产生当前点x 的邻域，然后从邻 域中挑选一个解x ，再从x 开始，重复搜索。如果邻域移动中接受前一移动的逆移 动，搜索就有可能陷入循环的危险，为了避免死循环和局部最优，算法中构造一个 短期循环记忆表一禁忌表( t a b ul i s t ) 。禁忌表中存放了刚刚进行过的l ( 禁忌长度) 个邻域移动，这些移动被看作是禁忌移动( t a b u m o v e ) 。对于当前的移动，再以后的 五次移动中是禁止的，l 次移动以后释放该移动。如果在l 次迭代内，能够把搜索 带到一个从未到过的区域，则此时该移动的禁忌状态就可以释放，不受禁忌表的限 制。禁忌表是一个先进先出的表，搜索过程中被不断修改，使禁忌表始终保持着上 个移动。即使引入了禁忌表，搜索仍有可能出现循环，一次必须给定停止准则来避 免循环的发生。当迭代次数大于给定值或在给定迭代次数内所发现的最优解无法改 进时，则算法停止。 由于禁忌搜索算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接 受劣解，所以具有较强的“爬山”能力，搜索时能够及时跳出局部最优解，转向解 空间的其他区域，从而增强了获得更好的全局最优解的概率，所以禁忌算法是一种 局部搜索能力很强的全局迭代寻优算法，禁忌搜索算法的流程图如图2 3 所示： 4 华北电力大学硕上学位论文 给定算法参数，随机产生初始解，置禁忌表为空 孬法收敛满毫、 n 由当前解产生邻域解，确定候选解 藐视准则满足 上n 候选解属性判断 y 将非禁忌对象对应的最佳解作为当前 解，并替换最早进入紧急表的对象 输出优化结果 将满足藐视准则的 解作为当前解，其 对应的对象替换更 新最优状态 2 3 粒子群优化算法 图2 - 3 禁忌算法流程图 2 3 1 粒子群优化算法的产生背景 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o np s o ) 算法是一种基于群体智能c s w a r mi n t e l l i g e n c e ) 方法的演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术。p s o 同遗传算法 类似，是一种基于群体的优化工具。系统初始化为一组随机解，通过迭代搜寻最优 值。但是并没有遗传算法用的交叉以及变异操作，而是粒子( 潜在的解) 在解空间追 随最优的粒子进行搜索。与遗传算法比较，p s o 的优势在于简单容易实现同时又有 深刻的智能背景，既适合科学研究，又特别适合工程应用。因此，p s o 一提出，立 刻引起了演化计算等领域的学者们的广泛关注，并在短短的几年时间里出现大量的 研究成果，形成了一个研究热点。p s o 最早是由k e n n e d y 和e b e r h a r t 受到人工生命 ( a r t i f i c i a ll i f e ) 的研究结果启发于1 9 9 5 年提出的，其基本概念源于对鸟群捕食行为 的研究。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物， 所有的鸟都不知道食物在那里，但是他们知道当前的位置离食物还有多远，那么找 到食物的最优策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟的周围 华北屯力大学硕上学位论文 区域，p s o 从这种模型中得到启示并用于解决优化问题。p s o 中，每个优化问题的 潜在解都是搜索空间中的一只鸟，称之为“粒子”，所有的粒子都有一个由被优化 的函数决定的适应值( f i t n e s sv a l u e ，每个粒子还有一个速度决定他们飞翔的方向和距 离，然后粒子们就追随当前的最优粒子在解空间中搜索。p s o 初始化为一群随机粒 子( 随机解) ，然后通过迭代找到最优解，在每一次迭代中，粒子通过跟踪两个极值 来更新自己，第一个就是粒子本身所找到的最优解。这个解称为个体极值；另一个极 值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群 而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。由 于认识到p s o 在函