（电力系统及其自动化专业论文）人工鱼群算法在电网网架规划中的应用研究.pdf

燕山大学r 学硕士学位论文 a b s t r a c t p o w e rn e t w o r k p l a n n i n gi sf i l li m p o r t a n tp a r to f p o w e rs y s t e mp l a n n i n g d u e t od i s c r e t e , n o n l i n e a ra n dd y n a m i cn a t u r e ，i ti sa l s oav e r yc o m p l e xo p t i m i z a t i o n p r o b l e mt h a ti sv e r yc o m p l e xa n dd i f f i c u l tt ob es o l v e d a r t i f i c i a l f i s h 舒a r m a l g o r i t h m ( a f s a ) i sar a n d o ms e a r c hi n t e l l i g e n ta l g o r i t h mt h a ti s b a s e do n s i m u l a t i n gb e h a v i o r so f f i s hs w a m l i ti ss u i t a b l ef o rs o l v i n g 鲥dp l a n n i n gb e c a u s e i th a sf a s te o r l v c r g c n c er a t ea n dg r e a tc a p a b i l i t yo fg l o b a lo p t i m i z a t i o n o nt h e b a s i so f a n a l y s i so f p e r f o r m a n c ea n dt h e o r y , t h i sp a p e rp r o p o s e san e wm e t h o di n n e t w o r kp l a n n i n g a c c o r d i n gt oc h a r a c t e r i s t i c so fn e t w o r kp l a n n i n ga n d ”f i s hs w a r mm o d e l ”， c o n c e p t so f ”d i s t a n c e ”n e i g h b o r h o o d ”a n d “c e n t e r ”i sp r o p o s e da n dp r e ya n d o p t i m i z a t i o ns t r a t e g yo f p r e y , s 、a n na n df o l l o w i sf o r m e d t h i st h e s i sa p p l i e dt h ei m p r o v e da f s ai nt r a n s m i s s i o np l a n n i n g ，w i t ht h e o b j e c 矗v ef u n c t i o nf o rt h em i n i m u mc o s ta n dd cf l o wm o d e lc o n s i d e r i n gn a n d n - 1s e c u r i t yc o n s t r a i n t sa n dg r i dl o s s ；i no r d e rt oi n c r e a s ee f f e c t i v e n e s si n p l a n i n g , a d o p th e u r i s t i cr e t r o g r e s s i o nm o d ea l g o r i t h mo f ns a f e t yc o m b i n e dw i t h a f s a t t t i sa r t i c l ep r e s e n t sa l lo p t i m i z a t i o ns t r a t e g yo nt h eb a s i so f p r e y , s w a r m a n df o l l o w o p e r a t o r st h a to b e y st h er u l eo fg u a r a n t e e b a s i cr a d i a t i o n ”t h a ti s a p p l i e di n d i s t r i b u t i o nn e t w o r kp l a n n i n g a l lp o s s i b l er o u t e sa l et a k e na s o p t i m i z a t i o nv a r i a b l e su s i n gt h eb i n a r yc o d i n g i n i t i a l i z a t i o nm e t h o d so fa r d t i c i a l f i s hp o p u l a t i o na l e r o o t - n o d ef u s i o n a n dr a n d o mi n i t i a l i z i n g f o r w a r da n d b a c k w a r ds u b s t i t u t i o nm e t h o di su s e dt oc o u n tl i n el o s so fp l a n n i n gn e t w o r k t o i m p r o v et h ee f f i c i e n c yo fd i s t r i b u t i o np l a n n i n g ，c o m b i n et h ei l l e g a ln e t w o r k r e s t o r a t i o ns t r a t e g yi n t ot h ep r o c e s s i n g a c c o r d i n gt o t h em e t h o da b o v e ，p r o e mf o r2u a n s r n i s s i o np l a n n i n g e x a m p l e sa n d 1d i s t r i b u t i o np l a n n i n ge a s l ji nm a t l a be n v i r o n m e n tt h er e s u l t s s h o wt h a tt h ep r o p o s e dm e t h o dc a r lq u i c k l yo b t a i nt h eo p t i m a ls o l u t i o no ft h e i a b s t r a c t n e t w o r kp l a n n i n ga n dh a sas t r o n ga b i l i t yi nr e s e a r c ho fg l o b a ls o l u t i o n s t h e p r o p o s e dm e t h o d si nt h i sp a p e ra r ef e a s i b l ea n de f f e c t i v ei np o w e rn e t w o r k p l a n n i n g k e yw o r d sp o w e rs y s t e mp l a n n i n g ；n e t w o r kp l a n n i n g ；a r t i f i c i a lf i s h b - v c a i i l a l g o r i t h m ；t r a n s m i s s i o nn e t w o r k s ；d i s t r i b u t i o nn e t w o r k s ；r a d i a t i o n r e s t d c t i o n i l l 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文人工鱼群算法电网网架 规划中的应用研究，是本人在导师指导下，在燕山大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不 包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本 人承担。 储签名：引堤 1 日期：二。0 7 年3 月力日 燕山大学硕士学位论文使用授权书 人工鱼群算法电网网架规划中的应用研究系本人在燕山大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕 山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。 本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并 向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人 授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布 论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密西 ( 请在以上相应方框内打“4 ”) 作者签名：壶l j 名递 导师躲羡 日期：z 口 7 年? 月z 日 日期：三釉7 年j 月己日 第1 章绪论 第1 章绪论 i 1网架规划研究的目的和意义 电力工业是国民经济的基础产业之一，电力是现代社会发展的重要动 力。随着国民经济的高速发展，社会对电力的需求量越来越大。为了满足 日益增长的电力需求，必须不断扩大电力系统规模。由于电力系统的发展 水平不仅会对国民经济各部门产生巨大影响，而且还涉及到大量的一次能 源消耗和巨额投资，所以合理地进行规划不仅可以获得巨大的社会效益， 也可以获得巨大的经济效益u 1 。电力系统规划的失误将会给国家建设带来 不可弥补的损失。电力系统规划一般包括电源规划和电网规划两部分，电 网规划又进一步分为输电网规划和配电网规划两类。电网规划在整个电力 系统规划中起着非常重要的作用，直接关系到电源发出的电能能否及时送 出及电力系统供电的安全性和经济性能否实现。 随着我国工业和第三产业的迅速发展，电网负荷迅速增长，为了解决 电力供应不足的问题，近年来各地纷纷加大发电厂的建设。但由于我国电 网建设速度明显滞后于发电和用电的增长速度，所以电网成为电能从电厂 到用户的“瓶颈”。随着我国经济的持续发展和人民生活水平的不断提高， 对高质量电力的需求也必将快速增长，因此为了满足不断增长的电力需求， 必须改变目前电力供应中发电、输电、配电比例失调的局面，加快电网的 规划、建设与改造 2 1 。 电网规划是一个相当复杂的问题，它需要大量在时间和空间上相互影 响的决策。目前，还无法将这些决策统一在一个模型中考虑。只能将其分 解成一系列相对简单的子问题，再通过子问题之间的迭代进行协调。按照 研究问题划分，广义的电网规划包括负荷预测、网架规划、无功规划、稳 定性分析和短路电流分析等。其中网架规划是电网规划中最核心的部分【3 】。 电网网架规划可以简称为电网规划。电网网架优化规划是一个非常复杂的 燕山大学_ 1 = 学硕十学能论文 组合优化问题，求解这类问题相当困难。特别是当网络规模很大时往往会 出现“维数灾难”问题。 网架规划的目的在于根据负荷预测的情况和投资及运行等费用最小的 原则，确定新建或扩建线路的类型、时间和地点，保证可靠的将电能由发 电中心送到用户，并且出入线及沿途环境都能够接受。 对电网的网架结构进行科学合理的规划具有十分重要的意义： ( 1 ) 科学的电网规划是电力企业战略发展的重要组成部份。供电企业是 靠电网扩展来发展壮大的，随着电力需求的高速增长，供电企业就必须不 断地满足这种需求，就势必形成业务扩展，带来电网的延伸与发展。这就 有一个电网建设何时介入、何时投入的问题。投入早了，就形成设备闲置， 发挥不了应有的作用，造成资金浪费；投入晚了，不能满足社会、经济对 电力的需求，又势必影响国民经济发展和人民生活。因此，科学合理的网 架规划是电力企业发展的战略需要。 ( 2 ) 科学的电网规划是提高电力系统投资效益的最有效途径。电力系统 的规划和建设是一个系统工程，涉及到一定时期内的多次投资，电网何时 建设、设施何时同步建设都有一个科学投入的问题，如何使整个的系统投 资最小，达到投资效果的最优化，在规划中充分运用技术经济学的原理， 采取动态分析，科学地进行电网建设规划，有利于系统的运行管理，减少 系统跨区域交叉供电，提高系统管理和运行效率。电力系统是一个有机的 整体，任何大型电厂或高压输电线路的投运，都将在不同程度上影响电力 系统运行和今后的发展。因此，做好输电网络的规划，无论是从经济上还 是从技术上都有非常重要的意义。 ( 3 ) 科学的配电网网架规划，可以降低系统的网络损耗，提高系统的供 电可靠性，极大地提高电网的运行效益1 4 j 。配电网直接面对的是千家万户、 各行各业，供电企业在保证供电质量的同时，还应兼顾电网的运行效率和 经济效益。低压电源如何分布，低压技术导则如何确定，供电可靠性能够 达到多少，客户的满意度有多高，都涉及到能否科学地制定配电网发展规 划。只有科学的配电网规划，才能够使配电设施布置合理，供电半径经济 实用，自动化程度高，供电可靠性高，实现客户服务优质、供电质量优良 2 第l 章绪论 的目标。 1 2 网架规划方法的研究情况 1 2 1网架规划问题的特点 网架规划问题具有以下的特点： ( 1 ) 离散性线路都是按照整数回路架设的，所以规划的决策变量的取 值必须是离散的或整数的。 ( 2 ) 动态性网架规划不仅要满足规划年限内的经济、技术等指标要 求，而且要考虑到网络今后的发展及今后网络性能指标的实现问题。 ( 3 ) 非线性线路电气参数与线路功率及网损等费用的关系是非线性 的。 ( 4 ) 多目标性规划的方案不仅要满足经济、技术上的要求，还必须考 虑社会、政治及环境因素，这些因素常常是相互冲突和矛盾的。 ( 5 ) 不确定性负荷预计、设备有效度以及水力条件等均存在显著的不 确定性。 因此，从数学上讲，网架规划是一个动态多目标不确定性非线性整数 规划问题f 5 j o 1 2 2 网架规划的主要方法 三十多年来，许多学者为研究电网规划的数学方法做了大量的工作， 设计上的少量改善往往就可以获得运行使用中巨大的经济效益。早期的电 网规划方法以方案比较为基础。这种方法从几个设定的待选方案中通过技 术经济比较选择出推荐的方案。然而，参加比较的方案往往是规划人员凭 经验提出，并不一定包括客观上的最优方案，更不可能包含全部可行方案， 因此最终推荐方案包含相当的主观因素和局限性。数学和计算机技术的发 展，使得电网规划新方法应运而生。目前电网优化规划方法主要分为传统 规划方法和现代启发式规划方法。 ( 1 ) 传统规划方法传统规划方法包括启发式方法( h e u r i s t i cm e t h o d s ) 和数学优化方法( m a t h e m a t i co p t i m i z a t i o nm e t h o d s ) 1 6 。启发式方法是一种 燕山大学工学硕十学位论文 以直观分析为依据的算法，通常是基于系统某一性能指标对可行路径上的 一些参数作灵敏度分析，根据一定的原则选择要架设的线路，主要用于输 电网规划p j 。启发式方法因为具有直观、灵活、计算时间短以及易于同规 划人员经验相结合等优点而在实际工程中得到较多应用。但它不是严格的 优化方法，不能很好地考虑各阶段各架线决策间的相互影响。因此，启发 式方法不能保证得出的规划方案最优。特别是当规划期较长、待选线数量 较多时，所得结果可能与真正的最优方案有很大偏差。 数学优化方法是对电网规划作数学描述，处理成有约束的极值问题， 然后用最优化理论进行求解。和启发式算法相比，数学优化方法在理论上 更为优越，因此得以广泛研究和发展。线性规划方法是数学优化技术中发 展最成熟的领域，同时也是应用最广泛的优化方法f 7 1 。线性规划模型具有 计算简单、求解速度快等优点，主要不足是用连续变量模拟离散的决策变 量，不能准确地描述输电网络规划的整数性。o 1 整数规划对解决小规模 的问题效果较好，但是当规划变量个数增加时会遇到“维数灾难”问题， 因此这种方法还有待改进1 8 j 。混合整数规划模型应用于输电网络规划，此 模型较为全面地反映了输电网络规划中的各个目标函数，但因为约束条件 和变量太多而难以实用【9 】。分支定界法对较大型的整数规划进行求解时， 往往还需要启发式方法配合，即不追求收敛到展优解，而是经验的放一些 可能的组合，提高速度 1 们。网络流法求解电网规划问题，不易增加约束条 件，在求解出初始解之后，还要检验其是否满足其它约束条件，所以不利 于求全局最优解【1 1 1 。 尽管数学优化发展较快，但各种数学优化方法在解决输电网络规划的 实际问题时还存在困难。对于一个实际系统来讲，利用数学优化方法求解 最佳策略的最大障碍是输电网络规划模型本身的非线性与非凸性。这大多 数取决于最优化程序本身内在的缺陷，如直流潮流模型或者更复杂模型的 收敛问题；当有大量离散变量存在时的最佳投资决策问题，以及在大量不 确定因素下的随机规划问题都存在大的不可想象的计算时间问题【1 2 】。 ( 2 ) 现代启发式算法随着现代计算机技术的发展，许多以前因为计算 时间太长而不能得到解决的问题有了新的方法。“现代启发式算法”就是 4 第1 章绪论 在这基础上发展起来的，它是通过模拟自然界中一些“优化”现象研究出 的一类比较新的优化求解算法，适用于求解组合优化问题以及目标函数的 某些约束条件不可微的非线性优化问题，这类算法也被归入人工智能的技 术范畴。它结合了启发式算法和数学优化方法的优点，比较接近于人类的 思维方式，易于理解，用这类算法求解组合优化问题在得到最优解的同时 也可以得到一些次优解，便于规划人员研究比较f 1 2 4 】。所以，现代启发式 算法成为了现阶段电网网架规划的主流方法。此类算法主要有模拟退火算 法( s i m u l a t e da n n e a l i n g ，s a ) ，遗传算法( g e n e t i ca l g o r i t h m ，g a ) ，禁忌搜 索法( t a b us e r e h 。t s ) ，蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) ，粒子群算 法( 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 ) 等d s , i 。 遗传算法是目前电网规划中广为使用的一种现代启发式寻优方法l l ”。 它通过编码将规划方案转变为一组组染色体，并列出一组待选方案作为初 始可行解，以适应函数的优劣来控制搜索方向，通过遗传、交叉、变异等 逐步完成进化，最终逐步收敛到最优解【l 引。同传统算法相比遗传算法具有 多路径搜索、隐并行性、随机操作等特点，对数据的要求低，不受搜索空 间的限制性约束，不要求连续性、导数存在、单峰等假设，可以考虑多种 目标函数和约束条件。遗传算法也存在计算速度慢，有时会收敛到局部最 优解等不足，目前对此也进行了些改进和研裂9 - 2 “。 模拟退火算法是以马尔科夫链的遍历理论为基础的一种适用于大型组 合优化问题的随机搜索技术，算法的核心在于模拟热力学中固体物质冷却 和退火过程，采用m e t r o p o l i s 接受准则避免落入局部最优解，渐进地收敛 于全局最优。已有学者尝试将这种方法应用于电网规划中【2 2 2 3 】。但模拟退 火为使每一冷却步的状态分布平滑要花费时间，而且这种算法属于单点寻 优，不能获得多个优化解。若能将模拟退火算法和其他优化方法结合在一 起使用，更能发挥其优势1 2 4 j 。 禁忌搜索是一种高效的现代启发式搜索技术，其基本思想是通过记录 搜索历史，从中获得知识并利用其指导后续的搜索方向，以避开局部最优 解。禁忌搜索法的搜索效率高，收敛速度很快，目前已受到规划工作者的 燕山大学工学硕士学位论文 重视【2 4 q 6 1 。但是禁忌搜索法是一种扩展邻域的单点寻优方法，收敛受到仞 始解的影响，而且禁忌表的深度及期望水平影响搜索的效率和最终的结果， 从数学上无法证明其一定能达到最优解，尚需进一步研究1 2 ”。 蚁群算法是由意大利学者m d o f i g o 研究总结出的一种新型的仿生启 发式优化寻优算法，它是一种基于种群的进化算法，该算法仿照蚂蚁群觅 食机理，它的特点是正反馈、分布式计算以及贪婪启发式搜索的应用。目 前有学者尝试将其应用于电网规划中【2 8 猡1 。但是该算法的寻优时间较长， 并且还没有很好地将规划模型处理成适合于蚁群算法求解的模型。如何合 理地将规划模型转变成适合蚁群算法的模型，有待人们进一步的研究。 粒子群算法是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种仿生类智能 算法【3 0 1 。该方法已经应用的输电网和配电网规划中【3 1 4 3 1 。p s o 通过记忆与 反馈机制实现了高效的寻优搜索，它的搜索实现了粒子信息的共享，粒子 的搜索是在整个空间根据粒子整体搜索到的信息来确定下一步行动的，所 以其搜索速度快，但缺点是容易陷入局部最优1 3 4 1 。 1 3 课题的提出 现代启发式算法成为了现阶段网架规划的主流方法和电网规划领域的 研究热点。评价网架规划方法的标准首先应该是能否找到最优的解方案( 或 者较优的方案) ，其次是能否快速的找到最优解1 1 6 1 。各种现代启发式算法 应用到电网规划领域中时也存在各自的优点和不足，并且在参照上述两方 面的标准并不能保证得到完全满意的效果。它们不能互相取代，而是应该 相互借鉴，互为补充【1 5 】。由于现代启发式算法之间存在着结构、研究内容 与研究方法的相似性，所以借鉴原有的方法，研究新的现代启发式算法的 应用可以为这一类方法的改进和电网网架规划研究提供新的思路和更广阔 的前景。 人工鱼群算法( a a i f i c i a if i s hs w a r ma l g o r i t h m ，a f s a ) 是一种新颖 的现代启发式算法口5 l 。它是基于模拟鱼群行为的随机搜索优化智能算法， 主要利用了鱼的觅食、聚群和追尾行为，从构造单个人工鱼个体的底层行 为做起，通过鱼群中个体的局部寻优达到全局最优值在群体中突现出来的 6 第1 章绪论 目的。文献【3 6 】和文献 3 7 1 的计算实例表明该算法具有良好的克服局部极 值，取得全局极值的能力。文献 3 8 1 将人工鱼群算法用于电力系统无功优 化，并与遗传算法、改进禁忌搜索算法进行了比较，结果表明a f s a 鲁棒 性强，全局收敛性好。文献 3 9 1 建立了一种新的人工鱼群神经网络训练模 型，利用人工鱼群算法训练神经网络的权值，再将该神经网络用于短期负 荷预测，结果表明该方法具有较强的自适应能力和较好的预测效果。 从总体上看，人工鱼群算法的特点应用于网架规划问题具有以下一些 优势： ( 1 ) 网架规划是离散、连续变量混合优化的问题，人工鱼群算法通过恰 当的编码或离散化方式可直接将离散问题结合到算法中； ( 2 ) 对大规模规划的维数灾问题，可以适当改进算法，通过并行化方法 来处理，算法的内在并行性为并行化处理的实现提供了便利； ( 3 ) 人工鱼群算法可以求解出系列的优化方案，可根据实际工程需要 提供不同的规划建议，增加了规划的灵活性； ( 4 ) 人工鱼群算法具有良好取得全局极值的能力，并且具有寻优效率 高，收敛速度快的优点，非常适合网架规划这样的大规模优化组合问题。 1 4 本文的主要工作 本文主要作了以下几方面的工作： ( 1 ) 在查阅相关文献和资料的基础上，阐述了电网规划和网架规划的重 要意义，介绍了网架规划方法研究的现状和发展前景。 ( 2 ) 提出了将一种新的现代启发式算法人工鱼群算法，应用到网架 规划领域，介绍了基本人工鱼群算法和鱼群模式的原理。 ( 3 ) 针对输电网网架规划的特点，定义了人工鱼群算法的参数及其物理 意义，制定了觅食、聚群和追尾三种行为为基础的寻优策略。为了加速收 敛进程，将安全意义的基于线路指标启发式倒推策略和人工鱼群算法结 合。给出了基于人工鱼群算法的输电网规划的设计流程，并且采用了2 个输 电网规划算例进行仿真验证算法的性能。 7 燕山大学- 【学硕士学位论文 ( 4 ) 通过对g a r v e r - 6 系统( 输电网规划) 算例的多次试验，对人工鱼群 算法的的主要参数对收敛寻优过程的影响作了详细的测试。 ( 5 ) 以基本的人工鱼群寻优框架为基础，根据配电网的辐射性约束特 点，设计了适用于中压配电网网架规划的保证“基本辐射性”的人工鱼群 算法。利用该方法对一个1 0 节点的中压配电网规划算例进行m a t l a b 环 境下的编程求解。 r 6 ) 针对配电网规划过程中出现违反辐射性约束的方案的问题，给出了 检测和修复这些不可行方案的策略。 s 第2 章人工鱼群算法基础 第2 章人工鱼群算法基础 2 1 人工鱼群算法的提出 人工鱼群算法是中国浙江大学的李晓磊博士于2 0 0 3 年提出的，它是基 于动物的集群行为进行寻求全局最优的算法，是行为主义人工智能的个 典型应用【4 0 l 。它从构造动物简单的底层行为作起，从多个动物个体的局部 寻优行为开始，最终在群体中使全局最优解值突现出来。该算法具有良好 的克服局部极值、取得全局极值的能力，并且算法的实现无需目标函数的 梯度等特性，并且其对搜索空间具有一定的自适应能力，本质上也属于群 智能算法的范畴j 。 集群是生物界常见的一种现象，如昆虫、鸟类、鱼类甚至是人类。随 着人们对生命本质的不断地了解，生命科学正以前所未有的速度迅猛发展， 使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆的探索起新的非经 典计算途径【4 2 】。在这种背景下，社会性动物( 如蚁群、鸟群、鱼群等) 的 自组织行为引起了人们的广泛关注，许多学者对这种行为进行了数学建模 并用计算机进行仿真，这就产生了所谓的“群智能”( s w a r mi n t e l l i g e n c e ) 。 社会性动物的妙处在于个体的行为都很简单，但是它们一起协同工作时， 却能“突现”出非常复杂( 智能) 的行为特征。2 0 世纪年代中期创立了仿 生学，人们从生物进化的机理中受到了启发，提出了许多用以解决复杂优 化问题的新方法，如遗传算法、进化规划、粒子群算法、蚁群算法等f 4 2 】。 群智能算法作为一种新兴的演化计算基数已成为越来越多的研究者的关注 焦点。群智能中的群体指的是“一组相互之间可以进行直接通信或者阗接 通信的主体，这组主体能够合作进行分布式问题的求解”，而群智能则是指 “无智能的主体通过合作表现出智能行为的特性”。群智能是在没有集中控 制且不提供全局模型的前提下，为了寻找复杂的分布式问题的求解方案提 供了基础。 与大多数基于梯度应用的优化算法不同，人工鱼群智能依靠的是概率 9 燕山大学1 = 学硕士学位论文 搜索算法。虽然概率搜索算法通常需要采用较多评价函数，但与梯度方法 和传统演化算法相比，其优点还是显著的：无集中控制约束，不会因为个 别个体的故障影响整个问题的求解，确保了系统具有更强的鲁棒性。以非 直接的信息交流方式确保了系统的扩展性，由于系统中个体的增加而增加 的通信开销也较少。并行分布式算法模型可充分利用多处理器，这样的分 布模式更适合于网络环境的工作状态。对问题定义的连续性无特殊要求； 系统中每个个体的能力十分简单，每个个体的执行时间也比较短，并且算 法实现简单( 4 ”。 人工鱼群智能方法易于实现，算法中仅涉及各种基本数学操作，其数 据处理过程对c p u 和内存的要求不高。人工鱼群算法具有以下的优点： ( 1 ) 算法只需要比较目标函数值，对目标函数的性质要求不高； ( 2 ) 算法对初值的要求不高，初值随机产生或设定为固定值均可； ( 3 1 算法对参数设定的要求不高，有较大的容许范围； ( 4 ) 算法具备并行处理能力，寻优速度快； ( 5 ) 算法具备很强的全局寻优能力。 2 2 鱼群模式设计与人工鱼群算法思想 鱼群模式和鱼群算法从具体的实施和到算法的整体设计理念，都不同 于传统的设计理念和解决方法，但同时也具有与传统方法相融合的基础。 随着在更多领域的应用与研究，鱼群模式和鱼群算法会有良好的应用前景。 传统的优化方法根据问题的性质不同，通常将问题划分为线形规划问 题、非线性规划问题、整数规划问题和多目标规划问题，有相应得一些较 成熟的常规算法。如应用于线性规划的单纯形法，应用于非线性规划的牛 顿法、共轭梯度法、序列二次规划法等，应用于整数规划问题的分支定界 法、割平面法和动态规划法等，这些方法都是基于严格的数学模型的，当 模型复杂的时候，如变量的维数多、约束方程多、非线性强，或者模型不 能用显式的方程来表达时，这些方法往往不能进行有效求解，或者求解的 时间过长，如组合优化问题的组合爆炸；或者求解的效果差，如陷入局部 极值、初始值直接影响寻优的结果等【4 0 】。 o 第2 章人工鱼群算法基础 人们从生物进化的机理和一些物理现象中受到启发，提出了用以解决 复杂优化问题的新方法，因其高效的优化性能、无需问题特殊信息等优点， 受到各领域广泛的关注和应用，研究较多的有模拟退火、遗传算法、禁忌 搜索、进化规划、进化策略等。文献 4 0 】将动物自治体的概念引入优化算 法中，采用了自下而上的思路，应用了基于行为的人工智能方法，形成了 一种新的解决问题的模式，因为从分析鱼类活动出发的，所以称为鱼群模 式。该模式应用于寻优中，形成了人工鱼群算法。下面就介绍鱼群模式中 的一些主要观点。 2 ，2 1 视觉 最原始、最直观的寻优方法应该是最优方向法，或者叫爬山法，它在 实施过程中仅仅需要比较一下目前状态和目的状态的优劣，然后选择较优 的状态，这样步步向最优状态迈进。当然，单纯的爬山法存在一些缺陷， 如步长的选择过大将造成算法的振荡而无法收敛，步长较小会造成算法收 敛速度过慢，且容易陷入局部极值中。但它对目标问题的性质要求很低， 甚至可以不是显式的数学表达式，并且实施简单，比较符合生物的行为方 式。鱼群模式，借鉴了爬山法的思想，引申出“视觉”的概念。 生物的视觉是极其复杂的，它能够快速感知大量的空间食物，这对于 任何仪器和程序都是难与之相比的，为了实施的简单和有效，在鱼群模式 中应用了如下的方法来实现虚拟人工鱼的视觉。一个虚拟人工鱼个体的当 前状态为x ，v i s u a l 为其视野范围，状态筑为其在某时刻视点所在的位置， 如果该位置的状态优于当前状态，则考虑向墨的方向前进一步，达到状态 x 。；如果状态置不比当前的状态更优，则继续巡视视野内的其他位置。 巡视的次数较多，则对视野内的状态了解更全面，从而对周围的环境有一 个全方面的认知，这有助于做出相应的决策和判断，当然，对于状态多或 无限状态的环境也不必全部遍历，允许一定的不确定性对于摆脱局部最优， 从而寻找全局最优是有帮助的。 其中，人工鱼个体的当前状态为x = x l ，x 2 ，x 。 ，其视野中的某个状 态为置= 群，) ，则上述的过程可以表示如下 燕山大学1 = 学硕七学位论文 = 薯+ v i s u a l - r a n d 2 尚脚埘耐 ( 2 1 ) ( 2 2 ) 其中，r a n d 函数产生o n l 之间的随机数，s t e p 为移动的步长。引入了 r a n d 后，实际执行了是一种可变步长的策略。 2 2 2 鱼群行为分析 鱼类与我们的关系密切，也为我们所熟知，通常我们可以观察到如下 可以应用到寻优算法种的鱼类行为： ( 1 ) 觅食行为这是生物的一种最基本的行为，也就是趋向食物的一种 活动；一般可以认为它是通过视觉或味觉来感知水中的食物量或浓度来选 择趋向的，因此，以上所述的视觉概念可以应用于该行为。 ( 2 ) 聚群行为这是鱼类比较常见的一种现象，大量或少量的鱼都能聚 集成群，这是它们在进化过程中形成的一种生存方式，可以进行集体觅食 和躲避敌害。 。 ( 3 ) 追尾行为当某一条鱼或几条鱼发现食物时，它们附近的鱼会尾随 其后快速游过来，进而导致更远处的鱼也尾随而来。 h ) 随机行为鱼在水中悠闲的自由游动，基本上是随机的，其实它们 也是为了更大范围的寻觅食物或伙伴。 以上是鱼的凡个典型行为。这些行为在不同时刻相互转换，两这种转 换通常是鱼通过对环境的感知来自主实现的，这些行为与鱼的觅食和生存 有着密切的关系，并且与优化问题的解决有着密切的关系。行为评价是用 来模拟鱼能够自主行为的一种方式。可以选用两种简单的评价方式：一种 是选择最优行为执行，也就是在当前状态下，哪一种行为向优的方向前进 最大，就选择这一行为；另一种是选择较优行为前进，也就是任选一种行 为，只要能向优的方向前进即可。 人工鱼是真实鱼个体的一个虚拟实体，用来进行问题的分析和说明， 借助于面向对象的分析方法，可以认为人工鱼就是一个封装了自身数据信 息和一系列行为的一个实体，可以通过感官来接收环境的刺激信息，并做 第2 章人工鱼群算法基础 出相应的应激活动。人工鱼所在的环境主要是问题的解空问和其他人工鱼 的状态，它在下一个时刻的行为取决于目前自身的状态和目前环境的状态 ( 包括当前解的优劣和其它同伴的状态) ，并且通过它自身活动的同时来影 响环境，进而影响其它伙伴的活动。动物一般不具有人类所具有的复杂逻 辑推理能力和综合判断能力的高级智能，它们的目的是通过个体的简单行 为或群体的简单行为而达到或突现出来的。 动物行为具有以下几个特点：动物通过感觉器官来感知外界环境，并 应激性的做出各种反应，从而影响环境，表现出与环境交互的能力；动物 有其特有的某些行为，在不同的时刻和不同的环境中能够自主的选取某些 行为，而无须外界的控制或指导；不像传统的基于知识的智能系统，有着 明确的目标，单个个体的行为是独立的，与总目标之间往往没有直接的关 系；总目标的完成是在个体行为的运动过程中突现出来的；各个体的行为 是实时的、并行进行的。 在一片水域中，鱼生存的数目最多的地方一般就是本水域中富含营养 物质最多的地方，依据这一特点来模拟鱼群的觅食等行为，从而实现全局 寻优，这就是鱼群算法的基本思想。人工鱼群算法主要有三种行为算子： ( 1 ) 觅食行为主要就是循着食物多的方向游动的一种行为，在寻优算法 中则是向较优方向前进的迭代方式。 ( 2 ) 在聚群行中，可以对每个人工鱼规定了这样2 个基本原则：1 ) 尽量 向临近伙伴的中心移动；2 ) 避免过分拥挤，这样就能基本实现人工鱼的聚 群能力。 ( 3 ) 追尾行为就是一种向邻近的最活跃者追逐的行为，在寻优算法中可 以理解为向附近的最优伙伴前进的过程。 2 3基本人工鱼群算法的数学描述 2 3 1 基本定义 人工鱼( a r t i f i c i a lf i s h ，a f ) 个体的在水域中的位置可以表示为向量 z 2 瓴，而，砘i m ) ，其中x j ( i = 1 2 一, d i m ) 代表要寻优的变量；d i m ，人工 鱼个体的变量维数：人工鱼当前所在的位置的食物浓度( 目标函数值) 表 燕山大学工学硕士学位论文 示为y = ，( z ) ；人工鱼个体之间的距离表示为哦，= l i 鼍省川；a f s i z e ， 表示人工鱼群的种群数量；s t e p 表示人工鱼移动的最大步长；t r y n u m b e r ， 表示人工鱼每次移动时的最大试探次数；v i s u a l ，人工鱼的感知距离，也 可以称为视野，代表了人工鱼个体每次移动的最大距离；6 ，拥挤度因子， 用于控制达到某个极值点的人工鱼个体的数量。 2 3 2 人工鱼的行为描述 ( 1 ) 觅食行为设人工鱼当前的状态为置，在其感知范围( v i s u a l ) 内 随机选择一个状态x ，。z 、e 分别为z 、j ，的食物浓度函数，如果在求 极小值( 求极大值问题同理) 中r r ，则向该方向前进一步；反之，再 重新选择状态x ，判断是否满足条件；反复几次后( 次数由t r yn u m b e r 决 定) ，如果仍不满足条件，则随机移动一步。 ( 2 ) 聚群行为设人工鱼当前的状态为置，探索当前邻域内( 即 喀， v i s u a l ) 的伙伴数目一，及此邻域的中心位置群，e 为耳的食物浓 度函数。如果( 耳n ，) 疆，表示中心位置的食物浓度较低且不太拥挤， 则朝中心位置髟，移动一步；否则执行觅食行为。 ( 3 ) 追尾行为设人工鱼当前的状态为z ，探索当前邻域内( 即 4 ， v i s u a l ) r 为最小的伙伴墨。i n ，。为j ，m 。的食物浓度函数。如果 瓦i 。的邻域内的伙伴数目船，满足( k ，2 ，) 喁，表明矗m 的状态具有较 低的食物浓度并且周围不太拥挤，则朝墨。的方向移动一步；否则执行觅 食行为。 ( 4 ) 随机行为随机行为的实现较为简单，就是人工鱼在视野内随机选 择一个状态，然后向该方向前进。其实，它是觅食行为的缺省行为。 2 3 3人工鱼群算法的全局收敛性 对于一种算法，其收敛性往往是人们所首要关心的问题。在人工鱼群 算法中，人工鱼的觅食行为奠定了算法收敛的基础，聚群行为增强了算法 收敛的稳定性和全局性，追尾行为则增强了算法收敛的快速性和全局性， 其行为评价也对算法收敛的速度和稳定性提供了保障( 4 0 1 。总的来说，算法 中对各参数的耿值范围还是很宽容的，并且对算法的初值也基本无要求。 1 4 第2 章人工鱼群算法基础 算法中，使人工鱼逃逸局部极值实现全局寻优的因素主要有以下几点： ( 1 ) 觅食行为中试探的次数较少时，为人工鱼提供了随机游动的机会， 从而跳出局部极值的邻域；随机步长的采用，使得在前往局部极值的途中， 有可能转而游向全局极值，当然，其相反的一面也会发生，就是在去往全 局极值的途中，可能转而游向局部极值，这对个个体当然不好判断它的 祸福，但对于一个群体来说，好的一面往往具有更大的概率； ( 2 ) 拥挤度因子的引入限制了聚群的规模，只有较优的地方才能聚集更 多的人工鱼，使得人工鱼能够更广泛的寻优；聚群行为能够促使少数陷入 局部极值的人工鱼向多数趋向全局极值的人工鱼方向聚集，从而逃离局部 极值； ( 3 ) 追尾行为加快了人工鱼向更优状态的游动，同时也能促使陷于局部 极值的人工鱼向趋向全局极值的更优个体的方向移动从而逃离局部极值区 域。 2 4 本章小结 本章介绍了人工鱼群算法产生的背景和理论特点。分析了鱼群模式和 人工鱼群算法的寻优思想，为把人工鱼群算法应用到网架规划领域提供了 理论基础。由于人工鱼群算法的研究才刚刚起步，还未形成像遗传算法那 样系统的分析方法和坚实的数学基础，许多问题还需要进一步的研究，但 是目前的研究已初步显示了其优势，随着研究的进一步的深入，该算法必 将获得越来越广泛的应用。 燕山大学t 学硕十学位论文 第3 章人工鱼群算法在输电网规划中的应用 3 1 引言 输电网规划通常是在未来的一个时问段内负荷增长情况、电源点的发 展及布局还有输电线路的详细资料都已知的基础上，提出了若干可行的输 电网络规划方案，应用分析工具，通过计算确定何时、何地建设什么电压 等级的以及多少回输电线路，才能满足负荷需求和保证电力系统安全运行， 同时所需的资金和运行费用都为最小。输电网络规划也称为主网规划，一 般将电压等级在2 2 0k v 以上的电网规划称为输电网规划【5 】。 对一切输电系统，必须满足下列条件：必须可靠且经济的把用户所需 要的电能，从各发电中心送到负荷中心；各负荷中心的电压均需保持在规 定的范围内。一个可靠的输电网络，至少还应能经得起各种各样的单一故 障和扰动。即对于各种单一故障，各负荷中心都能在合格的电压水平下， 得到必要数量的电能，并且系统内的任何元件都不会发生过负荷【6 1 。在某 些情况下，负荷要求供电高度可靠时，就必须经得起更为严格的考验，例 如，系统必须经得起双重故障和多重故障的冲击。 从数学上讲，输电网规划是一个带有大量约束条件的非线性整数规划 问题，所以其求解过程十分复杂。特别是当网络规模增大时往往会出现“维 数灾难”问题，到目前为止，这类方法还没有完全解决。常规的优化规划 算法概括起来可分为启发式和数学优化方法两大类。现阶段，各种基于人 工智能技术的新型优化算法已成为网架优化问题的主流寻优算法l i s , 1 6 1 。 人工鱼群算法是一种基于模拟鱼群行为的随机搜索优化智能算法，主 要利用了鱼的觅食、聚群和追尾行为，从构造单个人工鱼个体的底层行为 做起，通过鱼群中个体的局部寻优达到全局最优值在群体中突现出来的目 的。本章将人工鱼群算法应用于网架规划，根据输电网网架规划问题的特 点对基本的人工鱼群算法进行改造，定义了算法的参数，制定了算法的寻 优规则。 1 6 第3 章人工鱼群算法在输电网规划中的麻用 3 2 用于输电网网架规划的人工鱼群算法 基本的人工鱼群算法是用于优化连续域问题的【3 5 州。网架规划问题由 于架线走廊的架线数是离散值，所以也可以称为组合优化问题。文献1 3 7 利用人工鱼群算法对经典的旅行商问题进行了仿真，结果表明该算法解决 优化组合问题具有快速收敛的特点。 现代启发式方法往往只提供一种寻优框架，具体的寻优策略还需要根 据实际问题进行分析和设计【1 6 1 。本文对基本的鱼群模式思想进行改造，设 计了适合网架规划问题的人工鱼群算法。 3 2 1参数定义 人工鱼个体的在水域中的位置可以表示为向量x = 瓴，而，确i 。) ，其中 而( i = 1 2 ，d i m ) 代表要寻优的变量，而的物理意义是从零到线路走廊架 设线路回数上限之间的整数；d i m ，人工鱼个体( 决策变量) 的维数，这里 表示系统中可增建线路的走廊数；人工鱼当前所在的位置的食物浓度( 目 标函数值) 表示为y = 厂( ) ；人