基于智能优化算法的配电网络规划与优化运行研究

《基于智能优化算法的配电网络规划与优化运行研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

中文摘要随着国民经济的迅速发展和人们生活水平的日益提高，用户对供电的可靠性和电能质量提出了更高的要求。如何通过配电网络的优化配置和优化运行，在保证配电网络安全性和可靠性的前提下，尽最大可能发挥当前配电网络的潜力，以及从长远的、整体的角度出发，科学合理地规划我国配电网络，是当前电力规划和运行人员急需解决的问题。配电网规划和优化运行的复杂性主要表现在规模大、不确定、因素多和NP难的特点，仅仅依靠规划和运行人员的经验已经远远不能满足现代配电网络的要求。本文掌握了配电网络规划和优化运行的研究现状，深入分析了近年来新兴的几种智能优化方法的搜索效率和收敛特性，提出了几种混合智能优化算法用以弥补各种单一优化算法的不足，并用以解决配电网络规划中的变电站选址定容、配电网架联络线总体规划以及配电网络运行方面的网络重构和无功优化等问题，在很大程度上提高了配电规划和运行人员的工作效率。概括起来，本文的工作包括以下几个部分：1．提出了具有变异特性的粒子群优化算法(AMPSO)。此方法中，为了克服粒子群优化算法(PSO)的早熟现象，以种群的适应度方差大小衡量粒子群体的“聚集”情况，受遗传算法思想的启发，对发生“聚集”的粒子赋予变异操作。通过几个典型的函数优化问题，验证了AMPSO较强的全局寻优能力，并用此方法对配电网络变电站选址定容问题进行了计算，计算结果合理，可行。此外，在配电网络变电站选址定容的计算模型中，不仅考虑了地理信息对建站投资费用的影响，在选址过程中尽量避开湖泊、建筑物等一些不可行建站区域；而且考虑了线路投资和网络运行费用对站址选择的影响。在模型上体现了变电站选址定容是地理信息和电气信息两者共同作用的结果，其计算结果能够给配电网络规划人员提供强有力的支持。2．运用蚁群算法，以变电站间的距离、变电站富裕容量以及路径上的信息素为启发因素，用来解决在一定负荷密度和配电变电站间负荷转带比例下，考虑不同接线模式时的站间联络线优化问题，同时还以边际供电总成本最小为目标函数，运用快速高效的粒子群优化算法来解决变电站负荷转带比例这一平衡配电网络经济性和可靠性的优化问题，结合蚁群算法对站间联络线的优化，最终形成配电网络变电站总体联络规划方案。3．分别提出改进的禁忌搜索算法(RTS)和混合粒子群遗传算法(HGAPSO) 解决配电网络重构静态及多时段动态重构问题。混合粒子群遗传算法综合了遗传算法和粒子群算法的优点，弥补了遗传算法计算时间过长及粒子群算法易陷入局部最优的不足，其在计算速度和收敛性能上比任一单一算法都有很大的提高。禁忌搜索本身是一种局部搜索能力很强的优化算法，但是，如何寻找到问题的最优解一直是众多学者关注的问题。根据配电网络的具体特点，采用高效的遗传编码策略，并分析了禁忌搜索的收敛条件，从而在理论上证明此种方法在解决配电网络重构问题时能够找到全局最优解的必然性。通过对IEEE三个经典测试用例的计算和结果分析验证了上述两种算法的正确性。4．分别提出混沌优化算法(COA)和具有混沌特性的粒子群优化算法(CPSO)解决配电系统无功优化问题。混沌优化算法用类似载波的方法将混沌变量引入到优化变量中，利用混沌运动的遍历性和貌似随机性的特点直接对目标函数寻优，在摆脱局部最优上有很好的性能，并且理论上是一个可以找到全局最优解的算法。粒子群优化方法(PSO)计算速度快，可以很好地处理大规模混合整数规划问题，但是存在容易陷入局部最优问题。混沌粒子群优化方法(CPSO)结合混沌优化中混沌变量良好的遍历特性以及粒子群体搜索的快速性等特点，对即将重合而引起搜索能力下降的粒子赋予混沌状态搜索，有效的提高了算法的全局寻优能力，同时又保留了PSO方法计算速度快的特点。通过对IEEE两个配电网络测试用例验证了CPSO方法的性能。关键词：配电网络规划变电站选址定容配电网络重构遗传算法禁忌搜索粒子群算法蚁群算法混沌优化II ABSTRACTWiththerapiddevelopmentofnationaleconomyandtheimprovementofpeople’Stivingconditions，reliabilityandpowerqualityplayamoreimportantroleinpowersupplyindistributionsystem．Howtopromotecurrentpowerdistributionnetworkspotentialitybyconfigurationoptimizationandoptimaloperationwhileguaranteeingitssecurityandreliabilityandhowtopursuescientificandlongtermdistributionnetworkplanning(DNP)areurgentproblemsfordistributionpowerplannersandoperators．ThecomplexityofDNPanddistributionnetworkoptimaloperation(DN00)liesinitslarge—scale，uncertain，multi-factorandNPhardcharacteristics．Mereexperienceofplannersandoperatorscannotmeettherequirementsofmodemdistributionnetworks．Inthispaper,currentresearchofDNPandDNOOiSintroduced；thesearchefficiencyandconvergencepropertyofseveralemergingintelligentoptimizationmethodsareanalyzedandseveralhybridintelligentoptimizationalgorithmsarcputforwardtocompensatethedeficiencyofsingleoptimizationalgorithms．Moreover,thoseproposedalgorithmsareemployedtosolvesuchproblems嬲thesubstationlocatingandsizing(SLS)andgeneraltie-lineplanning(GTP)，aswellasdistributionnetworkconfiguration(DNC)andreactivepoweroptimization(RPO)innetworkoperation．Thesealgorithmscansignificantlyimproveworkefficiencyofplannersandoperators．Insum．theworkinthispaperisasfollows：1．111ealgorithmofAdaptiveMutationParticleSwarmOptimization(AMPSO、ispresentedtoovercometheprematurityofParticleSwarmOptimization(PSO)．AccordingtoGeneticAlgorithm(GA)'AMPSOobservesthe“clustering”ofparticleswarmsbythepopulationfitness’Svarianceandconductsmutationoperationonclusteringparticles．AMPSOindicatesitsglobaloptimizationsearchingabilitybyseveralclassicmathematicfunctionoptimizationproblems．ThemethodisusedtodealwithSLSproblemsinDNPandtheresultsdemonstrateitsfeasibilityandreasonableness．Besides，intheSLSmodel，notonlytheinfluenceofgeographicinformationonsubstationconstructioncostsisconsideredtoavoidunacceptableareassuchaslakesandbuildings；butalsotheeffectofsubstationequipmentscostsistakenintoaccount。Themodelincorporatesgeographicandelectricinformation，andSLSresultsareveryhelpfulfordistributionnetworkplanners．111 _____-___●—●—_————_————————一—————————_-____-●______●—————————●—————————____-●_-●——————————————一2．AntColonyOptimization(ACO)isemployedtosolvetheoptimizationoftie．1inesbetweensubstationsindifferentconnectionmodesundercertainloaddensityandloadtransferratioofsubstations．witllsuchheuristicfactorsasdistancesbetweensubstations，surpluscapacityandinformationalongtheroutes．Atthesalnetime，fastandeffmientPSOisusedtotackleloadtransferratioofsubstations，anoptimizationproblemtobalancetheeconomicalefficiencyandreliability,、Ⅳitlltheminimummarginalpowersupplycostastheobjectivefuncdon．Along、Ⅳiththetie‘lineplanningwithACO，thegeneralplanningresultofsubstationsinpowerdistributionnetworkisfinallyformed．3．RefinedTabuSearch(RTS)andHybridGAandPSO(HGAPSO)areproposedrespectivelytosolvepowerdistributionnetworkreconfigurationandtimelydynamicreeonfiguration．HGAPSOincorporatesthemeritsofGAandPSO，whichcompensatesGA'stimeconsumingandPSO’Slocaloptimumproblems．Thusitssearchingspeedandconvergencepropertyareimprovedgreatlycomparedwi廿leithersinglealgorithm．TabuSearchitselfhaSstronglocalsearchingability；however,howtofindtheoptimumsolutionalwaysappealstoresearchers’attention．Accordingtothespecificcharacteristicsofpowerdistributionnetwork，convergenceconditionsofTabuSearchareanalyzedandefficientgeneticcodingstrategyisemployedtoveilfytheoretitallythatthemethodCaD_certainlyfmdtheglobaloptimumsolutioninDNC．TheabovetWOmethodsareprovedtobecorrectandeffectivebyresultsanalysisonthreetypicalIEEEtestingexamples．4．ChaoticOptimizationAlgorithm(COA)andChaoticParticleSwarmOptimization(CPSO)areaddressedrespectivelytosolvereactivepoweroptimization．Inconsiderationoftheergodicityandrandomnessofthechaoticsystem，theoptimalsolutionisfiguredoutdirectlybytransformingthechaoticvariablesintooptimizingvariablesinCOAandtheproposedmethodshowsgoodperformancetoavoidlocaloptimum．PSOisgoodatdealingwithlarge-scaleintegerprogrammingproblems，whileitisapttofallintolocaloptimunl．OverlappingparticleswhichgraduallylosetheirsearchingabilityinPSOaleimposedondistinctergodicityinCOA，therefore，thepresentedCPSOalgorithmcombinestheergodicityinCOAandtherapidityofPSOinoptimafinding．CPSOistestedbytwoIEEEdistributionnetworkexamplesandtheresultsdemonstrateitshighefficiencyandpromisingpracticalapplications．KEYWORDS：distributionnetworkplanning，sub．ionlocatingandsizing， distributionreconfiguration，geneticalgorithm，tabusearch，particleswarmsoptimization，arltcolonyoptimization，chaoticoptimizationalgorithmV 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得墨盔盘茔或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。学位论文作者签名：蓟1虱皮签字日期：2矿砂年∥月／夕日学位论文版权使用授权书本学位论文作者完全了解鑫鲞盘堂有关保留、使用学位论文的规定。特授权盘鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向哥家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：妄1同皮签字日期：腑年石月，7日聊魏白童磊签字日期：z口盼年彳月夕日 天津大学博士学位论文第一章绪论1．1引言1．1．1我国配电网络现状第一章绪论电力系统是由发电、变电、输电、供电、配电和用电等设备和技术组成的一个将一次能源转换为电能的统一系统。配电系统是电力系统到用户的最后一环，它与用户的关系最为紧密，对用户供电可靠性和供电质量的影响也最为直接。配电系统通常包括配电变电站、一次配电线路(馈电线路)、配电变压器、二次配电线路、继电保护设施等，是连接发、输电系统与用户的重要环节。配电网络按电压等级来分类，可分为高压配电网(35～1lOkV)、中压配电网(6～lOkV)、和低压配电网(220～380V)；按供电区域的功能来分类，可分为城市配电网、农村配电网和工厂配电网等lIJ。早期我国的配电网络电压等级零乱而复杂。在50～60年代，随着我国配电网络的发展，低压和中压的电压等级逐步统一改造为220／380V及6～lOkV。又由于城市负荷密度的提高和大型电力用户的出现，现代配电网的最高电压等级已经发展到35～1IOkV，有的负荷密度很高的大城市甚至采用220kV作为配电网络电压等级¨J。我国与世界其它发达国家相比，配电网发展起步较晚，发展水平较低，建设相对落后，而且发电、输电、配电发展不够协调。发达国家都是电网(包括输电和配电)投资大于电源投资。而且配电网络投资又大于输电网络投资；我国则刚好相反，电网投资不到电源投资的一半，并且配电网络的投资又小于输电网络的投资。“。发电：输电：配电的投资比例显示，2000年为l：1．3：3．3，到2002年发展为1：1．45：3．7，发电和配电能力之比：2000年为1：1．45，到2002年为l：1．67。而据考察只本达到l：1：4．2，投资不足只有牺牲系统的裕度和可靠性。这种长期沿袭下来的“重发，轻供，不管用”思想，无论从资金、设备还是在技术上严重制约了配电网络的建设和发展。1994年夏天全国城市配电网普遍出现过载现象，特别是中低压配电网更为严重，“送不进、落不下、用不上”的矛盾充分暴露出来I”。80年代以来，许多大城市电网运行人员意识到我国配电网络存在的问题， 大津火学博十学位论文第一章绪论并积极致力于配电网络科学规划、优化运行与改造工作。近年来，配电网络建设、运行和改造引起了各级领导的高度重视，现已投入大量的资金分期、分批进行。各个地区也纷纷对现有的配电网络状况进行分析，根据需要和可能进行改造，来提高供电的可靠性和电能质量。1．1．2我国配电网络存在的问题目前，虽然我国配电网络得到了一定的发展，但是远远没有满足用户对供电的可靠性和电能质量的要求，总体发展水平比较落后。普遍存在设备陈旧老化、负荷过重、线路过载、事故率高、可靠性差等问题，主要原因归结为以下几点：1．配电网络建设落后长期以来，我国配电系统的建设并没有得到足够的重视，发电、输电、配电发展不够协调，原有的城市配电网络，特别是城市的中压配电网络，由于长期投资不足．设各陈旧老化，电网结构不合理，存在有电送不进、用不上的供电“瓶颈”现象。2．配电网负荷增长迅猛20世纪90年代以来，随着改革开放的进一步深入，第三产业迅速发展，城乡用电量增长迅猛，我国一些城市尤其是大中城市的中心商业区或者经济开发区的负荷密度急剧增加，1986～1993年全国用电负荷平均年增长率为9．2％，而其中居民生活和第三产业用电平均增长18％，不少城市平均年增长率在15％以上。这样就产生了线路走廊紧张，变电站布点困难等诸多问题，现有配电技术难以保证向用户供电的能力和质量，给城市电网带来了很大的压力，相当多的设备因为过负荷而发生故障，许多大中城市都有难以应付之感。3．配电网络技术经济指标落后、设备陈旧虽然我国配电网在规模上可以与国外发达国家相当，但是技术经济水平却还相对落后．线损率、可靠率、电缆化率等一些重要技术指标与国外水平还有很大差距，具体数据如表1-l所示。目前我国配电网络设备普遍陈旧甚至落后，小截面老旧线路、老式油断路器、老式柱上断路器等仍然大量在线工作。此外，现有的配电网络结构普遍比较薄弱，备用切换能力差，达不到“^卜1”的安全准则，供电可靠性差，事故停电频繁。2 天津人学博十学何论文第一章绪论表1-1国内外配电技术指标比较指标国外国内『居民生活用Ele：leL侈!J(％)约30约10大城市电缆化率(％)约100约10供电可靠性(％)99．9999．9线损率(％)约5约10负荷增长率(％)约2％>8设备投运年限(年)约20年约10年人均年用电量(kWh／人)600010004．配电网损率居高不下我国配电网线损率1995年达8．77％，1997年为8．20％，而日本、德国、法国等其线损率约为5．6％。按大致相同口径对比，可以发现造成这种差距的一个主要原因是城市配电网损耗大，大约高出2～3个百分点，按1997年水平，相当于多损耗180亿kwh的电量，按O．5元一度电计算，一年就可节约90亿元，如此巨大的电能损失，给我国社会、经济、环境造成的影响是相当大的。5．配电网络规划和设计不科学以往，我国配电网络的规划和设计主要依靠规划和设计人员个人的知识、经验等，对各种规划方案仅限于定性分析，不仅工作量大，而且还容易出现问题，对于规模同益扩大的配电网络，这种规划方法将越来越难以适应配电网络的科学建设和经济运行。我国和其它发达国家的城市电网规划成果的比较如表1．2：表1．2城市电网规划成果的比较内容国内国外发达国家规划模式不统一统一规划资料少，历史短，缺多、系统、有参考价值，计算机化高新建、改造区分一般不区分，改造较多尽量避免，在寿命周期内不改造评价指标少多以定性为主，从总量上控制，总负荷仅与总投每个设备投资与可能的供电负荷相工程与投资资相关，工程与各电压关，真正做到了量化。等级的负荷不够紧密。各级规定自己的规划有确定的规划报告模式规划报告报告，没有统一的模式 大津大学博十学位论文第一章绪论1-1．3配电网络规划和优化运行的意义配电网络的合理规划和优化运行可以提高配电网络的供电能力和可靠性，降低配电网络损耗，另一方面也可以节约国家基础建设投资，使有限的投资发挥最大的经济和社会效益，其意义主要体现在以下几个方面：11科学的变电站规划有利于系统的运行管理，减少系统跨区域交叉供电，提高系统管理和运行效率；2)科学的配电网规划和优化运行，可以降低系统的网络损耗，提高系统的供电可靠性，极大提高电网的运行效益：3)科学的城网规划和优化运行是提高系统投资效益的最有效途径；4)科学的配电网络规划和优化运行是配电自动化规划和实施的基础；5)配电网络规划和优化运行是电力企业战略发展规划的重要组成部分；6)国外专家认为，科学规划的效益是总投资额的5％左右。经济效益十分巨大；7)配电网络优化运行水平的高低，是配电自动化水平的综合体现，配电网络优化运行是配电自动化的重要内容。1．2本课题研究的概况1．2．4配电网络规划和优化运行的内容和特点1．配电网络规划和运行的内容配电网络规划包括以下几个部分：1)空间负荷及其分布预测；2)各级电压变电站的位置、容量以及供电范围的确定31各级电压网络规划：4)各级电压无功电源的配置；5)配电自动化规划；6)配电网络无功电压控制；7)配电网络重构；4 天津大学博士学位论文第一章绪论81故障恢复。2．配电网络规划的特点1)不确定因素较多：配电网络规划受国家政策调整、社会经济发展、人1：3变动及环境变化等因素的影响，电力系统的发展条件也在不断变化，规划期越长，条件、参数也就越难确定。2)涉及的部门较多：配电网络规划涉及到电力公司、城市规划、城市环保等各个部门。3)规模庞大，计算复杂：即使对一个小区的配电网络进行规划，也要有十几到几十座变电站、几百条中压线路和开关。从数学上讲，配电网规划是一个动态多目标不确定性非线性的大规模整数规划问题，一般的数学优化算法对于此类问题没有很好的解决办法。1．2．5优化算法在配电网络规划和优化运行应用综述配电网络规划要考虑城市土地价格、城市建设布局、环境保护等问题，而配电网络的优化运行则需要考虑当前开关状态、负荷水平、可调变压器分接头位置、电容器组投切状态等情况，都属于系统优化问题；从数学上看，配电网络规划和优化运行都属于复杂的多目标、多约束、非线性、非连续、混合整数规划问题。如何寻找～个有效的优化方法解决上述NP难的组台优化问题，受到了电力科学工作者的极大关注，并对此进行了广泛的研究。配电网络规划和优化运行的求解方法大致上可以分为经典的数学优化方法、启发式优化方法和智能优化算法【5】。1．经典的数学优化方法由于需要解决问题自身的非线性．所以非线性规划法(NonlinearProgramming)最先被应用配电网络规划和优化运行中。Fawzieta1．首先采用非线性规划方法规划了一个城市的郊区电网，指出非线性规划方法可以提高当前规划的质量I61。一年后．他又提出了一静态优化模型试图规划一个新建区的配电网络或对原有配电网络进行扩展规划。1981年Wall和Tram提出采用分支定界一运输模型来解决配电网络规划问题，并取得了一定的成果，他认为此方法要比线性规划算法的效率高得多【7J。在优化运行方面，最早且较有影响的优化运行算法是由H．w．Dommel和W．ETirmey在1968年提出的，他们用一种简化梯度法解决有功和无功最优潮流问题。并对后来的研究产生了很大的影响[81。1988年，CivanlarS和GraingerJJ率先用非线性规划方法对配电网络电容器优化问题进行了研究，并于1989年提出标准化等效馈线的概念，解决了较复杂配电网络的无5 天津火学博士学伉论文第一章绪论功电压控制问题【9】o在CivanlarS研究的基础上，M．Baran和F．F．wu考虑了电压约束的影响，建立了更接近实际情况的数学模型，同时将电容器问题分解成主从两级问题考虑分别确定电容器的数量、安装位置以及类型和大小【luJ。相对于无功优化问题，配电网络重构问题提出的要稍微晚一些。配电网络重构技术最早是由Merlin和Back于1975年提出来的，并将配电网络重构问题表达成一个非线性规划问题，然后用分枝定界法进行求解⋯l。文献[12]贝JJ在此基础上做了进一步的改进，其假设负荷是随电压变化的连续电流负荷，把每一个闭合开关看成一个电流源，用一交流负荷潮流算法来计算网络潮流，选出最优解。文献[131提出一种最优流模式法，基本原理是首先在节点注入电流固定的情况下，将网络支路的阻抗换成电阻，求解网络的KCL和KVL方程，得到有功网损最小为目标的支路电流分布。非线性规划是处理具有非线性特征优化问题最直接的方法，这种方法的数学模型建立比较直观，物理概念清晰，计算精度较高。然而，非线性规划方法不同程度存在计算量大、内存需求量大、收敛性差、稳定性不好、对不等式的处理存在一定困难等问题，其应用受到了一定限制。虽然配电网络规划和优化运行是一个非线性问题，但可以采用局部线性化的方法，通过将非线性目标函数和安全约束逐次线性化来对问题进行求解。文献[14]中。D．LWall等人在1988年提出了一种线性规划模型，它将目标函数中的零次项和二次项线性化，将配电系统规划视为对线性化的运输模型的求解。Thompson等人在1981年，采用整数分支定界方法来解决配电网络规划中的变电站站址选择问题fl”。Masud提出了一种线性整数规划模型并研究了不同参数的互相影响。线性规翅J方法在优化运行方面的研究也很广泛。1991年，K．R．CMamandur利用牛顿拉夫逊潮流计算中的雅可比矩阵，来得到系统状态变量对控制变量的灵敏度关系的“灵敏度分析法”对电力系统的无功进行优化计算【16l。邓佑满从实时控制的角度出发，用逐次线性整数规划模型研究了电容器优化投切问题[171。ChiangHsiaoDong等人受单纯形法的启发，提出了一种单回路优化法11s】(SingleLoopOptimizationMethod，SLOM)，该方法以有功网损最小为目标函数，解决了最优配电网络重构问题。线性规划法的优点是计算迅速，收敛可靠，便于处理各种约束，能满足实时调度对计算速度的要求，但优化精度较差。混合整数规划法的原理是先确定整数变量，再与线性规划法协调处理连续变量。它解决了前述方法中没有解决的离散变量的精确处理问题，其数学模型也比较准确地体现了配电网络规划和优化运行的实际情况。Goncn和Foote以一种全面的0一l线性规划形式给出配电网规划模型，由于它包含了主要的规划决策量6 天津人学博十学位论文第一章绪论(变电站的位置、变压器的大小、馈线路径及尺寸等)和详细的目标函数，因此是较完善的模型【¨，。他们利用混合整数规划同时优化变电站数目、大小和位置、网络路径、导线尺寸、导线更换及负荷转移。Fawzi等人将投资较小的元件费用曲线直接线性化，保留部分投资相对较大的元件的固定费用，以运行约束为边界条件，用分支定界法求解混合整数规划模型。在配电网络优化运行方面，文[20】结合Benders分解技术，采用混合整数规划法来求解无功优化问题，将混合规划法分解为整数规划和线性规划两个子问题，减少了求解规模，在计算灵敏度系数矩阵时，由于采用分块矩阵求逆法，大大节省了计算时间。文[21】给出了一种采用二次惩罚函数进行离散变量归整方法，但人工设置参数较多、且必须在计算过程中由经验确定引入惩罚函数的恰当时机。混合整数规划法在工程应用中更趋于合理性，但计算时间较长，且其解的结果与初值的选取有关。2．启发式方法数学优化方法用数学优化模型描述配电网络规划和优化运行问题，理论上可以保证解的最优性，但通常电力系统规模很大，有的网络具有上千个节点和线路，如果再考虑多阶段规划及本身众多的因素，此问题将成为一个规模巨大的优化难题，单靠数学优化技术是无法解决的。启发式方法(heuristicsmethod)不同于纯数学优化方法．它是以直观分析为依据的算法，而且同规划及运行人员的经验相结合，相对于数学方法能够较为准确地实际模拟电力行为。1988年，S．Civanlar等人首先提出支路交换法[221(BranchExchangeMethod，BEM)，利用丌关的丌合在两条馈线之间交换负荷从而达到对配电网络进行重构的目的。M．E．Baran等人在文献[221的基础上进行了改进，利用网损变化估算公式为二次函数的特点，将二次函数求极值的方法用于寻找最佳开关操作，降低了总的搜索次数口”。1989年D．Shirmohammadi提出了一种最优流模式法(OptimalFlowPattern，OFP)，把丌关组合的问题转化为优化潮流的计算问题，并对配电网络重构问题进行研究1241。在配电网络规划方面，启发式方法也得到了广泛的应用。1990年，Aoki，eta1．综合线性规划模型和启发式支路交换模型的特点，用支路交换法对单阶段配电网络规划问题进行了研究【251。Nlira，eta1．在1991年把Aoki，eta1．的单阶段规划模型扩展成了多阶段规划模型【26】。1997年，s．K．Goswami采用支路交换法，进一步实现配电网的综合规划，不仅考虑了配电网网架优化，还考虑了变电站的优化规划方案【27l。2002年，EdelmiroMiguez等人以投资，系统损耗和供电质量为目标函数，考虑电压、设备容量、以及配电网络放射性等约束条件，用一种改进的支路交换法来解决大规模的配电网络规划问题【28】。启发式方法简单、直观、计算量小，由于在迭代过程中只要找到满足指标 天津人学博士学何论文第一章绪论的解，此方法就停止计算，因此只能给出次优解而非最优解。3．智能优化方法智能优化算法兴起于20世纪80年代初期，是～种解决组合优化问题的智能技术，主要包括模拟退火(SimulatedArmealling，SA)、遗传算法(GeneticAlgorithm，GA)、禁忌搜索(TabuSearch，TS)、粒子群优化算法(ParticleSwarmOptimization，PSO)、蚁群优化算法(AntColonyOptimizaitonn，ACO)、混沌优化方法(ChaoticOptimizationAlgorithm，COA)、人工神经网络(ArtificialNepalNetworks．ANN)等。模拟退火是1953年由Metropolis等人为了模拟熔融态固体热平衡的形成而提出的一种简单算法，即Metropolis抽样算法。1983年，Kirkpatrick等人首先将这一算法应用于求解组合优化问题，提出了模拟退火算法。通过适当的控制物体的温度的变化过程，实现大范围粗略搜索与局部精确搜索相结合来寻求问题的最优解，它是局部搜索算法的扩展，理论上它是一个全局最优算法，所以它的计算结果较精确【29／。倪秋龙、黄民翔于2000年，提出了～种基于支路交换的模拟退火算法用于配电网规划中，提高了模拟退火过程的效率．缩短了计算的时间【30】。Hsiao．DongChiang等将配电网络重构描述为不可微、多约束、多目标函数优化问题，详细论述了模拟退火算法用于求解多目标优化问题的方法，并在不同的温度下采用不同的收敛指标来提高SA算法的速度。DanJiang等提出利用模拟退火算法进行配电网络重构和电容器投切的综合优化算法，不仅降低了线损也解决了配电网络重构过程中的电压越限问题13”。Chiang等人采用模拟退火算法确定了电容器的配罱和控制方案f32】。刘吉来于1998年在解决无功优化问题时，提出了将搜索过程与最优解更新序列分离的改进措施对模拟退火算法进行了改进【3引。贾德香等人结合高中压配电网的特点，采用记忆指导搜索方法改进模拟退火算法，并以30节点系统进行了验证【⋯。遗传算法(GA)，是J．Holland于1975年受生物进化的启发而提出的【3”。GA是基于“适者生存”的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适应生存过程，通过群体一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。遗传算法是目前在配电网络规划和优化运行应用最多的一种算法j1994年，VladimiroMuanda，J．V．Ranito和L．M．Pmenqt提出了一种简单遗传算法，用以解决多阶段的配电网络规划问题【3⋯。2003年Mates，M．A提出了一种高效的遗传算法，对编码方式，交叉算子和变异算子等进行了恰当的设计，对大规模的配电网络进行了规划13”。相对于在配电网络规划方面的应用，遗传算法在配电网络优 天津大学博十学位论文第一章绪论化运行方面的应用更为广泛。KoiehiNara等人首先将GA算法用于最优配电网络重构，以开关状念为基因进行编码并同时考虑网络损耗及约束条件罚因子，将问题转化为一个混合的[0-1】规则问题【3”。M．Srinivas等提出一种自适应的遗传算法，在进化过程中，及时地调整交叉率和变异率，提高了算法的整体性能【391。文[40】提出部分匹配逆转交叉法对遗传算法进行改进，该方法使完全相同的两个父串进行交叉也能产生新的基因组合，开辟了新的搜索空间。刘莉，陈学允提出了一种模糊遗传算法，对交叉率和变异率进行模糊控制，用支路的开关状态作为控制参数，缩短了染色体长度，同时对交叉位置的选取、变异的进行等提出了独特的方案，有效地提高了收敛速度，避免了不成熟收敛【411。马晋韬，杨以涵等对控制变量进行二进制编码，对优化编码和变异概率两个方面进行了研究，用IEEE30节点系统予以验证，指出该算法在处理非连续的和非平滑的函数寻优方面优于传统寻优方法【4“。文献【43】采用～种修正的遗传算法求解无功优化问题，算法借助Benders分解将原问题分解为投资子问题和运行问题，该算法缩小了求解空间，降低求解维数，加快了收敛速度。赵登福等在将遗传算法应用于电力系统无功优化时，针对无功优化的实际问题，提出了不同优化阶段对目标函数各项罚因子采用不同权重，并构造出分阶段适应性函数的措施，提高了计算的收敛速度㈣。禁忌算法(TabuSearch或TabOOSearch，简称TS)是近年来伴随计算机技术的发展而产生的现代优化技术【4列。其基本思想是利用一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步搜索方向。为避免落入局部最优，当达到局部最优解时，禁忌算法将搜索方向后退到目标退化最小的一个方向上，以此作为新的初始方向。2003年，H．Mori和YIimura提出了一种并行禁忌搜索算法来解决配电网络扩展规划的组合优化问题【461。王成山，王赛一于2004年提出了基于空间GIS和TS搜索相结合的方法，对城市中压配电网络规划进行了研究[47]o文献[48]用禁忌搜索算法对配电系统中电容器和电压调节器的地点进行了研究，在搜索过程中采用加权处理方法综合考虑有功网损最小和投资费用最小两个目标函数，取得了较好效果。2002年，陈根军等阐述了用于配电网络重构问题时Ts搜索方法中各成员的设计过程，并通过三个不同规模的IEEE测试用例对所提的方法进行了验证149】。2003年，唐红键和冯可在解决配电网络重构问题时，将改进的遗传算法和禁忌搜索法结合起来，不仅充分发挥遗传算法搜索范围广的优势，而且利用禁忌搜索的思想减少了很多不必要的搜索，提高了进化速度【501。除SA、GA、TS外，其它智能计算方法在配电网络规划及优化运行方面也有着广泛的应用。w．M．Lin等在2000年提出了一种进化规划方法，以费用最小9 天津入学障士学位论文第一章绪论(停电费用，馈线和变电站综合投资)为Ifl标函数，规划一个实际配电网络悼“。1996年，Y．GMoustafa等人以MATLAB为软件平台，用人T荆0经网络的误差方向传播法(BP)，结合专家系统对配电网络扩展规划的最优网架进行了规划15“。2003年，陈根军等采用“向上节点”的变量表示方法，用蚁群优化算法对一具有6个变电所、102条馈线的配电网络进行了规划【5⋯。文献[54]将自适应PSO算法应用于IEEE30节点系统的无功优化问题中，通过在优化过程中自动调节PSO算法的有关参数，克服了标准PSO算法需多次试算确定参数以及局部极值能力有所增强的缺点。赵涛等根据混沌变量的特定内在随机佳和遍历性来跳出局部最优点，提出了一种混沌优化方法来求解电力系统无功优化问题[551。Kyung．Hee，Jung用专家系统解决主变或馈线超载及约束越界问题，通过开闭联络丌关和分段开关实现网络重构[561。刘莉等从经济性和安全性出发，提出网损最小和负荷平簿为目标的多目标配电网络重构方法，采用进化规划解决配电网络重构问题【57】。虽然上述智能优化算法在配电网络规划和优化运行上有了很大的进展，但是单个智能优化算法都还存在这样或那样的问题或不足。为了解决此问题，混合智能算法应运雨生。在解决配电网络优化问题上有了进一步的提高。周玲等在比较了基因算法和禁忌算法各自优缺点的基础上，针对配电网网架优化的特点，提出采用基因／禁忌组合算法的策略，并应用于配电网网架优化规划。文献【4]比较了GA与SA的共性和异性，利用各自的优点，提出了GA／SA混合寻优法，并且用于地区电网无功优化的过程．算例结果表明混合算法的寻优性能均优于任何一个单一算法”⋯。在解决无功优化问题时，褚美茹等利用混沌优化算法增加了适应值较低个体的淘汰速度，提高了每代种群的平均适应值水平，加快了算法的收敛速度”⋯。段刚等在解决配电网络重构问题时，以最短路径法，按照某-JJl嗔序为每个负荷分别寻找供电路径，然后利用遗传算法选择最优的负荷排列顺序，从而实现在局部最优解中寻求全局最优解。1．3本文所作的工作如Iiif所述，配电网络规划和优化运行是非常复杂的～个大规模、非线性、多目标、多约束的组合优化难题。本文在以往配电网络规划和优化运行研究的基础上，根据配电网络规划和优化运行的特点，采用智能优化算法结合地理信息系统研究了配电网络规划和优化运行问题，主要的工作如下：1．受遗传算法进化思想的启发，提出一种具有变异特性的粒子群优化算法，10 天津人学博十学何论文第一章绪论通过合理的设计变异算子。有效地克服了粒子群算法未成熟收敛的问题，提高了粒子群算法的优化性能，并结合地理信息系统和配电网络规划的特点，对实际地区的配电网络规划过程中的变电站选址定容问题进行了研究。2．建立了在不同负荷密度下，采用不同接线模式时，兼顾经济性和可靠性的配电网架优化模型，并用蚁群算法对实际算例进行了优化。3．提出了一种禁忌遗传混合算法，并结合配电网络闭环设计、开环运行的特点，将遗传算法中的优化编码技术引入TABU搜索方法中来，根据算法中邻域结构独特的设计和搜索方式，证明了其在配电网络重构中的全局最优性。4．结合遗传算法和粒子群算法两者的优点，提出了一种混合的遗传粒子群算法。在搜索过程中不仅同代之间进化信息共享，而且父代到子代之间进化的信息也能够积累，丰富了进化信息，提高了搜索效率。在重构配电网络过程中，设计了基于环路的编码方式，并且粒子群通过对染色体操作进行寻优，很好的保持了混合算法在搜索过程中的一致性。5．提出了一种混沌优化算法来解决电力系统无功优化问题。用类似载波的方法将混沌变量引入到优化变量中，利用混沌运动的遍历性和貌似随机性的特点直接对目标函数寻优，并以几个经典算例对所提出的方法进行了验证。6．提出了一种混沌粒子群优化方法(CPSO)来克服粒子群优化方法(PSO)中趋向同一化(失去了多样蛀)，使得后期收敛速度明显变慢容易早熟而陷入局部最优解的缺点，该方法结合混沌变量良好的遍历特性以及混沌优化的特点，对即将重合而同一化引起搜索能力下降的粒子赋予混沌状态搜索，其余粒子仍以常规的粒子群优化方法搜索，从而提高PSO的寻优性能。 天滓人学博十学位论文第二章智能优化算法介绍2．1遗传算法第二章智能优化算法介绍近年来，随着人工智能应用领域的不断扩大，传统的基于符号处理机制的人工智能法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难越来越明显，于是人们开始致力于研究一些能够处理当前难题的新型算法。1975年，J．Holland受生物进化论的启发提出了遗传算法160](GeneticAlgorithms，简称GA)。GA是基于“适者生存”的～种高度并行、随机和自适应的优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最优解或满意解。目前，随着计算机技术的发展，GA越来越得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化等领域得到了广泛的应用16t-701。2．1．1遗传算法的基本描述1．遗传编码：按照遗传算法的工作流程，当用遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结构之间建立联系，即确定编码和解码运算。出于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。然而，编码的策略或方法对于遗传箅子，尤其是对交叉和变异算子的功能和设计有很大的影响。问题编码一般应满足完备性、健全性和非冗余性三个原则，完备性是指问题空闻中的所有点都能成为GA编码空间中点的表现型；健全性是指GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性是指染色体和潜在解必须一一对应。按照遗传算法的模式定理，DeLong进一步提出了较为客观明确的编码评估准则．称之为编码原理【7。l。具体可以概述为有意义建筑模块编码规则和最小字符集编码规则，鲍者表示编码应当易于生成与所求问题相关的短距和低阶的建筑模块：后者表示编码应采用最小字符集使问题得到自然、简单的表示和描述。目前的编码方式有二进制编码、大字符集编码、序列编码、实数编码、树编码以及乱序编码等许多方式【仉751。2，评价函数：遗传算法将问题空问表示为染色体位串空间，为了执行适者生存的原则，必须对个体染色体的适应性进行评价。因此，评价函数(适应函数2 天津大学博七学位论文第二章智能优化算法介绍timessfunction)就构成了个体的生存环境。根据个体的适应值，就可以决定它在此环境下的生存能力。若用p表示位串空间，妒上的适应值函数可表示为，_(．)：S‘寸R+。其中R+表示非负实数集合。对最小值优化问题，一般建立如下适应函数f(x)和目标函数g(x)的对应关系：厂(工)={。m“一g‘之：薯赢‘x’<。m“(z·t)其中，C。。可以是一个输入值或是理论上的最大值，或是到当前所有代或最近k代中90)的最大值，此时C。。。随着进化代数会有变化。对于最大化问题，一般采用下述方法：m)=P吖mi。n，鬻蛳”(2_2)其中，C⋯既可以是特定的输入值，也可以是当前所有代或最近k代中g(x)的最小值。3．遗传操作：标准遗传算法的操作一般都包括选择(selection，或复制reproduction)、交叉(crossover，或重组rcombination)和变异(mutation)三种基本形式，他们构成了遗传算法的核心，是模拟自然选择以及遗传过程中发生的繁殖、交叉和突变现象的载体。选择：即从当前群体中选择适应值高的个体以生成交配池(matingp001)的过程。目前，主要有适应值比例选择(fitness．proportionateselection)、Botlzman选择、排序选择(rankselection)、联赛选择(tournamentselection)等形式。为了防止出于选择误差，或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失，DeLong提出了精英选择(elitistselection。orelitism)策略17l】，另外，在机器学习等领域中，Holland等专家提出了稳态选择方法(steady．Stateselection)。交叉：是进化算法中遗传算法具备的原始性的独有特征。GA交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。通常使用的交叉方式有一点交叉、两点交叉、多点交叉、一致交叉等几种形式。交叉操作一般分为以下几个步骤：幻从交配池中随机取出要交配的一对个体：b)根据染色体长度L，对要交配的一对个体，随机选取11，￡一11中一个或多个基因位霹作为交叉点。C)根据交叉概率n(0≤P。≤1)进行交叉操作，配对个体在交叉点处相互交换各自的部分内容，从而形成新的一对个体。变异：模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变 天津人学博十学位论文第二章智能优化算法介绍染色体的结构和物理性状。在遗传算法中，反转某位等位基因的二迸制字符值来实现。新个体J‘=at'a2_·a，l的具体产生过程如下变异算子通过按照变异概率P。随机对于给定的染色体位串s=ata2⋯aLo(¨)∽。={1-：黧≯f∈{L2一．，L)(2-3)其中，x，e[0,t】，是对应于每一个基因位产生的均匀随机变量。为了保证个体变异后不会与其父体产生太大的差异，变异概率一般取值较小，以保证种群发展的稳定。在进化的楚个过程中，交叉操作是主要的基因重组和群体更迭的手段，变异操作的作用是第二位的17“，变异算子仅仅充当背景性的角色(backgroundrole)。针对具体问题以及为了便于对进化过程实施控制，在标准变异算子的基础上，又引入了其他类型的变异算子，比如：特定有效位变异、变异概率自适应调整、面向领域知识的位变异【77。91等，使得遗传算法的应用范围和应用效果得到较好的改善。4．群体设定以及终止循环的条件根据模式定理，群体规模对遗传算法的性能影响很大。种群规摸越大，遗传算予所处理的模式就越多，算法陷入局部解的危险性就越小，因此，从保持种群的多样性以防止陷入局部解的角度考虑，种群规模应较大。但是，种群过大会带来相应的问题。一方面，种群越大，个体的适应度评价计算量也会随之增加，从而影响算法的效率；另一方面，种群过大，随着进化代数的增加，会使少量适应度很高的个体被大量地复制而生存下来，而大多数个体被淘汰，从而影响个体的竞争。对此问题。己有一些学者进行了较深入的研究和分析，并得出了一些初步理论分析结果，Goldberg证明了使用二值编码的遗传算法时，群体中最优个体数目与编码的字符编码长度的关系【80】，孙艳丰等研究了自然数编码遗传算法的最优群体规模【8”。但在大多数情况下，种群规模的大小是很难进行计算，从理论上讲不同的解题过程应该有不同的最佳种群规模。关于GA迭代过程如何终止，一般采用设定最大代数的方法。首先该方法简单易行但不准确；其次。可以根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进行控制：第三，根据算法的离线性能和在线性能的变化判定；最后，在采用精荚保留选择策略的情况下，按每代最佳个体的适应值的变化情况确定【82l。综上所述，标准遗传算法的基本流程如图2．1所示：4 天津人学博十学位论文第二章智能优化算法介绍1)染也体解码2)计算目标函数值3)函数值积适应值映射4)适应值调整兰个皋奉算了I，选掸算了2交叉算下3．变异算了儿他一岛级算了确定实际问题参数集对参数集进行编码初始化群体只O评价群体塑足停止准则：二≥—叶|丝室＼—／L—fNo遗传撵作图2．1标准遗传算法的基本流程2．1．2GA的马氏链描述和收敛性分析预备知识：定义2．1．2．1称月×n方阵A=(ai)为(1)非负的，记A>10，若珊≥0，i,j=1,2，¨．"。(2)严格诉的，记A>0，若aⅡ>0，t，=1,2，．埘。(3)正则的．若A1>0，且存在自然数k，使A‘>0。(4)随机的，若爿≥o，∑口。=l，i=l，2，⋯，月。(5)规约的，若A>-OA且霆过相同的行和列初等变换后可转化为f吴；I的(5)规约的，且经过相同的行和列初等变换后可转化为}v二l的形式，其中C和71均为方阵。(6)不可约的，若A≥0且不归约。(7)稳定的，若彳是随机的且所有行相同。(8)列容的，若A是随机的且每一列中至少有一个正数。引理2．1．2．1若(jM和s为随机阵，且M>O，S为列容的，则CMS>O。证明：已A=CM，B=AS。由于C为随机阵，则C的每一行中至少存在一个 天津人学博士学位论文第二章智能优化算法介绍正数。从而Vf√∈{l，2⋯，，2}，口“=∑ciim自>o，即d>O。进而，由于S为列容的，则Vf，』∈{l，2⋯，月)，％=∑‰％>o。故CMS>O得证。引理2．1。2．2若P为『F则随机阵，则P收敛到一个全正稳定随机阵。即P。=【l，】，r一，1】。【p。，P2，-一，n】，其中[pI，P2，·一，P。】尸=【pl，p2，⋯，以】，∑p。=l'P，=⋯lirap}k1>o，即【A，P2W',P。】7是P7的特征值为1且各分量均为正数的特征向量。引理2．1。2．3若户=阪；1是随机的．其中C为m维严格正随机方阵，Re0，T≠0则儿雕]是一个稳定的随机阵．其中R。：liraVT’RC“。‘。箭同时，P4=队⋯，1r【pl，P2'．‘。，P。】，p，=。li—mp笋’芝。其中P，>O(0≤．，≤，")，P，=0(m+l≤，≤刀)。2．1．3标准遗传算法的马氏链描述在SGA中，令所有个体形成的有限空间为Q，所有种群对应的整个状态空间为G，其中每一种群为一个状态，一旦染色体长度三和种群数目Ⅳ给定且有限时，则Q的维数JQf有限，G的维数蚓=IQI“也有限。由于算法中每一代状态的转移依赖于选择(复制)、交叉和变异操作，且与进化代数无关，因此SGA可视为一个有限状态的齐次马氏链。鉴于算法中三个遗传操作是循环往复执行的，我们按“交叉寸变异_选择”顺序来考虑算法中状态的转移。从而，表征马氏链的状态转移矩阵P为矩阵C，肘和s的乘积，其中c，M和s分别为交叉、变异和选择操作所决定的状态转移矩阵。1．交叉操作交叉操作可视为状念空间上的随机函数。记交叉操作决定的状态转移矩阵为 天津大学博十学位论文第二章智能优化算法介绍C=(ci)。，其中。“为从状态f经交叉操作转移到状态J的概率。由于一个状态通过交叉操作总要转移到状态空间中的另一个状态，因此∑勺=l显然成立，即J=lc为随机矩阵。2．变异操作在SGA中，变异操作是独立作用于种群内各个个体的每一位基因上，记变异操作决定的状态转移矩阵为M=(％)⋯刊，其中mij为从状态i经变异操作转移到状态，的概率。由于染色体的每个基因具有相同的变异概率p户O，则m“=p：”(1-P。)”“>0，其中嘞为状态i与．，之间具有不同基因的位置的总数。例如，状态{(1000)，(0111)，(tolo))与状态{Omo)，(1110)，(o101)}之间的日目为7。因此M为，I：p：格正的随机矩阵。3．选择操作在SGA中．交叉和变异操作后得到的种群经选择操作后又将转移到另一个种群，记选择操作决定的状态转移矩阵为S=(s。)怫㈦。考虑比例选择(轮盘赌)策略，种群中染色体X被选中的概率为f(X∥∑．f(x。)>o／k=l则种群i经选择操作后保持不变的概率～S。≥H(f(x，)／f(X。))>0因此，转移矩阵s是随机且列容的2．1．4标准遗传算法的收敛性对应于有限状态马氏链的一般遗传算法(二进制或十进制编码)均是后文介绍的GASA混合策略的一种特例，本节仅讨论基于二进制编码的SGA的收敛性。定理2．1．4．1若SGA中交叉概率见E【0，l】，变异概率p二E(O，1)，并且算法采用比例选择策略，则SGA的状态转移矩阵P=印舔是严格正的。证明：利用上节矩阵C，M和S的定义以及引理3_3．1即可。注：根据上述定理可知，SGA是一个遍历马氏链，从而存在一个与初值无关的极限分布，由此算法的初始种群可以任意初始化，同时任何时刻从一个状态转移到另一个状态的概率不为0，即马氏链构成了强连通图。然而，尽管初始种群的随机性在理论上不影响极限分布，但由于实际算法中由于某些环节的近似处理(如终止准则)，算法的搜索结果存在一定的波动性，通常算法要执行多次才能得到较可靠的结果。 天津大学博十学位论文第二章智能优化算法介绍定理2．1．4．2SGA不能够以概率1收敛到全局最优解。证明令P(t)={X，(，)，⋯，x、(f)j为算法第r代的种群，其最优适配值为互=max{f(Xk(f))，k=l，⋯，N)，设／为全局最优的适配值。由定理313．1和引理3．3．2知，SGA以任意状态，为极限分布的概率lim∥=茚>0，因此，⋯limp{Z,=f‘}≤1一矿<1。注：上述定理从概率意义上说明了SGA不能够收敛到全局最优，其原因在于算法中最优解的概率遗失。因此，只要在算法中每代保留当前最优解，无论是选择之前还是在选择之后，算法将最终收敛到全局最优。从而有以下定理。定理2．1．4．3每代在选择操作后保留最优解的SGA以概率l收敛到全局最优解。证明：由于算法采用了保优技术，为方便起见，我们将保留下来的各代的最优个体存放在种群的第一号位罱．但它不参与遗传操作。即，在第f代进化时的种群为(X+O一1)，x；(f)，⋯。x、(r))，其中X+p—1)表示算法搜索至第H代所得到的最佳个体。从而，算法对应马氏链的状态空间维数将变为|Qr。然后，我们将包含相同的最优解的状态仍按在原状态空间的顺序进行排列，而对包含不同最优解的状态按最优解的适配值从大到小进行排列。由此，新的交叉、变异和选择操作对应的状态转移矩阵可表示为C+=diag(C，C，⋯，C)，M+=diag(M，M，⋯，肘)和S+=diag(S，S，⋯，S)。在选择操作后，算法要将当前种群中的最优解与前一代保留下来最优解进行比较，这一操作也可用矩阵U=(Ⅳ．，)表示。显然，状态Y(t)=(X’(，一1)，爿l(，)，⋯。xN(，))转移到y(f+1)=(Ⅳ+(f)，五(¨-1)，⋯，X、(f+1))的概率为ll，／fmax(，(墨O))，⋯，f(x。(f)))=．r’(f)P(y(，+Dlr(t))={and(Xl(f)，⋯，Ⅳ～(，))=(■(，+1)，⋯，。h(f+1))(2—4)【0，e／se从而，矩阵[，每一行均有且只有一个元素为l。而其他元素为0。同时，考虑到状态的排列顺序，可知矩阵己，为下三角矩阵。记U=UlJU2lU22u㈣q叫2’’u⋯其中uⅡ：010l”xlQJ“阶矩阵，且UIl为单位矩阵。从而，马氏链的一步转移矩阵为尸+=C+M+S+U=dI_ag(CMS，CMS，⋯，CMS) 天津人学|尊十学何论文第二章智能优化算法介绍CMSUIlCMSU2ICMSU22CMSUIe4iCMSUI叫2‘··CMSUIade4显然，P+为可约的随机矩阵，J|-CMSU．．严格正。从而，考虑到P+中第一位状态由好到坏的flF-yrJ；ll页序可知，『CMSU2I]R=l；I≠o，lc懈‰j由引理3．3．3可知，不包含最优个体的状态在马氏链的极限分布中的概率为0，包含最优个体的状态在马氏链的极限分布中的概率和为1。从而，算法将以概率l收敛到包含全局最优个体的状态，也即算法能够以概率1搜索到全局最优解。定理2．1．4．4每代在选择操作前保留最优解的SGA以概率1收敛到全局最优解。证明过程类似于定理33．3，在此不再赘述。2．2禁忌搜索算法2．2．1禁忌搜索算法简介禁忌搜索(Tabu)的思想最早是由Glover提出18”，其最重要的思想是标记对应已搜索到的局部最优解的一些对象，并在下一步的迭代搜索过程中尽量避开这些对象．从而保证对不同的、有效的搜索路径进行搜索。由于Tabu算法具有灵活的记忆功能和藐视准则，且在搜索过程中可以接受劣解，具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，因此它是一种局部搜索能力很强的全局迭代寻优算法。图l为Tabu算法与“爬山法”在寻优机制上的比较。Xo为初始解，X。(i=1，2，⋯，9)表示9步迭代中每步的最优解，Ⅳf(i=1，2，⋯，9)表示对应x，的邻域解的集合。首先通过比较珈邻域Ⅳ0内诸多候选解中的目标函数值找出最优解xl，同理找到在以x-为当前点、Ⅳl为邻域的最优解地，“爬山法”陷入局部最小值札，而Tabu算法则继续寻优，找到了比X3更优的解抽。≠q{莹三—．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．L=7 天泮人学博十学位论文第一二章智能优化算法介绍“爬山法”图2—2Tabu算法与“爬山法”的比较2．2．2禁忌搜索的基本原理考虑最一般优化问题，对于肿每一个解X，定义一个邻域^协)(由当前解x所有的移动操作而产生的解的集合定义为解x的邻域N(x))，禁忌搜索算法首先确定一个初始解X。初始解X可以从一个启发式算法中获得或者是从解集合肿任意选取。确定初始解后，定义解x的邻域移动M(x)，产生当前点x的邻域，然后从邻域中挑选一个解x。，再从x‘_丌始，重复搜索。如果邻域移动中接受前一移动的逆移动，搜索就有可能陷入循环的危险，为了避免死循环和局部最优，算法中构造一个短期循环汜忆表一禁忌表(TabuList)。禁忌表中存放了刚刚进行过的L(禁忌长度)个邻域移动，这些移动被看作是禁忌移动(TabuMove)。对于当前的移动，再以后的三次移动中是禁止的，￡次移动以后释放该移动。如果在￡次迭代内，能够把搜索带到一个从未到过的区域，则此时浚移动的禁忌状态就可以释放，不受禁忌表的限制。禁忌表是一个先进先出的表，搜索过程中被不断修改，使禁忌表始终保持着￡个移动。即使引入了禁忌表，搜索仍有可能出现循环，一次必须给定停止准则来避免循环的发生。当迭代次数大于给定值或在给定迭代次数内所发现的最优解无法改进时，则算法停止。出于禁忌搜索算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够及时跳出局部最优解，转向解空|．日J的其他区域，从而增强了获得更好的全局最优解的概率，所以禁忌算法是一种局部搜索能力很强的全局迭代寻优算法，禁忌搜索算法的流程图如图2．3所示：20 天洋人学博十学伉论文第二章智能优化算法介绍给定算：法参数，19f{机产生枷始解，置禁忌表为守由当前斛产生邻域解．确定假选解箍桃准则满足否?—＼—，一IN做选斛禁忌属件判断将满足藐视准则的解l作为当前解，苒对心的Y对象替换最早进入禁——．I忌表的对象，更新最优状态将_|『_禁忌对象对应的最佳解作为当前解：【}=替换最早进入禁忌表的对象图2-3禁忌搜索算法流程图2．2．3禁忌搜索的关键参数1．适配值函数：类似于遗传算法，禁忌搜索的适配值函数也是用于对搜索状态的评价，进而结合禁忌准则的藐视准则来选取新的当前状态。显然，目标函数直接作为适配值函数是比较容易理解的做法。当然，目标函数的任何变形都可作为适配值函数，譬如对极小化问题可将状态x的适配值f(x)定义为M—c(x)或e一”’，其中M为一足够大币数，C(X)为目标值，口>0。若目标函数的计算比较困难或耗时较多，如一些复杂工业过程的目标函数值需要一次仿真才能获得，此时可采用反映问题目标的某些特征值来作为适配值，进而改善算法的时间性能。当然，选取何种特征值要视具体问题而言，但必须保证特征值的最佳性与目标函数的最优性一致。2．禁忌对象：所谓禁忌对象就是被置入禁忌表中的那些变化元素，而禁忌的目的则是为了尽量避免迂回搜索而多搜索一些有效的搜索途径。归纳而言，禁忌对象通常町选取状念本身或状态分量或适配值的变化等。(1)以状态本身或其变化作为禁忌对象是最为简单、最容易理解的途径。具 犬洋人学博十学位论文第二二章智能优化算法介绍体而言，当状态由x变化到状态Y时，将状态Y(或x寸Y的变化)视为禁忌对象，从而在一定条件下禁止了J，(或X--->Y的变化)的再度出现。(2)状念的变化包含了多个状态分量的变化，因此以状态分量的变化为禁忌对象将扩大禁忌的范围，并可减少相应的计算量。譬如，对胃换问题，SWAP操作引起的两点互换意味羞状念分量的变化，这就可作为禁忌对象：对高维函数优化问题，则可将某一维分量本身或其变化作为禁忌对象。(3)类似等高线的原理，以适配值或其变化为禁忌对象则将处于同一适配值的状态视为相同状态，这在函数优化中经常采用。由于一个值的变化隐含着多个状念的变化，因此这种情况下的禁忌范围相对于状态的变化将有所扩大。可见，以状态本身为禁忌对象比以状态分量或适配值为禁忌对象的禁忌范围要小，从而给予的搜索范围要大．容易造成计算时帕J的增加。然而，在禁忌长度和候选解集大小相同且较小的情况下，后两者也会因禁忌范围过大丽使搜索陷入局部极小。3．禁忌长度和候选解：禁忌长度和候选解集的大小是影响TS算法性能的两个关键参数。所谓禁忌长度，即禁忌对象在不考虑藐视准则情况下不允许被选取的最大次数(通俗些，可视为对象在禁忌表中的任期)，对象只有当其任期为0时爿’被解禁。候选解集则通常是当前状态的邻域解集的一个子集。在算法的构造和计算过程中，一方面要求计算量和存储量尽量少，这就要求禁忌长度和候选解集的尽量小；但是，禁忌长度过短将造成搜索的循环，候选解集过小将容易造成早熟收敛，即陷入局部极小。禁忌长度的选取与问题特性、研究者的经验有关，它决定了算法的计算复杂性。一方面，禁忌长度t可以是定常不变的，如将禁忌长度固定为某个数(譬如t=3等)，或者固定为与问题规模相关的一个量(譬如r=√胛，”为问题维数或规模)，如此实现很方便、简单。另一方面，禁忌长度也可以是动态变化的，如根据搜索性能和问题特性设定禁忌长度的变化区间[0。，。。。】(譬如[3，101、0．9√n，1．1√H等)，而禁忌长度9113可按某种原则或公式在其区恒5内变化。当然，禁忌长度的区I刚大小也可随搜索性能的变化而动态变化。一般而言，当算法的性能动态下降较大时，说明算法当前的搜索能力比较强，也可能当前解附近极小解形成的“波谷”较深，从而可设置较大的禁忌长度来延续当前的搜索行为，并避免陷入局部极小。大量研究表明，禁忌长度的动态设置方式比静态方式具有更好的性能和鲁棒性，而更为合理高效的设置方式还有待进一步研究。候选解通常在当莉状态的邻域中择优选取，但选取过多将造成较大的计算量，而选取过少则容易造成早熟收敛。然而，要做到整个邻域的择优往往需要大 天津人学博十学位论文第二章智能优化算法介绍量的计算，如TSP的SWAP操作将产生e个邻域解，因此可以确定性或随机性地在部分邻域解中选取候选解，具体数据大小则可视问题特性和对算法的要求而定。4．藐视准则：在禁忌搜索算法中，可能会出现候选解全部被禁忌，或者存在一个优于“bestSOfar”状态的禁忌候选解，此时藐视准则将使某些状态解禁，以实现更高效的优化性能。在此给出藐视准则的几种常用方式㈣。(1)基于适配值的准则。全局形式(最常用的方式)：若某个禁忌候选解的适配值优于“bestSOfar”状态，则解禁此候选解为当前状态和新的“bestSOfar”状念；区域形式：将搜索空问分成若干个子区域，若某个禁忌候选解的适配值优于它所在区域的“bestSOfar”状态，则解禁此候选解为当前状态和相应区域的新“bestSOfar”状念。该准则可直观理解为算法搜索到了一个更好的解；(2)基于搜索方向的准则。若禁忌对象上次被禁时使得适配值有所改善，并且目前该禁忌对象对应的候选解的适配值优于当前解，则对该禁忌对象解禁。该准则可直观理解为算法『F按有效的搜索途径进行：(3)基于最小错误的准则。若候选解均被禁忌，且不存在优于“bestSOfar”状态的候选解，则对候选解中最佳的候选解进行解禁，以继续搜索：(4)基于影响力的准则。在搜索过程中不同对象的变化对适配值的影响有所不同，有的很大，有的较小，而这种影响力可作为一种属性与禁忌长度和适配值来共同构造藐视准则。直观的理解是，解禁一个影响力大的禁忌对象，有助于在以后的搜索中得到更好的解。需要指出的是，影响力仅是一个标量指标，可以表征适配值的下降，也可以表征适配值的上升。譬如，若候选解均差于“bestsofar”状态，而某个禁忌对象的影响力指标很高，且很快将被解禁，则立刻解禁该对象以期待更好的状态。显然．这种准则需要引入一个标定影响力大小的度量和一个与禁忌任期相关的阈值，无疑增加了算法操作的复杂性。同时，这些指标最好是动态变化的，以适应搜索进程和性能的变化。5．禁忌频率：记忆禁总频率(或次数)是对禁忌属性的一种补充，可放宽选择决策对象的范围。譬如，如果某个适配值频繁出现，则可以推测算法陷入某种循环或某个极小点，或者说现有算法参数不能发掘更好的状态，进而应当对算法结构或参数作修改。在实际求解时，可以根据问题和算法的需要，记忆某个状念的出现的频率，也可以使用某些对象或适配值等出现的信息，而这些信息又可以是静态的，或者动态的。静态的频率信息主要包括状念、适配值或对换等对象在优化过程中出现的频率，其计算相对比较简单，如对象在计算中出现的次数，出现次数与总迭代步数的比，某两个状态问循环的次数等。显然，这些信息有助于了解某些对象的特性， 大沣人学博十学忙论文第二章智能优化算法介绍以及相应循环出现的次数等。动态的频率信息主要记录从某些状态、适配值或对换对象转移到另一些状念、适配值或对换等对象的变化趋势，如记录某个状态序列的变化。显然，对动态频率信息的已录比较复杂，而它所提供的信息量也较多。常用的方法如下18目：(1)记录某个序列的长度，即序列中的元素个数，而在记录某些关键点的序列中，可以按这些关键点的序列长度的变化来进行计算：(2)记录由序列中的某个元素出发后再回到浚元索的迭代次数：(3)记录某个序列的平均适配值，或者是相应元索的适配值的变化：(4)记录某个序列出现的频率等。上述频率信息有助于加强禁忌搜索的能力和效率，并且有助于对禁忌搜索算法参数的控制，或者对相应的对象实施惩罚(如前文示例)。譬如，若某个对象频繁，则可以增加禁忌长度来避免循环；若某个序列的适配值变化较小，则可以增加对该序列所有对象的禁忌长度，反之则缩小禁忌长度：若最佳适配值长时间维持下去，则可以终止搜索进程而认为该适配值已是最优值。此外．许多改进的禁忌搜索算法还根据频率等信息在算法中增加集中搜索(intensification)和分散搜索(diversification)机制，以增加算法的搜索质量和效率。其中，集中搜索机制强调算法对优良区域的重点搜索，如基于最优或次优状态进行重新初始化或进行多步搜索，加强对应取得最优状态的算法参数的被选取概率等；分散搜索机制则强调拓宽搜索范围，尤其是那些来探索的区域，这与增强遗传算法种群多样性有些类似。显然，集中搜索和分散搜索在某些层面上是矛盾的，而两者对算法性能都有很大影响，因此作为一个较好的禁忌搜索算法，应当具有合理平衡集中搜索与分散搜索的能力，这也是许多论文实现对禁忌搜索算法性能改进的突破口，在此不再展丌介绍。2．终止准则：与模拟退火、遗传算法一样，禁忌搜索也需要一个终止准则柬结束算法的搜索过程，而严格实现理论上的收敛条件，即在禁忌长度充分大的条件下实现状态空间的遍历，这显然是不切合实际的，因此实际设计算法时通常采用近似的收敛准则。常用方法如下：(1)给定最大迭代步数。此方法简单易操作，但难以保证优化质量：(2)设定某个对象的最大禁忌频率。即，若某个状态、适配值或对换等对象的禁忌频率超过某一阈值，则终止算法，其中也包括最佳适配值连续若干步保持不变的情况：(3)设定适配值的偏离幅度。即，首先有估界算法估计问题的下界，一旦算法中最佳适配值与下界的偏离值小于某规定幅度时，则终止搜索。 犬津人学博十学位论文第一二章智能优化算法介绍2．2．4禁忌搜索的收敛性对一般问题minJr(x)，xex，其中如)为目标函数，z为有限的搜索空间，x为搜索状态。从图论的观点可解释如下：有限状态优化问题的禁忌搜索可用图G～=形爿)表示，其中．v为邻域结构，V为所有状态构成的顶点集，A为相应的边集，A=∽垤，e=(t一)．if一∈Ⅳ(x))。设k为算法迭代次数，&为Tabu算法在第k次迭代所搜索到的所有状态的集合。在证明算法的收敛性之前，首先对邻域结构作如下假设：(1)邻域结构是对称的，即Vx、一∈X，z∈N(x7)∞一∈Ⅳ(z)；(2)图@是强连通的，即Vx、x’eX，一定存在～条由X到X’的路径。引理2．2．4．1{鼠)(々≥1)序列非降，且收敛到极限F；证明：出㈣}(々≥I)的构造途径可知，S}∈S㈨，因此{墨)(t≥1)是非降的。同时，由于搜索空间为有限集，因此＆必然收敛到某一极限∥。引理2．2．4．2若邻域结构满足上述两个假设，同时存在迭代次数k‘，使得对所有的x∈S，Ⅳ(x)￡S，。成立S，=X，即算法收敛。证明：采用反证法。设s，≠z，则由图的连通性知，至少存在一条路径将X—S。．中的一个解(记为y)与Sk．中的一个解(记为上)连通。令Y到z的路径为e(y，工)=(M=y，y2，⋯，y。=x)，其中Y¨∈Ⅳ(只)，f_1,2，⋯，P一1。考虑路径P(y，x)中的第一‘个解Y，．，使得y，‘∈X—Sk．助，．+。∈Ⅳ(只．)。由邻域结构的对称性知，Y，．∈Ⅳ(y，·+I)，但是，既然Y。．∈Sr，则N(y。．+I)≤S★．，进而Y。．∈Sr。显然有矛盾产，土，因此gI理成立。引理2．2．4．1f^m≥1)序列和{玩)∞≥1)序列是单调序列，并且分别收敛到爿+和F，其中爿’和口’是构成集合Sl的一个分解：证明：首先，由集合的构造可知，对所有k≥1，A㈧￡Ak，Bk∈Bk∥因此∽j(々≥I)是非增序列．而(nA(k≥1)是非降序列。同时由于地}(￡≥1)和{四。)(￡兰1)的界分别为空集和x，且4nB,=彩，4u鼠=S。，因此两集合分别将收敛到两个极限集，并且．构成S’的一种分区。引理2．2．4．2若A’和B’分别是{^)(I≥I)和{吼)(女≥1)序列的极限，则有：(1)对所有X∈B’，^r(x)nA’=o：(2)对所有XEA‘，Ⅳ(x)nB+=o；(3)对所有x∈B+，N(x)￡B+：(4)A’=o。证明：(1)假设存在解X。∈B+，使N(x)nA+≠g，既然坼∈B‘，则有 天津大学博士学位论文第二章智能优化算法介绍hk≤t，N(x。)∈￡。则在肛l步迭代时有心+l=xi．，f’=min{i；x。∈Ⅳ(‰)}a既然Ⅳ(x)nA+≠o且A‘∈S女，则，可表示为i‘=rain{i；x．∈Ⅳ(以)nA‘j。这意味着以+。∈A’nB+，这显然与引理2．2．4．3矛盾。因此对所有x∈B’，N(x)nA’=o。(2)假设存在坼∈A’，N(xt)nB‘≠o，令x，∈N(xe)nB’，由于x，EB’，则N(x，)nA+=o．由于以∈一’，且‰∈Ⅳ(薯)，则以∈N(x。)nA‘，从而矛盾产生，因此对所有x∈A‘，．Ⅳo)nB’=o。(3)令X，∈B+，幽最的定义知，吮≤☆，N(x^)≤鼠。另一方面t由引理2．2．4．3可知，S。￡S‘=A’LjB‘，这意昧着N(xk)‘A‘uB‘，由于Ⅳ(瓢)nA+=o，从而可得N(x。)￡B’。(4)采用反证法。考虑x．．∈∥，f‘=max{i；x,￡A+)，这意味着f。4。约束因子法控制系统行为最终收敛。且可以有效搜索不同区域，该法能得到高质量的解。3．选择法Angeline1998年借鉴进化计算的选择概念，将其引入PSO算法。通过比较各 天津人学博十掌’悔论文第二章智能优化算法介绍个粒子的适应值．淘汰差的粒子，而将具有较高适应值的粒子进行复制以产生等数额的粒子来提高算法的收敛性Im”。Lovbjerg等人进一步将进化算法中的交叉操作引入PSO算法，交叉型PSO与传统的PSO模型的惟一区别在于粒子群在进行速度和位置的更新后还要进行交叉操作，并用产生的后代粒子取代双亲粒子(1021。实验表明，与传统的PSO及传统的遗传算法相比，交叉PSO搜索速度快，收敛精度高。4．邻域法suganthan于1999年提出了带有邻域操作的PSO模型在该模型中，用每个粒子所定义的当前邻域极值代替粒子群的当前全局极值f惜】。在优化的初始阶段，将邻域定义为每个粒子自身，随着迭代次数的增加，将邻域范围逐步扩展到包含所有粒子，则此时的邻域极值即为全局极值。5．拉伸法Parsopoulos和Plagianakos于2001年提出将拉伸技术用于PSO最小化问题求解，以避免陷入局部最小值的优化，这种模型称为SPSO[104】。sPso模型在检测到局部最优后。立即对优化的函数进行拉伸变形操作，从雨减小陷入局部最小的概率。PSO算法是一个新的基于群体智能的进化算法，其研究远没有像遗传算法和模拟退火算法那样深入，在理论上并不能保证能够得到最优解。PSO算法在进行优化问题的求解时应用范围有限，尤其对离散的组合优化问题，其理论建模还处于起步阶段。PSO算法中的一些参数，如学习因子cI，c2、惯性权重w以及粒子个数往往根据有限的应用经验确定，并不具有广泛的适应性。因此将PSO与进化算法、模糊系统、神经网络以及一些优化技术结合，根据不同的优化问题建立相应的PSO模型是PSO算法当前的研究重点。2．4蚁群优化算法蚂蚁是自然界中常见的一种生物．人们对蚂蚁的认识大部是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。20世纪90年代，意大利学者M．Dorigo，V．Maniezzo，A．Colorini等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟进化算法一蚁群优化算法I105】(AntColonyOptimization)。随后．这种新型的分布式智能模拟算法已逐渐引起人们的注意并广泛应用于求解分配、图论、指派等NP完全问题f‘峨108】。 天津人学博十学位论文第二章智能优化算法介绍2．4．1蚁群优化算法的基本原理人工蚁群算法是受到对真实的蚁群行为的研究的启发而提出的，为了说明人工蚁群系统的原理，先从蚁群搜索食物的过程谈起。象蚂蚁、蜜蜂、飞娥等群居昆虫，虽然单个昆虫的行为极其简单，但由简单的个体所组成的群体却表现出极其复杂的行为，原因是什么呢?仿生学家经过大量细致观察研究发现：蚁群中的蚂蚁以“外激素”(pheromone)为媒介的间接的异步的联系方式是蚁群算法的最大的特点【109】。蚂蚁在行动(寻找食物或者寻找回巢的路径)中，会在它们经过的地方留下一些化学物质(我们称之为“信息素”)。这种物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动(具体表现在后到的蚂蚁选择有这些物质的路径的可能性．比选择没有这些物质的路径的可能性大得多)，而后到者留下的外激素会对原有的外激素进行加强，并如此循环下去。这样，经过蚂蚁越多的路径，在后到蚂蚁的选择中被选中的可能性就越大(因为残留的外激素浓度较大的缘故)。由于在一定的时间内。越短的路径会被越多的蚂蚁访问，因而积累的外激素也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。fIE16蒜≥H《》H簪HI^图2—4蚁群觅食示意图下面我们引用M．Dorigo所举的例子来具体说明蚁群系统的原理。如图2-4所示，设A是巢穴，E是食物源。HC为一障碍物。由于障碍物存在，蚂蚁只能经由H或C出A到达E，或由E到达A。各点之间的距离如图1所示。设每个时间单位有30只蚂蚁由A到达B，有30只蚂蚁由E到达D点，蚂蚁过后留下的激素物质量(以下我们称之为信息)为l，为方便起见．设该物质停留时间为1。在初始时刻，出于路径BH、BC、DH、DC上均无信息存在，位于B和E的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BH、BC、DH。经过一个时闻单位后，在路径BCD上的信息量是路径BHD上信息量的二倍。t=l时刻，将有20只蚂蚁由B和D到达C，有10只蚂蚁由B和D到达H。随着时I．白J的推移，蚂蚁将会以越来越大的概率选择路径BCD，最终完全选择路径BCD。从而找到由蚁巢到食物源的最短路径。由此可见。蚂蚁个体之间的信息交换是一个正反馈过程。 天津人学博士学位论文第二章智能优化算法介绍2．4．2蚁群系统模型及其实现我们以求解n个城市的TSP问题为例浇明蚁群系统模型。对于其它问题，可以对此模型稍作修改便可应用。为模拟实际蚂蚁的行为，首先引进如下记号：设m是蚁群中蚂蚁的数量，d。(f，，=1,2，⋯，n)表示城市f和城市．，之间的距离，bi(f)表示f时刻位于城市i的蚂蚁的个数，。：夕筑(f)，fF0)表示t时刻在拶连线上残留的信息量。初始时刻，各条路径上信息量相等，设r,j(0)=C(c为常数)。蚂蚁k(k=l，2，⋯，m)在运动过程中，根据各条路径上的信息量决定转移方向，P‘。(，)表示在t时刻蚂蚁k出位置i转移到位置．，的概率，尸。。：』器，∈“如wedt。2．。。，v∈洲脚一‘00therwbe其中，allowed^={O，l，⋯，n-1}-tabu^表示蚂蚁k下一步允许选择的城市。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能。这里用tabu。(≈=1，2，⋯，脚)记录蚂蚁k目前已经定过的城市。随着时间的推移，以前留下的信息逐渐消逝，用参数1一P表示信息消逝程度。经过n个时刻，蚂蚁完成一次循环，各路径上信息量要根据下式作调整，r“(f+”)=P’f“(，)+△f"(2-12)ATiI=∑△r‘i／(2．13)f。。表示第k只蚂蚁在本次循环中留在路径上的信息量。△f。表示本次循环中所有蚂蚁留在路径上的信息量△ft。：j善若第k只蚂蚁在本次循环中经过驴(2-14)l0否则其中，Q是体现蚂蚁所留信息素数量的一个常数，厶表示第k只蚂蚁在本次循环中所走路径的长度。在初始时刻，％(o)=C(consj，△0=O，其中i,j=O，1，⋯，n一1，口，p分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用。踞，，表示出城市i转移到城市，的期望程度，可根据某种启发式算法具体确定。参数Q，C，口，∥，p可以用实验方法确定其最优组合，停止条件可以用固定循环次数或者当进化趋势不明显时便停止计算。根据具体算法的不同毛(，)'Az"。(，)及p’。(f)的表达形式可以不同，要根据具体问题而定。M．Dorigo曾给出三种不同模型。分别称之为蚂蚁圈模型(ant．cyclesystem)，蚂蚁数量模型(ant-quantitysystem)和蚂蚁密度模型(ant-densitysystem)，表达式分别如下：蚂蚁圈模型(ant．cyclesystem) 大洋人学博十学位论文第二章智能优化算法介绍A2-ko：{善若路径{『在蚂蚁女本次循环经过的路线上(2．15)}0其它蚂蚁数量模型(ant—quantitysystem)ATk,j：j著若路径l『处在蚂蚁。本次循环经过的路线上(2一16)【i其它蚂蚁密度模型(ant-densitysystem)△fk。=佗若路街处在蚂蚁髫循环经过的路线上(2．17)ACO算法具有很强鲁棒性、具有并行计算的本质、全局寻优能力强等特点，在很多领域获得广泛的应用。但也存在一些缺陷，主要有以下两点1．与其它的寻优算法相比．ACO算法的搜索时闯过长。一般地，ACO算法的时间复杂度为O(m．矿)(其中m表示循环次数，门为蚂蚁数)，大部分的计算时问被用于解的构造。2．ACO算法的执行过程中容易出现停滞现象，存在陷入局部极小的可能性。具体地说，就是搜索进行到一定的程度后，所有蚂蚁个体发现的解趋于一致，此时，即使采用随机搜索策略，也不能在解空间中进一步搜索，这不利于发现更好的解。原因就在于信息素轨迹更新规则中不被选用的弧段上的信息素轨迹和选中的弧段上的信息素轨迹的差异会变得越来越大，而蚂蚁始终沿着信息素轨迹高的弧段爬行，这就导致当前不被选用的弧段今后被蚂蚁选择的概率变得越来越小，进而使算法只会在某些局部最优解附近徘徊．出现停滞现象。2．4。3蚁群优化算法的改进措施鉴于基本蚁群算法的这些特点，人们提出了许多改进措施：1．蚁群系统ACS是Gambardella等在1996年提出的一种修正的ACO算法(ii0】。ACS与ACO算法的本质区别在于它对蚂蚁寻路的规则进行了一定的调整。ACS中使用了一种状态转移规则来指导蚂蚁最初的寻优过程，同时积累系统当前的状态【⋯】。fargmaxr；·叩；ifqsqo，J★={}e叶tz—18)Jotherwise其中^表示序号为k的蚂蚁下一步要到达的节点，q是一个随机变量，和是预先选定的一个阀值，J是服从概率分布．口：的一个随机变量，掣表示编号为k的蚂蚁在节点i处的可行邻域。状态转移规则的引入可使蚂蚁在进行路径选择时，不仅可以利用前面同伴提供的反馈信息，还可以进行一定程度的随机探索操作。 天津人学博十学位论文第二章智能优化算法介绍f。表示在路径(f，，)上的信息素，玑称之为能见度，是一个局部的启发式函数：口和口两个参数分别决定了轨迹信息素和能见度的相对熏要性。2．具有随机扰动特征的蚁群算法蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。但是，根据式(2．11)．所有通过路段(f，，)的搜索路径对应的候选解均会对该路段带来信息素的增量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引导信息，从而造成大量的无效搜索，使系统出现停滞现象。故可以用可变的扰动因子，使系统跳出局部最优⋯“。策略如下：1)在最初的几次迭代中，为加速算法的收敛。应取较大的转移概率，但如果～直不变必将导致随后的搜索出现停滞现象：2)由此，在随后的搜索过程中仅在最优值路径上保持原来的转移概率，其它路径上则适当减小转移概率，这样一方面可以提高路径选择的多样性(即起到一定的扰动作用)，另一方面可以使收敛趋于平缓：3)同时，为了防止最优的一条路径可能被漏选，故设计如下的扰动策略：只【＆)=‘篡黧嚣协㈣吒㈣引蛐”嚣：嚣：：瑟L@”’。一式(2．19)中，，为具有倒指数的扰动因子：“，P均是(O，1)中均匀分布的随机数。该公式表明：某次迭代过程中某只蚂蚁有若干条路径可选，对于信息素密度最大的那一条路径，应用转移概率公式，而对于其它的可选路径。采用随机选择方式。该公式是确定性选择与随机选择相结合的产物，确定性选择导致蚂蚁总是选择转移系数最大的路径，随机选择导致计算转移系数时具有较强的随机性，正是两者的共同作用彳‘使改进的具有更强的全局搜索能力。3．自适应调整信息素的ACO算法鉴于基本蚁群算法利用随机选择策略，使得进化速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停滞现象。文献[113]通过采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态地调整作确定性选择的概率，当进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态调整，缩小最好和最差路径上的信息量的差距．并且适当加大随机选择的概率，以利于对解空问的更完全搜索，从而可以有效地克服基本蚁群算法的两个不足。算法按照式(2．20)确定蚂蚁k出f转移到的下一城市，： 天津人学博十学位论文第二章智能优化算法介绍argmax(r,,。,(f)砣(f))如果r≤Pof={。"fkn啦(2-20)。I根据概率璐(f)选龌，其它P，r为(0，1)中均匀分白的随机数。当进化方向基本确定后用简单的放大(或缩小)方法调整每一路径上的信息量。实验表明，由于采用自适应选择和动态调整策略，算法的性能明显得到改善，该方法不仅能够加快收敛速度，节省搜索时间，而且能够克服停滞行为的过早出现，有利于发现更好的解，这对于求解大规模优化问题是十分有利的。蚁群算法是一种新型的模拟进化算法，从提出到现在仅经历了十多年的时间。虽研究时间不长，还不像其它的启发式算法那样已形成系统的分析方法和具有峰实的数学基础，但它却具有的正反馈、并行计算和强鲁棒性等许多优点，已经得到了广大学者的普遍认可，并获得了迅速的发展。可以预料，随着研究的深入，蚊群算法将给我们展示一个求解复杂组合优化问题的优秀寻优算法。2．5混沌优化算法2．5．1混沌的基本概念和性质混沌现象虽然已引起学术界的极大兴趣，但“混沌”一词至今还无一个公认的普遍适用的数学定义。有入认为．在不严格的意义上，如果一个系统同时具有对初值的敏感性以及出现非周期运动，则可以认为系统是混沌的。但更多的学者认为，给出混沌的精确定义是相当困难的事情【“41。混沌(chaos)一词首先有李天岩(T|Y．Li)和约可(J。A．Yorke)所提出。1975年他们在美国《数学月刊》上发表了题为“周期3意味着混沌”的文章，并给出了混沌的一种数学定义．现称为Li．Yorke定义。设连续自映射厂：，一，仁R，1是R中的一个区间。如果存在不可数集合Sc，满足：1)s不包含周期点。2)任给定爿。，置∈s(yI≠z2)有timsupl厂’rXlJ一．，1’，zzJ|>0(2-21)⋯limin,["!厂‘rⅣl，一f’rX2J}0(2—22)⋯这罩：．，。¨=／丫．厂r⋯厂(朋，表示l重关系。3)任给定x。∈S及厂的任意周期点P∈，有 天津人学博十学位论文第一二章智能优化算法介绍limsuplf’rxIJ—f’，爿2，【>0(2-23)⋯则称l在s上是混沌的。R．L．Devaney在1989年给出混沌的另一种定义。设Ⅳ是一个度量空间。一个连续映射厂jx呻x称为Ⅳ上的混沌，如果：1)厂是拓扑传递的：2)厂的周期点在x中稠密；3)厂具有对初始条件的敏感依赖性。扼要地说，混沌的映射具有三个要素：不可预测性：不可分解性及还有一种规律性的成分。因对初始条件的敏感依赖性，故混沌系统是不可预测的：因拓扑传递性，它不能被细分或不能被分解为两个在厂下相互影响的子系统。但是，混沌行为中仍有规律性的成分，即稠密的周期点。混沌的基本特征体现在宏观和微观两个方面：宏观上的无序无规律：混沌运动的规律在宏观上观察，呈现出一种混乱、貌似随机、且对初始条件十分敏感。尽管过程是严格确定的，但长期的行为却不能预计，而且像抛钱币那样随机。这种无序无律可分为内凛随机性、非周期性和局部不稳定性三个方面。混池运动中有一个十分明显的特征，即在某些方面对初值的敏感性。洛伦兹曾十分形象的提到“蝴蝶效应”，他说，由于系统在某些参数范围内对初值的敏感性“仅仅由于蝴蝶翅膀的一次萧萧的煽动，就会使得气象学家无法预测下一个月的天气情况⋯51。这种局部不稳定性或对初值的敏感性，有时被用来刻画判定混沌的发生、存在。微观上的有序有规律：混沌运动的另一个基本特征是微观上的有序有规律。通过人们不断的研究发现，混沌运动不是完全的随机运动，它有很深背景下的规律性。这种规律性体现在两个方面：无穷嵌套的自相似几何结构和普适性，混沌系统的吸引子常常是一个自相似嵌套结构。混沌运动不是完全杂乱无章的，它也存在一些普适性．这晕包括两个方面：即结构的普适性和测度的普适性。结构的普适性是趋向混沌过程中轨线的分叉情况与定量特征不依赖与该过程的具体内容，仅与数学结构有关。测度的普适性是指同一映射在不同的测度层次之间嵌套结构的相同。2．5．2混沌优化算法及其改进1．一般混沌优化算法混沌运动具有遍历性、随机性、“规律性”等特点。混沌运动能在一定范围内按其自身的“规律”不重复地遍历所有状态。由于混沌优化方法无须优化问题具有连续性和可微性的要求，又可以在一定范围内遍历求解。有利于找到全局最 天津人学博十学位论文第_二章智能优化算法介绍优解，因此在一定程度上可以克服传统优化方法的缺点【116】。Logistic方程(2．24)与其他产生混沌变量的动力系统相比简单、计算量小、使用方便，所以本文采用此方程来构造混沌序列。X⋯=∥。(1一x。)(2-24)已经证明方程(2-24)中／J∈【3．57，4】时系统处于混沌区域，在此区间内方程运动轨迹表现出混沌特性。所以当∥的取值为4时，z的轨迹为混沌轨迹。利用混沌运动对初值敏感的特点。对给定的目标函数设一类连续对象的优化问题为min厂(x)(2·25)其中X∈Rn，并且x，∈【日，，6J】。混沌优化方法的基本步骤如下：步骤1：算法初始化，置k=l，k’=1；对2．1式中的x。分别赋予f个具有微小差异的初值，则可得到i个轨迹不同的混沌变量t。。步骤2：通过(2-26)式用载波的方法将选定的f个混沌变量t。分别引入到(2-25)式的f个优化变量中使其变成混沌变量工’。m并将混沌变量的变化范围分别“放大”到相应的优化变量的取值范围。rt,n+l=f，十dix。l(2-26)其中c，，d，为常数，相当于“放大”倍数，(2-3)式为代数和，步骤3：用混沌变量进行迭代搜索令x，(女)=z。。+一计算相应的性能指标，(．i})，令_‘=Xi(0)，f+=f(0)If，(t)≤．厂’then厂’=．f(々)，薯‘=t(女)Elseif，(k)>厂then放弃x，(七)k=k+1步骤4：如果经过步骤3若干步搜索，’都保持不变，则按(2．27)式进行第二次载波。x+¨，+l=x，’+d，工¨什I(2-27)其中ajx，，。为遍历区间很小的混沌变量，口，为调节常数，可以小于l，t+为当前最优解，反之，返回步骤3。步骤5：用二次载波后的混沌变量继续迭代搜索。令xi(F)=x+。一计算相应的性能指标，(女’)Iff(☆‘)≤厂‘then．厂‘=，(女‘)，一‘=一(女。)Elseiff(^’)>厂’then放弃x，(膏‘)k’=k’+l步骤6：如果满足终止判掘则终止搜索，输出最优解t‘，f’反之返回步骤5。 天津人学博十学位论文第二章智能优化算法介绍2．混沌优化方法的改进在混沌优化方法中，针对混沌变量遍历范围内的某些状态需要很长时间才能达到的问题，算法采用了两次载波搜索来减少搜索时间。第一次载波搜索使算法在较短时』_白j内找到一个近似最优解(常位于全局最优解的邻域内)：第二次载波在近似最优解的邻域内进行细搜索，最终得到最优解。但是，对于一些优化变量很多、搜索范围很大的优化问题。如神经网络的训练问题，第一次载波探索很难在较短时问内到达最优解附近，使搜索效率大大降低，甚至难以找到最优解。为此我们对混沌优化方法进行了改进；不再采用两次载波，而是在每一步混沌搜索之后，在当前最优解的邻域内用随机搜索进行一定范围的细搜索，使搜索效率得到提高【¨71。改进后的混沌优化方法的具体步骤如下：步骤1．算法初始化。令仁l，产生i个轨迹不同的混沌变量‘。步骤2．拜j载波的方式将选定韵f个混沌变量分蹦引入到j个优化变量中，使其变成混沌变量，同时根据各优化变量的取值范围，将混沌变量的变化范围分别“放大”到相应的优化变量的取值范围。如式(2-28)所示。xi,n+t=c，+d。x⋯l(2—28)其中c，d，为常数，相当于“放大”倍数。步骤3．用混沌变量进行迭代搜索。令石，(Ji})=x。。+·计算相应的性能指标，(女)，令x。’=x，(O)，f’=f(o)If，(≈)≤．厂+then．厂‘=fA／O，X，’=x，(七)Elseif，：(七)>厂’then放弃t(七)end步骤4．在x’附近用随机扰动的方法进行n步细搜索。x，(H)=x．’+l(厅)(2—29)其中r(H)为随机扰动。计算相应的性能指标f(n)。If，(疗)≤厂‘thenf+=厂(抖)，葺’=t(H)Elseif．f(n)>．f‘then放弃x，(")end步骤5．如果k=k+I满足终止判据，则终止搜索，输出最优解x，‘，f’：反之，则返回步骤3。2．5．3混沌优化的Markov链描述和收敛性分析下面我们根据有关的Markov链理论对引入随机搜索后的混沌优化方法的收敛性进行分析。从算法的机理可以看出，算法在搜索过程中实际上包含着两种 天津人学博十学位论文第二章智能优化算法介绍搜索方式，每一步迭代都包含着步骤3的混沌搜索和步骤4的随机搜索，其中混沌搜索是搜索的主线，随机搜索是搜索的辅线。步骤3的混沌搜索始终按混沌变量自身的规律进行，因而仍具有遍历性。因此，算法具有全局渐近收敛性的关键在于步骤4的随机搜索也具有遍历性。步骤4随机搜索的过程为一随机过程．在搜索过程中每次搜索的结果仅与前一次搜索的结果有关，因此搜索过程可用Markov链来描述⋯”。而且实际搜索过程中所搜索的状态是一个个离散的状态，在一定的优化精度下相当于按一定的精度要求对其进行离散化处理，所以其状态空间可以看成有限状态空问，可以用有限Markov链描述。定理2．5．3．1描述随机搜索的Markov是齐次和不可简约的。首先，在随机搜索过程中，转移概率只与搜索状态所处的位置有关，而与时刻川无关，即对任意状念■，，其转移概率P．，=(所，m+≈)=P{x(m+七)=JIx(m)=i}(2-30)因此．描述随机搜索的Markov链是齐次的。其次，在随机搜索过程中对任意状态i，J，必然存在_|2≥l，使尸，，(月)>0，只．．(n)>0。所以状态i可达状萄，状萄可达状态“即状念f’．，是连通的。而由一个连通的状态类组成的Markov链称为是不可简约的，因而描述随机搜索的Markov链是不可简约的。定理2．5．3．2描述随机搜索的Markov链只有正常返状态。证明由于随机搜索过程可用有限Markov链来描述，且定理1中已经证明了描述随机搜索的Markov链是不可简约的，因此整个状态空间构成唯一的闭集。由于非常返状态集不可能是闭集，所以描述随机搜索的Markov链只能由正常返状态组成。定理2．5．3．3描述随机搜索的Markov链是非周期的。证明在随机搜索中，每一步的搜索方向都是随机产生的，其下一个状态只取决于当前状念及随机扰动。对任意状态f，不存在一个d>l，使除n=d，2d，⋯，之外的一切只，(月)=0，所以描述SA，GA，CIA，的Markov链是非周期的。定理2．5．3．4描述随机搜索的Markov链是遍历的。证明由于描述随机搜索的Markov链具有非周期，正常返状态，因此根据有关定理可知，对任意状态，有憋只。(一)2瓦1(2-31)对于一个不可简约的Markov链，如果它的状态是非周期正常返状态(Ⅳ．(T。：2×T“”2×T。；2×T州2×Tlj2×T孙3×T¨。2XTm一联绗情况l×T．I×T．；2×T。。2×T¨．2×n--3×Tm一l×Tj”2×T¨l×Toi2×T．”3×T”ⅧIXTL‘41×Ti⋯3×T⋯2·Ⅱ辊性水99．992099994899993299．993699．993399．993499．993899995899．993099．996099．9909999946平(ASAI】建议贽川i55．53185．63225．76210．'7122：5．76160．54165．56195．66160．：54240．82150．5l230．78(J』元)停屯挂失29．79224．57639．40835．19337．68325．57925．45l19．12031．50324．33236．97531．472(Ⅳ元)图4—10格尔木地区手拉手接线模式联络线总体布局图4-1l格尔木地区两分段两联络接线模式联络线总体布局 大津人学博{：学位论文第四章配电网络变电站联络线总体规划在格尔木配电网络联络线规划中，手拉手接线模式下，当站间负荷转移比例为表4．22时，配电网络折算为年的总费用为2813．5万元，其中建设费用为2136．1万元，停电损失为677．39万元；两分段两联络接线模式下，当站闯负荷转移比例为表4．23时，配电网络折算为年的总费用为2850．6万元．其中建设费用为2307-8力I元，停电损失为542．83万元。可见，当前负荷密度下(10．44MW／km2)，采用手拉手联络接线模式并且站问负荷转带比例如表4．22所示时，配电网络的联络线总体舰划结果最好。4．5小结本章根据蚁群算法最适合寻找最小路径的特点，以变电站闻的距离、变电站富裕容量以及路径上的信息素为启发因素，运用蚁群算法(ACO)计算了在一定负荷密度和配电变电站间负荷转带比例下。考虑不同接线模式时的站间联络线优化问题，并提出了相应的解决方案。在配电网络联络线规划过程中，站闻转带负荷比例是平衡配电网络建设费用和停电损失的一种体现。在寻找站间转带负荷最优比例时，往往又需要确定站间联络线优化接线问题，此优化过程是一个菲常耗时的双重优化难题。本章还以边际供电总成本最小为目标函数，运用快速高效的粒子群优化算法解决变电站负荷转带比例的优化问题，结合蚁群算法对站闽联络线的优化．最终形成配屯网络变电站联络总体规划方案。 天津人学博十学位论文第五章配屯网络重构5．1引言第五章配电网络重构配电网络重构就是在保证配电网络呈辐射状、满足馈线热容、电压降落等要求的前提下，确定一种配电网络最佳的运行方式，使配电网络的某一指标(线损、负荷均衡或供电质量等)达到最优。正常条件下，配电调度员根据运行情况进行丌关操作柬调整网络结构．一方面平衡负荷，消除过载，提高供电电压质量：另一方面降低网损，提高系统的经济性。在发生故障时，隔离故障，缩小停电范围，并在故障后迅速恢复供电。如图5．1所示，配电系统中一般有两种类型的开关：联络开关和分段开关，虚线表示的支路上装有联络开关，而其它用实线表示的支路上装有分段开关。当运行方式改变时，通过打开或闭合联络开关和分段开关，把负荷成功的由重负荷支路转移到轻负荷支路上，以平衡各支路负荷，提高电能质量，减少线路损失。以图5．1为例，肖馈线3上的负荷在正常运行条件下变为重负荷时，联络开关2l被合上以将节点14上的负荷从馈线3转移到馈线2．同时打开分段开关24以维持配电网络的辐射状网络结构。从馈线来看，有两种重构类型，一是馈线内重构，重构时负荷在同一条馈线内转移：二是馈线闯重构，重构时部分负荷从一条馈线转移到另一条馈线。从电源来看，重构又可分为单电源重构和多电源重构，单电源重构时，负荷在同一电源下的同一馈线或不屙镄线嘲转移；多电源重构时。负荷在分属不同电源的馈线之间转移。图5-1IEEE三馈线系统 天津人学博十学何论文第五章配电网络重构配电网络重构是1975年由英国人A．Merlin和H．Back在文献【ll】中首次提出，并用枚举法将开关一个个打开、关闭，不断进行潮流计算。随着研究的不断深入，基于各种物理和数学的重构方法都得到了发展。由于配电网络中存在着大量的丌关，寻找基于这些开关闭合状态的最优网络拓扑结构将面临“组合爆炸”的问题。虽然数学优化方法如单纯形法、分支定界法、网络流法和Benders法等具有严格意义上的最优性，但是这类方法在解决上述问题时受到计算复杂度的困扰，即面临“维数灾”1139]。启发式方法，如支路交换法(BEM)和最优流模式算法(OFP)．其计算速度有了极大的提高，但是最终收敛性仍然取决予网络初始结构，缺乏数学意义上的全局最优性【l柏】。专家系统和人工神经网络方法在解决此类问题时，对约束条件的考虑比较困难，且无法保证最后所得的解是全局最优解¨4“。模拟退火算法(SA)是一种基于热力学的退火原理建立的随机搜索算法，虽然在理论上证明是一种以概率l收敛到全局最优解的全局优化算法，但是该类算法的参数难以控制。并且由于其巨大的计算量，往往不能适应于实际应用中【l”J。遗传算法(GA)是模拟生物进化过程的计算模型，由于其内在的隐含并行性和整体搜索策略以及优化时不依赖梯度信息的特点，遗传算法在解决组合优化问题上有着广泛的应用。但是，遗传算法在应用中也存在着一些问题，如遗传操作中会产生大量不可行解，编码或参数设嚣不当容易发生早熟现象以及局部寻优能力较差等不足【14”。如何根据遗传算法的特点，结合一些局部搜索能力强的其它算法。是近期以来众多学者研究的热点。很多学者研究发现．如果将遗传算法同其它算法集成到一起构成混合算法，往往能够提升算法的寻优性能【1“叫舶】。本章提出改进禁忌搜索和混合粒子群遗传算法解决静态以及动念配电网络重构问题。在改进禁忌搜索中，根据配电网络独有的特点采用基于环路的遗传编码方式，并运用禁忌搜索独特的邻域结构设计，保证了算法的全局收敛性能。在混合粒予群遗传算法中，利用粒子群优化算法较强的局部寻优能力．在进化过程中运用粒子群优化和遗传进化两种搜索机制，并且采用整个群体信息共享的策略，进一步提高遗传算法的寻优性能和计算效率。5．2网络重构的数学模型5．2．1静态网络重构的数学模型如Iji『所述，配电网络重构的主要目的是降低网损、消除过载、平衡负荷、提高电能质量和供电可靠性，这些目标相互联系、影响，却又不完全一致。目前，配电网络重构基本上是以网损最小为目标函数，也就是确定配电网络中哪些联络开关需要闭合、那些分段开关需要打开，以使最终的网络具有最小的线路损失， 大津人学博十学亿论文第五章配电网络重构可用数学公式描述如下：毗一=薯，，并厶为线路总数：r为支路电阻；尸为有功功率；9为无功功率；”l为功率注入节点J的电压幅值。同时配电网络重构应当满足如下的约束条件：1)配电网的潮流约束∑函6^=Load，+∑Loss，Sub。为变电站k的复功率；Load，为节点．，的负荷；Loss，为支路i的功率损耗：n为变电站个数；m为节点数；2)容量约束』，S，。，kl，⋯，L，，，为流过元件的电流；，。伪元件的最大允许通过电流；￡，为元件数。3)电压约束％s¨≤KIj=l，⋯，N■为节点_，的电压：_，为节点，的电压下限；‰为节点，的电压上限；Ⅳ为节点数。4)辐射状运行约束g，∈G，，g。表示当前的网络结构；G。表示所有允许的辐射状网络配罱。5)丌关操作次数约束(5-1)(5-2)(5·3)(5-4)(5—5) 天津人学博十学位论文第五章配电网络重构N二≤N二。。，z∈S(5-6)M是第z个丌关的动作次数；M。。是第z个丌关的动作次数上限；S为所有丌关组成的集合。5．2．2多时段动态网络重构的数学模型上述基于单时制断面方式进行的静态网络重构，寻优的目标函数只能是该时阳J断面下的目标最优，考虑的约束条件也都是该时间断面下的静态约束，这在很大程度上限制了配电网络重构的应用功能和范围。实际配电系统线路上供应的负荷是动态地随时问发生变化的．这既有用电方式改变引起的动态变化，也有事故方式导致的动念变化l¨71。为了在负荷动态变化过程中更好地保证配电系统的安全、优质、经济运行，常常需要对配电网络结构进行动态调整，即需要进行动态重构。综合考虑网损和丌关操作费用使配电网在一段时间(T=tt-to)内收益最大的目标函数表示为maxF=11c(，)(R(f)一只p))斫-K(T)S(5·7)c(t)为在7、时刻的电价；只(t)为在tI时刻的网损：Bo(f)为在to时刻的网损；K(T)为在时段r内开关总的操作次数；s为每次开关操作的费用。第一项表示通过网络重构在时段r内节约的能量损耗费用，第二项表示开关操作费用。在整个时间段r内应满足同静态网络重构相同的约束条件。数学上(5-7)为目标考虑的配电网络重构属于动态优化问题，处理该类问题的一般解决方法是分时段静态优化．即认为在各时段内负荷保持不变，分段越多就越逼近最优解。但分段越多，要求开关设备的动作次数也就越多，然而-丌关设备有一定的使用寿命，频繁的动作无论从经济上还是技术上都不切合实际。由此可见，在实际应用中静态优化的时I训段不能分得太细。按照上述思想．假设将时段(7=f厂靠)划分为M个小时间段，每个时间段的长度为A71，，则将式(5-7)离散化后可得．!LmaxF=∑C，(异，一只，)△I—K(T)S(5-8)J。l至此，网络重构的动态优化问题简化为几个静态重构优化问题的合成，但总 天津人学博士学位论文第五章配电网络重构体问题的优化解并不是静态问题解的简单叠加，这主要体现在下一个时间段的重构是在上一个时间段网络重构的基础上进行的，前后时间段之间互有联系。5．3网络重构的计算方法5．3．1编码方式编码是应用遗传算法时首要解决的问题，也是设计遗传算法时的一个基本步骤。编码方法除了决定个体的染色体排列形式之外．还决定了个体从搜索空间的基因型变换到解空间的表现型的解码方法，另外，编码方法也影响到交叉算予、变异算子等遗传算予的运算方法。可见．编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率，一个好的编码方法会使得遗传进化运算简洁有效；而一个差的编码方法可能会导致交叉运算、变异运算等遗传操作难以实现或产生大量的无效解。在配电网络重构问题中，遗传编码的好坏对算法寻优效率的影响尤为明显。许多文献将网络中的丌关状态用0和】表示，每个开关占掘染色体的一位，0代表丌关断丌，l代表开关闭合。各个开关状态组合在一起就形成了一条染色体，染色体的长度为配电网络中所有开关的数量。这种方式简洁明了，较二进制编码方式有了很大的提高。但是这种编码方式没有充分利用配电鼹终的特点，并且在运算过程中会产生大量的无效解，严重影响了算法的效率。如图5一l中的配电网络．一共有16条支路，如果单纯以支路开关的状态来编码，则解空间会产生2”=32768组解，而实际问题的有效解空闻只有190组解。有效解只占问题空间的0．5798％．可见如此编码其搜索效率是非常低的。因此．在选择染色体时必须注意到配电网的如下性质：在整个配电网中，相对于常闭的一般丌关而言．联络丌关占较小的一部分，且当任意1个联络开关闭合时，在配电网中必然产生环啜，为了保持配电网树状运舒，只需把粗应环网中的分段玎关断丌。根据此特点，本文以联络开关数量为染色体长度，环路开关号为染色体内容编制染色体¨4s．I。在图5-1的基础上增加了环路信息后如图5．2所示：闭合联络丌关15、21和26会产生一系列环网，选择其中支路最少的三个环网为基本候选单位。如图环路l包含的丌关集合为{ll，12，15，19，18，16)；环路2包含的支路集合为{16+17，2l，24，22}；环路3包含的支路集合为(1l，13，14，26，25，23，22}。染色体的基本构成原则是3个环路中分别选择一个支路丌关组成一个初始的染色体，比如12121114。就是一个候选染色体。编码后初始染色体的搜索空间的解有Ci+C：+d=210个，有效解占问题空间的90．476％，可见采用此编码 天津人学博十学位论文第百章配电网络重构方式极大提高了算法的搜索效率。在上述基于环路的编码策略中可见，支路开关I1属于环路】和环路3的公共支路开关并且直接连接电源，如果断丌此支路显然不是一个合理的选择，因而此类公共支路开关不设置为染色体编码范围之内。进一步精简后，环路l包含的开关集合为{12，15，19，18)：环路2包含的丌关集合为{17，2l，24}；坏路3包含的丌关集合为{13，14，26，25，23)。精简后搜索空间为4×3×5：60．100％为有效解。精简后搜索空间虽然没有覆盖整个的问题空间。出于去除了一些明显的不合理的玎关组合状态，因此不影响算法的全局寻优性能。图5-2具有环路信息的IEEE三馈线系统5．3．2改进的禁忌算法禁忌算法具有灵活的已忆功能和藐视准则，且在搜索过程中可以接受劣解，具有较强的“爬山”能力，搜索时能够跳出局部最优解。转向解空问的其他区域，因此它是一种局部搜索能力很强的全局迭代寻优算法。本节首先从邻域的定义出发，结合5．2．1的编码策略，对改进禁忌搜索算法(RefinedTabuSearch，RTS)的邻域结构、适应函数、禁忌长度、候选解集、藐视规则和终止判据等方面进行详细的设计和说明。定义l：V集合肖={xl工=毛，z2，⋯，L}，Xj∈R，称Mr(_)=协翌(5．9)lX．1=月Me(Xi)=学篙O-lo)分别为当fill,点X，的“向甜移动操作”和“向后移动操作”，同时肘，(茗，)和M。(x，)也称为点x，在集合x中的一维向前邻域和一维向后邻域，分别记为w，(x，)和Ⅵ(x，)。 大津人学博十学位论文第五章配电网络重构定义2：Vx∈R“．并且而为x的第i个分量，称0I'X2，⋯，工川，ws(xt)，xHl，⋯，Xn)为x在而的一个向前邻域，已为B．1(工)。称Ol'X2。⋯，Xi-I，Wb0『)，Xi+l，⋯砧为x在』f的一个向后邻域，记为丑。，(J)。称&(x)=B啊(工)u％，0)为x在赫的一个邻域集合。定义3：Vx∈R”，并且而为x的第i个分量，称Q(z)={B，O)li-1，2,---,丹)为羔的邻域集合。邻域结构：在禁忌搜索过程中，如何确定搜索空间(状态空间)是决定算法效率的关键，根掘具体问题的特点设计出的优化变量。在优化过程中会有更高的搜索效率。禁忌搜索的每一个新的状态都是通过根据当前点在其邻域的“移动”操作产生的。禁忌搜索是局部邻域搜索的一种扩展，因此“移动”和邻域结构的设计非常关键，它决定了当前点的邻域解的产生形式和数目，以及各个解之间的联系。下面将根据图5．2为例，来说职对邻域结构的定义。图中含有3个环路，根据5．2．1的编码方式，即染色体的表现形式为∽l’册2，m3)，其中环路l(m1)的开关集合为{12，15，19，18}；环路2(m2)的开关集合为{17，21，24}；环路3(m3)的开关集合为{13，14，26，25，23)。设优化变量的当前状态善=(15，21，26)，第一个分量Xl的向前邻域B托(x)=(12，21，26)．向后邻域％．(x)=(19，21，26)。可见，x在Xl=15的一个邻域集合为{(12，21，26)，(19，21，26)}。分别对优化变量中的三个分量进行“移动”操作．就产生了一个初始的邻域集合fl(x1。初始邻域集合中满足配电网约束的元素构成了当前点有效的邻域集合赋工)埘。。。由前文定义以及文中设计的邻域结构可见，本文的邻域结构是对称的，即：如果x是Y的邻域，则J，也是X的邻域。此外，根据配电网的运行特点，网络拓扑结构必须是连通的，没有孤岛存在，因此本文提出的方法满足了第二章2．2．4的两个假设。从而保证了算法的收敛性。适应函数：禁忌搜索的适应函数是对于搜索状态的评价，进而结合禁忌准则和藐视规则束选取新的当前状态。可见．目标函数直接作为适配函数是比较容易理解的做法。网络重构的目标函数如式(5-1)，属于极小值优化问题，综合考虑到约束条件，本文采用的适应度函数为r—jL—x一，J‘c一、rE一11、‘10其它⋯“式中c。。、为以给定的常量，，为综合考虑网络和约束条件后的函数，表达为．f=^一．十∑口，+(，，-1巾。)2+∑反’(圪一■。)2(5—12)pItcI式中的第一项疋。的函数表达式见式(5-1)；第二项为违反容量约束的惩罚函数：第三项为违反电压约束的惩罚函数。8l 天津人学博十学位论文第五章配电网络重构禁忌长度和候选解集：禁忌长度和候选解集的大小是影响禁忌算法性能的两个重要参数。深度越大，搜索的效率越高，但是最终的结果可能越差。反之t减小禁忌表的深度，虽然有可能找到更优良的解．但是降低了搜索效率。如果表的深度过浅．还可能使迭代陷入循环。一般而言，当算法的性能动态下降较大时，说明算法当前的搜索能力比较强，也可能当前解附近极小解形成的“波谷”较深，从而可以设计较大的禁忌长度来延续当前的搜索行为，并避免陷入局部最小。禁忌表的深度一般情况下应随问题规模的增大而增大。候选解集一般在当前状态的邻域内选取，但选取过多将造成较大的计算量，选取过少则容易造成早熟现象。通常，邻域解规模越大则适当增加候选解的个数。藐视规则和终止判据：在禁忌搜索过程中，可能会出现～个优于“bestSOfar”状态的禁忌候选解，此时藐视规贝0将会使此状态解禁，以实现更高的优化性能。随机组合类算法常采用的一种退出迭代的判定条件为：是否达到预定的最大迭代次数，而这种预定的最大迭代次数一般是根据经验给定。显然，迭代次数的多少应与寻优问题舰模有关。凭经验给定最大迭代次数可能会产生两类问题：一是优化过程早已达到最优解，但是没有达到最大迭代次数，优化过程还要做许多次不必要的迭代计算：二是，优化过程已经达到最大迭代次数，但是尚未达到最优解就退出优化过程。兼顾搜索质量和效率，本文采用的终止判据是给定最优状态连续保持不变的最大持续迭代步数厶。。，其具体大小视问题的规模和难度而定。综上所述，基于改进禁忌搜索的配电网络重构的流程如图5．3所示。设置算法胡始参数，设置禁总表为空随机产生初始解N由当前解乖I配电网络的环路数M，根据对私域结构的殴计．产生2M个邻域解，并庄式(5．13)计算并邻域解的适应度候选解集、肖前禁总袭及藐视准则确定F一个解为当前解。井更新蔡总表满足收敛条件?F—r一输出计算结果图5-3改进禁忌搜索重构的流程 大泮人学博十学位论文第五章配电网络重构5．3．3混合粒子群遗传算法遗传算法(GA)将问题的求解表示成“染色体”的适者生存过程，通过群体的世代进化．包括复制、交叉和变异等操作，求得问题的最优魍或满意解。粒子群优化算法(PSO)模拟社会的群体行为，每个个体通过统计迭代过程中自身和群体发现的最优位置修正自身的寻优方向和速度．从而寻得最优解。GA和PSO在以下方面有相同之处：a)采用多点搜索策略；b)以适应值作为搜索的依据；C)进化(迭代)均是在前一次的基础上进行的。在GA中，每当新的一代产生，上一代的很多有价值的信息被抛弃。同GA相比，PSO具有简单、灵活、有记忆性的特点，但是在全局收敛性方面较GA差。结合GA和PSO各自的优点和相同之处，本小节提出一种混合的遗传粒子群算法(HybridGAandPSO，HGAPSO)。在HGAPSO寻优过程中，部分个体以粒子群优化的搜索策略寻优，部分个体以标准的遗传操作迸化，只有适应度值高的个体才有机会进入下一代寻优，整个群体的进化信息共享，这样既遗传进化中有价值的信息，提高了粒子群的搜索效率，又能保证算法的全局收敛性。下面说明混合算法几个主要方面的设计情况，HGAPSO的主要流程如图l图5—4HOAPSO算法主要流程适应度函数：适应度函数的适应值是遗传算法和粒子群算法指导搜索方向的重要依据，因此在寻优的过程中构造一个合适的适应度函数非常重要。本算法的适应度函数的设计同前一小节改进的禁忌搜索的适应度函数相同，具钵见式(5．11)和(5-12)。 大津人学博十学位论文第五章配吨网络重构交叉和变异的自适应调节：在遗传进化过程中，交叉操作采用随机定位、两点交叉的方式。在进行变异操作时，首先随机选定要变异的基因，然后在此基因所对应环路丌关集合中随机选定一个其他开关柬替换作为当前基因的开关。遗传算法参数中的交叉率和变异率的选取是影响算法性能的关键．目前普遍采用自适应交叉率和变异率的调节策略。第pl代的交叉率和变异率如下式：P。(f+1)=l，似×．厂(啪P。(，+1)=l／(卢×厂(r))其中口：交叉因子权重：口：变异因子权重：f(t)：适应度平均值。惯性权重法对粒子群算法进行改进：在本次混合算法的PSO中采用Shi等提出的惯性权重法改进粒子群体的搜索策略．粒子群体更新方程如下：V，1w¨。+c,rand?(p。be、st：一《)+(5-13)c2rand；(gbest：一或)x}‘=《+v譬‘(5．14)通常．权重系数W由下式来确定w=‰一监选×ite，iter,na、f5—15)w‰，H。分别是w的最大值和最小值；iter，iter。。分别是当前迭代次数和最大迭代次数。粒子群对染色体的操作：在HGAPSO算法中，粒子群体的寻优是通过对染色体的基因操作来完成的。粒子群体的寻优速度根据当前染色体分别由局部最优染色体和全局最优染色体的丌关位置决定。仍以图5-2为例，此配电网络中有三个环路，其中环路1的丌关集合为{12，15，19，18)；环路2的开关集台为{17，21，24)：环路3的玎关集会为{13，14，26，25，23}。假设当前点对应的染色体为15121126，局部最优解和全局最优解对应的染色体分别为19|21125和12}21126。则当前点和局部最优点距离矢量有三个分量。第一个分量的计算过程为：在环路l开关集合中查看丌关15和丌关19的相对位置．计算从丌关15需要几个基本步或逆步翻‘能到丌关19，这罩一个基本步为开关右移一位．逆步为开关左移一位，基本步的单位为1，逆步的单位为一l。因此上述空间两点距离矢量的第一分量为1。同理其它两个分量分别为O和l，所以当前点同局部最优点的距离矢量为(1，0．1)。根据以上的距离矢量产生方式，同样可以计算出蘸点圆全局最优点的距离矢量为(一l，O，0)。计算出上述各点的距离后，再根据式(5一13)和(5．14)就可以计算 大津人学博十学静论文第五章配电网络重构出各个点的寻优速度和位置．再经过进一步的进化，从而找到最优解。其它策略：为了确保算法的收敛性，算法中采用最佳个体保留策略如下：在进化过程中．当前最优个体不经过交叉、变异等操作直接进入下一代。在算法终止条件方面．本文综合考虑群体平均适应值同最大适应值的接近程度是否小于给定误差以及当自U进化代数是否达到最大进化代数。基于HGAPSO配电网络重构的计算步骤如下：步骤1：设置初始参数：混合算法中的种群数量触。。(设定遗传算法种群数量Naa，粒子群算法种群数^钿，使M。=^b+％。)，遗传算法中的各种参数设置，粒子群算法中的各种参数设置：步骤2：随机初始化遗传算法和粒子群算法的种群：步骤3：计算当前种群的适应度．并找出当前种群中适应度最高的解作为当前全局最优解；步骤4：根据步骤3的计算结果，令适应度高的一半个体存活。淘汰其它适应度低的个体：步骤5：步骤4中存活的个体分别进行遗传进化和粒子群搜索；步骤6：如果满足收敛条件，则输出最终结果．如果不满足．则转到步骤3。5．4算例分析5．4．1静态网络重构分析1．IEEE．16节点3馈线测试系统(如图5-2)额定电压为23KV，有16个节点，16条支路．3个联络开关{t5,21,26)，总负荷为29．7十j17．3(MVar)。改进禁忌搜索算法(RTS)中算法参数设置为：邻域解个数设为6，候选解个数设为3，初始禁忌长度设为4，收敛判据厶。设为4，目标函数中的C。。。耿2000。混合粒子群遗传算法(HGAPSO)中算法参数设黄为：种群数量设为20，其中GA种群数设为10，PSO数量设为lO，染色体长度设为3，最大进化代数设为100，目标函数中的c一取2000。分别用遗传算法、粒子群算法、改进的禁忌搜索算法以及混合粒子群遗传算法对此算例进行计算，计算结果如表5．1所示。网络重构以前，网络状态为三个联络开关15，21和26打开，其它分段开关闭合．此时系统网络损耗为521．36KW，最低电压发生在节点12，其标幺值大小为0．9702；重构后，网络的结构为开关19，17和26打开，其它开关闭合，此时系统网络损耗降低了9．54％。为471。62KW．最低电压仍然发生在节点12，其标幺值大小为O．975l，提高了O．5％。三条馈线所带的负荷分别由9．5+j5．1MVar， 天津人学搏十学位论文第五章配电网络重构15．1+js．7Mvar和5．1+j3．5变为10．1+j5．2，13．5+j7．7和6．1+j4．4。可见，网络重构在降低网络损耗和负荷均衡方面效果明显，对电压质量的提高也有一定帮助。表5．1不同算法的重构结果表首次发现最优解的掉法耗_}I；j时间(秒)采Ⅲ算法计葬的晟优解重构屙的网损(Mw)迭代次数GA191171260．471621520．4PSO19117[260．47162248．3HGAPSO191171260．47162lO4．1RTS19}171260．4716261．2IEEE一16节点测试用例中，上述几种算法的寻优性能比较如表5—2所示，表中的数据为100次测试中收敛到全局最优解的次数。不同算法中最佳适应值曲线以及RTS和HGAPSO的动态搜索曲线分别如图5-5．图5-6和图5-7所示。表5．2几种算法的寻优性能比较测试系统GAPSOHGAPS0R，rSIEEE-16¨点9890100lOO图5，5IEEE．16节点几种算法最佳适应值动态曲线 天津人学博十学位论文第五章配电网络重构图5—6IEEE一16节点RTS当前适应度值和最佳适应度值动态曲线图5．7IEEE．16节点HGAPSO平均适应度值和最佳适应度值动态曲线从表5～1和5—2可见，IEEE．16节点测试用例中，RTS和HGAPSO具有良好的收敛特性，其中RTS无论在计算时问还是在收敛性能上均优于其它几种算法，这主要是因为禁忌算法本身具有很强的局部搜索能力，结台本文独特的邻域结构设计，馒RTS在配电网络重构上的全局收敛方面有了理论依据。两HGAPSo结合了GA和PSO两种算法的优点，在解决配电网络重构问题上，也显示了相当卓越的性能。 犬津人学博十学位论文第五章配电网络重构2．IEEE．33节点测试系统(如图5-8所示)是一个额定电压为12．66KV的配电网络，有33个节点，37条支路，5个联络开关{33，35。34，37，36}，总负荷为3．715十j2．3MVar。在计算过程中，改进禁忌搜索算法(RTS)中算法参数设置为：邻域解个数为10。候选解个数取5，初始禁忌长度为5，收敛判据拓。。。为6，目标函数中的C。。取1500。混合粒子群遗传算法(HGAPSO)中算法参数设置为：设置种群数量为30其中GA种群数为15，PSO数量为15，染色体长度为5．最大进化代数为100，目标函数中的C～取1500。分别用遗传算法、粒子群算法、改进的禁忌搜索算法以及混合粒子群遗传算法对此算例进行计算，计算结果如表5．3所示。⑧图5．81EEE．33节点测试系统图网络重构以前，网络状态为五个联络开关33，34，35，36和37打开，其它分段开关闭合．此时系统网络损耗为206．68KW，最低电压发生在节点17，其标幺值大小为0．91336；重构后，网络的结构为玎关7，9，14，32和37打开，其它开关闭合．此时系统网络损耗为141．60KW．降低了31．49％，最低电压发生在节点3l，其标幺值大小为0．938．提高了2．7％。可见。IEEE．33节点测试系统中，网络重构在降低网络损耗和提高供电电压质量方面效果明显。 大津人学博十学位论文第五章配电网络重构表5．3IEEE．33节点不同算法的重构结果表首次发现最优解的采刚算法计算的最优解噩构后的网损(kW)算法耗用时间(秒)选代次数141．60GA7191141371322l40．4141．60PS071911413713228l8．3141．60HGAPSo719114137132128．1141．60ItTS71911413713282．8相比IEEE一16节点的测试系统，IEEE一33节点测试用例的开关数、支路数以及环路数都要多～些，规模稍微大一些．所以在计算时间上要稍微长～些，但总体来看，RTS和HGAPSO性能优越．计算时间短．寻优效率高。由于计算量以及算法的寻优机理方面的原因，GA计算最为耗时。上述几种算法的寻优性能比较如表5—4所示．表中的数据为100次测试中收敛到全局最优解的次数。不同算法中最佳适应值曲线以及RTS和HGAPSO的动态搜索曲线分别如图5-9，图5．10和图5．1l所示。表5-4IEEE．33节点几种算法的寻优性能比较测试系统GAPSOHGAPSoRTSIEEE．33测试系统9685100图5-9IEEE-33节点几种算法最佳适应值动态曲线 大沣人学博七学位论文第五章配屯网络重构图5—10IEEE一33节点RTS当前适应度值和最佳适应度值动念曲线图5．11IEEE．33节点HGAPSO平均适应度值和最佳适应度值动态曲线3．IEEE．69节点测试系统(如图5．12所示)也是一个额定电压为12．66KV的配电网络，有69个节点，73条线路．5个联络开关{69，70，71，72，73}，总负荷为3802．2+j2694．6KVar。改进禁忌搜索算法(RTS)中算法参数设置为：邻域解个数取lO．候选解个数取5．初始禁忌长度取5，收敛判据如。取lO，目标函数中的c。。取1500。混合粒子群遗传算法(HGAPSO)中算法参数设置为：种群数量设为40，其中GA种群数设为20，PSO数量设为20。染色体长度设为5。最大进化代数设为100．目标函数中的C⋯取1500。分别用遗传算法、粒子群算法、改进的禁忌搜索算法以及混合粒子群遗传算法对此算例进行计算，计算结果如表5-5所示 大津人学博十学位论文第五章配电网络重构’6o。1@图5一12IEEE．69节点测试系统图网络重构以前，网络状态为三个联络开关69，70，7l。72和73打开，其它分段开关闭合，此时系统网络损耗为230．84kW．最低电压发生在节点54，其标幺值大小为0．909：重构后，网络的结构为开关69，14．55，72和6l打开，其它开关闭合，此时系统网络损耗降低了49．05％，为103．86KW。最低电压发生在节点50，其标幺值大小为O．9425，提高了3．69％。可见，网络重构在降低网络损耗，提高供电电压质量和负荷均衡方面效果明显。表5．5IEEE。69不同算法的重构结果表首次发现最优解的采Hj算法计算的晟优解重构后的网损(kw)算法耗川时间(秒)迭代次数GA69l1415517216IJ03．862272．1PSO69114155172161103．86313I，6HGAPSO69114155172161103．86159．4RTS69114155172161103．86103．79l 天津人学博七学佗论文第五章配电网络重构表5-6几种算法的寻优性能比较测试系统GAPSoHGAPSoRTSIEEE．6917点9587100图5一13IEEE．69节点几种算法最佳适应值动态曲线相比前面两个测试系统，IEEE．69节点测试用例的开关数、支路数以及环路数最多，规模最大，所以在计算时间上最长。与前面的算例结果相同的是，总体来看，RTS和HGAPSO性能优越，计算时闻短，寻优效率商。上述几种算法的寻优性能比较如表5-6所示，表中的数据为100次测试中收敛到全局最优解的次数。不同算法中最佳适应值曲线以及RTS和HGAPSO的动态搜索曲线分别如图5．13，图5．14和图5．15所示。图5—14IEEE．69节点RTS当前适应度值和最佳适应度值动念曲线 大津人学博十学位论文第五章配屯网络重构图5-15IEEE-69节点HGAPSO平均适应度值和最佳适应度值动态曲线从上述几个算例的计算结果以及分析来看，简单遗传算法在解决配电网络重构问题时搜索时间最长；粒子群搜索算法速度比较快，但是全局收敛能力较差：混合的粒子群遗传算法综合了遗传算法的全局收敛和粒子群搜索速度快的优点，在搜索过程中采用进化信息共享的策略．使其在解决配电网络重构问题上全局收敛性能更强，搜索速度更快：出于禁忌搜索本身具有很强的局部搜索能力，结合根据配电网络特有的性质而作的编码方式以及本文独特的邻域结构设计，改进的禁忌搜索算法是这些算法中性能最好的一个，在进行配电网络重构时，其无论在全局收敛性还是在计算速度方面都显示出了无与伦比的性能。5．4．2动态网络重构分析配电系统中负荷节点的数目很大，并且配电系统中各节点的负荷往往是综合性负荷，各节点负荷曲线的变化情况相差较大。但是，配电系统中各节点负荷类型所占的比重不同，因此负荷曲线形状也不相同。文[149]把配电系统中基本负荷种类可分为工业、商业、居民生活用电三类，并设置其功率因数分别为0．99，0．9，O．85，认为配电网络一年的负荷可以用18条典型曲线模拟，分别为上述三种类型的负荷在冬、夏、春(秋)三个季节的工作日和休息日的曲线(3．3,2=18)。图5．16～5．18分别为某地区冬季工作同上述三种负荷类型的典型曲线。 天津人学博十学位论文第五章配电网络重构图5．16工业负荷典型曲线图5—17商业负荷典型曲线图5-18居民生活负荷典型曲线94 天津人学l尊十学位论文第五章配电网络重构在静态网络重构所采用的三个算例中，IEEE．16节点测试系统的负荷被看作是恒定的，所以在动态重构中只考虑后两种测试用例。并且在IEEE．33和IEEE．69节点测试用例中，根据文[12]和文[150]所给的数掘作为所研究时间段内各节点的峰荷。用此峰荷和各个节点负荷曲线即可得到各个计算时间段内负荷的大小。分别用HGAPSO和RTS对动态重构进行计算，经过比较发现两者计算结果相同，开关操作结果和网络损耗结果分别如表5．7，表5。8以及图5．19，5．20所示。图5—19IEEE一33节点动态重构网损曲线图5—20IEEE一69节点动态重构网损曲线 天津人学博十学位论文第五章配电网络重掏时间(小时)0～89～12131415～1617～19202l22～23I开关状态状态l状态2状态l状态2状惹；1状态2状态1状态2状态1表5-8IEEE-69重构后开关状态时间(小时)0～l2～345～67～89～10lI～181920～23l开关状态状态l状奋2状态1状态3状态i状毒4状态1状态5状态lIEEE．33测试系统的动态网络重构中结果表5-7中，状态l表示丌关7，9，14，37和32断丌。其它开关闭合的情形；状态2表示开关7．9，14，37和36断丌，其它丌关闭合。在重构过程中丌关动作共16次，其中开关32动作8次，丌关36动作8次。IEEE-69测试系统的动态网络重构中结果表5_8中，状态1表示丌关58，69，23．14和70断-丌，其它开关闭合的情形：状态2表示开关53．69．23．14和70断开，其它开关闭合；状态3表示开关55，69，23，13和70断开，其它_丌关闭合：状态4表示开关52，69，23．13和70断开，其它丌关闭合；状念5表示开关54，69。23，14和70断开，其它丌关闭合：本次动态重构中．开关动作共20次，其中开关58动作8次，丌关53动作2次，开关55动作2次．丌关14动作2次，L丌关13动作2次．丌关54动作2次，开关52动作2次。多时问段落配电网络动态重构的关键是必须考虑开关约束条件的处理及寻优策略的选取和调整。开关约束包括所有操作丌关的总操作次数约束和单个丌关的操作次数约束。本文在进行动念网络重构时，首先不考虑开关操作次数的约束，计算出一个初始结果，然后再根据此初始结果进行合理的调整。即在给定开关操作次数的条件下。调整开关状念，使给定的目标函数最大。假设开关总操作次数不超过4次，单个歼荚的操作次数不超过2次．那么动态重构后的计算结果如表5．9和表5．tO所示。表5-9考虑丌关操作次数约束后IEEE．33节点系统的结果时I'n7(小时)0～45～89～23费埘(元)开笑状态状态1状态2状态12893．47表5．10考虑_丌关操作次数约束后IEEE．69节点系统的结果时间(小时)O～89～1920～23费蹦(元)开关状态状态1状态2状态12754．36 大泮人学博十学协论文第五章配也网络重构5．5小结本章分别提出改进的禁忌搜索算法(RTS)和混合粒子群遗传算法(HOAPS0)解决配电网络重构中静态及多时段动态重构问题。混合粒子群遗传算法综合了遗传算法和粒子群算法的优点。弥补了遗传算法计算时间过长及粒子群算法易陷入局部最优的不足，其在计算速度和收敛性能上比任一单一算法都有很大的提高。禁忌搜索本身是一种局部搜索能力很强的优化算法，但是，如何寻找到问题的最优解一直是众多学者关注的问题。本章根据配电网络的具体特点，采用高效的遗传编码策略，并分析了禁忌搜索的收敛条件，从而在理论上证明此种方法在解决配电网络重构问题时能够找到全局最优解的必然性。通过对IE髓三个经典测试用例的计算和结果分析表睨，HGAPSO和RTS两种算法无论在寻优速度方面。还是在全局收敛性方面都有着相当卓越的性能。其重构结果对配电网络运行人员的决策有着很高的参考价值。 天津人学博十学位论文第^章配电系统无功电压优化控制6．1引言第六章配电系统无功电压优化控制目前．我国配电网络存在供电能力不足，网架结构薄弱，供电可靠性较差。城网线损率偏高(1997年达812％)等问题。同样，电网的电压合格率也不能令人满意．个别城市220V电网用户电压甚至达不到180V．其原因主要有：电力负荷中异步电动机和中小容量变压器占有很大比重，其消耗的无功功率约占全国无功负荷的80％～90％：管理上欠严格，有些电网的自然功率因数过低，而有些电网的功率因数过高；电网结构不合理，导线截面太小和无功潮流不台理等。在配电系统中，通过适当投切电容器组并配以带负荷调压变压器分接头档位的调整，不但可以降低网络损耗提高系统运行的经济性。并且还可以使各节点的电压控制在容许的范围内以提高电压质量。配电系统电容器的投切能够改变系统注入无功功率的大小，而变压器分接头的调节可以控制无功功率的流动fIs“。无功对电压的影响主要反映在以下三个方面：1)由于无功功率的不平衡．会弓；起电压的偏移。根据负荷的电压静态特性，当一个地区无功过剩时，电压将会升高．无功功率不足时，电压将会降低；2)由于无功潮流在电网中流动产生的电压降落，是造成电压偏移部分原因：3)由于无功负荷在线路中产生的电压降同无功负荷Q成正比，所以随着无功负荷的变化，将Bl起电压降的交化。无功负樯变化越大，电压变动也就越大。通常，配电网络无功优化分成规划和实时运行两类。规划问题一般是指在电网结构确定的酊提下，计算无功毒}偿设备最佳安装地点、类型和容量，达到节省投资费用的目的：无功优化实时运行问题则假定设备的配簧已经确定，需要根据负荷的动态变化，利用现有的无功朴偿设备和调压手段，优化网络的无功潮流，用以达到网络损耗最小或运行费用最小的目的lI”J。对于35～llOkV中高压配电网，调节无功潮流的主要手段是改变有载调压变压器的分接头位置和并联电容器的投切组数，对于lOkV中压配电网络，无功补偿的主要手段是并联电容器组的投切。本章在混沌理论和粒子群搜索的基础上，针对配电系统无功优化问题，提出了混沌优化和混沌粒子群优化两种动态无功优化方法．并通过两个配电测试系统分析了这两种算法在无功优化问题上的性能。 犬津人!学博十学位论文第六章配电系统无功电压优化控制6．2配电网络无功优化的数学模型配电网无功优化控制，一般在馈线端电压和在各负荷功率已知的条件下，通过控制配电网中电容器组的投切和变压器分接头的档位来实现。目标函数通常要考虑以下几个方面的因素：a)网损最小b)电压水平最好c)无功补偿容量最小d)补偿经济效益最大e)电容器配置成本最低。其中后三种主要是对无功优化规划而言，对优化控制，本文以前两种为优化目标，并且把电压目标以约柬条件的形式体现，其静态无功优化目标函数如下：min．f(x。X。)=min(P，。。)(6一1)并且满足如下约束方程只=¨∑矿，(G。COSe0+或sine,,)iEJⅣ．，i≠j(6—2)j￡N，Q=¨∑Vi(GI，sinO,一Becose,)i∈Nw(6-3)K7。。≤K7墨K7．。。9I<乡s。Q,～(6-4)_。。≤■≤■。。s，，≤s^．。t∈R”且t=[K。Qf。】为控皋4变量。分别为变压器变比和无功{}偿容量；_E矗“且_=【■，S。】为状态变量，分别是负荷点电压，平衡节点的出力；Ⅳ．表示和节点f关联的节点集合；Ⅳ。是所有PQ节点的集合：s，是支路通过的功率。综合考虑目标函数和约束条件，本文以下式作为目标函数min，(x。_)=min(PL．。十五∑‘i；-二!：参k)2)(6—5)口，㈣，⋯l式中，五为违反电压约束的惩罚因子；口为违反节点电压约束节点集合：‰。分别为第i节点电压的限值；K。。一。。分别为节点电压r的上限和下限；在电力系统实际运行中，由于负荷总是不断变化的，所以针对单个时间断面 天滓人学博十学位论文第武章配电系统无功电压优化控制进行的静态优化计算是无法满足实际运行需要的【‘531。考虑将各点负荷形态变化的系统优化为动态优化。要真诈得出一个可操作的无功优化方案，就要有一个可行的动态优化算法。由于配电网络结构的辐射状特性，可以将优化问题分解为针对各独立予网的子优化问题。假设子网内共有一个母线，所台可投切电容器组，z个带有载调压分接头的变压器。以一天系统网损之和(能量损耗)最小为目标函数，选取电容器投切和有载调压分接头调节为控制变量。考虑电压约束与投切量的整数约束，假设实际系统允许一天内电容器组最大的投切次数为&，变压器分接头的最大允许调整次数为S。则耩确的动态优化模型可写为min厶。=∑fCx。^)(6—6)i=lS．，．‰。sV≤¨。。。Qmm≤9≤乏乙。。Q=KB，(6-7)■。≤T≤z。。∑S。≤S。，j1，∑SosS，l=l式(6—6)中f(x。，x，)的表达式为(6—5)。V=嘭，V2，⋯，吒。r，代表24个时段内各母线电压矩阵；Q=【g，鲮，⋯，Q2。】』．代表24个时段内各电容器组的容量矩阵；T=[一．毛．⋯，t。】，，代表24个时段内各可调变压器分接头档位矩阵：B为一m维的对角阵，其对角元素为相应电容器组的单台容量：K=【墨，K：，⋯，K。】『，墨为时段i内电容器组投入运行台数，为一m维矢量：&代表24小时内各电容器组总的投切次数，为一m维矢量；S代表24小时内各变压器分接头总的调节次数，为一，维矢量：6．3基于混沌粒子群的配电系统无功优化理论上，配电系统无功优化问题属于大规模、非线性、混合整数规划问题。出于问题是多变量，多约束性问题，所以不能保证目标函数是凸函数，更不能保证其可微可导性。传统的无功优化理论分析方法如线性规划、非线性规划、混合整数规划、灵敏度分析、内点法等由于对目标函数和约束条件有连续、可微的要求，一般得到的结果往往是局部最优解，不能保证全局最优l”4】。近年来，各种智能算法，特别是由于遗传算法对问题适应性强、适合处理整数变量的组合优化 天渖人学博十学伉论文第八章配电系统无功电压优化控制问题、理论上具有全局收敛性等特点，自然地被人们应用于无功优化计算，虽然取得了一定进步．但是仍然存在计算速度慢，局部收敛性差以及处理大规模问题时容易陷入局部最优等问题u55州”。6．3．1混沌优化方法混沌运动具有遍历性、随机性、“规律性”等特点，混沌运动能在一定范围内按其自身的“规律”不重复地遍历所有状态。因此，如果利用混沌变量进行优化搜索，在一定程度上优于随机搜索，同时也克服了传统优化方法容易陷入局部最小的困难。混沌优化(ChaoticOptimizationAlgorithm，COA)用类似载波的方法将混沌状态映射到优化变量中，并把混沌运动的遍历范围同优化变量的取值范围联系起柬，然后利用混沌变量进行搜索【l⋯。与其它产生混沌变量的动力系统相比，本文用来构造混沌序列的Logistic方程具有结构简单、计算：量小、使用方便的特点，其方程如式(6—8)所示。工¨=雎。(1一x。)(6-8)已经证明方程(6—8)中卢E【3．57，4l时系统处于混沌区域，在此区间内方程运动轨迹表现出混沌特性。混沌优化的基本步骤见第二章2．5．2，其流程如图6．1所示：图6-1混沌优化流程10l 大津人学蹲十学位论文第八章配电系统无功电压优化控制下面运用混沌优化方法对两个给定方程进行求解(E求最小值，值)，表6—1给出了这两个函数的理论值与本文的计算值的具体数据相应的函数图像如图6—2和图6—3所示。只=置bP一‘H“i1E：05+堕盟生单二?：姜‘【1．0+0．001(x2+y2)】2其中(6-9)式E中(x，．y)∈卜2,2】tE中(x，J，)∈【-5，5】。表6一l混沌优化计算结果与理论结果对比R求最大同时绘出(6—9)(6—10)函数精确解计算值相对误差(％)0．7071070．707l一O．001％F1—0．707107一0．7070一O．015％O．00．000130．013％R0．00．0002l0．021％图6-2Fl的函数图像图6-3R的函数图像 天津人学博+学位论文第六章配电系统无功电雁优化控制由图6～2和图6-3中可以看出，与一函数最小值对应的点有两个，这旱我们只用一个代表。在对函数的分析以及函数图像的绘制中我们发现函数R有多个局部极小点。传统的非线性规划、线性规划、二次规划等算法．对于非线性系统采用分段线性及用目标函数和约束条件方程的一阶和二阶导数来求得寻优方向，这种处理在很多情况下走向局部极小，甚至造成发散，而混池优化方法能够有效地找到全局最优点．可以很好地解决陷入局部最小点甚至发散的问题。混沌优化方法虽然能够解决优化的全局最优问题，但是其属于单点搜索算法，仍然存在计算时削过长的问题。同具有多点搜索并且全局收敛特性的遗传算法相比，混沌优化方法并没有优势。然而混沌优化的思想值得借鉴，并且可以结合其它计算速度快的算法，组成混合算法．来提高整体算法的寻优性能。6．3．2混沌粒子群优化方法粒子群算法的基本原理在2．3．2已经说明，粒子群体由于“趋同性”而容易陷入局部最优韵分析见3．3．3。在粒子群体搜索过程中，如何避免这种“趋同性”是目前提高粒子群全局寻优搜索性能的关键。考虑到混沌运动对初始值敏感以及遍历的特性，如果粒子群出现粒子“重叠”的情况，则把此粒子赋予混沌运动。运用混沌优化中类似载波的方法将优化变量映射到混沌空间中，并把混沌运动的遍历范围同优化变量的取值范围联系起来，经过若干次迭代使邻近的点迅速分离，用以提高PSO的寻优性能，所谓混沌遍历．就是系统由某个初始状态开始．按照其自身的运动规律，在经过了足够长的时间后，不重复地经历相空间中的所有状态。混沌遍历较之随机遍历性能更优越．其原因就是混沌遍历的规律性及不重复性，而随机遍历则是无规则运动。图6-4相邻两点的混沌运动轨迹103 天淖人学搏十学位论文第人章配电系统无功电压优化控制图6-4是初始值分别为0．501和0．502两个点Logistic方程‰+l=搬。(1"xn)的混沌演化轨道，初始距离仅为O．001，采用Logistic方程迭代后，两个点逐渐按其lyapunov指数分离。图6-4中．上图为两个点的演化轨迹，下图为两个点演化轨迹对应的距离。由图6-4中可以看出，前六次迭代两个点的距离还比较近．在图中表现为两个点基本重合．当迭代次数超过7次后，两个点则迅速分离，分别按照各自的混沌轨道运行。可见，即使十分相近的两点经过若干次迭代后，此两点分别产生迥然不同的轨迹。我们把群体中含有被赋予混沌运动个体的粒子群优化算法称为混沌粒子群优化算法【”oJ(ChaoticParticleSwarmOptimization。CPSO)，大致流程如图6—5所示：图6．5CPSO的基本流程在CPSO搜索过程中。采用惯性权重法自适应调整权重系数W，取值如下：一Ⅵ一导11e》胁，L一(6—11)式中w。。．W。分别为惯性系数的最大值和最小值：矗P，。。，lter分别为最大迭代次数和当前迭代次数。权重因子Cl,旬对于CPSO的收敛性也起到了重要的作用，分别代表粒子飞向个各体最优解和全局最优解的加速权重。根据一般的经验，c^o设定为1．5—2．0。此外，在CPSO的搜索过程中，对于粒子更新的速度有一个晟大值的限制。最大速度v,nax也起着平衡全局和局部搜索能力的作用，一般将速度限值Vmax设置为变量搜索空间的10--20％。分别用CPS0和COA对上述两个测试函数计算结果如表6．2所示。上述两个测试函数分别采用PSO和 天津人学1尊十学位论文第六章配电系统无功电压优化控制CPSO以及COA两种算法连续运行100次．收敛到全局最优解的次数分别是87、83和100、100以及100，100，三者的比较如图6-6所示。表6．2CPSO和COA计算结果比较函数COA方法GPS0方法计算误著(％)计算时间(秒)计算误差(％)计算时间(秒)只一O．Ol鼹18O．012％O．21^0．021％2l0．015％O．23图6-6三种优化方法全局寻优能力比较从表6—2以及图6．6可见，由于CPSO综合了COA和PSO两者的优点，其在计算速度方面继承了PSO的性能，远远快于COA；在全局寻优性能方面继承了COA的特点，其性能又优于PSO。运用混沌粒子群(CPSO)优化算法解决配电系统无功优化问题的具体计算步骤如下：步骤l：输入控制变量的维数和上下限值，设定状态变量的限值：设爱粒子群体的规模M、最大迭代次数^P‰．、惯性系数w的上限I'Vrnax和下限W，。、权重因子c，和。的取值、牲子更新的最大速度等参数：步骤2：在控制变量的变化范围内随机生成M个解，按式(6．6)计算目标函数值．取其中最小值作为群体当前的最优解并记录楣应的解为‰，设定每个粒子当前位置为其认知优化解j：；枷，并设定当前迭代次数lter为l：步骤3：判断当前迭代次数Iter是否到达最大迭代次数加r。。，若不满足条件，置迭代次数Ber=lter+l：若满足条件，则输出无功优化计算结果： 大津人学博十学何论文第六章配电系统无功电压优化控制步骤4：由式(2，7)计算各微粒的飞行速度．如果飞行速度小于给定的最大速度，按式(2-8)更新微粒的当前位置，否则设定v，“V#．max，然后按式(2—8)更新微粒的当前位置；步骤5：查看粒子群体中的重迭状况，如果有粒子重迭(距离小于给定的误差)，则一个粒子不变，其他粒子赋予混沌运动，并在给定的若干步内用混沌优化搜索；步骤6：检查群体中每个粒子各个控制分量的变化情况，如果存在越限情况，则这些分量被限制为约束的上限值或下限值；步骤7：比较每个微粒的目标函数值和当前个体最优解五蛐对应的目标值．后蛐，若对于某个微粒而占，其目标值小于局。则将当前点作为该微粒当前的个体最优解局缸。选择所有微粒的个体最优解五如。中的最小值作为微粒群当前迭代过程的全局最优解．廓。并与上一次迭代的／函。比较，取目标函数值小的点作为群体认知的最优解并转到步骤3。6．4算例分析算例l是IEEE，14节点测试系统，该系统包含一台可调变压器和3个无功补偿节点，系统接线如图6．7所示。系统数据以及负荷数据见文献[161]和[1621。=：图6—7IEEE．14节点系统图计算过程中馈线始端的电压为1．0，变压器可调变上下限分别为1．05和O，95。其分级步长为2．5％，分接头档位变量为攘型，取值范围为卜2，2】，并联电容器106 犬津人学博十学位论文第六章配电系统无功电压优化控制分别安装于节点2(容量为200kVar)．节点9(容量为140kVar)和节点lO(容量为140kVar)。无功优化过程中，可调变难器分接头最大允许动作次数设为15，电容器最大允许投切次数没为10。取粒子群体规模为30，最大迭代次数为100，最大和最小惯性常数分别设置为0．9和0．4，学习因子ChC2的取值均为2．0。优化前，节点13和节点14电压偏低(如图6．8)，一天24小时系统有功损耗占总供电量的7．38％，为338．65kWh，优化后系统有功网损占总供电量的5．26％，为241．37kWh，采用COA和CPSO优化结果相同，具体计算结果如表6．3和表6-4所示。图6-8优化前系统电压状况表6-3IEEE．14节点测试系统无功优化结果时间变压器电容器l电容器2电容器3(小时)分街头档l：：7：投切状况1．10O2一lO0O3．1O04．10Ol5．1O16．1O0l7．20l8．2Ol9．1lIllOOl1ll12l13Ol14Ol50l160l 大泮人学博十学何论文第六章配电系统无功电压优化控制17Ol118Ol119l1l20l12ll0l22lOl23Ol24l0O表6．4优化后最低节点电压状况时间段(小时)l-34—一67～1415—-2122～24电压值(p．u)0．958240．959570．966140．961220．95641发生时间3时6时ll时20时22时所在。l，点1413lO1413由表中的计算结果可见，IEEE-14节点测试系统采用无功优化后．系统有功网损下降明显(降损率28．73％)：节点电压得到了有效的改善，最低电压出优化前的O．9392提高到0．95824，提高了3．1％。可调变压器分接头动作8次，电容器1，2，3均动作2次，都满足约束条件。采用COA计算大约需时2小时18分；采用CPSO计算占用时间为238秒。可见CPSO在计算速度上要远远高于COA。算例2是IEEE．30节点测试系统，该系统包含5个无功补偿节点，系统接线如图6-9所示。图6．9IEEE．30节点测试系统图 犬津人学}尊十学位论文第六章配电系统无功电压优化控制系统数据以及负荷数据见文献[163]。计算过程中馈线始端的电压为1．0，并联电容器分别安装于节点13(容量为350+3×175k、协)，节点15(容量为350+3×175kVar)．节点19(容量为275十3×75k、协)．节点23(容量为750kVar)和节点25(容量为375+3>(75kVar)。无功优化过程中，单组电容器最大允许投切次数设为10。取粒子群体规模为40．最大迭代次数为100，最大和最小惯性常数分别设置为0．9和0．4，学习因子CI,C2的取值均为2．0。优化前，一天24小时系统有功损耗占总供电量的8．37％，为26．4085MW．h，优化后系统有功网损占总供电量的6．25％，为19．7307MW．h。采用COA和CPSO优化结果相同，具体计算结果如表6—5及图6—10和图6．1l所示。图6．10IEEE．30节点测试系统某一时刻优化前后电压状况表6—5IEEE．30节点测试系统无功优化结果电容器档位状况系统补偿容域时段ClC2C，C-C，(kⅧ)I2O29752lO0O28003lO0l7254l0Ol725510l7256lO02115072102132582l22350931l22525lO3j21326751I4I2l32850124l2132850 犬淖人学博十学位论文第A章配电系统无功电压优化控制134l2l328501442l330251542l330251643I433501743l433501843l435251943l43：5252043l334502l32l330252232I22775233l0O21500242O297S胬6．11优化前后系统有功弼损情况表6．5中．电容器组档位0表示电容器均不投入(补偿容量为O)。出表6．5和图6．10及图6．1l中的计算结果可见，IEEE．30节点测试系统采用无功优化后．系统有功网损到了有效的改善．下降明显(降损率25．29％)；电压幅值得到了很大的提升。从图6．10可见，优化前有19个节点电压标幺值低于O．95，最低电压发生在节点14，其大小仅为O．8085，优化后系统电压全部合格．最低电压发生在节点27．其大小提高到0．9564。从电容器组动作次数上看，14电容器组动作了6次，24电窖器组动作了8次，34电容器组动作了5次．4。电容器组动作了2次，54电容器组动作了6次．均满足约束条件。采用COA计算大约需时2小时52分；采用CPSO计算占用时间为254秒。可见CPSO在计算速度上要远远高于COA。110 大津人学博十学位论文第六章配电系统无功电压优化控制6．5小结本章分别提出混沌优化算法(COA)和具有混沌特性的粒子群优化算法(cPsO)来解决配电系统无功优化问题。混沌优化算法用类似载波的方法将混沌变量引入到优化变量中，利用混沌运动的遍历性和貌似随机性的特点直接对目标函数寻优，在摆脱局部最优上体现了很好的性能，并且理论上是一个可以找到全局最优解的算法。混沌优化虽然存在上述优点，但是其寻优过程计算量很大，需要较长的计算时1．自j。粒子群优化方法(PSo)计算速度快，可以很好地处理大规模混合整数规划问题．但是存在容易陷入局部最优问题。混沌粒子群优化方法(CPSO)结合混沌优化中混沌变量是好的遍历特性以及粒子群体搜索的快速性等特点，对即将重合而引起搜索能力下降的粒予赋予混沌状态搜索，有效地提高了算法的全局寻优能力，同时又保留了PSO算方法计算速度快的特点。通过对IEEE两个配电网络测试用例的计算验证了CPSO方法的性能。 犬津人学博十学位论文第七章结论随着生产力水平的推进和我国经济的快速发展，配电网络的建设、改造以及优化运行逐渐得到了电力系统规划和运行部门的重视。近年来新兴的智能优化算法的发展和应用，为解决配电网络规划和优化运行提供了新的思路。本文在传统的配电网络规划和优化运行的基础上，应用智能优化新技术，针对配电网络变电站选址定容，配电网络联络线总体规划．配电网络重构以及无功优化等问题进行了研究，主要结论如下；l，建立了用于解决配电网络变电站选址定容的综合数学模型。此模型不仅涉及用地性质、交通状况、施工条件、地质地形等地理信息，而且还考虑了变电站建设费用，线路投资和网络运行费用等电气信息。通过几个实际地区的算例表明．由此模型计算出的站址更加合理、可行。2提出了具有变异特性的粒子群优化算法，以种群的适应度方差大小衡量粒子群体的“聚集”情况，对发生“聚集”的粒子赋予变异操作用以克服粒子群优化算法的早熟现象，并用于解决变电站选址定容问题．计算结果币确。算法全局寻优能力较基本粒子群算法得到了很大提高。3，运用蚁群算法，以变电站问的距离、变电站富裕容量以及路径上的信息素为启发因素．解决了在一定负荷密度和配电变电站蚓负荷转带比例下，考虑不同接线模式时的站闻联络线优化问题，同时还以边际供电总成本最小为目标函数，运用快速商效的粒子群优化算法解决了变电站负荷转带比例这一平衡配电网络经济性和可靠性的优化问题，结合蚁群算法对站间联络线的优化，最终形成配电网络变电站总体联络规划方案。在总体联络规划方案中，当规划区内负荷密度较高时．适宜采用联络较强的接线模式：当规划区域负荷密度较低时，适宜采用联络相对较弱的接线模式。不同的变电站站间负荷转带比例以及不同的接线模式下，最终的总体联络规划方案不同。4．提出了改进的禁忌搜索算法，并分析了禁忌搜索的收敛条件。从而在理论上证明此种方法在解决配电网络重构问题时能够找到全局最优解的必然性。通过对几个IEEE经典测试用例验证，表明在配电网络重构问题上，改进的禁忌搜索算法速度快，效率高．全局收敛能力强。5．提出了混合粒子群遗传算法．并应用于解决配电网络重构静态及多时段 犬洋人学博十学位论文第七章结论动态重构问题。陔方法综合了遗传算法和粒子群算法的优点，弥补了遗传算法计算时问过长及粒子群算法易陷入局部最优的不足，其在计算速度和收敛性能上比任一单一算法都有很大的提高。在解决配电网络重构问题过程中，根据配电网络闭坏设计丌环运行的特点，采用基于环路的高效遗传编码策略，进一步提高了算法的搜索效率。混合粒子群遗传算法适应能力强，搜索速度快，具有广阔的应用前景。6．提出了具有混沌特性的粒子群优化算法解决配电系统无功优化问题。混沌粒子群优化方法结合混沌优化中混沌变量良好的遍历特性以及粒子群体搜索的快速性等特点，对即将重合而引起搜索能力下降的粒子赋予混沌状态搜索．有效地提高了算法的全局寻优能力．同时又保留了方法计算速度快的特点。通过对两个IEEE配电网络测试用例的计算和结果分析，验证了该方法快速、正确和有效。 天津人学博十学位论文参考文献[1]陈章潮，唐德光，城市电网规划与改造．北京：中国电力出版社，1998．[2]蓝毓俊，现代城市电网规划设计与改造，北京：中国电力出版社，2004．[3]H工．willis，H．Tram，M．V。Engel，etal，OptimizationApplica：tionstoPowerDistribution．IEEEComputerApplicationsinPowert1995，8(4)：25-31．[4]王成山，王赛一，葛少云等，中压配电网不同接线模式经济性和可靠性分析，电力系统自动化，2002，26(24)：34-39．【51余贻鑫，邱婶，支Ⅱ若沁，基于启发式算法与遗传算法的配电网重构。龟网技术，200t，25(11)：19-22．【6】T．H．Fawzi，K．EAli，ANewPlanningModelforDistributionSystems，IEEETramOnPAS，102(9)：3010-3017．【7】Tram，H．N．，Watl，D．L．，Optimalconductorselectioninplanningradialdistributionsystems，IEEETransactionsonPowerSystems，1988，3(1)：200～206f8】KWDommel，W．F．Tmney,OptionPowerFlowSolution，IEEETransOnPas，1968，87(10)：l866--q876．【9】Civanlar,S．，Gminger,J．J．，Forecastingdistributionfeederloads：modelingandapplicationtovolt／VArcontrol，IEEETransactionsonPowerDelivery,1988，3(1)：255-264．【10]Baran，M．，Wu，F．E，Optimalsizingofcapacitorsplacedonaradialdistributionsystem，IEEETransactionsonPowerDelivery,1989A(1)：735-743．【1l】MerlinA．，BackH．，SearchforaMinimal—LossOperatingSpanningTreeforanUrbanPowerDistfibufionSystem，ProceedingsofFifthPowerSystemComputationConference，Cambridge，1975：2—6．【12]Baran，M．．Wu，EF．，Networkreconfigurationindistributionsystemsforlossreductionandloadbalancing，IEEETransactionsonPowerDelivery,1989，4(2)：140l～1407．[13]ShirmohammadiD．，HongH．W，，ReconfigurationofElectricDistributionNetworksfarResistiveLineLossReduction，IEEETransonPWRD，1989，4(2)：1492—1498．114 大洋人学博十学位泛文参考文献[14]D．L．Wall，GL．Thompson，Anoptimizationmodelforplanningradialdistributionnetworks-IEEEonPowerApparausandSystems，1979，98(3)：lD61～l068．【15]GL．Thompson，D．L。Wall，ABranchandBoundModelForChoosingOptimalSubstationLocmions，IEEETramOilPowerApparausandSystems，1981，100(5)：2683-2688．【16]MamandurK．R．C．．ChenowethR．D．，Optimalcontrolofreactivepowerforimprovementinvoltageprofilesandforreallossminimization,IEEETransonPowerApparausandSystems，1981，100(7)：123～128。【17】邓佑满，张伯明，相年德，配电网络电容器实时优化投切的逐次线性整数规划法，中国电机工程学报，1995，15(6)：375～383．[18]ChiangHsiaoDong，ReneJeanJueau，Optimalnetworkreconfigurationindistributionsystems，PartI：Anewsormulastionsandsolutionmetholdology．IEEETransonPWRD，1990，514)：1902～1909．【19]GonenT’GooteB⋯LDistributionsystemplanningusingmixed-integerprogramming，lEEProc-C，1981，128(2)：70---79．【20]RamaI．S．RamachandranK．H⋯SOptimalReaetivePowerAllocationforImprovedSystemPerfor2manee，IEEETransactionsonPowerApparatusandSystem，1984，PAS2103(6)：61-75．【211朱太秀，电力系统优化潮流与无功优化，电网技术，1990，19(4)：153～161．[22]S．Civanlar，J．J．Grainger,H．Yin，Distributionfeederreconfigurationforlossreduction，IEEETransonPowerDelivery，1988，3(3)：1246～1253．【23]MesutE．B．，FelixF．W．，Networkreconfigurationindistributionsystemsforlossreductionandloadbalancing，IEEETransonPowerDelivery，1989，4(2)：140t～1407．【24]DaiushShirmohammadi，H．WayneHong，Reconfigurationofelectricdistributionnetworksforresistivelinelossesreduction，IEEETransonPowerDelivery，1989，4(2)：1492-1498．【25}Aoki，K．，Nara，K．，Saloh，T．elal，Newapproximateoptimizationmethodfordistributionsystemplanning，IEEETransactionsonPowerSystems，1990，5(1)：126～l32．【26]Nara，K．，Satoh，T，Aoki，K，etal，Multi—yearexpansionplanningfordistributionsystems，IEEE‘I'ransactionsOilPowerSystems，1991，6(3)：952—958． 天津人学博+学位论文参考文散[27]Goswami，S．K．，Distributionsystemplanningusingbranchexchangetechnique，1EEETransactionsonPowerSystems，1997，12(2)：718-723．【28]Miguez，E．，Cidras，J．，Diaz-Dorado，E．etal，Animprovedbranch-exchangealgorithmforlarge—scaledistributionnetworkplanning，IEEETransactionsonPowerSystems，2002，17(4)：931-936．[29]KirkpatrickS，GelattC．D，，VeechiM．P．，Optimizationbysimulatedannealing，Science，220：377～383，【301倪秋龙，黄民翔，基于支路交换的模拟退火算法在配电网规划中的应用，电力系统及其自动化学报，2000．12(4)：31-35．【3I]DanJiang，RossBaldick,OptimalelectricdistributionsystemswitchreconfigurationindistributionsysⅫ【rIsusingsimulatedannealing，ElectricPowerSystemsRearch，1994，12(29)：227—238．【32]Hsiao—DangChiang，Jin—ChengWang,JianzhongTong,Optimalcapacitorplacement．replacementandcontrolinlarge·scaleunbalanceddistributionsyaems：systemsolutionalgorithmsandnumericalstudies，IEEETransactionsonPowerSystems，1995，10(1)：363—369．【33]文0吉来，无功优化的改进模拟退火算法，电力学报。1998，13(2)：86--89，【34]贾德香．唐圉痰，韩净，基于改迸模拟退火葬法的电网无功优化，继电器，2004，32(4)：32-35．【35]HollandJ．H．，Adaptationinnaturalandartificialsystems，MI：UniversityofMichiganPress．[36]Miranda,V．Ranito，J．V．，Proenea，L．M．，Geneticalgorithmsinoptimalmultistagedistributionnetworkplanning，IEEETransactionsonPowerSystems，1994，9(4)：1927-1933．【37]Mates，M．A．，Anewpowerflowmethodforradialnetworks，IEEEPowerTechConferenceProceedings，Bologna,2003，2：1～5．【38]KoichiNam，AtsushiShiose，MinoruKitagawa，Implementationofgeneticalgorithmfordistributionsystems10ssminimumreconfiguration，IEEETransonPowerSystem，1992，7(3)：1044—1051．【39]M．Srinivas，L．M．Patmaik，Adaptiveprobabilitiesofcrossoverandmutationingeneticatgorithms，IEEETransonSystems，ManandCybernetics，1994，24(4)：656～667．6 天津人学博十学位论文参考文献f40]余贻鑫，段刚．基于最短路算法和遗传算法的配电网络重构，中国电机工程学报，2000，20(9)：44--49．【41】刘莉，陈学允，基于模糊遗传算法的配电网络重构，中国电机工程学报．2000，20(2)：66-69．[42】马晋瞍，L-L．Lai，杨已涵，遗传算法在电力系统无功优化中的应用，中国电机工程学报，1995，15(5)：347～353．【43lLee，K．Y，XiaominBat，Young—MoonPark，Optimizationmethodforreactivepowerplanningbyusingamodifiedsimplegeneticalgorithm，IEEETransactionsonPowerSystems，1995，lO(4)：l843～1850．【44]赵登福，周文华，张伏生等，遗传算法在无功优化应用中的改进．电网技术，1998，22(10)：34—43．[45]GloverF．，Tabusearch-Partl，ORSAJournalonComputing，1989，1(3)：190--206．[46]Mori，H，Iimura,Y，ApplicationofpadlcJtabusearchtodistributionnetworkexpansionplanningwithdistributedgeneration，IEEEPowerTechConferenceProceedings，2003，Bologna，V01．1，Page(s)：6．【47】王成山．王赛一，基于空间GIS和Tabu搜索技术的城市中压配电网络规划，电网技术，2004，28(14)：69～73．【48]Yann—ChangHuang，Hong-TzerYang,Citing-LienHuang,SolvingthecapacitorplacementprobleminaradialdistributionsystemusingTabuSearchapproach，IEEETransactionsonPowerSystems．1996，ll(4)：1868-1873．【49]陈根军，李魑洗，唐国庆，基于Tabu搜索的配电网络重构算法，中国电机工程学报，2002，22(10)：28—33．【50]唐红键，冯可，配网重构算法的改进和研究，电力勘探设计，2003。第四期，PP：53～56．【51]Lin，WM．，Yang，C．D．，Tsay,M．T-，Distributionsystemplanningwithevolutionaryprogrammingandareliabilitycostmodel．IEEProceedingsGeneration，TransmissionandDistribufion，2000，147(6)：336-341．[52]Moustafa，Y．G—Amer．A．H．，Mansour，M．M．etal，Anartificialneuralnetworkforoptimumtopologyindistributionexpansionplanning,CanadianConferenceonElectricalandComputerEngineering，1996，V012，pp：786～789．[531陈根军，王磊，唐国庆，基于蚁群最优的配电网规划方法，电网技术，2003，27(3)：7l-75． 天泮人学博1：学位论文参考文献【54]Fukuyama，Y．，Yoshida，H．，AparticleSW￡Lrnloptimizationforreactivepowerandvoltagecontrolinelectricpowersystems，Proceedingsofthe2001CongressonEvolutionaryComputation，2001，Voll，Page：97～93．【55]赵涛，熊信银，吴耀武，基于混沌优化算法的电力系统无功优化，继电器，2003，3t(3)：20～25．【56]Kyung—HeeJung，HoyongKim，YunseokKo，Networkreeonfigurationalgorithmforautomateddistributionsystemsbasedonartificialintelligenceapproach，IEEETransactionsOOPowerDelivery，1993，8(4)：1933-1941．【57]；(tJ莉，姚玉斌，陈学允等，进化规划在配电网络多目标重构中的应用，哈尔滨工业大学学报，2000，32(1)：120--126．[58VJJ吉来．混合寻优法在无功优化中的应用研究，电力建设，1998，第九期，Pp：1-5．【59]褚美茹，崔明勇，混沌遗传算法在配电网无功优化中的应用。信息技术，2004，28(10)：48-50．[60]Holland，J．H．，Adaptationinnaturalandartificialsystems：Anintroductoryanalysiswithapplicationstobiology，control，andintelligence，l“edition，AnnArbor，MI：TheUniversityofMichiganPress，1975．【61]BookerLB．，GoldbergD⋯EHollandj⋯HClassifierSystemsandGeneticAlgorithms，ArticifialInterlligence．1999，40：235—282．【62]HisaoIshibuchi，AFuzzyClassifierSystemsthatGeneratesFuzzyIfThenRulesforPatternClassificationProblems，ICEC’95，1995，2：259～764．【63]FugerH，PopulationEvolutionStrategiesforStructuralImageAnalysis，ICEC’95。1995。1：229~234．[64]VittorioManiezzo，EvolutionoftheTopologyandWeightDistributionofNeuralNetworksIEEE’rransonNeuralNetworks．1994，5(1)：1238—1242，【65]KrishnakumarK，GoldbergD⋯EControlSystemOptimizationUsingGeneticAlgorithm．JournalofGuidance，ControlandDynamics，1992，15(3)：735-740．【66]MichalewiczZ，JanidowC，BrawezydJ．，AModifiedGeneticAlgorithmforOptimalControlProblem．ComputersMathApplication，1992，23(12)：83～94．[67]TakahashiR．H．C．，PeresP．L⋯DFerreiraP．A．V．，MultiobjectiveH2GuaranteedCostPIDDesign，IEEEControlSystemsMagazine，t997：37--47．118 犬津人学博1一学位论文参考文献【68]PorterB．，JonesA．H．，GeneticTuningofDigitalPIDControllers，ElectronicsLetters，1992，28(9)：834--844．[69]GeS．S，LeeT．H．，ZhuG，GeneticAlgorithmTuningofLyapunovBasedControllers：AnApplicationtoaSingleLinkFlexibleRobotSystem，IEEETransonIndustrialElectronics，1996，43(5)：567～573．【70]FogelD．B．，ApplyingEvolutionaryProgrammingtoSelectedTravelingSaelsmanProblemsCeberneticsandSytems，1993，24(1)：27～36．【71]DeJong，Ananalysisofthebehaviorofaclassofgeneticadaptivesystems(PH．DDissertation)，UniversityofMichigan，No．76～9381，1975．【72]Davis，L．、Handbookofgeneticalgorithms，VanNostrandReinhold，NewYork，1991．【73]Michalewica，Z．，Geneticalgorithms+datastructure=evolutionprograms，3“edition，NewYork：Springer-Verlag，1996．[74]Grefenstette，j．J．Gopal，R．，Rosrrmila,B．，VanGucht，D．．Geneticalgorithmforthetravelingsalesmanproblem，InProceedingsoftheFirstInternationalConferenceonGeneticAtgorithms(ICGA1)，Hillsdale，1985：160-168．【75]Mitchell，D．，Selman，B．，Levesque，H．，Hardandeasydistributionofsatproblems，InProceedingsoftheTenthNationalconfefenceonArtificialIntelligence。AAAIPress／TheMITPress，1992：459～464．[76]Goldberg，D．E．，Geneticalgorithmsinsearch，optimizationandmachinelearning，MA：Addison-WesleyPublishingCompany，1989．[77]Srinivas，M．，Patnaik，LM．，Adaptiveprobabilitiesofcrossoverandmutationingeneticalgorimthms，IEEETransonSystems，ManandCybernetics，1994，24(4)：656-667．[78]Dorigo，M．，Schneph，U．，etal，Genetic—basedmachinelearningandbehavior—basedrobotics：anewsynthesis，IEEETransonSystemsManandCybernetics，1993，23(1)：14t～154．[79]Qi，x．F．，Palmieri⋯FAdaptivemutationingeneticalgorithm，InProceedingsoftheSecondAnnualconferenceonEvolutionaryProgramming．CA：EvolutionayProgrammingSociety．1993：l92-196．【80]GoldbergD．E．，Geneticalgorithminsearching，optimizationandmachinelearning．1989．MA：AddisonWesley．119 天津人学博十学位}仑文参考文献【81】孙艳丰，王众托，自然数编码遗传算法的最优群体规模，信息与控制，1996，25(5)：3l7-320．[82]JiaoL，WangL，Anovelgeneticalgorithmbasedonimmunity，IEEETransonSystems，ManandCybernetics，2000，30(5)：552-561．183】GloverF'LugunaM．，TabuSearch．BaselSwitzerland，SciencePublishers，1993．【84】WENFu—shuan．ChangC⋯SAtabusearchapproachforfaultsectionestimationandstateidentificationofunobservedprotectiverelaysinpowersystems，Proceedingsof1996internationalconferenceonintelligentsystemsapplicationstopowersystems，KoreaSeoul，1996：341～347．[85】HanafiS．，OntheConvergenceofTabuSearch，JournalofHeuristic，2000，7：47-58．【86】Kennedy，J．，Eberhart。R．，ParticleSwarmOptimization．IEEEInternationalConferenceonNeuralNetworks，Perth，Australia,1995。4：1942～1948．【87】RayT，LiewK．M．，ASWalTllwithalleffectiveinfortmationsharingmechanismforunconstrainedandcomstrainedsingleobjectiveoptimizationproblems，1EEEInternationalConferenceonEvolutionaryComputation，Seoul。2001：752～760．[88】AngelineP．J．，UsingselectiontoimproveparticleswRrmoptimization，IEEEInternationalConferenceOnEvolutionaryComputation，Anchorage，1998：842-849．【89】C．EJuang，AHybridofGeneticAlgorithmandParticleSwarmOptimizationforRecurrentNetworkDesign，IEEETrans．onSystem，ManandCybernetics，PartB，2004，24(2)：997-1006．【90】黄艳新，周春光．邹淑雪等，一种基于类覆盖和粒子群优化的模糊神经网络系统，计算机研究与发展，2004．41(7)：1053～1061．【91】冯林，张名举．贺明峰等。基于粒子群优化技术的点匹配算法，系统仿真学报．2004，16(8)：1686-一1691．[92]赵波，郭创新，曾一家．基于粒子群优化算法和动态调整罚函数的最优潮流计算，电：E技术学报．2004，19(5)：47-54．[93】Iacoban，R．，Reynolds，R．G，Brewster,J，，Culturalswarms：modelingtheimpactofcultureonsocialinteractionandproblemsolving，Proceedingsofthe2003IEEESwarmIntelligenceSymposium。SIS‘03：205-211．120 大津人学博十学位论文参考文献【94】EberhartR．C．，ShiY．，Particleswarmoptimization，developments，applicationsandresources，ProceedingsoftheIEEECongressonEvolutionaryComputation，Piscataway，2001，pp：81-86．【95】ShiYuhui，EberhartR．，ParameterselectioninparticleSWaVID_optimization，Procofthe7thAnnualConfonEvolutionaryProgramming，WashingtonDC，1998，pp：591-600．【96】EberhartR．，ShiYuhui，Trackingandoptimizingdynamicsystemswithparticleswarms，ProeIEEEInternationalConferenceonEvolutionaryComputation，Hawaii，2001，pp：942-950．【97】徐海，支Ⅱ石，马勇等，基于改进粒子群游优化的模糊逻辑系统自学习算法，计算机工程与应用，2000．(7)：62～63．【98】ShiYuhui，EberhartR．tAmodifiedparticleswarm_optimizer，PmcIEEEInternationalConferenceOnEvolutionaryComputation，Alaska，1998，pp：292～697．【99】shiYuhui，EberhartR．c．，Empiricalstudyofparticleswarmoptimization,ProceedingofCongressonEvolutionaryComputation，Piseataway，1999，PP：1945-1949．【lOO]ClercM．，Theswarmandthequeen：towardsadeterministicandadaptiveparticleswarmoptimization，ProceedingsoftheCongressOnEvolutionaryComputation，Piscataway，1999，pp：1951-1957．[101】AngelineP．，Usingselectiontoimproveparticleswarmoptimization，ProceedingsofIJCNN，Washingtom，1999，pp：84-89．【102]FukuyamaY．．Fundamentalsofparticleswarmtechniques，ModernHeuristicOptimization’FechniquesWithApplicationstoPowerSystems，IEEEPowerEngineeringSociety，2002，pp：45-51．【103】SuganthanP．N．，Particleswarmoptimizerwithneighbourhoodoperator，ProceedingsoftheCongress01"1EvolutionaryComputation,Piscataway，1999，pp：1958～1961．【104】ParsopoulosK⋯EPlagianakosV～PMagoulasG．D，，etal，Improvingparticleswai]l-ioptimizerbyfunction‘‘stretching”，HadjisawasN．，PardalosP．，AdvancesinConvexAnalysisandGlobfloptimization，TheNetherlands：KluwerAcademicPublishers．2001．445～457． 大津人学博十学{f7：论文参考文献[105】DorigoM，ManiezzoV，ColomiA，Antsystem：optimizationbyacolonyofcooperatingagents，IEEETransonSystems，Man，andCybemetics--PartB：Cybernetics，1996，26(1)：29--41．【106】DorigoM，CaroG—DGambardellaL．M．．Antalgorithmsfordiscreteoptimization，ArtificialLife，1999，5(3)：137-172．【107]CostaD．，HenzA，，Antscallcolourgraphs、Journaloftheoptationalresearchsociety，1997，48：295～305．[108】孙新宇，万筱宁，孙林岩，蚁群算法在混流装配线调度问题中的应用，信息与控制，2002，31(6)：486～490．【109】DorigoM，GianniDiCaro，ThomasStutzle．Antalgorithms；FutureGenerationComputerSystems，2000，16：5～7．[110]DorigoM，OambardeUaL．M．，Antcoloniesf．ormetravelingsalesmanproblem，BioSystems，1997，43，pp：73～81．[11l】DofigoM，GambardellaL．M．，Antcolonysystem：Acooperativelearningapproachtothetravelingsalesmanproblem，IEEETransonEvolutionaryComputation，1997，l(1)：53～66．【112】郝晋，石立宝，周家启．一种求解最优机组组合问题的随机扰动蚁群优化算法，电力系统自动化，2002，16(23)：23-28．【113]覃刚力，杨家本。自适应调整信息索的蚁群算法．信息与控制，2002，31(3)：198～201．[114]麦结华，以整个空阀为Li，Yorke混沌集的连续映射，科学通报，t997．42(141：1494--1497．【115】常树人．吕可诚，浅澄“混沌”，大学物理．1999，18(10)：39-48．【116】李兵-蒋慰孙，混沌优化方法及其应用．控制理论-q应用，1997。14(4)：613--6lS．【117]王凌，郑大钟，李清生，混沌优化方法的研究进展，计算机技术与自动化，2001，20(1)：1-5．【118]李兵，混沌优化方法的改进及其收敛性分析．唐山学院学报，2003，16(11：5～6．(119】齐文斌，南志远，综合评判模型在变电站选址中的应用，现代电力，1999，16(1)：39～46． 天津人学博十学位论文参考文献[120】王成山，魏海洋，肖俊等，变电站选址定容两阶段优化规划方法，电力系统自动化，2005，29(4)：62～66．[121】杨丽徙．王家耀，贾德峰等，GIS与模糊模式识别理论在变电站选址中的应用，电力系统自动化，2003，27(18)：87-89．【122】DaiHongwei，YuYixin，HuangChunhua,etal，Optimalplanningofdistributionsubstationlocationsandsizes-modelandalgorithm，IEEE10“ConferenceonComputer,Communication，ControlandPowerEngineering，1993，5(1)：351-354．【123】李德仁，龚健雅，边馥苓。GIS的数据组织与处理方法。测绘通报，1994，第一期，pp：28-37．【124】李宁．孙德宝，岑翼刚等。带变异算子的粒子群优化算法，计算机工程与应用，2004，17：12一14，【125】牛辉，程浩忠，张焰等，电网扩展规划的可靠性和经济性研究综述，电力系统自动化，2000．22(1)：51-56．【126]张焰，电网规划中的可靠性成本一效益分析研究，电力系统自动化，1999，23n5)：33-36，[127】陈庭记，程浩忠，何明等，城市中压配电网接线模式研究，电网技术，2000，24(9)：35-38．【128】YifanTang，PowerDistributionSystemPlanningwithReliabilityModelingandOptimization，IEEETransactionsonPowerSystems，1996，ll(1)：181-189，【129】CarvalhoP，M。SFerreiraL．A．F．M．，UrbanDistributionNetworkInvestmentCriteriaforReliabilityAdequacy,IEEETRANSACTIONSONPOWERSYSTEMS，2004，19(2)：1216--1222．【130]曹世光，柳焯，于尔铿，缺电成本与可靠性规划的研究，电网技术，1997，21(9)：52～57．[131】YUYixin，WANGChengshan，GEShaoytmetal，ModelsandMethodsforUrbanPowerDistributionNetworkPlanning．TrartsactionSofTianjinUniversity，2004，10(2)：91～96．(132】Rong-LiangCherkKimAllen，RoyBiUinton，Value-BasedDistributionReliabilityAssessmentandPlanning，1EEETransoilPowerDelivery，1995，lO(1)：421"--429． 六津人学溥十学位论文参考文献[133】牛雪媛，陈根永，谢志棠等，考虑停电损失的配电网网架规划的免疫算法，继电器，2004，32(7)：1∞13．[134】郭永基，电力系统可靠性分析．北京：清华大学出版社，2003．【135】严超，郭永基，程林，供电可靠性承诺／赔偿法．电力系统自动化，2002，26(181：ll～14．【l36】Nara，K．，Hayashi，Y．，Yamafuji，Y．ctal，ATabuSearchalgorithmfordeterminingdistributiontielines，IntemationalConferenceonIntelligentSystemsApplicationstoPowerSystems，1996，pp：266-270．【】37】段刚，余贻鑫，中压配电网络联络线优化的算法和实现．电力系统自动化，1999，23(15)：10～14．[1381高炜欣，罗先觉，基于蚂蚁算法的配电网网络规划．中国电机工程学报．2004，24(9)：l10—l14．[139】周青山，向铁元．罗亚等，快速环路分解遗传算法在配电网络重构中的应用，中国农村水利水电，2004．7：98～100．[140】TaylorT．，LubkemanD．，Implementionofheuristicsearchstrategiesfordistributionfeederreconfiguration，IEEETransonPWRD，1990，5(1)：239～246．[141】JungKyungHee，KimHoyog，KoYunscok，Networkreconfigurationalgorithmforautomationdistributionsystemsbaseonartificialintelligenceapproach。IEEETPD，1993．8(4)：1933～1941．[1421胡敏茇，陈元，配电系统最优网络重构的模拟退火算法，电力系统自动化，l994．18(2)：24-28．[143】葛少云。刘自发，余贻鑫。基于改进禁忌搜索的配电网络重构，电网技术，2004，28(23)：22-26．【144】Jean-MichelRenders，StephaneP．Flasse，嘶bridMothodsUsingGeneticAlgorithmsforGlobalOptimization，IEEETransonSystems，Man，andCybernetics，1996，26(2)：243～258．【145】JohnYen，JamesC．Liao，BogjuLeeetal，AHybridApproachtoModelingMetabolicSystemsUsingaGeneticAlgorithmandSimplexMethod，IEEETrailsonSystems．Man，andCybernetics，1998，28(2)：173-191．[146】卢耀川，廖迎晨，陈星莺，基于遗传退火法的网络重构技术，电力自动化设备，2003，23(1)：28～31．124 大津人学1月t-t-学位论文参考文献【147】赵登福，刘云，周文华，以能量损耗最小为目标函数的网络重构，西安交通大学学报，1999，33(8)：16～19．【148】Zhu，Jizhong，Chang，C⋯SRefinedgeneticalgorithmforminimum—lossreconfigurationofelectricaldistributionnetwork，ProceedingsoftheInternationalConf01"1EnergyManagementandPowerDelivery,EMPD，1998，v012：485-489．【149】Goswamis．K．，BasuS．K．Anewalgorithmforthereeonfigurationofdistributionfeedersforlossminimization，IEEETransonPowerDelivery,1992，7(2)：1484-1491．【l50】PeponisG-J．，PapadopoulosM．P．，HatziargyriouN．D．，OptimalOperationofDistributionNetworks，IEEETransactionsonPowerSystems，1996．11(1)：59-67．【151】HsuY．Y．，KuoH～CDispatchofCapacitorsonDistributionSystemUsingDynamicProgramming,lEEProceedings，1993，140(6)：433～438．【152】胡泽舂，王锡凡，配电网无功优化的分时段控制策略，电力系统自动化，2002，23(6)：45---49．f153】陈星莺．钱锋．杨素琴．模糊动态规划法在配电网无功优化控制中的应用，电网技术，2003，27(2)：68-71，[154】ErtemS．TudorJ．R．，OptimalShuntCapacitorAllocationbyNonlinearProgramming．IEEETransonPowerDelivery，1987，2(4)：1310---1316．【155】谭涛亮。张尧．基于遗传禁忌混合算法的电力系统无功优化，电网技术，2003．28(11)：57～6t。【156】余欣梅，李研，熊信银等，基于PSO考虑谐波影响的补偿电容器优化配置，中国电机工程学报，2003，23(2)：26～31．[157】张荚蓉，盂昭勇，李剑，基于TS和GA算法的配电电容器优化投切，继电器，2004．32(14)：29～31．【158】周皓．周晖，电网无功电压综合控制的改进sA算法，继电器，2004，32(1)：24—27．[1591褚美茹，崔明勇。混沌遗传算法在配电网无功优化中的应用，信息技术，2004．28(10)：48-50．【1601刘自发。葛少云，余赡鑫，基于混沌粒子群优化方法的电力系统无功最优潮流，电力系统自动化，2005．29(7)：53～57． 大津人学蹲十学位论文参考文献[161】S．Civanlar，J．J．Grainger，H．Yin，DistributionFeederRecontigurationforLossReduction，IEEETransactionOBPowerDelivery，1998，3(3)：1217-1223．【162】T．P．Wagner，A．Y．Chikhani，R．Hackam．FeederReconfigurationforLossReduction：AnApplicationofDistributionAutomation，IEEETransactiononPowerDelivery，1991，6(4)：1922-1933．[1631Santoso，N．1．，Tan，O．T．，Neural—netbasedreal-timecontrolofcapacitorsinstalledondistributionsystems，IEEETransactionsonPowerDelivery,1990，5(1)：266-272．126 大沣人学博十学忙沦文发表论文剥科研情况说明发表论文和科研情况说明发表的论文：1．刘自发，葛少云，余贻鑫，“一种新的电力系统无功优化方法”，天津大学学报，2005，38(5)：443～447。2．葛少云，刘自发，余贻鑫，“基于改进禁忌搜索的配电网络重构”，电网技术．2004，28(23)：22～26(El收录，05018764901)。3．赵杰辉，葛少云，刘自发，“基于主成分分析的径向基函数神经网络在电力系统负荷预测中的应用”，电网技术。2004，28(5)：35．--40(El收录．8036285)。4．刘自发，葛少云。余贻鑫，“基于混沌粒子群优化方法的电力系统无功最优潮流”，电力系统自动化，2005，29(7)：53～57。5．刘自发，葛少云，余贻鑫．“一种混合智能算法在配电网络重构中的应用”，中国电机工程学报，(已录用)。参与的科研项目：1．协助丌芨了辽宁“电力市场营销辅助决策支持系统负荷预测部分”，2003年1月完成。2．主持丌发了CAMPower软件中潮流计算模块，2003年9月完成。3．主持玎发了Ultracom2．0串口通讯软件，2004年12月完成。 天津人学博十学位论文致谢致谢本文的研究工作是在导师余贻鑫教授和葛少云副教授的悉心指导下完成的．二位导师严谨求实的学风和为人师表的风范使我受益终生，在此致以我崇高的敬意和由衷的感谢!在研究生期间．一直得到黄纯华教授、王成山教授、和路志英副教授、贾宏杰副教授、林济铿副教授等的热心关怀和指导，在此表示我衷心的感谢。在博士期问，还得到本研究组的张弘鹏、魏伟、吴建中、樊纪超、刘洪等博士研究生和赵杰辉、王澍、尹叶秀、刘洪、董静嫒、闰大威、董智、侯学波、张栋、张振宇、巫卿、张国良等硕士研究生人的大力支持，以及天大求实电力新技术有限公司刘昱、王辛、申刚、李小宇、刘中胜、张群华、徐英虎、刘宇等工程师在课题期f白j给予的合作和帮助，这晕谨表谢意。感谢王风梅、王宝囡老师几年来在学习以及生活上的关心和帮助。最后，特别感谢我的妻子何文给予我的深深理解和全心支持，感谢我的女)b支JJ姝给予我对人尘的感悟和动力，感谢我的父母和家人给予我的鼓励与关怀以及靳现林工程师、陈德志搏士、王会凯先生、郑国珍女士及其家人在工作及生活上的帮助和关心。二零零五年五月三十同于天津大学自动化学院406室 基于智能优化算法的配电网络规划与优化运行研究作者：刘自发学位授予单位：天津大学参考文献(163条)1.陈章潮.唐德光城市电网规划与改造19982.蓝毓俊现代城市电网规划设计与改造20043.HLWillis.HTram.MVEngelOptimizationApplicationstoPowerDistribution1995(04)4.王成山.王赛一.葛少云.谢莹华.尹页秀.林瑞兴中压配电网不同接线模式经济性和可靠性分析[期刊论文]-电力系统自动化2002(24)5.余贻鑫.邱炜.刘若沁基于启发式算法与遗传算法的配电网重构[期刊论文]-电网技术2001(11)6.THFawzi.KFAliANewPlanningModelforDistributionSystems7.TramHN.WallDLOptimalconductorselectioninplanningradialdistributionsystems1988(01)8.HWDommel.WFTinneyOptionPowerFlowSolution1968(10)9.CivanlarS.GraingerJJForecastingdistributionfeederloads:modelingandapplicationtovolt/VArcontrol1988(01)10.BaranM.WuFFOptimalsizingofcapacitorsplacedonaradialdistributionsystem1989(01)11.MerlinA.BackHSearchforaMinimal-LossOperatingSpanningTreeforanUrbanPowerDistributionSystem197512.BaranM.WuFFNetworkreconfigurationindistributionsystemsforlossreductionandloadbalancing1989(02)13.ShirmohammadiD.HongHWReconfigurationofElectricDistributionNetworksforResistiveLineLossReduction1989(02)14.DLWall.GLThompsonAnoptimizationmodelforplanningradialdistributionnetworks1979(03)15.GLThompson.DLWallABranchandBoundModelForChoosingOptimalSubstationLocations1981(05)16.MamandurKRC.ChenowethRDOptimalcontrolofreactivepowerforimprovementinvoltageprofilesandforreallossminimization1981(07)17.邓佑满.张伯明.相年德配电网络电容器实时优化投切的逐次线性整数规划法1995(06)18.ChiangHsiaoDong.ReneJeanJueauOptimalnetworkreconfigurationindistributionsystems,PartⅠ:Anewsormulastionsandsolutionmetholdology1990(04)19.GonenT.GooteBLDistributionsystemplanningusingmixed-integerprogramming1981(02)20.RamaIS.RamachandranKHSOptimalReactivePowerAllocationforImprovedSystemPerfor2mance1984(06)21.朱太秀电力系统优化潮流与无功优化1990(04)22.SCivanlar.JJGrainger.HYinDistributionfeederreeonfigurationforlossreduction1988(03)23.MesutEB.FelixFWNetworkreconfigurationindistributionsystemsforlossreductionandloadbalancing1989(02)24.DaiushShirsohammadi.HWayneHongReconfigurationofelectricdistributionnetworksforresistivelinelossesreduction1989(02) 25.AokiK.NaraK.SatohTNewapproximateoptimizationmethodfordistributionsystemplanning1990(01)26.NaraK.SatohT.AokiKMulti-yearexpansionplanningfordistributionsystems1991(03)27.GoswamiSKDistributionsystemplanningusingbranchexchangetechnique1997(02)28.MiguezE.CidrasJ.Diaz-DoradoEAnimprovedbranch-exchangealgorithmforlarge-scaledistributionnetworkplanning2002(04)29.KirkpatrickS.GelattCD.VecchiMPOptimizationbysimulatedannealing30.倪秋龙.黄民翔基于支路交换的模拟退火算法在配电网规划中的应用[期刊论文]-电力系统及其自动化学报2000(4)31.DanJiang.RossBaldickOptimalelectricdistributionsystemswitchreconfigurationindistributionsystemsusingsimulatedannealing1994(29)32.Hsiao-DongChiang.Jin-ChengWang.JianzhongTongOptimalcapacitorplacement,replacementandcontrolinlarge-scaleunbalanceddistributionsystems:systemsolutionalgorithmsandnumericalstudies1995(01)33.刘吉来无功优化的改进模拟退火算法1998(02)34.贾德香.唐国庆.韩净基于改进模拟退火算法的电网无功优化[期刊论文]-继电器2004(4)35.HollandJHAdaptationinnaturalandartificialsystems36.MirandaV.RanitoJV.ProencaLMGeneticalgorithmsinoptimalmultistagedistributionnetworkplanning1994(04)37.MatesMAAnewpowerflowmethodforradialnetworks200338.KoichiNara.AtsushiShiose.MinoruKitagawaImplementationofgeneticalgorithmfordistributionsystemslossminimumreconfiguration1992(03)39.MSrinivas.LMPattnaikAdaptiveprobabilitiesofcrossoverandmutationingeneticalgorithms1994(04)40.余贻鑫.段刚基于最短路算法和遗传算法的配电网络重构[期刊论文]-中国电机工程学报2000(9)41.刘莉.陈学允基于模糊遗传算法的配电网络重构[期刊论文]-中国电机工程学报2000(2)42.马晋弢.L.L.Lai.杨以涵遗传算法在电力系统无功优化中的应用[期刊论文]-中国电机工程学报1995(5)43.LeeKY.XiaominBai.Young-MoonParkOptimizationmethodforreactivepowerplanningbyusingamodifiedsimplegeneticalgorithm1995(04)44.赵登福.周文华.张伏生.夏道止遗传算法在无功优化应用中的改进[期刊论文]-电网技术1998(10)45.GloverFTabusearch-PartⅠ1989(03)46.MoriH.IimuraYApplicationofparalleltabusearchtodistributionnetworkexpansionplanningwithdistributedgeneration200347.王成山.王赛一基于空间GIS和Tabu搜索技术的城市中压配电网络规划[期刊论文]-电网技术2004(14)48.Yann-ChangHuang.Hong-TzerYang.Ching-LienHuangSolvingthecapacitorplacementprobleminaradialdistributionsystemusingTabuSearchapproach1996(04)49.陈根军.李繼洸.唐国庆基于Tabu搜索的配电网络重构算法[期刊论文]-中国电机工程学报2002(10)50.唐红键.冯可配网重构算法的改进和研究[期刊论文]-电力勘测设计2003(4)