基于鱼群遗传混合算法求解最佳抢修路径的研究.pdf

基于鱼群遗传混合算法求解最佳抢修路径的研究 李浩，胡资斌 ( 华北电力大学电气与电子工程学院，河北保定0 7 1 0 0 3 ) S t u d yo nO p t i m a lM a i n t e n a n c eP a t hB a s e do nF i s h - s w a r ma n d G e n e t i cA l g o r i t h m L Ih a o ，H UZ i - b i n ( S c h o o lo fE l e c t r i c a la n dE l e c t r o n i cE n g i n e e r i n g , N o a hC h i n aE l e c t r i cP o w e rU n i v e r s i t y ，B a o d i n g0 7 1 0 0 3 ) A b s t r a c t ：R e c e n tr e s e a r c ha b o u tb e s tr e p a i rp a t ht e c h n o l o g yo fp o w e rd i s t r i b u t i o nn e r ki sm o s t l yc o n c e n t r a t e di nt h es h o r t e s tp a t h a l g o r i t h m I nt h el i g h to ft h es h o r t e s tp a t h ，m a n ya l g o r i t h m sh a v es o m ed i s a d v a n t a g e s A r t i f i c i a lf i s h - s w a r ma l g o r i t h mi sn o te a s yt o e n l a r g et h es e a r c hs p a c ea n de a s yt of a l li n t ol o c a lo p t i m a ls o l u t i o n G e n e t i ca l g o r i t h mh a ss t r o n gr o b u s t n e s s ，b u tt h el o c a ls e a r c h a b i l i t yi sv e r yb a d T h i sp a p e rh a sm i x e du pa r t i f i c i a lf i s h - s w a r ma l g o r i t h ma n dg e n e t i ca l g o r i t h m , c o m b i n e dt h e i ra d v a n t a g e s A n d e x p e r i m e n tr e s u l t ss h o wt h a tt h em e t h o di sf e a s i b l e K e yw o r d s ：p o w e rl i n e ；a r t i f i c i a lf i s h s w a r ma l g o r i t h m ；g e n e t i ca l g o r i t h m ；o p t i m a lp a t h O引言 电力线路将发电厂、变电站、配电设备和电力用 户连接成1 个有机整体，其运行情况直接影响电力 系统的运行可靠性。因此，保证电力线路的正常运 行对提高电力系统的可靠性、安全性具有重要作 用。当电力线路发生故障导致停电时会严重影响人 们的生活质量，也会对生产设备以及产品的生产造 成严重后果，因此必须快速抢修故障，以确保可靠供 电。于是，就引出了电网最佳抢修路径问题。 遗传算法是由美国的J o h nH o l l a n d 教授于 1 9 5 7 年提出的1 种仿生型优化算法它具有大范围 快速全局搜索能力但传统的遗传算法有着计算无 目的性、收敛速度慢、易陷入局部最优解的问题【1 1 。 鱼群算法是中国李晓磊博士于2 0 0 2 年提出的，它是 1 种基于动物行为的寻求全局最优的新思路，从构 造动物简单的底层行为做起，通过各动物个体的局 部寻优行为。最终在群体中使全局最优化的值突现 出来。很多学者对鱼群算法加以研究改进并应用到 各个领域。有学者提出基于变异算子的人工鱼群混 合算法 2 1 。也有学者提出通过改进鱼群搜索行为改 进算法效果的思想1 3 1 。本文尝试在鱼群算法求解的 基础上，用遗传算法对解进行优化以求解最佳抢修 路径的全局最优解。 1鱼群算法的基本原理 鱼群在一片水域中一般都能找到富含营养物质 的地方并聚集成群。在这种群体活动过程中。并没有 统一的协调者，而是通过每个鱼类个体的自适应性行 为而达到的，鱼类个体的行为可总结为下面几种典 型类型：觅食行为、聚群行为、追尾行为和随机行为。 ( 1 ) 觅食行为。鱼的基本行为，当发现附近有食 物时，会向该方向游动。 ( 2 ) 追尾行为。当某条鱼发现该处食物丰富时 电网技术一。lAz、，、，z。J工c 万方数据 ：i ： 攀 霎 c 其它鱼会快速尾随而至。 ( 3 ) 聚群行为。它们往往能形成非常庞大的群。 ( 4 ) 随机行为。当闲暇无事时，鱼会轻松地自由 游动。 鱼群算法采用了自上而下的设计方法，每个人 工鱼的设计可以采用面向对象的构造方法，把鱼个 体的状态、属性和行为都封装为1 个对象。 人工鱼个体状态( A F - _ X ) 可表示为向量X = 9 x 。， 石2 ，) ，人工鱼当前所在位置的食物浓度表示为 y = f ( x ) ，Y 为目标函数值域。人工鱼个体之间距离 表示为d q = l l x i x i l l ；y 括删表示人工鱼的感知范围； 艿表示拥挤度因子：A 心t e p 表示人工鱼移动的步 长。人工鱼的行为描述如下： ( 1 ) 觅食行为：设人工鱼当前状态为X h 在其感 知范围内随机选择1 个状态X i ，如果Y i r j ，则该方 向前进一步；反之，再重新随机选择状态X i ，判断是 否满足前进条件；反复几次后，如果仍不满足前进 条件，则随机移动一步。 ( 2 ) 聚群行为：设人工鱼当前状态为置，探索当 前领域内( 即d o V i s u a l ) 的伙伴数目I l , f ，如果n f N 6 ，表明伙伴中心有较多的食物并且不太拥挤，如果 此时Y i y 。，则朝伙伴的中心位置方向前进一步；否 则，执行觅食行为。 ( 3 ) 追尾行为：设人工鱼当前状态为置，探索其 领域内状态最优的邻居X M A x ，如果y 。 y 龇，并且 X 眦的领域内伙伴的数目7 , f 满足n f N z。J工c 万方数据 表1 算法成功率对比表 黼称铤霸5 单0 触够r ) j 5 0 数黼s 专燃。 算法名称2 5 代成功 计算次数美l ；X 誉。善翟X ：” 次数次数 “+“ 表明。鱼群遗传混合算法能够解决电力系统故障抢 修搜索最优路径问题，鱼群算法优秀的收敛能力提 高了搜索速度。遗传算法为搜索全局最优解提供了 保障本混合算法具有一定的实际应用能力。 5 结论 本文尝试用鱼群遗传混合算法求解电力故障 抢修中最优路径的搜索问题，通过实验验证了该混 合算法具有一定的可行性，较传统遗传算法和单纯 的鱼群算法在收敛性和寻优成功率上都有提高，但 该混合算法在计算初始化时，需要设定的参数较 多特别是鱼群算法中鱼群搜索的循环次数难以把 握循环次数过小。算法收敛不完全。循环次数过 大，易浪费资源。要想取得较好的计算效果，参数值 需要根据实际情况多次调整选定。 参考文献 1 】X I O N GSW ，L ICJ AD i s t r i b u t e dG e n e t i cA l g o r i t h mt oT S P 【C 】P r o c e e d i n g s o f t h e 4 t h W o r l d C o n g r e s s ，2 0 0 2 ，( 3 ) ：8 2 7 - 1 8 3 【2 】 【3 】 【4 】 【5 】 黄华娟，周永权基于变异算子的人工鱼群混合算法m 计算机工程与应用，2 0 0 9 4 5 ( 3 3 ) ：2 8 3 1 范玉军，王冬冬，孙明明改进的人工鱼群算法阴重庆师 范大学学报。2 0 0 7 2 4 ( 3 ) ：2 3 2 6 W A N GJP H UMJ AS o l u t i o nf o rT S PB a s e do nA r t i f i c i a l F i s hA l g o r i t h mf C l C I N C 0 9 I n t e r n a t i o n a lC o n f e r e n c e ， 2 0 0 9 ，( 2 ) ：2 6 2 9 X 1 A OJM Z H E N GXM 。W A N GXH 。e ta 1 AM o d i f i e d A r t i f i c i a lF i s h S w a r mA l g o r i t h m 【C 】T h eS i x t hW o r l d C o n g r e s s ，2 0 0 6 ，( 1 ) ：3 4 5 6 - 3 4 6 0 【6 】梁艳春，吴春困，时小虎，等群智能优化算法理论与应用 I M l 北京：科学出版社2 0 0 9 【7 】李敏强，寇纪松，林丹遗传算法的基本理论与应用【M 】 北京：科学出版社2 0 0 2 【8 】8 G E NM ，C H E N GR ，W A N GD G e n e t i cA l g o r i t h mf o rS o l v i n g t h eS h o r t e s tP a t h P r o b l e m C I E E EI n t e r n a t i o n a l C o n f e e r e n e eo nE v o l u t i o n a r yC o m p u t a t i o n ，1 9 9 7 ：4 0 1 - 4 0 6 【9 】F UMY ，X U EB AP a t hP l a n n i n gA l g o r i t h mB a s e do n D y n a m i cN e t w o r k sa n dR e s t r i c t e dS e a r c h i n gA r e a 【C 1 P r o c e e d i n g o ft h eI E E EI n t e r n a t i o n a lC o n f e r e n c eo n A u t o m a t i o na n dL o g i s t i c s ，2 0 0 7 ：11 9 3 - 11 9 6 【l o 】王联国，洪毅，赵付青，等一种改进的人工鱼群算澍J 】 计算机工程，2 0 0 8 ，3 4 ( 1 9 ) ：1 9 2 1 9 4 【1 l 】苏煜，王薇一种适用于配电网重构的改进遗传算法叨 陕西电力，2 0 0 6 ，3 4 ( 7 ) ：2 6 2 9 ( 责任编缉付小平) 收稿日期：2 0 1 1 - 1 1 - 2 1 作者简介：李浩( 1 9 8 5 一) ，河南郑州人，硕士研究生，研究方向为 电力系统继电保护。 + - + 一+ 一+ - 卜- + - + - 卜卜- + 一- + - + - + 一+ - + - 卜- + - + + - 卜- - + - + 一- 卜- + - - 卜卜- + - 卜- + - 卜卜卜- + - + 卜- + - 卜卜- + - 卜- 卜- 卜- + - + ( 上接9 3 页) 效应、绝缘配合及成本造价等各方面来综合考虑其 结构参数。由以上分析可以看出。在满