（电力系统及其自动化专业论文）基于成本效益分析的输电网络规划设计方法的研究.pdf

。舻， 垒! ! ! ! 兰呈! s t u d yo ft r a n s m i s s i o nn e t w o r k p l a n n i n gb a s e do nc o s t b e n e f i ta n a l y s i s a b s t r a c t n o w a d a y s ，t h e e c o n o m i co ft r a n s m i s s i o nn e t w o r ko p t i o n a l p l a n n i n g s c h e m e si ss t u d i e dc o m p a r a t i v e l ya b u n d a n t wi t ht h e a c c i d e n ta p p e a r i n gc o n s t a n t l y ，t h ep o w e rn e t w o r ko p e r a t e si sp a i d a t t e n t i o nt o s t e a d i l ys a f e l y ，t h e c o n s i d e r a t i o no fr e l i a b i l i t ya n d s e c u r i t yo fp l a n n i n gs c h e m e si st h ei m p o r t a n ts u b j e c tt h a td e s i g n e r s g e n e r a l l yp a yc l o s ea t t e n t i o n t o a tp r e s e n t b e c a u s et h ee c o n o m i c l o s s e st h a tt h ep o w e rs u p p l yr e l i a b i l i t yq u e s t i o nc a u s e st ou s e r sw i l l b e c o m et h ei m p o r t a n tf a c t o rt h a tw i l lb ec o n s i d e r e dw h i l em a k i n gt h e p r i c eo fe l e c t r i c i t yi nt h ef u t u r e s ot h et o t a lc o s to fp o w e rn e t w o r k s u p p l yp o w e rs h o u l d n to n l yi n c l u d ep o w e rn e t w o r ke x p a n dc o s to f i n v e s t m e n t ，o p e r a t i n g c o s to fc o n s t r u c t i o n ，b u ta l s oi n c l u d et h e u n s e r v e de n e r g yc o s to fd e m a n ds i d et h a tt h ee l e c t r i c i t ys u p p l i , e do f p o w e rn e t w o r kw i t hi n s u f f i c i e n t l yo rs t o p p e dc a u s e st ou s e r sl o s s e s b ys t u d y i n g t h et r a d i t i o nt r a n s m i s s i o nn e t w o r kp l a n n i n gd e s i g n m e t h o d ，o nt h eb a s i so fs u m m a r i z i n gf o r e f a t h e r s r e s e a r c h ，t a k i n gt h e c o s t b e n e f i ta n a l y s i st h e o r yi ne c o n o m i c sa sab a s i s ，a n a l y z i n gt h e e c o n o m ya n dr e l i a b i l i t yo ft h en e t w o r ks c h e m e s ，if u r t h e ri n v e s t i g a t e m a t h e m a t i c sm o d e lo ft r a n s m i s s i o nn e t w o r kp l a n n i n ga n da s k i n gt h e m e t h o do f s o l v i n g i n o r d e rt o s y n t h e s i z e a n dc o o r d i n a t et h e c o n t r a d i c t i o nb e t w e e nt h es c h e m e se c o n o m ya n dr e l i a b i l i t ya tf i r s t ， i n t r o d u c i n g c o s t - b e n e f i ta n a l y z et h e o r y ，ip r o p o s em u l t i - o b j e c t m a t h e m a t i c sm o d e lo ft r a n s m i s s i o nn e t w o r kp l a n n i n g ，h a v ep e r f e c t e d i i i a b s t r a c t t h e a p p l i c a t i o n o ft h ec o s t b e n e f i t a n a l y z e i nt h e p r a c t i c e o f t r a n s m i s s i o nn e t w o r kp l a n n i n gp r o j e c t ，h a v em e tt h en e e d so fr e a l i t y o fp o w e rd e v e l o p m e n t ；s e c o n d l yu s i n gm u l t i o b j e c to p t i m a lt h e o r i e s t oo p t i m i z et h em a t h e m a t i c sm o d e l ，a d o p t i n gt h ei m p r o v e dg e n e t i c a l g o r i t h ma sa s k i n gs o l v i n gt o o l s ，ib e c o m et h ea s k i n ga n ds o l v i n go f t h eq u e s t i o np o s s i b l et oo p t i m i z et h em u l t i - o b j e c tm o d e l ；a c c o r d i n g t o t h em o d e la n da l g o r i t h mp u tf o r w a r di nt h ep a p e rf i n a l l y ，1w r o t et h e c o r r e s p o n d i n ga n a l y s i sp r o c e d u r e ，a n dh a sc a l c u l a t e da n da n a l y z e d o a v e r - 6 n o d e s y s t e m a n dp o w e rn e t w o r k e x p e r i m e n t a ls y s t e mo f 18 - n o d e r e s p e c t i v e l y t h e r e s u l t si n d i c a t et h e f e a s i b i l i t y a n d e f f e c t i v e n e s so ft h em e t h o dp r o p o s e di nt h ep a p e r k e y w o r d s ：c o s t - b e n e f i ta n a l y z e ，t r a n s m i s s i o n n e t w o r k p l a n n i n g ， g e n e t i ca l g o r i t h m ，u n s e r v e de n e r g yc o s t l v 关于学位论文使用授权的说明 本人完全了解广西大学有关保留、使用学位论文的规定，即： 广西大学拥有在著作权法规定范围内学位论文的使用权，其中包 括：( 1 ) 已获学位的研究生必须按学校规定提交学位论文，学校可以 采用影印、缩印或其他复制手段保存研究生上交的学位论文；( 2 ) 为 教学和科研目的，学校可以将公开的学位论文作为资料在图书馆、资 料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内 容。 本人保证遵守上述规定。 ( 保密的论文在解密后遵守此规定) 作者签名：赵兰鉴歪 日期：型靼盟 导师签名：乏壑堕鹭 日期：趁华些 第一章绪论 第一章绪论 1 1 输电网络规划研究的意义 电力是现代社会发展的重要动力。随着国民经济的高速发展， 社会对电h 力的需求量越来越大。为了满足b 益增长的电力薷求，必 须不断扩大电力系统规模。由于电力系统的发展水平不仅会对国民 经济各部门产生巨大影响，而且还涉及到大量的一次能源消耗和巨 额投资，所以，合理地进行规划不仅可以获得巨大的社会效益，也 可以获得巨大的经济效益。电力系统规划的失误将会给国家建设带 来不可弥补的损失【lj 。 由于电力系统的复杂性，人们通常将电力系统分为发电系统、 输电系统及配电系统三个子系统进行分析和研究。相应地，电力系 统的规划一般也分为电源规划、输电网络规划和配电网络规划三个 部分在电力系统中，输电系统是一个中间环节，负责将电能从各 发电中心送到各负荷中心、因此，输电网络规划直接关系到电源发 出的电能能否及时送出。电网设备投资巨大，且设备寿命长达数十 年，使电力系统未来的发展强烈受“过去权重”的制约。因此，输电 系统的投资决策直接影响着电力系统的长期发展。合理的输电系统 结构是电力系统安全可靠经济运行的物质基础。 因此，在现阶段对输电网络规划的方法进行研究具有重要的现 实意义。 1 2 输电网络规划研究的内容和特点 输电网络规划的任务是根据规划期内负荷增长和电源规划方案 确定相应的最佳电网结构，以满足经济可靠输送电能的要求。输电 网络规划的基本原则是在保证将电力安全可靠地输送到负荷中心的 前提下，使电网的建设和运行费用最小其中有几点基本的要求： ( 1 ) 正常运行要求：在电力系统设备完好的情况下，保证各项 运行指标，如线路输送功率、发电机出力、系统电压水平和稳定储 第一章绪论 备系数等指标在给定的允许范围内。 ( 2 ) 安全运行要求：在某些设备故障、检修( 如n 1 或n - 2 运行方式) 的情况下，满足给定的供电可靠性要求 输电网络规划是一个系统优化问题，具有以下特点： ( 1 ) 多目标性 一个规划合理的电网不仅要在技术上先进可行，达到安全可靠、 灵活方便的目标，也要实现经济上投资合理、产出效益高的目标， 同时还要在社会效益、环境保护等方面满足要求。而技术，经济和 环境保护要求之间通常会相互影响甚至相互矛盾。因此，评价一个 方案优劣是一项复杂的工作。若将所有问题都加以考虑并用一个统 一的数学模型进行规划，这将是一个非线性大系统多目标数学规划， 其求解是非常困难的。 一 ( 2 ) 不确定性 输电网络规划是以未来电力系统发展条件如电源和负荷的发展 水平为基础的。由于受国家政策调整、社会经济发展、人口变动和 环境变化等因素影响，电力系统的发展条件也在不断变化，而且越 远的将来，条件越模糊、越不确定，甚至是不可预料的。因此，不 确定性是长期输电网络规划的又一突出特点。上述不确定因素对规 划方案的合理确定有着显著影响，必须在制定规划决策时加以考虑。 ( 3 ) 非线性 电力系统就其本质来说是一个非线性的大系统，线路电气参数 与线路功率、传输功率与网损等关系是非线性的，这使输电网络规 划的目标函数、约束条件也都是非线性的。若采用数学上的非线性 规划算法来求解，对具有一定规模的输电网络规划来说相当困难。 ( 4 ) 动态性 。 动态性是长期输电网络规划尤为突出的特点之一长期输电网 络规划为多阶段输电网络规划，规划期内既要考虑各阶段电网方案 的可行性，又要考虑各阶段之间的相互影响，还要考虑整个规划期 内的要求，各阶段输电网络规划之间存在着动态性对于这种多阶 段动态规划问题，最严格的是依据数学上的动态规划方法求解，但 因输电网络规划的众多变量和约束条件，使得用动态规划方法求解 2 第一章绪论 极容易造成“维数灾难”闼题，求解变得非常困难。故动态规划方法 虽然理论完善却难以实用。至今尚未见到用动态规划法进行大规模 输电网络规划取得成功的报道。 ( 5 ) 整数性 由于线路是按照整数回路架设的，所以输电网络规划的决策变 量必然是o - 1 整数性质的。丙数学上的整数规划算法对于多决策变 量、多约束条件的大规模输电网络规划来说很难适用。 1 3 输电网络规划研究方法综述 长期以来，各国学者和工程技术人员对输电网络规划进行了大 量的研究，提出了各种各样的方法。从传统的方法开始，先后经历 了几十年的发展过程。计算机技术的飞速发展以及系统工程、运筹 学等科学领域取得的璀璨成果，为改进输电网络规划提供了坚实的 基础，加快了规划工作的进程。 在最初的传统启发式方法【3 1 1 4 1 ( 如逐步加线、逐步减线法等) 中， 没有明确的目标函数，而是将线路投资等隐含目标与线路的有效性 指标相结合，规划运算过程结束的原则是网络中没有冗余线路( 逐步 减线法) 或网络中没有过负荷线路( 逐步加线法) 。这类模型以隐式的 直流潮流方程为约束，具有简单、易于计算等特点。 还有一类模型以明确的经济性指标为目标函数的模型。该类模 型以网络投资费用、运行费用、设备折旧维修费用和电能损耗费用 等经济性指标之和为目标函数，其中应用最广泛、最为大家所接受的 是“水平年输电网络规划数学模型”【 。该模型以预测的某一规划水 平年的负荷水平为已知条件，以待选线路为决策变量( x i 0 ，1 ) ，以 线路建设投资和系统运行费用为目标函数，以确定性可靠性指标 一一n 1 原则为约束条件之一。常见的方法是首先建立满足正常运 行情况的电力网络的架线方式，然后进行断线分析，通过消除断线以 后出现的过负荷现象，对网络扩展方案进行修改，直到满足给定的约 束条件为止。 这类模型把可靠性分析作为后校验计算，可靠性标准是以确定 3 第一章绪论 指标，忽视了供电可靠性的经济价值对用户方的影响，在输电网络 规划工程实践应用中具有很大的局限性，不能灵活地适应输电网络 规划过程中来自供电方、用户方和其它方面对输电网络规划方案的 不同要求和约束。， “需求侧管理”【5 】的兴起使人们的可靠性观念发生了变化。人们不 再仅以供电方节省投资为目的，而开始注重投资的效益，认识到由于 减少投资造成的停电损失超过节省资金的可能性，于是以用户的停 电损失为基础，提出了可靠性价值。用户在购买电力的同时也购买了 电力的个重要品质一定的供电可靠性。由于供电可靠性问题 给用户造成的经济损失必将成为今后制定电价时要考虑的重要因 素。因此，电网供电总成本不应再仅包括电网扩展建设的投资成本、 运行成本。还应包括由于电网电力供给不足或中断造成的用户缺电 损失，即需求侧的缺电成本【6 l 。 由于电力系统故障多是随机发生的，而且许多故障超出了系统 工程人员的控制能力，因此一般说绝对定的毫不中断地联系供电实 际是不可能的。虽然增加投资可以提高可靠性，然而过高的投资违 反了经济性的约束。为了摆脱经济性和可靠性约束之间相抗衡的困 境，几十年来，设计规划人员一直在探索确实可行的判据和分析技 术。 。 成本效益分析方法作为一种经济分析方法，通过对标的物成本、 效益的分析与评价，可综合协调其成本效益之间的关系，近年来受 到国内外学者的广泛重视。1 8 1 4 年杜普依特提出了消费者盈余概 念，这概念引出了净效益的概念，成为目前成本效益分析的基础。 1 9 3 6 年成本效益分析方法在美国首先得到了实际应用，以后在各种 领域得到了广泛的发展 7 】 ，近年来，国内外许多专家、学者致力于应用成本效益分析方法 进行输电网络规划的研究，提出了一些很有价值的理论和观点f 8 】【9 1 。 建立不少规划模型【1 0 1 【1 ，值得我们研究 针对各种规划模型，人们研究出了多种求解方法，目前的电网 优化规划方法可分为启发式方法和数学优化的方法两大类。 。 启发式方法是一种以直观分析为依据的算法，通常是基于系统 4 第一章绪论 菜一性能指标对可行路径上的一些参数作灵敏度分析，根据一定的 原则选择要架设的线路。主要由过负荷校验、灵敏度分析、方案形 成三个部分组成。 启发式方法又分为两种。第一种是逐步扩展法，即根据灵敏度 分析的结果，以最有效的线路加入系统逐步扩展网络幢】【13 1 。另外一 种是逐步铡推法。即首先将所有待选线路全部加入系统，构成一个 冗余的虚拟网络，然后根据灵敏度分析，逐步去掉有效佳低的线路。 启发式方法因为具有直观、灵活、计算时间短以及易于同规划 人员经验相结合等优点而在实际工程中得到较多应用。但它不是严 格的优化方法，不能很好地考虑各阶段各架线决策间的相互影响。 因此，启发式方法不能保证得出的规划方案最优。特别是当规划期 较长、待选线数量较多时，所得结果可能与真正的最优方案有很大 偏差4 与启发式方法相比，数学优化方法在理论上要优越些，输电系统 规划可以应用运筹学上的各种优化理论和求解法来求解。数学优化方 法是对输电网络规划作数学描述，处理成有约束的极值问题，然后用 最优化理论进行求解。和启发式算法相比，数学优化方法在理论上更 为优越，因此得以广泛研究和发展。数学优化的主要方法有：线性规 划、非线性规划、整数规划、混合整数规划和动态规划方法。 线性规划方法是最优化技术中发展最成熟的领域，同时也是应用 最广泛的优化方法。人们常常采用近似措施将非线性问题线性化，以 便利用线性规划处理非线性优化问题。线性规划模型的主要不足是用 连续变量模拟离散的决策变量，不能准确地描述输电网络规划的整数 性，得到的结果要么偏离最优解，要么不满足约束条件。1 9 7 0 年k a l 。 t e h b a c hj c 等人酋先提出求解输电网络规划问题的线性规划法5 】， 19 8 5 年v i l l a s a n ar 等人作了改进 16 1 ，但这些方法都是基于灵敏度分析 建模，精度不高，并且用连续变量确定离散的0 1 整数变量，带来较大 误差，解的最优性无法得到保证。但因线性规划法具有计算简单、求 解速度快等优点，在输电网络规划中还是得到了较多的应用和发展。 。 1 9 7 3 年，p u n t e l 等人提出了一种输电网络非线性规划模型，并采用 “非线性规划法中的梯度法来求解此模型，利用伴随网络的方法求解性 5 第一章绪论 能指标相应于支路电纳的梯度向量，进而选择有效线路加入。由于存 在解的取整问题，为了保证解的可行性，文献【1 7 】中只好采取循环的方 法来解决，这就无法保证解的最优性 1 9 7 4 年，l e e 等人把输电网络规划表述为一系列的0 一l 整数规划问 题，并利用o 1 隐枚举法进行求解us 。0 - 1 整数规划，对解决小规模的 问题效果较好，但当规划变量个数增加时会遇到“维数灾难”问题，因 此这种方法还有待改进；0 - 1 隐枚举法，在0 - 1 整数规划的基础上有了很 大改进，大大减小了整数规划的规模，但是该算法的搜索计算量较大， 计算时间较长，同时，由于采用了一些近似方法，因此，所得结果也 不一定是问题的最优解。 1 9 8 5 年s h a r i f n i a 建立了输电网络规划的混合整数规划模型，此模 型较为全面地反映了输电网络规划中的各个目标函数，但因为约束条 件和变量太多而难以实用u g 。 随着网络规模与规划时间的增加，人们开始研究电网的多阶段动态 规划问题。提出了动态规划数学模型。求解过程分两步：第一步是把原 问题作为一般线性规划问题求得一松弛解，第二步用分枝定界法求得最 优解。这种方法具有连续性和滚动性，解决了多阶段规划问题中各阶段 方案间的协调与过渡问题。 九十年代以来，以模拟进化算法，模拟退火算法和t a b u 搜索算法 为代表的新型数学优化方法的兴起为输电系统规划问题的解决提供 了新的途径，其中，遗传算法得到了较多的研究。 遗传算法是一种人工智能的方法，也是一种框架结构的算法。它是 根据自然界优胜劣汰的原则进行搜索和优化的，遗传算法在自适应控 制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命 等领域的应用中展示出优越性和魅力 2 0 j 。 遗传算法己在电力系统的许多方面得到了应用1 2 1 - 2 3 j ，如在电力 系统的经济调度、无功优化、输输电网络规划 2 4 1 2 ”、以及配输电网络 规划等方面都使用了遗传算法。利用遗传算法进行输电网络规划，能 在较短的时间内提供若干个最优、次优优化方案，而且能避免一般优 化算法的局部最优或维数灾难等问题，遗传算法原则上可以加入任何目 标函数和约束条件，算法在电力系统规划上的应用为电力系统规划 6 第一章绪论 开创了一条新的途径。 文献 2 4 1 首先将遗传算法应用于单阶段输输电网络规划，约束条件 主要考虑了线路的过负荷约束，文中采用网络最大流法计算系统过负荷 量。为改善算法的收敛性，作者采取了保留优良品种的措施，提出的成 对变异原理极大地改善了算法的收敛性。文【2 6 】在此基础上进行了改进， 主要是采用了竞争的选择机制。文2 5 】在建模时还考虑了n 1 安全约束， 但给出的算例结果并不满足n 1 安全要求。文【2 1 1 则利用模拟退火算法来 求解输电系统规划问题，对某8 9 节点、1 8 3 支路系统的计算结果比 b e n d e r s 分解法、启发式方法的结果在投资费用上节省7 左右。文献 2 2 1 在并行计算机上实现了用于解决输电系统规划的并行模拟退火算法，对文 献 2 l 】的算例得到了更为经济的方案。模拟退火算法的主要缺点是计 算时间较长1 9 9 7 年浙江大学的文福栓教授【2 3 】将t a b u 搜索用于输电系 统规划，算例系统的结果证明了算法的可行性。文【2 7 】中将遗传算法用 于大规模系统的规划，并与文献1 2 2 】的结果进行了比较，表明遗传算法 能够搜索到比模拟退火算法更优的解。文 2 8 】的作者进一步将遗传算 法、模拟退火算法及t a b u 搜索结合起来构成一种混合方法来求解输督 网络规划问题，得到的结果优于三种算法中任一单独算法得的结果。 文 2 9 】将遗传算法用于复杂的多阶段输电网络规划，并对算法采用了 改进措施，提高了算法的全局收敛性。以上方法都成功应用于输电网 络规划，结果表明了这类新型优化方法非常适用于解决输电网络规划 问题。 1 4 本文所作的工作 本文选择基于成本效益分析的输电网络规划作为主要的研究方 向，研究工作涉及到以下几个方面：成本效益分析法在输电网络规 划中的应用、多目标输电网络规划模型及求解方法、适用算法的优 化以及相关程序的编写等多个方面。全文共分为六章。各章的主要 内容介绍如下： 第一章对输电网络规划的内容、特点和研究动态进行阐述，分 析了传统输电网络规划中存在的问题，在此基础上提出了成本效益 7 第一章绪论 分析应用于输电网络规划设计的思想。 第二章对成本效益分析的理论基础及其在输电网络规划中应用 的意义和改进作了详细介绍，并建立了多目标输电网络规划模型。 第三章对本文建立的数学模型的解算工具即遗传算法的基本原 理进行了介绍，并针对其不足之处做出了改进。 第四章结合本文的研究内容，对本文建立的数学模型中所需求 解的缺电成本作了研究。 第五章算例与分析。 第六章全文总结及以后的研究方向。 8 第二章成本效益分析 第二章成本效益分析 2 1 成本效益分析法的理论基础 成本效益分析3 0 1 是经济学里的一个全称名词，包含着对一个 工程甸题的投资成本和由此产生的效益进行评价构全过程。成本 效益分析以杜普依特有关消费者盈利的观念为基础，它使用潜在的 帕雷托优越性作为决策标准，为工程问题的分析研究提供了一个数 量方面的基础。这一标准揭示了一个优越的规划方案必须由获利者 给亏损者以潜在的补偿而使双方不存在很大的差别，使得各方面的 净效益达到平衡。 在图2 1 ( a ) 中，总成本( t c ) 和总效益( t b ) 都是规划收 益( b ) 的函数；图2 1 ( b ) 绘出了边际成本( m a r g i n a lc o s t m c ) 、 边际效益( m a r g i n a lb e n e f i t - - m b ) 和平均成本( a c ) 与规划收益 的关系。 所谓边际成本是指每增加一个单位的收益而需增加的投资成 不，即收益为( b + 1 ) 早位h 寸阴思成本藏丢收盈为占盯阴思厩本： 里要；边际效益是指因增加了一个单位收益而获得的效益或因此而 础 减少的总成本：罢。下文边际成本、边际效益分别简称为成本、 叫 效益。 平均成本是指分摊到每个单位收益的总成本：x c = 睾：净效益 7 p 7 1 7 1 疗为茧神嚣滴士荫虎太 丌r ：t r 一矿 当净效益t t b 最大时，则： a t t ba t ba t c 一 = = 0 0 a b8 ba b 9 第二章成本效益分折 即： 0 t b ；0 t c ( 2 2 ) a b强 式( 2 - 2 ) 表明当成本与效益相等时，规划净效益达到最大，此 时每增加单位成本，就会增加单位效益。 由图2 1 可以看出，当m c 小于m b 和a c 时，m b 和a c 均下降； 当m c 大于m b 和a c 时，m b 和a c 均上升。 图2 1 成本效益关系图 f i 9 2 一lc h a r to fc o s t b e n e f i ta n a l y s i s 证明：m b = 等 写成增量形式： m b ：a t b 一仰 d m b册l 抛昭 d ba b 2a bd a b 文献【3 2 】已证明了解= 等则式( 2 - 5 ) ： d m b17 龃bd 龋b 、 d b曲、曲d a b 。 1 0 ( 2 - 3 ) ( 2 4 ) ( 2 5 ) 一一 笙三童壁奎整垄坌堑 一 - _ _ _ - _ - _ _ - _ - _ _ - - _ _ _ _ _ _ _ _ 。_ - _ _ - - _ - _ - - = 击( _ 脚+ m c )。面+ 则：当枷 埘时，d 拈m b m b 时，d , t l l , x a e p ( 叻 鲥茜0 ，f = 1 ，z ，m l| l i = 0 ，扭1 2 ， 当p = 1 时，( 甲) 就是单目标规划。 在( v p ) 中，先求解品格单目标问题 m 蝉z ( x ) ，= 1 ，2 ，p ( 2 1 0 ) * ( 2 1 1 ) 设其最优值为f j 【x ) ，称厂+ = ( z + ，兀+ ) 7 为值域中的一个理想 点。因为一般很难达到，于是，在期望的某种度量下，寻求距离厂 最近的，作为近似值。一种最直接的方法是构造评价函数 厅一 p ( z ) = 、f 【z ( z ) 一，】2 ( 2 - 1 2 ) y ，= l 然后极小化舛厂( 工) 】，即求解 厅一 咖妒 m ) _ 、莓 ：( 垆删 ( 2 - 】3 ) 并将它的最优解x 作为( v p ) 在这种意义下的“最优解”。 采用理想点法，把本文建立的多目标输输电网络规划模型转变 为单目标问题时，便可使用单目标优化问题的求解方法求出最优解。 经过研究分析，本文选择采用遗传算法求解( 第三章介绍) 。9 1 7 第三章遗传算法原理及应用 第三章遗传算法原理及应用 3 1 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ) 【2 0 】是模拟自然界生物体进化过程 与机制求解极值问题的一类自组织、自适应人工智能技术。它模拟 达尔文的自然界进化论与孟代尔的遗传变异理论，是具有“生存+ 检 测”的迭代过程的搜索算法，具有坚实的生物学基础 它提供从智能 生产过程观点对生物智能的模拟，具有鲜明的认知学意义；它适应 于无表达或有表达的任何类型函数，具有可实现的计算行为：它能 解决任何类型实际问题，具有广泛的应用价值。 早在2 0 世纪5 0 年代，就有一些生物学家着手有计算机模拟生 物的遗传系统。2 0 世纪6 0 年代末，美国m i c h i g a n 大学的h o l l a n d 教授及其学生提出一种基本生物遗传和进化机制的适应于复杂系统 优化计算的自适应概率优化计算1 9 7 5 年，h o l l a n d 著书a d a p t a t i o n i nn a t u r ea n da r t i f i c i a ls y s t e m s ( 自然界和人工系统的适应性) ，阐 述了从设计人工适应系统中找到的这种基本自然演化原理的搜索机 制一一遗传算法。以一种群体中的所有个体为对象，并利用随机化 技术指导对一个被编码的参数空间进行高效搜索。h o l l a n d 建立了 s c h a m a 定理和隐含并行性原理，为遗传算法的发展奠定了基础，同 一时间内f o e g l 和s c h e m a 等人，研究了另外两种基于自然演化的算 法一进化规划( e v o l u t i o n a r yp r o g r a m m i n g ) 和进化策略( e v o l u t i o n s t r a t e g i e s ) ，分别简称e p 和e s 。这三种算法构成了目前进化算法 ( e v o l u t i o n a r yc o m p u t a t i o n ) 的三大分支。 d ej o n g 首先将遗传算法用于函数优化设计，他提出的在线和 离线指标是目前衡量遗传算法性能的主要指标作为新型的优化技 术，遗传算法在结构优化和参数优化，特别是具有非线性、多峰值、 不确定的复杂问题等领域特别有效。经过3 0 年的研究和应用，遗传 算法已经成为非线性优化和系统识别的一个有效工具，被广泛应用 于机器人系统、神经网络学习过程、模式识别。图形处理、工业优 1 8 第三章遗传算法原理及应用 化控制、自适应控制、遗传学、社会科学等方面，已解决n p 完全 性、规划控制等问题，取得了很好的效果，切今为止，遗传算法是进 化算法技术中应用最多、比较成熟并广为人知的算法。它在工程应 用领域取得成功应用，包括在作业调度和排序、可靠性设计、设备 布置和分配、交通问题等许多优化问题。 3 2 遗传算法( g a ) 的基本步骤 遗传算法是一种基于生物自然选择和基因遗传机制的随机搜索 算法，与传统搜索算法不同，遗传算法从一组随机参数称为“种群 ( p o p u l a t i o n ) ”的初始解开始搜索过程。种群中的每一个个体是问题 的一个解。称为“染色体( c h r o m o s o m e ) ”。染色体是一串符号，比如 一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。 在每一代中用“适应度( f i t n e s s ) ”来测量染色体的好坏，生成的下一代 染色体称为后代( o f f s p r i n g ) 。后代是由前一代染色体通过交叉 ( c r o s s o v e r ) 或者变异( m u t a t i o n ) 运算形成的。在新一代形成过程中， 根据适应的大小来选择部分后代，淘汰部分后代，从而保持种群大 小是一个常数。适应度高的染色体被选中的概率较高。这样经过若 干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解 或次优解。 遗传算法的主要步骤如下所述： ( 1 ) 编码 g a 在进行搜索之前先将解空间的解数据表示成遗传空间的基 因型串结构数据，这些串结构数据的不同组合便构成了不同的点。 根据变量要求的不同，可以采用不同形式的编码，如浮点编码、 二进制编码等。以二进制编码为例： 将变量采用一定长度的二进制字符串表示，对多个变量可以将 各变量的二进制连接在一起便可以形成码链即染色体或个体。 设任意待求变量，用足位二进制进行编码，五的上下限分别为 口，和岛，对应的二进制编码为搠，则毛和啦对应的关系为： k 一一 啊。，蕾= 盔+ 脚，= 【f = l 弗；t - 科二( 3 1 ) 1 9 第三章遗传算法原理及应用 这里我们应该注意到当变量的个数太多或者取值的范围太大时用二 进制编码会使的编码很长，从而影响到收敛速度。对于这种情况可 以先采用十进制编码进程搜索计算，当接近解时，缩小了解的空间， 再应用实数编码从而再空间上求精确解。 ( 2 ) 初始群体的形成 随机产生个个体，这个个体构成了一个群体。它代表了优