（电力系统及其自动化专业论文）基于gaaa算法的最优潮流问题研究.pdf

华匕电力人学硕七学侮论文摘要 摘要 电力系统的最优潮流问题是一种典型的非线性舰划问题，系统规模的不断扩大 使得变量和约束条件的数目大大增加，最优潮流问题变得越来越复杂。近年来，智 能优化算法的发展为解决大规模非线性规划问题提供了新的研究思路和方法，本文 在总结现有最优潮流算法的基础上，通过对多种最优潮流算法的比较，提出了采用 遗传算法和蚂蚁算法相结合的g a a a 算法，该算法既保持了遗传算法的全面搜索能 力，又利用了蚂蚁算法并行分布的特点。从两改善了传统优化算法在时阍效率和计 算精度上的矛盾。采用i e e e 节点系统对g a a a 算法进行了数值验证，计算结果证 明了该算法的可行性和有效性。 关键词：电力系统，最优潮流，g a 从算法，遗传算法，蚂蚁算法 a b s t r a c t t h eo p t i m a lp o w e rf l o w i n g ( o p f ) i sat y p i c a ln o n l i n e a rp r o g r a m m i n gp r o b l e m t h e c o n s t a n te n l a f g e m e n to ft h es c o p eo ft h ep o w e fs y s t e l 程m a k e sl h en u m b e fo ft h e v a r i a b l e sa n dc o n s t r a i n tc o n d i t i o n si n c r e a s e ，a n dm a k et h eo p fp r o b l e mc o m p l e x r e c e n t l y ，i n t e i l i g e n to p i i m i z a t i o na l g o r i i h m sp r o v i d en e wt h o u g h t sa n dm e t h o d sf o r s o l v i n gt h el a r g e - s c a l en o n l i n e a rp r o g r a m m i n gp r o b l e m b ya n a l y z i n ga n dc o m p a r i n g m a n yk i n d so fo p fa i g o r i t h m sa n dr e s e a r c hs t a t u s ，i h i sp a p e rp r o p o s e st h eg a a a a l g o r i t h mt h a t i st h ec o m b i n a t i o no fi h eg e n e t i ca l g o r “h ma n dt h ea n ia l g o r i l h m t h i s m e t h o dn o to n l yr e m a i n sg e n e t i ca l g o r i t h mg o o dq u a l i t y0 fs o l u t i o n ，b u tu s e sa n t a l g o r i t h mc l a s s i f i c a t i o np a r a l l e la i g o r i t h l n ， s oi 】m p f o v e st h et i m ee f f i c i e n c ya n dl h e c a l c u l a i i o na c c u r a c ya tt h es a m et i m e t h ep a p e ru s et h ei e e es y s t e mt 0 t e s tt h e a l g o r i t h m ，t h er e s u l t ss h o w st h a ct h ep r o p o s e da l g o r i t h mi sp r a c t i c a b l ea n de f f e c t i v e 、 ，a n gc a n ( p o w e rp l a n tt h e r m a lp o w e re n g i n e e r i n g ) d i r e c 耋e db yp f o f l u j i n l i n g k e yw o r d s ：p o w e rs y s t e m ，o p f g a a aa i g o r i t h m ，g e n e t i ca l g o r i t h m ，a n t a i g o r i t h m 声明尸明 本人郑重声明：此处所提交的硕士学位论文 。，c + ，o 。 ( 3 3 ) 华北电力大学硕士学位论文 若目标函数为最大问题，则 1 鼢( ，o ) ) - - 乇石， c o ，c 一，o ) o h c - 7u j ( 3 4 ) 上述是最常见的三种适应度函数，总之适应度函数的设计一定要满足单值、连 续、非负、最大化、合理、计算量小且具有一致性，通用性强。 遗传操作：基于上述适应度值，选择个体用来复制下一代。选择操作体现了“适 者生存 的原理，“好 的个体被选择用来复制，而“坏”的个体则被淘汰。然后 选择出来的个体经过交叉和变异进行再组合生成新的一代。这一群新个体由于继承 了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方 向进化。因此，遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。 遗传操作包括三个基本遗传算子：选择、交叉、变异，选择和交叉基本完成了 遗传算法的大部分搜索功能，变异增加了遗传算法找到接近最优解的能力。 ( 1 ) 选择 选择就是利用编码后求得的各个个体的适应度的大小，从中选出一些适应度高 的个体，并淘汰一些适应度较小的个体以生成交配池的过程。然后再对优良的个体 进行交叉和变异操作。 在选择算子中，先计算适应度，找出当前群体中适应度最高和最低的个体，将 最佳个体保留并替换最差个体，直接进入下一代，将剩余个体按选择概率进行操作。 选择概率的常用分配方法有按比例的适应度分配和基于排序的适应度分配两种，前 者是利用比例于各个个体适应度的概率决定其子孙的遗留可能性，而后者则是按照 目标值进行排序，适应度取决于个体在种群中的序位，常用的选择方法则包括轮盘 赌选择法、随机遍历抽样法、局部选择法和锦标赛选择法。这几种选择方法均以适 应度为基础进行选择，不同的选择方法的行为是有差别的，基本遗传算法达到收敛 的代数与选择强度成反比，较高的选择强度是很好的选择方法，但是太高会导致收 敛过快，解的质量差，因此一定要慎重选择方法。 本文采用轮盘赌( r o u l e t t ew h e e ls e l e c t i o n ) 方式来实现选择。这种方式首先计算每 个个体的适应值，然后计算出该适应值在群体适应值总和中所占的比例，来表示该 个体被选中的概率，这样既能保证最佳个体的适应度值不会减小，最佳个体不会被 交叉变异操作所破坏，也能不断提高该群体的平均适应度值。比例选择法体现了生 物进化过程中“优胜劣汰，适者生存”的思想，并且保证将优良的基因遗传给下一 代。轮盘赌法中的个体被选中概率为： 华北电力大学硕士学位论文 写i 五盘五 ( 3 5 ) 式中， 为个体f 的适应度，足是个体被选中的概率，为个体数目。 ( 2 ) 交叉基因重组 基因重组是把两个父个体的部分结构加以替换重组而生成新个体的操作，也称 为交叉( c r o s s o v c r ) 。重组的目的是为了能够在下一代产生新的个体，就像人类社会 的婚姻过程，通过重组交叉操作，遗传算法的搜索能力得以飞跃地提高。基因重组 和交叉是遗传算法获取新代优良个体的最重要的手段。 通常使用的遗传算子是单点交叉法，就是按交叉概率p c ( 0 印c 1 ) 实施交叉操作， 两个个体编码串( s t r i n g ) 在交叉位置处( c r o s s p ) 相互交换各自的部分编码从而形成新 的一对个体。例如两个1 1 位变量的父个体： 父个体1 ：01110011010 父个体2 ：1010110 0 l01 假设交叉点的位置定为5 ，那么交叉后生成的两个子个体分别为： 予个体1 ：o111010 o101 子个体2 ：101o1011010 以上就是单点交叉的过程，但是，单点交叉法操作的信息比较小，交叉点的位 置的选择可能会带来较大的偏差，单点交叉算子不利于长距离的保留和重组。 ( 3 ) 变异 重组之后是子代的变异，变异算子是模拟自然界生物进化的中染色体的基因突 变现象，从而改变染色体的结构和物理性状。子个体变量以很小的概率或步长产生 转变，变量转变的概率或步长与维数成反比，与种群的大小无关。变异操作通过按 照变异概率沏p j 随机反转某位等位基因的二进制字符的值来实现。变异本身是一种 局部随机搜索，与选择霞组结合在一起，保证了遗传算法的有效性，使遗传算法具 有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟 收敛。在变异操作中，变异率不能取得太大，如果变异率大于o 5 ，遗传算法就退 化为随机搜索，导致遗传算法的一些重要的数学特性和搜索能力也就不复存在了。 控制参数的设计：控制参数的设计主要包括种群大小和遗传算子概率的设定， 种群大小是每一代个体的固定总数，即初始解的个数，所以其对结果和计算时间都 有影响，为了能使初始解在解空间分布均匀，种群的大小不能太小也不能太大，需 要根据所求的问题来确定。遗传算子主要包括交叉率和变异率，交叉率的经验取值 华北电力人学硕十学位论文 为0 2 5 1 之问，变异率的经验取值则分布在0 1 之问，般取0 0 0 2 之间的一 个数。 从上述的分析中，我们可以看出遗传算法具有进化计算的所有特征，同时又具 有自身的特点： 1 ) 直接处理的对象是决策变量的编码集而不是决策变量实际值本身，搜索过程 既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。 2 ) 遗传算法是一种目适应搜索技术，具有很高的隐含并行性，其选择、交叉、 变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，同时能以 很大的概率收敛于最优解，具有较好的全局优化求解能力。 3 ) 遗传算法直接以目标函数值为搜索信息，具有较好的普适性和易扩充性。 4 ) 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到 满意的结果，但是在搜索过程中所有的个体都有可能陷入于同一极值而停止进化， 或接近最优解的个体总是被淘汰从而导致进化过程无法收敛。 3 1 3 遗传算法的算例分析 假设一个简单函数： 似) = 5 工6 3 缸5 + 8 2 5 工4 6 一+ 3 6 ，工( o ，3 5 ) ( 3 6 ) 采用遗传算法进行计算求取函数厂( x ) 的最小值，选取种群规模为3 0 ，搜索精度 为0 0 1 ，适j 踅度函数为只标函数本身，毖冈莺组选择单点交叉，交叉率为o 7 8 ，变 异选择二进制变异，变异率为0 0 2 ，可以得到为遗传迭代5 0 次后适应度函数值的 图形： 42 甥43 辗 t 翘 鉴4 5 4 6 7 i 0 燃3 1 最侍适晦值示意图 华北电力人学硕十学位论文 由上图可以看到从第7 代左右丌始适应值变化率就已经很小了，到第2 0 代以 后基本上就不发生变化了，这时可以认为已经找到全局最优解，此时z = 3 触) = 一 4 5 ，全程运行所用的时间为0 3 6 s 。另外遗传算法的种群规模，交叉率，变异率等 参数对函数的求解有着一定的影响，因此选取合适的参数是很重要的，请参考文献 【2 6 1 ，这罩不再详述。 3 2 蚂蚁算法 3 2 1 蚂蚁算法的发展 蚂蚁算法是最近几年j 。提出的一种新型的随机搜索模拟进化算法，它是继模拟 退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法以后的 又一种应用于组合优化问题的启发式搜索算法，由意大利学者m d o r i g o 等人首先提 出【心】，他们又称之为蚁群系统( a n te c o l o g ys y s t e m ) ，并用该方法求解旅行商问题 ( t s p ) 1 2 7 1 、指派问题【2 8 1 、j o b s h o p 调度问题1 2 9 1 、图着色问题1 3 0 1 、车辆调度1 3 、集 成电路设计1 3 2 l 以及通信网络负载问题的处理【3 3 l 等，取得了一系列较好的实验结果。 受其影响，蚁群系统模型逐渐引起了其他研究者的关注，并用该算法来解决一些实 际问题。蚂蚁算法在动态环境下表现出了高度的灵活性，如其在电信路由控制方面 的应用被认为是目前较好的算法之一。目前，国内也有一些学者对蚂蚁算法及其在 电信领域的应用开展了研究1 3 4 。5 1 。虽然对此方法的研究刚刚起步，但一些初步的研 究结果已经显示出蚁群算法在求解复杂优化问题的一些优越性，证明它是一种很有 发展前景的优化方法。 从数学模型上来说，为了克服蚂蚁算法存在的收敛速度慢，容易出现停滞现象， 人们提出了很多改进的措施。带精英策略的蚂蚁系统是最早的改进蚂蚁系统，该算 法类似于遗传算法中的精英策略，为了保留住一代中的最佳适应个体，在每次循环 之后，给予最优解额外的信息素量，这样可以使蚂蚁系统找出更优的解，但是使用 精英蚂蚁过多会导致搜索早熟收敛，因此需要选择精英蚂蚁的个数。文献f 1 2 】中提 到一种壁于优化排序的蚂蚁算法，陔算法将蚂蚁按照路径长度进行排序，然后根据 对信息素量更新的贡献和排名的化次进 r 加权。德国学者提出了一种最大最小蚂蚁 算法，是比较好的一种算法，该算法限定了信息素允许值的上下限，在防止算法过 早停滞及有效性方面较蚂蚁系统a s 算法仃较大的进步。蚂蚁算法是一种新生算法， 具有很强的通用型和鲁棒性，从提出到现在，仅仅几十年的时间便引起了人们强烈 的关注。 3 2 2 蚂蚁算法模型的基本原理 华北电力大学硕士学位论文 生物学家的研究已经表明，蚂蚁之间可以通过一些信息素进行协同作用，实现 蚂蚁之间的信息交流和传递。经过观察发现，生物世界中的蚂蚁在搜索食物时，能 在其走过的路径上释放一种信息素，使得在一定范围内的其他蚂蚁能够察觉到并影 响其搜索行为。蚂蚁个体之间就是通过这种信息素来相互传递信息的，从而能相互 协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该物质， 而且蚂蚁在运动过程中，能够感知路径上这种物质的存在及其强度，以此来指导自 己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。 如图3 - 2 ，a 为蚂蚁巢穴，b 为食物源，从a 到b 有两条路径可走，a c b 是较 长的路径，a d b 是较短的路径。假设有8 只蚂蚁，分别用1 ，2 ，3 ，8 ，表示，开始 时蚁穴中的蚂蚁向食物源移动，由于路径上没有蚂蚁移动，因此这两条路径上均没 有信息素分布，则蚂蚁选择这两条路径的机会均等。设蚂蚁1 ，2 ，3 ，4 选择a c b ，蚂 蚁5 ，6 ，7 ，8 选择a d b ，速度相同的情况下，当蚂蚁5 8 到达食物源b 时，蚂蚁1 4 还在途中，在靠近b 端的位置还没有留下信息素，因此蚂蚁5 8 中的大部分蚂蚁 按原路返回。假设蚂蚁5 7 选择b d a ，蚂蚁8 选择了b c a 。当蚂蚁1 4 到达食 物源后返回时，由于一共有7 只蚂蚁经过b d a ，而只有5 只蚂蚁在b c a 上留下了 信息素，因此蚂蚁1 4 中的大部分蚂蚁也选择了b d a ，假设是蚂蚁1 3 。这样， 当第一次搬运食物后，路径a d b 上相当于有1 0 只蚂蚁留下了信息素，而路径a c b 上相当于仅有6 只蚂蚁留下了信息素，第二次搬运食物时，由于两条路径上的信息 素不等，那么较多的蚂蚁就会选择信息素多的路径，而只有一少部分蚂蚁选择了信 息素较少的路径，如此继续下去，由大量蚂蚁组成的蚁群的集体行为便表现出一种 信息正反馈的现象：当某路径上经过的蚂蚁越多时，留在相应路径上信息素轨迹也 越多，以致信息素的强度增大，后来的蚂蚁选择该路径的概率也就越高，从而进一 步增加该路径的信息素强度。蚂蚁个体之间就是通过这种信息的交流达到快速搜索 食物的目的的。 c 图3 2 蚂蚁搜索路径 3 2 3 蚂蚁算法模型及其改进 蚂蚁算法最早应用于旅行商问题，旅行商问题是指给定n 个城市和两辆城市之 华北电力大学硕士学位论文 间的距离，要求确定一条经过各城市当且仅当一次的最短路径，根据上述原理我们 就这个问题对基本蚂蚁算法模型进行分析研究。 现在用求解平面上万个城市的t s p 问题【1 2 1 ( 1 ，2 ，3 ，尼表示城市的序号) 为例说明蚂蚁算法的基本模型。对于其它问题，可以对此模型稍作修改便可应用。 假设将小只蚂蚁放入刀个随机选择的城市中；d i jo ，j = 1 ，2 ，3 ，厅) 表示城市 f 和城市f 之间的距离；( 0 ) 表示f 时刻在城市i 和城市j 连线上残留的信息量，初 始时刻，各条路径上信息量相等，设t i j ( 0 ) = c ( c 为常数) 。蚂蚁七他= l ，2 ，m ) 在运动过程中，根据各条路径上的信息量选择下一个它还没有访问的城市，同时在 完成一步( 从一个城市到达另外一个城市) 或者完成一个循环( 完成对所有行个城市的 访问) 后，更新所有路径上的残留信息量。选择下一个城市的依据主要为：t i ( t ) 一t 时刻在城市i 和城市j 连线上残留的信息量，即由蚁群算法所提供的信息；m 一蚂 蚁由城市f 转移到城市，的期望信息，这一启发式信息可由所要解决的问题给出， 并由一定的算法来实现，在t s p 问题中一般取m = 1 d i j ，m 在这里可以称为先验 知识。p ：( t ) 表示在f 时刻蚂蚁七由城市f 转移到目标城市的概率： p ：( t ) = 一胩a n 吣 0 ， o t h e n i s e ( 3 7 ) 供蚂蚁选择下一个目标城市的可能性是题目本身所提供的启发信息叩。与从“蚂 蚁”目前所在城市到目标城市路径上残留信息量z i ( t ) 的函数。由公式( 1 ) 可知，蚂蚁 在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向，即，= 衄) ( ) 概率值最大的方向。上式中： a l l o w e d k = l ，2 ，n ) t a b u k 表示在f 时刻蚂蚁七下一步允许选择的城市( 即 还没有访问的城市】。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能，这 罩用l a b u k = ( 1 ，2 ，肌) 记录蚂蚁目前已经走过的城市： o 【一残留信息量的相对重要程度； b 一期望值的相对重要程度； 经过，1 个时刻，蚂蚁完成一次循环，在进行下一轮循环前，必须将最新的蚂蚁 访问过的各路径上留下的新信息加入到t “中。信息量要根据下式作调整： z q ( n + t ) = p 吒( t ) + 啊 瓴= 璐瞄 2 3 ( 3 8 ) ( 3 9 ) 华北电力大学硕士学位论文 式中： p 一信息残留系数。模仿人类记忆的特点，旧的信息将逐步削弱，随着时间的推 移，以前留下的信息将要逐渐消逝，用参数1 一p 表示信息消逝程度( 即挥发程度) 。 厶百i j k 一第七只蚂蚁在本次循环中( 在时间段t 到( t + n ) 内的访问过程中) ，留在i 到 j 路径上的信息量； 厶一表示本次循环中所有可能经过路径可的蚂蚁留在f 到_ 路径上的信息量的 增量。 关于缸i j k 的计算，m d o r i g o 曾给出三种不同的实现方法1 1 2 1 ，分别称之为蚁周 模型( a n t c y c i es y s t e m ) ，蚁密模型( a n t d e n s i t ys y s t e m ) ，蚁量模型( a n t - q u a n t i t ys y s t e m ) 。 它们的差别在于表达式f ：的不同： 在a n t c y c l es y s t e m 模型中： 睁辟如果蚂蚁删路径i j 【o ，否则 ( 3 - 1 0 ) 在a n t d e n s i t ys y s t e m 模型中； 苗：苦，如果蚂蚁k 经过路径i j i o ，否则 ( 3 1 1 ) 在a n t q u a n l i t ys y s t e m 模型中： r ；= r 嚣蚍绁鼢巧 ( 3 - 1 2 ) 上述式( 4 ) 、( 5 ) 、( 6 ) 中： q 一为一常量，为蚂蚁循环一周或一个过程在经过的路径上所释放的信息素总 署 = = 巴 l k 一表示第七只蚂蚁在本次循环中所选择的路径长度。上述三种算法的区别在 于：前者利用的是蚁群的整体信息，即走完一个循环后才进行残留信息量的全局调 整；而后两种模型中蚂蚁每走一步( 即从时间f 到f + 1 ) 都要更新残留信息的量，而 不是等到所有的蚂蚁对所有，1 个城市的访问以后。 2 4 华北电力大学硕士学位论文 下面是根据上述介绍总结出蚂蚁算法的几个主要步骤： ( 1 ) 初始化算法参数。设循环次数初值f = 0 ，路径( f ，| ) 上的信息素q ( 0 ) = c 。 ( 2 ) 如果f 小于预先设定的最大允许循环次数且无退化行为( 即找到的都是相同 解) ，则领f = f + 1 和七= 0 ，并转步骤( 3 ) ；否则输出最佳路径。 ( 3 ) 派出第七只蚂蚁。蚂蚁以一种随机策略完成一个旅程，每个旅程都代表旅 行商的一次巡回旅游，即问题的一个解。同时令七= “1 。 ( 4 ) 用评价函数蚂蚁的旅程，并记录当前最好解。 ( 5 ) 如果七 0 为启发式因子，分别表示蚂蚁在运动过程中各个区域吸f j i 强度及j f j 望值在蚂蚁选择 搜索区域中所起的不同作用。 根据式( 3 8 ) 对信息索强度进行更新，由于信息素与函数的适应度成正比，蚂蚁 搜索到的解越好，函数的适应度越高，信息素就会越强，所以这罩令信息素更新值 和遗传算法中适应度函数相同，即缸= ，j f 铆p s 5 。 蚂蚁算法的循环过程如下：所有蚂蚁在一定的小邻域范围b o u n d a r e a 内进行随 机搜索，设原来的位置点为x ，则新的位置点为x = x + x ，其中x 为随机取值， 若新的位置点比原来的位置点更优，则用新的位置点取代原来的位置点，否则不变。 2 6 华北电力大学硕士学位论文 在所有蚂蚁完成随机搜索后，对蚂蚁所在区域内的信息素进行更新并选出其中适应 度最差的蚂蚁，然后根据它的状态转移概率进行转移，函数雕) 的寻优问题就这样 借助于历只蚂蚁在b 曲，工m 。x 】的等分区域间的不断移动以及区域内的局部随机搜索 来进行的。以上蚂蚁算法的模型我们暂且称之为普适性的蚂蚁算法。 由此可见，每只蚂蚁要么以上述规则从当前区域按照转移概率转移到另一个区 域进行随机搜索，要么在当前区域继续进行局部随机搜索【3 引。一旦蚂蚁的数目足够 大，在先验知识的引导下的随机搜索下最终收敛到函数的最优解。 优化过程的具体算法步骤如下： 步骤1 根据具体优化问题确定最大循环次数及蚁群规模m ； 步骤2 确定变量的取值范围，并初始化蚁群所在位置及其信息素大小； 步骤3 所有蚂蚁在一定邻域范围内进行随机搜索，并更新该区域的吸引强度大 小，找出适应度最差的蚂蚁f 。 步骤4 根据蚂蚁f 的状态转移概率对其进行转移，更新区域的吸引强度并求出 所有蚂蚁的目标函数值。 步骤5 判断终止条件是否成立，否则转向步骤3 ，直至终止条件成立。 3 2 4 蚂蚁算法算例分析 假设连续函数为式( 3 - 6 ) ，蚂蚁数目肌为5 ，启发因子a = 1 ，= 0 9 ，信息素 挥发系数，o “= 0 8 ，初始信息素值触d ( 0 ) = 1 ，按照上述步骤进行迭代计算得到当 工= 2 9 1 时，最优解似) = 一4 4 8 。下图为迭代过程中的目标函数值。 fi ；!i l |i；i i ；i；i l1 ； i 科：譬高善：害二二 ：i 毒i i ： ； i j ；ii 小卜l 专l l l l 毒二；) 睾睾与 爿 图3 3 蚂蚁算法的目标函数值 从上图可以发现当运行迭代到第1 0 次时，函数值变化率很小，到达第2 0 次后 2 7 华北电力大学硕士学位论文 函数值的变化率几乎为零，由此得到函数的最优解，运行时间达到o 0 3 4 。 3 3 遗传算法和蚂蚁算法相结合的g 从a 算法 为了能够更好的找到问题的最优解，蚂蚁算法和其它智能算法结合形成新的算 法是学者们广泛研究的一个课题。遗传算法具有大规模快速全局搜索能力，但当求 解到一定范围时往往做大量无为的冗余迭代，对于系统的反馈信息利用不够，求解 精度效率较低，蚂蚁算法主要是通过蚂蚁群体之间的信息素传递和更新达到最终收 敛于最短路径上，其原理是一种正反馈机制，但是其初期信息素匮乏。遗传算法和 蚂蚁算法的融合正是基于遗传算法的快速全局搜索能力和蚂蚁算法的全局正反馈 收敛机制，初期采用遗传算法生成信息素分布，后期利用蚂蚁算法正反馈求解精确 解，优势互补。 3 3 1g a a a 算法的基本模型及其改进 g a a a 算法【3 8 1 中的遗传算法是基于优胜选择遗传算法的原理与定义，首先结合 解决的具体问题，采用简单的二进制编码，结合目标函数设定适应值函数，随后利 用r a n d 函数随机生成一定数量的二进制编码种群，根据适应值函数选择准备进行交 配的染色体父个体，并对所选择的父个体进行交叉变异从而得到新的种群，然后在 选择交叉变异，不断的迭代求解从而得到较优解。 在g a a a 中蚂蚁算法采用了最大一最小蚂蚁系统m m a s 算法1 32 1 ，考虑到将 m m a s 与g a 算法相衔接，信息素更新模型采用蚂蚁圈模型进行信息素更新，即一 圈中只有最短路径的蚂蚁才进行信息素修改增加，其轨迹强度的更新方程可定义 为： ( t + 1 ) 2 册( t ) + 畸( t ) ( 3 - 1 5 1 其中t i j ( t ) 为路径( i ，j ) 在t 时刻的信息素轨迹强度；r ：为蚂蚁j i ：在路径( i ，j ) 上 留下的单位长度轨迹信息素强度；p 表示轨迹的持久性，o “m 积 “； “j l l j n ，若掰+ 血 工m - x ( “，工) = 工m i n 一工i ， x i x m i 且 1 o ， x m i n 石i 工删 h 4 ) 由此可以看出，当所有不等式约束都满足时，惩罚项缈等于零。只要有某个不 等式约束不能满足，就将产生相应的惩罚项，而且越界量越大，惩罚项的数值也越 大，从而使目标函数额外的增大，这就相当于对约束条件未能满足的一种惩罚，当 罚因子，足够大时，惩罚项在惩罚函数中所占的比重也越大，优化过程只有使惩罚 项逐步趋于零时才能使惩罚函数达到最小值，这就迫使原来越界的变量或函数向其 约束限制靠近或回到原来规定的限值之内。 4 2 遗传算法的最优潮流 4 2 1 遗传算法的在电力系统中的发展和应用 遗传算法的应用研究己经从早期的组合优化问题扩展到现在广泛应用于神经 网络、机器学习、智能控制、非线性优化、系统辨识、信号处理及故障诊断等问题， 尤其是在许多工程实际中获得了成功应用。下面我们简要介绍遗传算法在电力领域 中的应用情况：( 1 ) 利用g a 求解电力系统中优化问题，避免了常规数学优化方法的 局部最优问题。( 2 ) 遗传算法在输电网络规划中的应用。输电系统规划的约束条件非 常复杂，并且随着电网规模的日益扩大，输电系统规划决策变量的维数迅速增大， 传统的优化方法由于面临组合爆炸、维数灾而未能很好地解决这个问题。遗传算法 可以考虑多种目标函数和约束条件，特别适合于整型变量优化的求解，为输电网络 规划问题的求解开创了一条新的途径。( 3 ) 将遗传算法应用于地区电网停电恢复，利 用g a 适合解决优化问题的特点，由遗传算法对停电区域进行网络重构，从而形成 最优的恢复方案，避免了基于规则的专家系统解决此问题的局限性。( 4 ) 利用g a 对 实际分布系统中的滤波器的安装位置、安装个数和参数进行统一优化，以配电网中 无源和有源滤波器的总费用最小为目标函数，以谐波电压和滤波器的安全运行为约 束条件，将遗传算法应用于配电网谐波抑制工作。 4 2 2 遗传算法的最优潮流计算 基于遗传算法的最优潮流求解过程主要包括染色体串设计、遗传操作设计以及 为满足基本潮流方程等式约束而采用牛顿法对染色体串各基因值修正等过程。在最 优潮流问题中，通常取发电费用最小做为目标函数，选取控制变量中的发电机( 除 平衡节点) 有功出力p g 和所有节点电压幅值v m 作为该问题的变量，而变量的取值 范围6 d h 玎d 为【p g m 。p g m i 。；v m m 。v m m i 。】，收敛精度为0 0 0 l ，根据收敛精度和取值 3 3 华北电力大学硕士学位论文 范围就可以确定染色体串长度，适应度函数为1 0 0 ( 1 + f + 聊。用遗传算法进行o p f 计算的基本步骤： s t c p1 选择控制变量，确定染色体串的长度，输入交叉和变异概率等参数； s t e p2 先对控制变量进行编码，形成进化的个体，随机产生若干个符合o p f 约 束条件的个体作为初始种群； s t e p 3 计算每个个体的适应度函数值，按照选定的选择策略从中选择出第一代 父体进行交叉和变异操作，产生新的子代； s t e p 4 验证每个子代是否符合o p f 的约束条件，进行目标函数和适应度函数的 计算； s t e p 5 判断迭代是否符合终止条件，若符合则停止，输出函数最优解，否则转 到步骤3 ，重复进行计算直到符合终止条件。 按照上述步骤，我们对选用电力系统i e e e 3 0 节点系统对遗传算法进行验证， 种群规模为1 0 0 ，迭代次数设为3 0 0 ，交叉率为0 8 ，变异率为0 0 2 ，经过计算运行 得到下图： 、 1 图4 1 采婀遗传算法的最优潮流计算 从图4 1 中可以看出遗传算法程序最终收敛，迭代次数为1 0 0 次时系统的f 1 标函数值基本上没有什么变化了，当到达大约1 3 0 次左右时就得到了最优解，得到 的系统最小发电费用为5 8 7 7 9 ，纵的运行时问为6 5 6 s 。 虽然遗传算法o p f 能在全局收敛至最优解或近似最优解，但由于每产生一个个 体鄙要进行是否符合约束条件的验证，所以该算法计算量大，整个算法的收敛速度 较慢。另外，对于较大的电力系统来说，控制变量多，而且变量的变化范围大，随 机或经交叉和变异产生的个体较难符合o p f 潮流平衡约束条件，因而使得遗传算法 o p f 很难应用于大规模电力系统。 华北电力大学硕士学位论文 4 3 蚂蚁算法的最优潮流计算 4 3 1 蚂蚁算法在电力系统中的应用 蚂蚁算法在电力系统的应用还处于刚刚起步的状态，对于电力系统优化， 涉 及到如下几个方面i ”l ：第一，确定在规划期内何时、何地、建立何种类型、多大 容量的一批发电厂，最经济合理地满足电力负荷发展的需要；第二，在已知规划 水平年的预测负荷和电源规划的基础上，根据现有网络和给定参数，合理布局新 建线路，使输电网络设计能适应负荷要求、发展灵活可靠、满足安全运行要求且 经济性最好：第三，进行无功优化，使电力系统在满足无功负荷需求和电压水平 要求的前提下，充分发挥现有的各种调压措施的作用，寻求合理的无功补偿点和 最佳补偿容量，使费用最低：第四，要在电力工业中引入竞争机制， 就需要发 展电力市场，由用户选择发电公司，根据用户对每一个发电公司的购电报价和每 一个发电公司的保留电价，在满足各种约束的条件下，使报价合理的用户可以从 电网中的任意发电公司购得所需数量的电能。上述许多问题存在维数灾、局部最优 和约束条件及目标函数不易处理等特点，随着系统规模的增大，待选方案将显著 增多，发生“组合爆炸 现象，有的还属于典型的非凸多峰问题，除了全局最优解 外，一般还存在若干局部最优解，因此用传统的优化方法解决这类问题，往往得不 到满意的结果，特别在系统规模较大时更是如此。 4 3 2 采用蚂蚁算法计算最优潮流 下面我们采用蚂蚁算法进行l e e e 3 0 节点数值实验，为了能够得到较为精确的 最优解，本文采用了上章所提到的改进的蚂蚁算法。与遗传算法类似，选取发电费 用最小作为目标函数f ，控制变量中的发电机( 除平衡节点) 有功出力p g 和所有节 点电压幅值v m 作为该问题的变量。由3 2 3 节可知，蚂蚁算法中的信息素【( 即区 域的吸引强度) 是一个重要的量，蚂蚁的移动会导致信息素的变化，由于开始时每 个区域内的蚂蚁未曾移动过，因此选择信息素初始值为1 。信息素值与适应度函数 成正比( 砌e 5 s = 1 0 0 ( 1 + f + 聊) ，适应度函数是对蚂蚁个体的评价，蚂蚁所搜索到 的解越优，适应度越高，信息素越好，因此本文设信息素更新缸= 厅仂e 船。 蚂蚁算法的最优潮流计算步骤如下： s t e p l 输入原始数据，获取节点信息和支路信息，确定控制变量，取值范围为 fp g m a xp g m i n ； v m m a xv m m i n 】。 s t e p 2 假设在变量的取值范围幻“，l d 内有，1 个区域，每个区域有组蚁群，每 组蚁群有以个蚂蚁，疗为控制变量的维数。在控制变量的取值范围内随机取m 组变 3 5 华北电力大学硕士学位论文 量值，单位区域长度6 d “万如陀= 6 d “刀枷，每组蚁群代表一组变量值，每个蚂蚁代 表一个变量，随后对算法中部分参数进行初始化。 s t e p 3 根据基本潮流计算求出该系统的状态变量、目标函数f 、惩罚函数项矽 以及适应度函数，随后在一定范围内移动每个区域内的蚂蚁，使得“= “+ | l ，其中 l = 6 d 朋如朋，口蒯厅，玎为正整数，从而得到新的控制变量口、目标函数，以及适 应度函数疗铆跚，与移动前的值进行比较，将较优值赋予该组蚂蚁。 s t e p 4 通过计算得到最差区域( 即该区域得到的适应度函数最差) 并计算该区 域的状态转移概率p ，p 根据式( 3 1 4 ) 进行计算，该区域内的蚂蚁按照状态转移概 率进行转移。 s t e p 5 更新各个区域的信息素值，确定目标函数值是否已经符合终止条件，若 没有则在区域内和区域间继续移动，否则输出该目标函数值。 按照上述介绍，采用i e e e 3 0 电力系统进行验证发现，该算法在一定条件下可 以得到较优解，但是如果初始值取的太差的话就有可能在迭代次数范围内得不到较 好的解。取不同初值在相同的迭代次数内所得到的结果如下： 图4 2 蚂蚁算法选择不同初值时的运行结果 当初值很大的时候在一定的达代次数范嗣内收敛很慢，如图所示，在达代次数 达到1 0 0 次时还没有得到最优解。而当初值取得很好的时候，函数在第1 0 次左右 就得到了最优解。当然，最优解的取得还与甩值有关。当取相同的初值，但每次n 值取值不同，那么蚂蚁算法的性能又有所不同，如图4 3 ： 华北电力大学硕士学位论文 卯f 卯硼2蜘 图4 3 选择不f 司n 值时的运行结果 由上图可以看出当所取的初值相同时，每次取值的大小不同，那么蚂蚁算法的 收敛速度也不同，当甩= 1 0 ( 肛1 ) 时，大约在5 0 次左右时达到收敛值，但是其收敛 值不够精确，当_ ，l = 2 ( 豇2 ) 时，同样大约在5 0 次左右时达到了收敛，但是与 = 1 时不同的是，它的收敛速度不如它好，但是当疗= 1 ( f x ) 时最优潮流最优解容易陷 入局部最优，因此，本文选择咒= 2 。 为了在初始值不是很好的情况能够收敛，本文将迭代次数增加到3 0 0 ，l 值选 择为2 ，启发因子口勿j l l 口= 1 ，d “= 0 8 运行程序得到下图： l f _ l 、 _ ， 图4 4 蚂蚁算法程序运行结果 从图中可以看出程序运行不到1 0 0 次的时候已经收敛到5 9 0 2 4 ，运行时间为 1 6 8 8 5s ，和遗传算法得到的收敛值相比较发现，虽然蚂蚁算法运行时间较快，但是 得到的结果远不如遗传算法要好。 3 7 翻啪附；暑m刚嘲断瞄瞄鲋翳研翳奶鲫 华北电力大学硕士学位论文 4 4 基于改进的g 从a 算法的最优潮流计算 g a a a 算法在电力系统中的应用非常少，但是这种算法具有遗传算法的全局搜 索性又具有蚂蚁算法的分布并行性，优势互补，具有很大的优越性。本文将其中的 蚂蚁算法进行了改进，然后再和遗传算法结合，形成新的g 肌算法，该算法在一 定程度上解决了蚂蚁算法因离散化的问题而导致解的精确度降低的问题。下面采用 改进的g a a a 算法对最优潮流问题进行计算研究，选取i e e e 3 0 节点电力系统。 与前面的算法类似，在计算之前，我们需要做如下工作：取发电费用最小做为 目标函数，选取控制变量中的发电机( 除平衡节点) 有功出力p g 和所有节点电压幅 值v m 作为变量，取值范围为【p g m 。xp g m i 。；v m m 。xv m m i n 】。设定蚂蚁算法中蚂蚁的个 数和由遗传算法得到的次优解的个数相同，均为m 个。并假定信息素初始值纪d 0 和次优解的适应度值相等，其它参数均与蚂蚁算法的相同。 最后，按照以下步骤完成计算： s t e p l 输入原始数据，获取节点信息和支路信息，获取控制变量“的个数及其 各自的变量取值范围6 d “，z d ，根据求解精度获取群体规模n ，最大迭代次数觑陀r ， 遗传算法的交叉概率p y 和变异概率p _ r ，l ，蚂蚁算法的信息素挥发度厂d h ，蚂蚁的组 数m ，信息启发式因子口勿j l z 口和期望值启发式因子6 p 纪等参数。 s t e p 2 对所要搜索的空间进行编码，随机产生包含各个个体的初始种群，然后 进行解码形成初始变量，求出各自的目标函数和适应函数。 s t e d 3 当前迭代次数为f ，选择出适应值较高的个体，淘汰并替代适应值最小的 个体，对这些优良个体进行选择，交叉和变异，然后对经过上述操作产生的新种群 进行解码，采用罚函数的方法处理不等式约束条件从而求出最终的目标函数f 和适 应值函数疗伽e s s 。 s t e p 4 判断迭代次数是否已经达到最大值，若是则输出较优解，进行下一步， 否则转到第3 步继续迭代。 s t e p 5 根据第4 步得到的结果确定信息素仞始值胁d o ，并将由遗传算法得到的 较优解作为蚂蚁算法的初始值，随后蚂蚁群随机的选择初始值，计算出各自的目标 函数和适应函数。 s t e p 6 设当前迭代次数为f ，每组蚂蚁按照一定的半径分别进行搜索，得到新的 群体，计算目标函数f 和适应值函数，j f f _ l p 船，随后比较适应值函数疖铆p s s ，求出每 组蚂蚁的状态转移概率p ，p 根据式( 3 1 4 ) 进行计算，并将适应值最差的蚂蚁按照 状态转移概率进行转移。 3