（电力系统及其自动化专业论文）基于粒子群优化算法的变电站选址研究.pdf

华北电力大学硕士学位论文 摘要 变电站选址是配电网规划的重要组成部分。其位置是否合理直接影响到网架结 构，关系到电网的可靠性和运行的经济性。 基于群智能，本文提出了一种用于配电网变电站选址的新算法。首先阐述变电站选 址的重要性：接着介绍粒子群优化算法理论；然后结合考虑影响变电站选址的实际因素 拟定具体的规划方案，建立变电站选址的数学模型，并对标准粒子群优化算法进行改进， 提出具有模糊自适应性的粒子群优化算法，用该算法对简化的变电站选址模型进行优 化，并用d e l p h i 语言编程；最后用一个实例介绍了该算法的应用。算例结果表明，该 方法更具科学性和工程实用价值。 关键词：变电站，选址，粒子群优化，模糊，自适应性 t h es i t es e l e c t i o nf o rs u b s t m i o n sp l a y sas i g n i f i c a n tr o l ei nd i s t r i b u t i o nn e t w o r k p l a n n i n g d i s t r i b u t i o nn e t w o r ks t r u c t u r ei si n f l u e n c e db yt h es i t e a sw e l la si t sr e l i a b i l i t ya n d e c o n o m i ce f f i c i e n c y an e wa l g o r i t h mb a s e do ns w a n t li n t e l l i g e n c ef o rt h es i t es e l e e t i o no fd i s t r i b u t i o n n e t w o r ks u b s t a t i o n si si n t r o d u c e d t h es i g n i f i c a n c ef o rt h es u b s t a t i o ns i t es e l e c t i o ni sf i r s t r e p r e s e n t e d t h e nt h et h e o r yo fp a r t i c l es w a l t i io p t i m i z a t i o na l g o r i t h mi sf o r m u l a t e d a n d t h e nt h es p e c i f i cp l a n n i n gp r o j e c ti ss t u d i e do u ta c c o r d i n gt oa c t u a lf a c t o r sw h i c hi n f l u e n c e t h es i t es e l e c t i o n t h em a t h e m a t i e a lm o d e lf o rt h es u b s t a t i o ns i t cs e l e c t i o ni se s t a b l i s h e d a f t e rs t a n d a r dp a r t i c l es w a m io p t i m i z a t i o na l g o r i t h mi si m p r o v e d ，t h en e wa l g o r i t h mt h a t p o s s e s s e so ff u z z ya d a p t i v ec h a r a c t e ri sf o r m u l a t e d ，b yw h i c h ，t h es i m p i em a t h e m a t i c a lm o d e l f o rt h es u b s t a t i o ns i t es e l e c t i o ni so p t i m i z e d ，a n dt l l es o f t w a r ei sp r o g r a m m e db vd e l p h i t h c a t l l ed e f i n i t i v em a t h e m a t i c a lm o d e li sd e v e l o p e db a s e do i lp a r t i d eb 如v a h no p t i m i z a t i o nt o c o n f i r mt h es u b s t a t i o nl o c a t i o n f i n a l l yat y p i c a la p p l i c a t i o ni sp r e s e n t e da sac a s es t u d y t h e c a s es h o w st h a tt h i sm e t h o di sm o r es c i e n t i t l e a n do fp r a c t i c a lv a l u ei np r o i e c t s h ey a n g h u a ( e l e c t r i cp o w e rs y s t e ma n da u t o m a t i o n ) d i r e c t e db yp r o f z h a n gj i a n h u a k e y w o r d s ：s u b s t a t i o n ，s i t es e l e c t i o n ，p a r t i c l es w a r mo p t i m i z a t i o n ，f u z z y , a d a p t i v e 声明 本人郑重声明：此处所提交的硕士学位论文基于粒子群优化算法的变电站选址研 究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得 的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 学位论文作者签名：继 日期：盘! 生 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文：同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期： 导师签名： 日期：趣l ：!茳 华北电力大学硕士学位论文 1 1 电网规划中的站址问题 第一章绪论 1 1 ，1 最优选址问题及选址问题的重要性 在运筹学中，最优选址问题是指已知一些现有设施的地址，希望确定一个或几 个新设施的地址，在满足业务要求、服务要求、技术条件等约束情况下，使某目标 函数达到最优化，目标函数一般是与这种业务有关系的某一价格函数取最小值“1 。 选址问题有两种不同的类型：单源( 单设施) 选址问题和多源( 多设施) 选址问题。 单源选址问题是对于位置已经知道的若干个现有设施，找出单一的一个新设旌的最 优地址；多源选址问题是对于已经知道的若干现有设施，找出两个或更多的新设施 的最优地址。3 。如果有关区域中的任一点都和别的点的地位相同，也就是从数学上 来讲，有无限个可能的地点存在，则这类阀题就是连续型选址闯题：如果在某一区 域中只有有限个位置需要考虑，而且这些位置在事先就能具体说出来。这类问题就 是离散型选址问题m 。 选址问题已经渗透到国民经济的各部门，大到城市规划中的基础设施，如电力、 通信、交通、供热系统中相关设备或站址的选取和定位，小到商店、工厂的地理位 置确定等等。虽然研究的对象不同，但选址是否合理。均将直接影响到由此产生的 社会效益和经济效益0 1 。选址问题是规划项目前期工作中最重要的内容，它的任务 就是在规划区范围内，确定设备的具体位置。选址是否合理，直接影响企业的投资、 建设速度、施工难易，以及建成后长期的生产经营管理和经济效益，也对城市建设、 地区经济和自然环境有极大影响。由于选址工作是一项复杂的经济、政治和技术相 结合的工作，要考虑各方面的因素”1 。因此，要满足上述各方面的要求，会遇到很 多特殊的问题和矛盾，必须综合考虑0 1 。例如，供热系统是市政设施的重要组成部 分，尤其在我国北方地区，它已成为人们越过寒冷冬天的生活必需品。近年来，随 着集中供热的迅速发展，供热规模越来越大，多热源供热系统不断涌现，为了降低 供热成本和提高供热效率，多热源选址优化已成为迫切需要“3 。在内陆的集装箱运 输网络体系中，“无水港”是集装箱运输及多式联运中极其重要的环节。它是集装 箱在内陆运输的枢纽，为集装箱运输向内陆发展提供支持，其实质是港口的功能在 内陆的延伸。“无水港”选址是否合理，直接关系到船务公司的运输成本、经济效 益和运输效率“3 。而停车设施规划是城市交通规划的重要组成部分，在有限的城市 空间中，合理布局停车设旌，最大限度地提高停车设施服务水平和符合城市可持续 发展的需要，是选址规划面临的突出问题n ，。 1 华北电力大学硕士学位论文 1 1 2 变电站优化选址的意义 变电站规划是电网规划的重要组成部分。根据电源情况及用电量需求，建立合 理的电网结构，是电网规划设计的主要任务之一。要确定合理的电网结构，必须首 先确定变电站的位置，使变电站规模和供电范围最佳，从电网建设和运行来说就是 要得到一个投资和运行费用均为最小的结构”1 。在常规的电网变电站规划中，往往 都是通过对大量数据的统计确定出水平年的负荷量，再考虑原有变电站的布局，经 人工分析比较最终确定出新建变电站站址。据调查，电力企业在进行变电站站址 选择时，经常都是依靠经验确定站址，这样就很难保证所选站址是最优站址”1 。这 种传统的变电站选址方法没有量的概念，工作量大，工期也较长，其主要缺点是人 为因素影响较大“。 电力系统中变电站站址的选择，对系统的安全性和经济性有很现实的意义“”。 电网投资在整个电力系统及其整个基础设施工程中占了很大比例，电网规划的优化 将会带来可观的经济效益。3 。变电站布局的合理化不仅可以节省建设投资，而且可 以极大地降低电网损耗，提高运行管理水平和调度的灵活性。变电站是主网和配网 的交汇点，既是上级电网的负荷点，同时又是下级电网的电源点。”。变电站站址的 选择关系到电网的规划是否合理，直接影响电力企业的经济效益，同时还将直接决 定整个电网的结构，而不同的网架结构将产生不同的系统运行成本和系统的安全级 别。因此，在电网规划中，变电站站址的选择是一个重要问题，它的优选直接影响 未来电网的结构，关系到整个电网的可靠性，也会带来可观的经济效益。因此，迅 速而有效地确定出若干有希望的候选站址以及新增站点与原网络各节点的联络关 系，是电网规划应该深入研究的起点和方向，对电网的优化规划具有重大意义0 1 。 1 2 最优化方法在变电站选址中的应用概述 如前所述，变电站站址规划要考虑用地规划、土地价格、环境保护、交通运输、 施工条件等问题，属于系统优化问题；从数学上看，变电站站址规划属于复杂的多 目标、多约束、非连续的非线性规划问题，一般采用运筹学中的单源( 单站址) 或多 源( 多站址) 连续选址。”模型。计算机技术和优化方法的发展为电力科学工作者和 技术人员提供了很多有效的算法来解决单站址连续选址问题，但对于多站址连续选 址闯题，由于要确定的变屯站站址的数量不止一个，并且每座变电站的容量未知，再加 上还存在负荷点的分配( 归属) 问题，因而属于n p 难的组合优化问题，其中涉及到连 续量、离散量和集合量，目前还没有一种有效的算法来处理这一难题。变电站站址 规划的求解方法大致上可以分为传统的数学优化方法、现代启发式方法和智能优化 算法3 。 2 华北电力大学硕士学位论文 1 2 1 传统的数学优化方法 对单站址连续选址，传统的优选方法主要是数值迭代法，即目标函数对决策变 量求偏导，令其为零，然后采用数值迭代法进行迭代，即可求得其解。 对多站址连续选址，情况要复杂得多，如上所述，算法必须要同时处理连续量、 离散量和集合量，传统解法一般有混合整数一分枝定界法、随机终点法和交替选址一 分配法等。1 9 8 1 年，t h o m p s o n 等人采用混合整数一分枝定界法来解决电网规划中的 变电站站址选择问题“。近几年，我国学者提出运用运输问题模型来校核变电站的最 佳位置、容量和供电范围“，采用混合整数一分枝定界法求解规划问题“，而且提 出了无需提供待选站址的变电站选址、定容的算法方案o7 。随机终点法是从h 个总 数中随机取出m 个数，把这m 个数作为电源点，然后分配给拜一m 个负荷点，使总费用 最小，即最后选出的m 个点即为最优解。交替选址一分配法是一种单调下降的收敛过程， 将再个负荷点组成的集合划分成元素个数大致相等的m 个子集，对其中的每一个子集解 一个单站址连续选址问题，如果求出的这个电源点和每一个负荷点的距离比目前分配中 的那个电源点靠的更近；则重新分配各负荷点，继续进行单站址选址直到得到满意的结 果“，1 ”。 1 2 2 现代启发式方法 现代电网结构的复杂性和规模的庞大性对电网规划提出了更高的要求，传统的 数学优化技术已经不能满足这一要求。现代启发式方法不同于传统的数学优化方 法，它是以直观分析为依据的算法，两且同规划及运行人员的经验相结合，相对于 纯数学方法能够较为准确地实际模拟电力行为。 1 9 8 8 年，s c i v a n l a r 等人首先提出支路交换法”1 ( b r a n c he x c h a n g em e t h o d ，b e m ) ， 提出之初，仅用来对配电网进行重构。此后，支路交换法获得进一步发展和应用。1 9 9 7 年，s k g o s w a m i 采用支路交换法实现了配电网的综合规封j ，不仅考虑了配电网网架优 化，还考虑了变电站的优化规划方案。“；层次分析法。1 也获得了较广泛地应用，它是 将一个具有多层次、多属性指标因素的复杂方案的选优决策问题，通过层次序列化 和因素重要性的判断及因素定量计算得到优选方案，是定性与定量相结合的多目标 决策技术；专家决策系统决策法通过专家经验建立专家系统来选撵变电站的位置， 由于变电站选址前期工作中诸多因素不可能完全清楚，选址的各项评估值又是一个 模糊量，因此，充分吸收已有的专家知识，建立一个完善合理的决策推理模型实现 变电站选址的科学决策，具有十分重要的意义。基于证据理论的综合评判模型即属 于此类专家决策系统，它采用证据理论和模糊集理论，通过建立一系列变电站选址 决策的指标体系，把变电站选址问题分解成若干个子问题子证据，在对子问题子证 据处理后，采用某种证据合成规则合成得到整个问题的结论。与此同时，作为其特 3 华北电力大学硕士学位论文 例的模糊综合评判模型也在变电站站址规划中得到了较为广泛地应用，但它只适用 于对所研究的对象十分了解的情况“。 1 2 3 智能优化算法 随着电网规模越来越大，变电站选址的数学模型也越来越复杂，这就要求采用 性能更好、速度更快的算法来选址，智能优化算法便是其中一类。包括：i ) 模拟退 火算法“”( s i m u l a t e da n n e a l i n g ，简称s a ) ，该算法基于m e n t e c a r l o 迭代求解策略， 由某一较高初始温度开始，利用具有概率突跳特性的m e t r o p o l i s 抽样策略( 在温度t ， 由当前状态i 产生新状态，两者的能量分别为占。和e ，若e ，t e ；则接受新状态，为 当前状态；否则，若概率只= e x p 一僻，一e ；) l k t 】大于 0 ，1 区间内的随机数，则仍旧 接受新状态，为当前状态，若不成立，则保留新状态i 为当前状态，其中k 为 b o l t z m a n n 常数) 在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最 终得到问题的全局最优解；2 ) 遗传算法o “矧( g e n e t i ca l g o r i t h m ，简称g a ) ，其操 作过程十分简单，即建立与目标函数有关的适应度函数或评价函数，然后对决策变 量进行编码，从一个具有个( 决策变量数) 特征字符串的初始群体出发，循环地 根据适应度值执行选择、交叉和变异操作，直到满足某一终止准则，即得问题最优 解的编码串，通过译码最终得到最优解；3 ) 人工神经网络优化算法”( a r t i f i c i a l n e u r a ln e t w o r k s ，a n n ) ，其网络模型有多种，h o p f i e l d 模型是最常用的一种，它是 一种非线性动力学模型，通过引入类似l y a p u n o v 函数的能量函数概念，把神经网络 的拓扑结构( 用连接权矩阵表示) 与所求问题( 用目标函数表示) 对应起来，转换成神 经网络动力学系统的演化闯题。因此，在用h o p f i e l d 求解优化问题之前，必须将问 题映射为相应的神经网络。具体步骤如下： ( 1 ) 选择合适的问题表示方法，使神经网的输出与问题的解相对应； ( 2 ) 构造合适的能量函数，使其最小值对应问题的最优解； ( 3 ) 由能量函数和稳定条件设计网络参数，妇连接权值和偏置参数； ( 4 ) 构造相应的神经网络和动态方程； ( 5 ) 用硬件和软件模拟。 另外，变电站站址优化规划方法还有网络图论法、最小路径法“1 、混合贪心 - - h o p f i e l d 神经网络优化算法“”等。 基于群智能的优化算法有两种：蚁群算法旧1 ( a n tc o l o n yo p t i m i z a t i o n ，简称 a c 0 ) 和粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 算法。在下一章将 简要介绍蚂蚁算法和详细介绍粒子群优化算法。 4 华北电力大学硕士学位论文 1 3 本文的主要工作 变电站优化选址的一般表述是：在一定区域范围内，寻优新建变电站的位置坐 标，使某目标值( 如投资和运行费用) 达到最优。由于变电站位置坐标的寻优为一个 带约束的复杂非线性规划问题，需要定位的变电站可能又不止一座，考虑到变电站 选址需要达到多个目标要求，因此变电站优化选址又是一个多目标优化问题。本文 在以往变电站站址规划研究的基础上，根据电网规划中变电站选址的原则和要求，采用 智能优化算法结合考虑影响选址的实际因素研究了变电站的优化选址问题，主要工作如 下： ( 1 ) 拟定变电站站址规划方案。提出将已有变电站和新建变电站分而治之的策 略，对于已有变电站，保持其位置不变，根据其新变电容量( 优先考虑扩建) 、容 载比要求及“就近”原则，结合考虑影响变电站选址的实际因素，确定出该已有变 电站的最佳供电面积，从而该已有变电站的不变的位置就是最佳站址。已有变电站 的供电范围确定后，规划区内剩余的负荷将由m 座新建变电站供电。根据变电站供 电范围不能交叉、重叠的原则以及新建站的容量( 满足容载比要求) ，将剩余负荷 分成m 个区域，这样在每个区域内只需新建一座变电站，从而多站址连续选址优化 问题就转化成单站址连续选址问题。 ( 2 ) 在基本粒子群优化算法理论的基础上，结合参考其他文献，提出一种具有模糊 自适应性的粒子群优化算法( f a p s o 算法) ，通过计算适应度平均值，将粒子分为两个 小种群，并采用不同的惯性权值，有效地克服了算法运行后期粒子的趋同性问题，增大 了粒子之间的差异，保证了算法的全局搜索能力，提高了算法的优化性能。 ( 3 ) 建立基于f a p s o 算法理论的变电站站址优化模型。在选址的通用模型的基础上， 结合拟定的变电站规划方案，提出基于f a p s o 算法理论的变电站站址优化模型。该模型 为一单站址连续模型，充分考虑了变电站投资和建设费用以及线路投资和网络运行费 用，但变电站费用要受到地理信息等实际因素的影响，这些实际因素无法量化，不可能 在模型中体现，因此，为简化问题，模型中只包含线路费用函数。 ( 4 ) 在( 3 ) 提出的模型的基础上，用d e l p h i 语言编程，实现f a p s o 算法，即开发一 套用于变电站站址优化规划的软件。 5 华北电力大学硕十学位论文 2 1 引言 第二章粒子群优化算法概述 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 算法是人类受到生物 系统运行机制的启发而建立和发展起来的一个研究工具，最早源于对鸟群觅食行为 的研究，由e b e r h a r t 博士和k e n n e d y 博士于1 9 9 5 年发明”1 ，是一种基于群智能方法 的演化计算技术啪，是演化计算领域中的一个新的分支。 与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法( g e n e t i ca l g o r i t h m ， 简称g a ) 不同的是，粒子群优化算法的运行机理不是依靠个体的自然进化规律，而 是对生物群体的社会行为进行模拟，是通过个体之间的协作来寻找最优解的。在生 物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为，这种行 为体现的是一种存在于生物群体中的信息共享机制。p s o 算法就是对这种社会行为 的模拟，即利用信息共享机制，使得个体间可以相互借鉴经验，从而促进整个群体 的发展。 p s o 算法和g a 类似，也是一种基于迭代的优化工具，系统初始化为一组随机解， 通过某种方式迭代寻找最优解。但p s o 算法没有g a 的“选择”、“交叉”和“变异” 算子，编码方式也较g a 简单。“3 “。由于p s o 算法容易理解、易于实现，所以p s o 算 法发展很快。在函数优化、模式识别、模糊系统控制、神经网络训练等领域已得到 广泛应用 3 2 “7 o 2 2 进化算法简介 在自然界的漫长的进化过程中，各种生物与自然环境相互作用，表现出了复杂 的行为。随着科技和社会的进步，人类涉足研究的领域越来越广，研究生物的习性 和行为方式便是其中之一。随着研究的深入，人类发现，自然界中的各种生物不仅 仅可以被动地适应环境，更熏要的是它能够通过学习、模拟与仓口造，不断提高自己 适应环境的能力。人类从中受到启发，于是便开始了模拟生物或各种自然现象的研 究。特别是电子计算机的问世，更加速了人类模拟生物的研究进程，并不断涌现出 新成果，如神经网络、模糊系统、进化算法等。神经网络是人类对其大脑信息处理 机制的模拟，模糊系统是人类对其思维方式的模拟，遗传算法是对生物进化机制的 模拟，免疫算法是对免疫机理的模拟o “。除了向自身结构学习以外，人类还可以向 其自身的进化这一更为宏观的过程学习，来增强自己解决问题的能力，其代表的方 法就是进化算法。它们都具有一定的自组织、自适应性，而且尤其重要的是，它们 都是具有高度并行的算法。这些方法的出现，为利用计算机解决复杂问题带来了希 6 华北电力大学硕士学位论文 望。 自然界的进化是经过漫长的自适应过程一进化过程而获得结果的，自然进化过 程本质上就是一个学习与优化的过程，这一优化过程使生命体达到适应环境的最佳 结构与效果。进化算法就是基于这种进化思想而发展起来的一种通用的问题求解方 法，即我们不必非常明确地描述问题的全部特征，只需要根据自然法则来产生新的 更好解。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进 行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采 用种群( 即一组表示) 的方式组织搜索，这使得它可以同时搜索解空间的多个区域。 而且用种群组织搜索的方式使得进化算法特别适合大规模并行。在赋予进化算法自 组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使进 化算法具有不受其搜索空间限制条件( 如连续、可微、单峰等) 的约束及不需要其它 辅助信息( 如导数) 的特点。这种崭新的特点使得进化算法不仅能获得较高的效率而 且具有简单、易于操作和通用的特性。目前，进化算法已经在机器学习、过程控制、 经济预测、工程优化等领域取得了巨大的成功，可以预测，进化计算必将会获得更 广泛而深入的应用。 2 3 群智能方法 长期以来，以群居生活的昆虫，如蚂蚁、蜜蜂、黄蜂、白蚁等，引起了包括自 然学家和艺术家在内的人们的兴趣。昆虫群体行为的奇妙之处在于：昆虫的个体都 很简单，但当它们一起协同工作时却能表现出很复杂的行为，如蜜蜂能够建造完美 的蜂窝，蚂蚁觅食能够找到最短的路径，简单的昆虫能建造复杂形状的巢穴等。群 居昆虫中的每一个个体看上去都有自身的行动方式，并且整个群体在整体上呈现出 高度的有组织性。显然，在所有个体活动的完美集成过程中不需要任何的指导。事 实上，研究社会性昆虫的科学家发现在群体中的协作是高度自组织的，它们的协调 行为是通过个体之间的交互行为直接实现，或者个体与环境的交互行为间接实现 的。虽然这些交互行为非常简单，但是他们聚在一起却能解决一些难题啪1 。 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫行为的模拟设计了 一系列新的求解问题的算法，这就是计算智能领域中的群智能算法。”( s w a r m i n t e l l i g e n c e ，简称s i ) 。如果说进化算法是人们对生物自身进化过程的模仿，那 么建立在人工生命基础上的群智能算法就是对群居生物社会系统的模拟。群智能在 没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案 提供了基础。 计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ，简称c i ) 领域中，有两种基于群智能 的算法：蚁群算法和粒子群优化算法。下面简要介绍人们最早研究的蚁群算法， 7 华北电力大学硕士学位论文 在后续章节将详细介绍粒子群优化算法。 2 3 1 蚁群算法 蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它 就返回巢中通知同伴并沿途留下一种称为“信息素”( p h e r o m o n e ) 的物质作为蚁群 前往食物所在地的标记。科学家们对此进行过试验：用人造的信息素在纸上画一条 路径，对蚂蚁进行试验，结果蚂蚁果然都沿着有信息素的路径行走。随着时间的推 移，信息素会逐渐挥发，如果两只蚂蚁同时找到同食物，又采取不同路线回到巢 中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近 的路线前往食物所在地。蚁群在觅食过程中能够找到最近或者障碍最小的路径到达 食物源。 根据蚂蚁的集群觅食活动规律，人们设计了一个利用群体智能寻找最优路径的 蚁群算法，它是人们受蚁群觅食活动行为的启发而建立的机制，主要包括以下四个 步骤： ( 1 ) 一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回； ( 2 ) 蚂蚁在往返途中，在路上留下外激素( 信息素) 标志，蚂蚁利用信息素进 行相互通信； ( 3 ) 外激素将随时间逐渐蒸发( 一般可用负指数函数来描述，即乘上因子e “) ； ( 4 ) 由蚁穴出发的蚂蚁，其选择路径的概率与各路径上的外激素浓度成正比。 利用同样原理可以描述蚁群进行多食物源的寻食情况。 蚁群算法己经成功运用在求解很多离散优化问题上。最著名的是9 0 年代d o r i g o 提出的利用蚁群优化算法来解决计算机算法学中经典的“货郎担问题”，即假设有n 座城市，需要对所有n 座城市进行访问且只访问一次的最短距离。 在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”来摸索不同路线，并 留下会随时间逐渐消失的虚拟“信息素”。虚拟“信息素”也会挥发，每只蚂蚁每 次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根 据“信息素较浓的路线更近”的原则，即可选择出最佳路线。由于这个算法利用了 正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算 法，所以它能够不局限于局部最优解。蚁群算法也存在一些缺点，如需要较长的搜 索时间，容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全 一致，不熊对解空间进行进一步搜索，不利于发现更好的解。 目前，除了也已得到公认的模拟退火算法、遗传算法、禁忌搜索算法等计算智 能算法外，新加入这个行列的蚁群算法正在开始崭露头角，为复杂困难的组合优化 问题提供了新颖的具有竞争力的求解算法。“”3 。 8 华北电力大学硕士学位论文 2 3 2 群智能的特点 ( 1 ) 群体中相互合作的个体是分布的，这样更能够适应当前网络环境下的工作 状态； ( 2 ) 没有中心控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某 几个个体的故障而影响整个问题的求解； ( 3 ) 每个个体只能感知局部信息，不能直接拥有全局信息。个体之间不是直接 通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性； ( 4 ) 系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且 实现也比较简单，具有简单性； ( 5 ) 群体的复杂行为通过简单个体的交互过程来实现，具有自组织性。 目前，群智能的研究还处于初级阶段，并且存在许多困难，但因为具有这些优 点，可以预言群智能的研究代表了以后计算机研究发展的一个重要方向“。下面详 细介绍粒子群优化算法。 2 4 粒子群优化算法 2 4 1 粒子群优化算法的基本原理 p s 0 算法的基本概念源于对鸟群觅食行为的研究。我们可以设想这样个场景： 一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那 里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么 呢? 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 事实上，研究者发现鸟群在搜寻食物过程中经常会突然改变方向、时而散开、 时而聚集，其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适 宜的距离，也就是说，鸟群的觅食行为呈现出群体特征。通过对类似生物群体行为 的研究，研究者发现其中同样存在着这样一种群体特征，这就是社会信息共享机制， 它为群体的进化提供了一种优势。可以用几条简单的规则将这种群体行为 ( s w a r m b e h a v i o r ) 在计算机中建模，也就是在计算机中用这几条简单的规则来建 立个体的运动模型，r e y n o l d s 使用下列三个规则作为简单的行为规则1 ： ( 1 ) 向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 这就是著名的b o i d ( b i r d o i d ) 模型。在这个群体中每个个体的运动都遵循 这三条规则，通过这个模型来模拟整个群体的运动。p s 0 算法从这种模型中得到启 示并用于求解优化问题，这就是p s 0 算法形成的基础。 9 华北电力大学硕士学位论文 如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中飞行的一只觅 食的“鸟”就是p s o 算法中在解空间中进行搜索的一个“粒子” ( p a r t i c l e ) ，也 是优化问题的一个解。“食物”就是优化问题的最优解。粒子是一个虚构的概念， 它只有速度和加速度用于本身状态的调整，没有质量和体积“。p s o 算法中，粒子 的位置代表被优化问题在搜索空间中的潜在解，它根据自己的飞行经验和同伴的飞 行经验来调整自己的飞行。所有的粒子都有一个由被优化的函数( 目标函数) 决定 的适应度值( f i t n e s sv a l u e ) ，实际操作中通过该适应度值来评价粒子的“好坏” 程度，每个粒子还有一个速度决定他们飞翔的方向和距离。粒子们追随当前的最优 粒子在解空间中搜索。p s o 初始化为一群随机粒子( 随机解) ，然后通过迭代找到最 优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。一个是粒子本身 目前所找到的最优解，称为个体极值点，记为p i 或p 。；另一个极值是整个种群目 前找到的最优解，称为全局极值点，记为p 。或g 。( p 。，中的最优值) 。 在p s o 中，每个优化问题的潜在解都可以想象成d 维搜索空间上的一个点，假 设在一个d 维的目标搜索空间中，有，个粒子组成一个群体，其中第i 个粒子在该d 维空间里的位置表示为矢量t 一 n ，t2 ，一，x 。) ，将蕾代入目标函数或由目标函数 决定的适应度函数就可以计算出其适应度值，根据适应度值的大小衡量x i 的优劣。 第i 个粒子的“飞行”速度也表示为一个d 维的矢量，记为h = p 。v 。，v 。) 。第 i 个粒子迄今为止搜索到的最优位置即个体极值点或局部极值点，记为 p 1 0 。) a n ，p 。一，p 。) ，整个粒子群迄今为止搜索到的最优位置即全局极值点， 记为p 。( g 。) i ( p p ，p 庐) 。每个粒子用自己的飞行速度决定其飞翔的方向 和距离，并且知道自己到目前为止发现的最好位置p 。和现在的位霞t ，这个可以 看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所 有粒子发现的最好位置g 。，这个可以看作是粒子同伴的经验。然后粒子们就追随 当前的最优粒子在解空间中搜索。粒子就是这样通过自己的经验和同伴中最好的经 验来决定下一步的运动的。 k e n n e d y 和e b e r h a r t 最早提出的p s o 算法采用下列迭代公式对粒子进行操作： v ；v ：+ c l r a n d ：p 刍一k ) + c 2 r a n d ：o 品一k ) 搿1 ；也+ 口1 ( 2 一1 ) ( 2 2 ) 式中，i ；l 2 ，r ，r 是该群体中粒子的总数；d l 2 ，d ，d 是目标搜索 空间的维数；咭为第膏次迭代粒子f 飞行速度矢量的第d 维分量，介于一v 。和v 一之 间，v 是常数，由用户设定；为第七次迭代粒子f 位置矢量的第d 维分量；p u 为 粒子f 个体最好位置p b e s t 的第d 维分量；p 鲥为群体最好位置g m 的第d 维分量；c 1c ： 为学习因子或加速因子；r a n d 。，r a n d ：为随机函数，产生 o ，1 】之间的随机数。 1 0 华北电力大学硕士学位论文 另外，式( 2 - 1 ) 的第一项屹前还可以加上一个不变的惯性权重因子w ，与式 ( 2 - 1 ) 、( 2 - 2 ) 一起称为基本或标准p s o 算法公式。式( 2 - 1 ) 主要通过三部分来 计算粒子f 的新速度：第一部分是粒子i 前一时刻的速度，说明了粒子该时刻的状态； 第二部分是粒子f 当前位置与自己最好位置之间的距离，是自身认知部分 ( c o g n i t i o nm o d a l ) ，表示粒子本身的思考；第三部分是粒子i 当前位置与群体最 好位置之间的距离，为社会部分( s o c i a lm o d a l ) ，是一个从当前点指向种群最好 点的一个矢量，反映了粒子间的协同合作和知识的共享。三个部分共同决定了粒子 的空间搜索能力：第一部分起到了平衡全局和局部搜索的能力；第二部分使粒子有 了足够强的全局搜索能力，避免局部极小；第三部分体现了粒子间的信息共享。在 这三部分的共同作用下粒子才能有效的到达最好位置。粒子i 通过式( 2 - 2 ) 计算新 位置的坐标，通过式( 2 - 1 ) 和( 2 - 2 ) 决定下一步的运动位置。 另外还要补充说明的是，粒子在不断根据速度调整自己的位置时，要受到最大 速度p 。的限制。当心超过v 一时将被限定为v 。 p s o 算法不需要像遗传算法一样采用二进制编码( 或者采用针对实数的遗传操 作) ，直接采用实数编码是该算法的一个优势。例如对于问题r a i n f ( x ) 一z ；+ x ，工：+ 茗； 求解，粒子可以直接编码为o ，工：) ，而适应度函数就是，o ) 。接着就可以利用前面 的过程去寻优。这个寻优过程是一个迭代过程，中止条件一般设为达到最大循环数 ( 迭代次数) 或者最小错误( 偏差) 要求。 p s o 算法没有g a 的复杂操作，需要调节的参数不多，但是参数的设置对算法的 性能却有很大的影响，下面列出了这些参数以及经验设置“。： 惯性权重w 在i o 9 3 2 l 区间范围内一般有较好的性能，但每次从1 4 减少到0 要 比用固定的好。最大速度v 一对惯性权重的取值也有影响，一般认为，最大速度y 。 较小时权重近似为l ，最大速度v 。，较大时权重为0 8 ，p s o 算法的性能较好。 学习因子c ，和c ，用来控制粒子自身豹记忆和同伴的记忆之间的相对影晌。合适 的选择可以提高算法速度、避免局部极小。实验表明c l = c ：t2 或c ，一c ：一0 5 均是 好的选择，但一般c + c ，墨4 较好。 最大速度v 一决定粒子在一个循环中最大的移动距离，通常应不超过粒子的宽度 范围。如果v 。太大，粒子可能飞过最优解的位置；如果太小，可能降低粒子的全 局搜索能力。 粒子数目( 种群大小或群体规模) 一般取2 0 4 0 ，对大部分优化问题，1 0 个粒 子就已经足够了。当然一些特殊问题可取的更多，如对多目标优化等比较难的问题， 或者某些特定的问题，粒子数可以取到1 0 0 2 0 0 个。粒子的维度是由优化问题的 维数( 解空间的维度) 所决定的。 华北电力大学硕士学位论文 2 4 2 基本粒子群优化算法的步骤和流程 2 4 2 1 算法步骤 步骤1 ：初始化粒子群，即在允许的范围内随机设定r 个粒子的初始位置z ? 和初 始速度v , o ( i 一1 , 2 ，r ) ； 步骤2 ：计算每个粒子的适应度值，将每个粒子的p 。坐标设置为其当前位置， 且计算出其相应的个体极值，从个体极值中选出最好的，就是全局极值，并将g 。设 置为最佳粒子的当前位置； 步骤3 ：对每个粒子，比较它的适应度值和它当前的个体极值，如果其值好于 该粒子当前的个体极值，则将p 。设置为该粒子的位置，且更新个体极值。如果所 有粒子的个体极值中最好的优于当前的全局极值，则将g 。，设置为该粒子的位景， 且更新全局极值； 步骤4 ：利用公式( 2 - 1 ) 和( 2 - 2 ) 更新每个粒予的速度和位置； 步骤5 ：检验是否满足终止条件( 预先设定的最大迭代次数或最小偏差要求) ， 若满足，则停止迭代，输出最优解；否则转到步骤2 。 2 4 2 2 算法流程 华北电力大学硕士学位论文 图2 一l 基本p s o 算法流程图 2 4 3 粒子群优化算法的改进措施 在工程实际中，每个优化问题都有各自的特点，互不相同，因此优化算法必须 同领域知识相结合，以保证算法的有效性，但包含过多的问题领域知识也会因此导 致算法对其它问题的脆弱性1 。 p s o 算法也不例外。目前研究人员已经对基本p s o 算法提出了多种改进措施， 正如上面的观点所认为的，这些改进算法需要针对具体问题的特点，根据领域知识 对算法参数进行设置，在提高某种性能的同时也为此付出相应代价。 1 3 华北电力大学硕士学位论文 另外，p s o 算法具有收敛快、效率高的优点，但同时也存在精度低、易陷入局 部收敛等缺点，p s o 在寻优过程中，由于所有的粒子都向最优解的方向飞去，所以 粒子易于趋向同一化( 失去了多样性) ，使得后期收敛速度明显变慢，并且所能达 到的精度也比g a 低“。若加速因子、最大速度等参数设置的太大，粒子群可能错 过最优解，造成算法不收敛。针对上述缺点，很多学者对如何提高p s o 算法的性能 作了大量的研究，下面是几种常见的改进措燕： 2 4 3 1 惯性权重法 s h i 等提出了惯性权重的方法，粒子更新方程为 v 1 = 州h k + c l r a n d ：( p ：一算：) + c 2 r a n d ；x ( p 刍一x ：) 右1 - k + 略1 ( 2 - 3 ) ( 2 4 ) 上式体现了惯性权重w 对粒子飞行速度的影响。研究发现，较大的w 值有利于 全局搜索，较小的w 则有利于局部搜索，算法成功与否的关键取决于粒子全局搜索 能力与局部搜索能力的平衡关系。因此，选择一个合适的w 可以平衡全局和局部搜 索能力，这样可以以最少的迭代次数找到最优解。 由于惯性权重的设置对p s o 算法性能的关键作用，目前己经有很多文献对惯性 权重进行了研究，并且对算法作了不同改进。下面介绍几种常见的基于惯性权重的 改进方法。 ( 1 ) 惯性权重线性递减法 s h i 和e b e r h a r t 提出了一种根据算法迭代次数使惯性权重线性递减的方法。算法 在初期使用较大惯性权重，具有较强全局搜索能力，后期则使用较小惯性权重，提 高局部搜索能力。文献 4 5 中试验了将w 设置为从0 9 到0 4 的线性下降，使得p s o 在开始时探索较大的区域，较快地定位最优解的大致位置，随着w 逐渐减小，粒子 速度减慢，开始精细的局部搜索( 这里w 类似于模拟退火中的温度参数) 。通常， 权重系数h ，由下式来确定： w ：w m 一w _ m a x - - w m i nx i t e r l f e x ( 2 5 ) w 一，k 。分别是w 的最大值和最小值；i t e r ，i t e r 。分别是当前迭代次数和最大迭 代次数。 模拟实验表明这种改进算法能提高收敛速度，但在解决多峰函数问题时，容易 陷入局部最优。 ( 2 ) 模糊惯性权重法 1 4 华北电力大学硕士学位论文 除此之外，s h i 和e b e r h a r t 还提出使用自适应模糊控制系统优化调整惯性权重的 方法。该模糊控制系统有两个输入、一个输出，根据输出结果来动态修改惯性权重 w 。s h i 和e b e r h a r t 提出的模糊控制系统把当前惯性权重以及与函数值对应的目前为 止发现的最优解( 记为， ) ) 作为系统输入。由于不同范围内问题的函数值不同， 必须对， ) 进行规范化处理。一般采用下式进行规范。”：