【毕业学位论文】（Word原稿）配电系统电压升级技术与效益研究-电机工程

1 圣约翰技术学院 甲种研究案成果报告 题目：配电系统电压升级技术与效益研究 位： 电机工程系 职级 ： 副教授 姓名：郭政谦 执行期间：自民国 92年 08月 01日起至民国 93年 07月 31日 中 华 民 国 九 十 三 年 七 月 一 日 2 目录 中文摘要 . 错误 !未定义书签。 英文摘要 . 错误 !未定义书签。 第一章 簡介 . 错误 !未定义书签。 1研究動機及目的 . 错误 !未定义书签。 1研究步驟 . 错误 !未定义书签。 第二章 多目標最佳化與遺傳演算法 . 错误 !未定义书签。 2加權均值式求解法 . 错误 !未定义书签。 2遺傳演算法 . 错误 !未定义书签。 2遺傳演算法基本工作原理 . 错误 !未定义书签。 2遺傳演算法的實例說明 . 错误 !未定义书签。 2遺傳演算法與其他方法比較 . 错误 !未定义书签。 第三章 配電系統電壓降之規劃 . 错误 !未定义书签。 3系統電壓降之問題描述 . 错误 !未定义书签。 3連結迴路連結線之位置選定 . 错误 !未定义书签。 3標函數 . 错误 !未定义书签。 3制條件 . 错误 !未定义书签。 3解過程 . 错误 !未定义书签。 3電容器組調度以改善電壓 降 . 错误 !未定义书签。 3標函數 . 错误 !未定义书签。 3制條件 . 错误 !未定义书签。 3解過程 . 错误 !未定义书签。 第四章 模擬結果分析 . 错误 !未定义书签。 4線連結型態之選定 . 错误 !未定义书签。 4線於不同連結架構之電壓降分析 . 错误 !未定义书签。 4容補償饋線於不同架構之電壓降分析 . 错误 !未定义书签。 4端雙連結迴路架構之電容補償特性比較 . 错误 !未定义书签。 4連結迴路架構之最佳連結位置選定 . 错误 !未定义书签。 4連結迴路架構之電壓調整改善 . 错误 !未定义书签。 第五章 結論 . 错误 !未定义书签。 參考文獻 . 错误 !未定义书签。 3 中文摘要 近年来配电系统的重要性随着负载密度持 续成长而渐受重视，用户所能得到的供电品质也取代以往的经济性考量，跃居为目前电业的主要考量，并促使配电自动化的脚步加快实现。在具备配电自动化系统后，其现有之配电系统型态及馈线连结架构，便能有重新评估及改变之可能。尤其对于目前已存在的高供电品质需求之用户，若能经由一连串绵密的分析、仔细的考量，并配合完整的规划下，更改其现行之配电馈线连结型态，改善目前因辐射状配电系统所造成先天不足之现象，将能使电业在未来的自由化之路，具备更高的竞争力。此外，虽然配电系统的供电品质可有许多的提升方法，然而经由改善系统之电压调整率应 是最根本的策略。基于此，本计划依序的探讨了配电系统电压调整之升级技术及效益，首先针对国内外实用之不同配电馈线连结型态，研究其对于电压分布之影响，探讨在不同结构下的效益，并于研究结果中提出双连结回路馈线型态，以改善传统上回路及网路架构之缺点。其次，根据所提出之双连结回路配电系统型态，针对双回路连结线于实际馈线上的位置选定，进行多目标最佳化的理论分析与研究，同时针对馈线于正常及故障状态下，使其电压分布之情形有最佳之状态。最后，运用并协调多种目前电业普遍使用中之电压改善技术，包括：有载分接头切换器，变电所并联电容 器组及馈线上之并联电容器组等，一起结合应用于所提出之双连结回路配电系统型态上，以多目标规划方式，将电压分布 、 虚功潮流 、 馈线损失 、 功因改善 、 有载分接头切换次数及电容器组切换次数等同时予以最佳化，并在系统电压及电流之限制条件下，提供一套完整的最佳化改善策略与运转控制。本计划可提供电业之系统规划及分析人员，评估配电系统在不同架构下的电压调整情况及改善策略，并提供适当之馈线系统结构与电压改善方法，以针对配电自动化系统，建立适当的配电系统型态与操作策略。 4 英文摘要 of to to of do in of in to in of be a to of be In of to of of in of of in of of in be to of we up of to of of it is an be 5 第一章 简介 1研究动机及目的 完整的电力系统 (含发电系统 (输电系统 (配电系统 (用户 (四大主要部分。在以往许多专家学者均不断致力于研究如何提升发电及输电系统之效率，其间也获致相当之成效。而反观配电系统方面，因所涵盖之范围广大，且所含括之资料亦相当广泛且复杂，欲将这些资料完整储存于电脑中以实行自动化架构，着实需要花费相当多之 记忆容量与计算时间，而其所获得之改善效果，可能远远不及所付出之代价；因此，过去所投入配电系统之研究相对较少。但近几年来，一方面由于生活水准提高、工商业持续发展，导致冷气负载及用电器具的成长，使得电力需求与日遽增，造成配电系统之负载密度持续攀升；另一方面在电脑技术、控制方式及通讯系统上也有长足的发展及进步；因而促使许多专家学者重新注意配电系统上之问题。 配电系统乃为整个电力系统的最末瑞，并与众多用户的负载直接接触，在电业自由化的竞争压力下，消费导向、顾客至上已成为必然的趋势。基于此，配电系统运作之良窳对于电业 而言已变得非常重要，因为不良的供电品质，将使用户感到不适而转向其他电业寻求服务，如此所造成的连锁效应，将导致电业蒙受重大损失；因此，在这时代中，配电系统的重要性，在整个电力公司的运作中，即显得特别突出。然而，由于用户多属低压用电之情况，故造成配电系统拥有线路长、元件多、且复杂度高的特性，这情况造成配电系统的不易管理与操作；据研究指出 1， 2，一般电力事业单位，约有占百分之五至百分之十三的总发电量，浪费在配电系统的线路损失上；配电系统之难以驾驭，由此可见一般；再加上配电系统的总投资成本大、重要性高，因此，如 何规划、运转配电系统，使其达到经济、安全、有效率且高品质等目标，实乃刻不容缓且 6 相当艰巨之工作。 在整个电力系统的运转规划问题方面，以往之研究重点一直置于系统调度中心的能源管理系统，此乃由于调度中心所掌控之范围，泛及全国庞大网路，就安全性而言，往往牵一发而动全身。再则，就经济性而言，往往些微的调度差异即导致巨额的成本变动。因此，发、输电系统的监控设备、信号网路及电脑设施，无不力求绵密而齐备，调度方式亦以自动化和即时为原则。相对的，由于区域性配电调度场站，数量需求较多，每个调度单位所辖控之范围多仅止于为数有限的 主变压器及馈线，而且网路皆为放射状架构。因此，配电系统若欲设置如输电系统般之精密监控与自动化操作设施，殊不经济也似无必要，一般多赖有经验的操作人员以人工方式为之。然而，近年来新电源的开发计画及系统之扩建工程屡受阻挠，缺电与限电危机愈来愈明显，再加上经济快速发展，用户对于系统供电品质之要求日益提高，配电系统如微血管般的遍及全国，并且深入各个乡镇；为达到充分利用现有设施之目标，舒缓扩建之压力，降低电力的损失，并提高供电品质，配电自动化 3是继发电能源管理系统后，电力事业另一个不得不全力以赴的目标。再者， 电脑软硬体、通信设施及监控设备，近年来皆有长足的进展，不但在价格上大幅降低，在功能上亦倍增于以往，如此使得配电自动化之可行性及经济性大幅增加，导致各方之研究，不论从理论到实际，亦日益充实。 分散型供电型态为目前发电技术主要的发展方向之一，对传统上的集中型发电系统而言，势必将产生若干影响。台湾于推动电业自由化之际，亦必须掌握此一发展趋势，予以留意。现阶段而言，传统的电力公用事业面临各种管制面、体制面、技术面以及经济面的挑战。在众多挑战之下，电业必须适时的改变其市场结构及经营型态；分散型供电系统的概念，并非要完 全取代集中发电式的供电型态，而是对于大型配电负载中心的特定尖峰用电需求，提供一种有效且符合经济的供电方式。尤其在愈都市化的地区，超高大楼不断增建，使得用电尖峰时段非常集中，反观配电及变电设施却因居民的抗争而无法相对的扩充，造成发电容量无法有效传送的区域限电问题。在台湾，这种现象已屡见不鲜，而且情况愈来愈明显。 7 为满足整体电力系统之需求，传统的集中式发电设备动辄数十万千瓦，因而忽略配电系统小型供电方式之可行性，而此种供电系统通常只需几千千瓦即可。此外，传统的供电规划方式往往忽略输配电成本大幅上升的趋势，同时也忽略了集中式供电方式可能导致部分偏远区域的供电边际成本急速攀升。因此，未来电业的规划将会愈来愈重视配电系统的相关资讯及配电自动化，包括：用户组成成份、负载需求特性、电力消费型态、需求面管理、区域限电事件分析、以及用户对不同供电品质的愿付价值 (to 这些都是过去电力公司所忽略的。 基于上述之分析可知，提供良好的供电品质，将成为目前电业所应积极推动之策略，以有效解决目前配电系统之困境。一旦配电自动化系统及分散式供电型态运转后，现行之配电系统型态及连结架构，便有重新评估之必要；因 为，如此一来对于电业而言，其所属之配电系统型态便不再是唯一且固定不变的。此外，对于部分目前已存在之特殊负载，若能在完整的规划、仔细的考量及绵密的分析下，更改其现行之配电馈线型态，改善因目前辐射状配电系统所产生之先天不足现象，则将使电业在为来自由化之后，拥有较高的竞争力。 配电系统常见的型态有辐射，环状，网路 . 等等。经由配电自动化的实施使得原本固定型态的系统，可配合需求做一些弹性的调整。目前相关研究文献都只限于探讨在同一个架构下的改善策略 10而我们乃是针对现今国内外较常用之一次配电系统，且台电目 前系统较易改接及新设之型态为主，找出较佳馈线结构，并考虑与电压调整策略配合应用，以提供系统规划及操作人员做参考，同时亦探讨不同的馈线结构型态之各种电压调整策略对电压调整的影响以及建议。经由文献的探讨和系统的模拟，我们可知由某一配电架构要做电压调整改善策略或是转变为另一种架构时，有那些评估的方式，策略的建议或馈线结构之间的好坏差别，各有的利弊得失，以充分提供可靠的资讯给予运转及维护人员参考，避免因人为的疏失导致民众及系统本身的损害。 目前台电配电系统之一次配电网路大部份采用放射型架构，除此之外，尚有部分采用放 射连络型架构，而于都会区之地下配电网路则采常开环路型系统。常开环路型系统在负载转供时会产生瞬间停电现象，无法符合今日高科技 8 用户对用电品质的要求。一般常见一次配电系统的四种型态其基本系统特性如下 : 一般而言，配电馈线从变电所一直到最末端用户之间的距离约有数公里之远，馈线电压会随着负载大小及线路阻抗而渐渐的下降，因此馈线末端的用户，将可能因压降太大，而无法有效率的运转其负载，并且造成负载寿命的减低；同时对于一些定功率输出的负载，由于输入电压的降低将使所需之电流增加，进而导致馈线更大的压降。如此反复的结果，甚至 会造成电压崩溃 (问题。因此，让整条馈线尽量维持在理想的电压下，不但对用户来说是一件非常重要的事，即使对于电力公司而言，亦代表着电力的供电品质，对一个自由化的电力市场而言，此项因素无疑的是同业间的一项竞争利器。 理想配电系统之馈线电压应保持定值，且不易受用户负载之大小与特性所影响。然而，实际配电系统中，存在许多非电阻性之元件及负载，造成系统电压电流相位之差异，产生虚功率之流动，因此，负载端的电压将随负载的需量不同而有所变动，降低了系统的供电品质。配电系统之电压调整 (其目的在调整用户进屋端电压于规定的容许变动范围内。用户进屋端电压视高压线、杆上变压器、低压线及接户线电压降及瞬时电压变动情形而异。配电系统合理的电压调整可谓相当复杂，如欲改善用户端电压，需先确立配电系统电压调整方式。一般电气机器均设计于运转电压较额定电压 (下变动不多使用时始可发挥其高度的性能。若运转电压愈离额定电压 (即名牌电压 )，则机器特性的影响愈大，其程度自应视机器种别而异。由电气机器立场而言，供给电压变动愈少愈佳。机器运转电压范围设计愈宽，不 但制造有困难，其价格、特性、效率等亦有难点。在某一限界点以上，另设电压调整器 (能较放宽机器电压变动范围为经济。另一方面由电力供给者立场，容许电压变动幅度愈窄，控制所需费用愈高。因此，容许电压变动幅度需符合要求，所需电力供给的设备及电气机器两者费用综合衡量后决定较妥，但事实上电力供给设备及用户电气机器其数量庞大，实无法允许急剧的改变， 大部份电气机器规定容许 5%之变动幅动，大部份机器均根据此规格制造，故供给电压容许变动幅度，以标 9 准电压的 5较合理。 配电系统电压调整改善之策略甚多，有些是在负载增加时，提高配电馈线之送电端电压，以有效减少馈线用户，于轻载与重载间的平均电压差，即可达到减少电压幅度之效果。有些策略则是利用降低馈线阻抗，以期减少线路电压降与电压幅度。此外，亦可加装功因改善设备，以减低负载电流，进而减少电压降与电压幅度。每种策略对于改善电压之程度，及所需之成本等皆有其独特之处，兹将配电系统用以改善电压调整之策略列于下： 1. 利用发电机调压控制器 ( 2. 装设配电变电所调压设备 ( 3. 平衡高压馈线负载 (on 4. 扩充导线容量 ( 5. 以多相式线路替代单相高压线 (to 6. 转移部份负载至新设配电馈线。 7. 提高配电馈线电压等级 ( 8. 装用高压馈线调 压器。 9. 装设并联电容器于高压配电馈线 ( 10. 装设串联电容器于高压配电馈线 ( 上述之电压改善方法，究竟采用何者最为妥当？其实并无一定的规则。而是需要针对系统大小、负载种类、既有设备位置，须调整之电压量、供电区域型态，及系统将来之扩充与负载增加率等因素，加以慎密研究探讨，并依据过去之经验而后方能决定。 配电系统型态之选择应考虑用户 (负载 )及电业 (台电公司 )之需求。虽然有如上述之各种不同配电系统型态，但仍希望以最小投资以得最适合系统为最后目标 ，系统之电压调整或幅度应达到何种程度，端视用户之负载性质及生产过程所需而定。有些用户对于电压变化有较大的容许程度，但有些则不行，例如 10 科学园区之用户，若系统产生过大之电压降，导致用户保护电驿跳脱，则在此短时间的停电过程中，将可能造成数亿元之亏损；基于此，适当且完整的考量用户之需求，审慎的评估配电系统所采行之型态架构，应是一个负责任的电业所应具备的条件。 配电系统供电品质的提升，应从电能的取得充足与稳定为基础，再考虑其安全性及电气特性影响因数的改善，而本整合型计画中各子计画以整合分工的方式，针对其影响因数加以探 讨，以获得较全面且详实的结果，将有助于配电系统整体供电品质与运转效率的提升。由于现在用户设备对电压变化更为敏感，电压的过高或过低更会影响设备寿命及性能，所以电压调整特性已成为电力品质优劣的重要因数，本子计画以探讨配电系统电压调整升级技术与效益，并加强子计画四虚功率补偿电压调整方式之不足，对其他电压调整方式作更完整的探讨与研究。 基于此，本计划依据在国内外所实用之不同配电系统型态与各种电压调整策略，完整的研究其对于各种电压调整之影响，探讨在不同的配电系统型态下的效益。完成后，将可提供电业一份完整且详细的参考资 料，以期能帮助系统规划及分析人员，有效的针对未来的配电自动化系统架构，及目前扩建或改建配电系统时，一份完整且适当的建议，以辅助电业于配电系统之规划与分析。 首先，本计画完成国内外相关研究报告及重要文献之搜集工作，并已取得台电实际配电系统之相关资料 (包括馈线资料、线路资料、负载电压调整系统资料等 )，及国内外各种不同配电系统型态之资料等。针对这些所取得之文献及资料，同时利用 套专业电力及配电分析软体，分别对于辐射状，回路状及网路状等配电型态进行正常及故障状态下的电压分析，研究结果发现，网 路状架构虽然可得到较佳的电压分布效果，但却须付出较多的型态变更成本，因此较适合对电压变动要求特别严格之区域，反之，回路状所须付出的型态变更成本较低，但在故障状态下，电压变动较大。基于此，本计画提出一折衷型态，即是将原本回路状在末端连结之外，再于馈线的中间部分取一适当处多出一条连结线，使馈线形成双连结之回路型态。此配电型态经过分析发现，无论在正常或故障状态下，整条馈线电压的分布较回路状佳， 11 并接近于网路状型态，且所须之成本只比回路状多一条连结线，但却比网路状少了许多。 其次，基于之前的研究结果，并着重于所提出之 双连结回路配电系统型态，针对连结线于馈线上的位置选定，进行最佳化的理论分析与研究，同时针对馈线于正常及故障状态下，使其电压分布之情形能有最佳之状态。因此本年度提出一最佳的连结位置之选定规划，使于先前计画中所提出之双连结回路配电系统型态，有最佳的电压调整效益。 最后，延续早先的研究结果，本计画以常用之电压改善技术同时结合在一起，其中包括：有载分接头切换器 (变电所并联电容器组及馈线上之并联电容器组等，应用于所提出之双连结回路配电系统型态上，以多目标规划方式，将电压分布，虚功潮流，及线路损失等同时最佳 化，并在系统电压及电流之限制条件下，提供一套完整的最佳化改善策略与运转控制。本计画将可提供系统运转人员一个完整之解决方案。 1研究步骤 本计划之所进行之研究步骤如下条列所示： 首先于馈线架构之选定上步骤如下： 1. 搜集国内及国外之相关研究报告、重要文献及参考资料。 2. 配电系统之资料搜集 (包括馈线资料、线路资料、负载资料、电压调整系统资料、台电相关之馈线历史记录 等 )。 3. 国内及国外之各种不同配电系统型态资料的建立。 4. 配电系统各种电压调整改善策略之分析与研究。 5. 配电系统负载潮流模拟程式之建立。 6. 配电系统电 压调整率模拟程式之建立。 7. 各种电压调整改善策略对不同配电系统型态电压调整影响之分析与研究。 8. 电压调整于各种电压调整改善策略对不同配电系统型态之优劣分析 12 与探讨。 9. 撰写年度报告 其次于双连结回路之最佳位置选定上步骤如下： 1. 搜集国内及国外之相关研究报告、重要文献及参考资料。 2. 配电系统之馈线资料搜集。 3. 配电系统最佳化理论分析与建立。 4. 多目标规划法之推导、分析及改善。 5. 目标函数之推导、分析与相关研究。 6. 配电系统不同馈线结构之分析与研究。 7. 双连结回路系统之馈线结构最佳化程式建立。 8. 双连结回路系统馈线结构对电压调整影 响之分析与研究。 9. 双连结回路系统馈线结构与其他馈线结构型态之优劣分析与探讨。 10. 根据台电的实际馈线资料，进行程式模拟及实例分析。 11. 撰写年度报告。 最后于电压改善之最佳化 1. 搜集国内及国外之相关研究报告、重要文献及参考资料。 2. 台电配电系统之馈线资料搜集 (包括变电所并联电容器组资料、主变压器 路资料、负载资料、馈线上之切换式并联电容器组资料，电压调整系统资料、台电相关之馈线历史记录 等 )。 3. 台电于主变压器 4. 台电于变电所及馈线上之并联电 容器的设定策略分析及研究。 5. 双连结回路系统之多目标最佳化理论分析与建立。 6. 双连结回路系统馈线结构与电压调整改善策略并用之分析与研究。 7. 目标函数之推导、分析与相关研究。 13 8. 配电系统多目标最佳化程式之建立。 9. 根据台电的实际馈线资料，进行程式模拟及实例分析。 10. 撰写年度报告。 14 第二章 多目标最佳化与遗传演算法 2加权均值式求解法 在多目标规划的问题中，有些目标函数之间并无明显的绝对关系，即是在求解的过程当中，若某一函数值变好时并不一定表示另外的函数值会变好或变坏；有鉴于此，本节提出另一个多目标求解法， 其目的也是希望能找出一个解，让问题中所有的目标函数均能同时达到最佳的情况，但是由于解只能有一个，而目标函数却可能有很多项，因此决策者必须依据所需，在所有的目标函数之间作一些取舍。 如前所述，对于多目标规划的问题大多以乘上加权值的方式来求解，如下所示： T W O W O W On n 1 1 2 2 . . . . . . . (2利用上式即可将整个多目标函数变成单目标规划的问题，如此一来虽然可以很容易的求解，但是目标函数之间的单位并不相同，彼此之间也很难有对映的转换关系。因此，如何决定权重值 W ，以代表决策者对于目标函数之间的轻重关系，就变得非常困难，甚至于根本无法完成。基于此，本节将提出新的加权均值式求解法，使得使用者在求解的过程中，不需要考虑目标函数间的单位差异关系，即可顺利解决此多目标规划问题，求解出最佳的解决方案，以满足使用者的要求。 加权均值式求解法系由两个步骤所组成，详述如下。 【步骤一】 先对单一目标函数 遗传演算法进行最佳化求解，而不考虑其余目标 15 函数的影响，如下所示： 最小化 并满足 所 有限制条件 (2假设所求得之解为 则所有目标函数在 构下所得之值如下所示： O S O i d e a 2111(.() =) ) 如果遗传演算法所求得之解为全域最佳解，那么上式中的 定是目标函数 最佳值，而 为目标函数 最佳解。换言之，无论将来是否一 起考虑其余目标函数，都绝对无法再找到更佳的解，因此上式中以下标 同理，再对目标函数 行单一目标函数的最佳化求解，如下所示： 最小化 并满足 所有限制条件 (2假设所求得之解为 则所有目标函数在 构下所得之值如下所示： 16 O i d e a 222(.() ) = ) 如前所述，上式中的 目标函数 最佳值，亦即为最理想之值。接下来，继续的重复此一过程，对其余的目标函数分别求出在单一目标要求下，求得之最佳解。 由上述的过程中，可以得到每一个目标函数的最佳值，亦即为最理想值，分别为， . 和 同时再根据上述的结果，并利用下面的式子来求得非理想 (。 O O S O S O Sn o n i d e a l 1 12 3 m a x ( ( ( ( ), ), . . . . . . . , ) O O S O S O Sn o n i d e a l 2 21 3 m a x ( ( ( ( ), ), . . . . . . . , ) . . O O S O S O Sn n O n O n On o n i d e a l n m a x ( ( ( ( )1 2 1), ), . . . . . . . , ) (2【步骤二】 根据步骤一的结果可以发现， . 和 为理论上的最佳解答，但实际上可能无法找到一个解答 S ，同时使得所有的目标函数 均为理想值。同理， O . 和 则是理论上的较差解；基于此，我们分别将所有的 视为最佳化的方向，并且把 视为最佳化过程中的底部，找出一个相对接近所有的 的解来当成最佳解，如下所示： 17 最小化 T W O ii ii i d e a ln o n i d e a l i d e a l 1并满足 所有限制条件 (2其中 W 1100% 由上面的式子可以发现， 其最佳化的函数式已经不是原来的目标函数，而是类似经过均值化 (结果，如此一来，当要决定加权值 ，只需要根据决策者对于各个目标函数的重视程度，适当的对每一个目标函数的加权值予以分配即可，对于目标函数之间单位不同的问题，则完全不需要加以考虑。 图 2 開始以 遺 傳 演 算 法 求 ( 2 式 並 找 出 最 佳 解結束以 遺 傳 演 算 法 求 出O O Oi d e a l i d e a l i d e a , . . . ,根據 ( 2 - 1 2)式 找 出O O On o n i d e a l n o n i d e a l n o n i d e a , , . . . ,使 用 者 根 據 需 求決定加權項 加权均值式求解法之流程图 18 2遗传演算法 遗传演算法的基本概念是在 1970年 代由密西根大学的 授首先提出。当时 授以及他的学生希望发展一种人工系统(能够详细的描述自然界进化的适应性过程，并期望此系统至少可以模拟一些自然进化时所需的重要机制。基于此研究目标下发展出了遗传演算法的雏形。 到了 1980年代，当年 授成功的将遗传演算法应用于管线运输 (控制，并以此论文获得了 1985年的青年研究学者总统 奖 (1985 使得遗传演算法的潜力受到学术界的重视；之后， 续发表了许多论文及专书，建立了遗传演算法的数学基础。至此，学者们便不再怀疑遗传演算法的收敛性问题，而开始大量的将遗传演算法应用到各种有关控制及最佳化的工程领域上。而到了 1980年代后期，更有每年定期开会的遗传演算法的国际研讨会。 基本上，遗传演算法是一种基于模拟自然界 优胜劣败、适者生存 的搜寻法则，虽然属于一种随机搜寻模式，但它并不是 盲目的去搜寻解答。藉由模拟达尔文进化论 ( 最适者生存 的自然法则，遗传演算法能有效率的搜寻复杂问题的最佳解。也因为遗传演算法是使用随机搜寻模式而非斜率搜寻模式，经由基因交换及突变等运算子 (操作，遗传演算法不会像一般搜寻法一样，会有陷于局部最佳解无法跳出的情况产生。此外，由于遗传演算法对于求解问题上的限制很少，在求解前所需的已知条件也很少，因此遗传演算法被认为是一种强健的搜寻法则，其基本流程图如图 2 19 開始初 始 化 : 產 生 第 一 代 族 群計 算 族 群 中 各 個 染 色體 的 適 合 度 函 數 值選 出 較 佳 的 染 色體 以 進 行 配 對進 行 基 因 配 對 及 突變 以 產 生 子 代計 算 子 代 中 各 個 染 色體 的 適 合 度 函 數 值將 子 代 中 適 合 度 值 較 佳 之 染色 體 保 留 並 去 除 父 代 中 具 較差 適 合 度 值 的 染 色 體是 否 收 斂 ?結束否是图 2遗传演算法的基本流程图 2遗传演算法基本工作原理 遗传演算法系利用人工染色体来描述问题，人工染色体通常由许多二进制的基因所组成，图 2色体中的基因必须与问题的目标函数具有相当程度的关联，当二者之间的关联性愈强时则求解的效率愈高。而每个染色体之后都联结一适合度值 (辨别该染色体的优劣，适合度函数应细心的设计以使族群中优良的染色体能被凸显出来。然后，问题的求解就在适合度函数的进化过程中进行。遗传演算法的三个基 本运算子为：染色体复制、基因交换、及基因突变。这三个运算子的工作原理将在下面小节中详述。 20 1 0 1 1 . 0 合度值 图 2典型人工染色体之结构 2染色体复制 由父代族群 (衍出子代族群 (第一个步骤是染色体复制。染色体复制的主要工作是选择父代族群中优良的染色体来演化出下一代。这里所谓的 优良染色体 指的便是适合度值较佳的染色体，也就是目标函数值较好的染色 体。在本论文中，我们采用 轮盘式父代选择法 (选择优良的父母以演化出下一代染色体，它包含了三个主要步骤，如下所述： 1. 将族群中全部的染色体之适合度值相加，得到一个算术和，称之为 2. 随机的产生一个介于 0到 。 3. 从族群中的第一个染色体开始，当它的适合度值与之前所有染色体的适合度值相加后之值，大于或等于 染色体便获选参加配对。 但是在执行这三个步骤之前，必须先算出所有染色体的适合度值，再将 族群中的染色体依适合度值的大小，由高至低顺序的做好排序。如此一来，对于适合度值愈高的染色体，在轮盘上所占的面积就愈大，被选中的机会自然很高，反之，适合度值较低者，在轮盘上所占面积则较小，能参予配对的机会自然就不多了。此方法完全依照适合度值的优劣给予不同的配对机率，正好符合自然界 优胜劣败 的自然选择精神。 2基因交换 基因交换是整个遗传演算法中最重要的一个运算子，它是藉由将二个父代染色体中的基因做交换或重新排列组合以产生二个新的子代。这项操作就好像 21 二位科学家彼此交换研究资料一样。新产生的 子代染色体往往因为同时拥有二个父代染色体中的优秀基因而使得它的适合度值比其父代染色体还要高。 在本论文中，采用了一种新的基因交换技术称为 制式交换法 (制式交换法会产生一个和父代染色体结构相同的二进制覆罩(覆罩内是利用随机乱数所产生的二进制值，然后二个父代染色体便依照此覆罩上的二进制值来做基因交换，以产生子代，再覆罩中 1代表基因交换， 0则代表不交换，如图 2 父亲 : 母亲 : 随机覆罩 : 0 1 0 1 1 0 0 子女 A : 子女 B : 图 2染色体之制式交换法 明了制式交换法的收敛速度的确优于传统的单点交换法(双点交换法 (基于此，本论文采用此制式交换法，作为基因交换的方式。 2基因突变 自然界的演进除了依靠优胜劣败的进化理论之外，还有一项重要的因 素就是突变。突变隐含了一些往较好的方向瞬间变化的机会，而在遗传演算法的进化过程中，虽然只靠染色体复制和基因交换即可搜寻求解，但是有时太相近的父代染色体所演化出的下一代，将会因为与父代相似而使搜寻点在求解空间上被局限于某一范围，如此一来光靠基因交换将使问题的求解陷在某一点而无法跳出。利用基因突变便能有效的克服此一弱点。基因突变是指在人工染色体中的某一个随机位置，其基因值发生突然的变化，如图 2变显然能提 22 供染色体一个突然进化的机会，但另一方面，突变也可能让染色体往较坏的方向变化，根据实验结果显示经常性 的突变并不能加快求解的收敛速度，因此突变的机率通常都不会定的太高，以兼顾求解的品质及收敛的速度。 父代 : * 子代 : 图 2染色体之突变 2遗传演算法的实例说明 在本节中将以一个简单的最佳化实例，来示范如何进行遗传演算法的求解。 【实例】 考虑一个简单的最佳化问题如下： f ( )x x 2 ，试求使函数 f(x) 有最大值之 x 。 各类参数值如下： o 染色体字串的位元数： 5o 族群大小 ( 4 o 基因交换机率 ( 1.0 o 突变机率 ( 0 染色体字串的编码方式如下所示： 23 b4 b3 b2 b1 24 23 22 21 20 x b i ( )204 b 0 , 1 i 因为染色体的字串长度为 5先利用随机投掷五个硬币来产生初始族群，其中正面代表 1，反面代表 0。由于族群大小为 4，这项工作要重复进行四次。所产生的四个染色体字串及其对应的各种函数值如表 2 接着便可依照这四个染色体字串的适合度值来建立一个轮盘，如图 2后利用 轮盘式父代选择法 从轮盘中选出参加配对的父母染色体，最后以 单点交换法 对已配对的父母染色体做基因交换。此配对及基因交换的结果如表 2示。从表 2表 2结果可看出，在初始族群中 f(x)的总和、平均值及最佳值分别为 1170、 293 及 576，但到了第二代族群中， f(x)的这些相对应值便已进化到 1754、 439及 729。由这个现象可以体会 到遗传演算法的进化 (求解 )过程，的确能够产生出较良好的子代。 表 2初始族群 染色体 字串 初始 族群 x f(x) f (%) fi/f 配对 次数 (1) 01101 13 169 (2) 11000 24 576 (3) 01000 8 64 (4) 10011 19 361 总和 ( f) 1170 均 (f) 293 大值 576 24 ( 4 )3 1 %( 2 )4 9 %( 1 )1 4 %( 3 )6%图 2利用适合度值来建立一个轮盘 表 2染色体复制及基因交换 轮盘法 配对 染色体 复制 交换