（电气工程专业论文）基于电网分区的无功优化并行算法研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 等级电压控制的出现极大地提高了电力系统的安全稳定性和经济性，而无功电 压优化作为等级电压控制中极为关键的一环，也使得现有的无功电压优化算法面临 着新的挑战如何提高无功优化算法的计算速度已成为当前急需解决的重要课题。 本文从并行计算这一角度出发，根据目前电网大多采用无功电压分层分区平衡 的特点，通过对电力系统分布式特征的研究，提出了一种基于电网分区的无功优化 并行算法，从粗粒度上实现了无功优化的分布式并行计算，极大地提高了算法的并 行度。 在本文的算法中，如何保证各分区在计算上的完全独立，是一个十分关键的问 题。为此，本文运用辅助问题原理，通过构造辅助问题，使得无功优化并行计算中 不再出现不同变量间的交叉乘积，从而避免了增广拉格朗日函数中增广二次项对系 统可分性的破坏，实现了各个子分区在计算上的完全分离。不过，大电网在进行分 区并行计算时，随之又出现了多平衡节点之间的协调问题。而“一变量”的提出为 解决这一问题提供了可能。电压相角作为“一变量”，可以通过中间变量进行协 调，实现各分区间节点电压相角的统一文中还对中间变量在辅助问题原理中的运 用进行了推导，并给出了修正后的无功优化并行计算迭代公式。 对于各子分区内部，其计算过程已经完全独立，可根据具体情况分别采用不同 的方法进行优化计算由于原一对偶内点法具有计算时间对求解问题的规模不敏感、 计算精度较高等特点，因此，本文对各个子分区统一采用非线性原对偶内点法进行 求解。并且，针对该方法不能很好地处理离散变量、易出现不可行解等不足作出了 改进。在引入二次罚函数机制，对优化计算中的离散变量进行处理的同时，采用模 糊约束隶属函数对软约束做了模糊处理。这些改进方法，有效避免了无功优化计算 中经常出现不可行解的情况，大大提高了算法的收敛可靠性。 最后，通过i e e e l l 8 节点算例对研究内容进行了测试，采用四种不同优化方法 进行计算，并对优化结果作出了对比分析，验证了本文算法的有效性 关键词：无功优化，电网分区，辅助问题原理，变量，内点法，罚函数，模糊约束 重庆大学硕士学位论文英文摘要 a b s t r a c t t h ea p p e a r a n c eo fh i e r a r c h i cv o l t a g ee o n l r o lg r e a t l yi m p r o v e st h es e c u r i t ya n d e c o n o m i ce f f i c i e n c yo f p o w e rs y s t e m a ss i g n i f i c a n ts l 烈j o no f h i e r a r c h i cv o l t a g ec o n t r o l e x i s t i n gr e a c t i v ep o w e ro p t j l i l i 刎o na l g o r i t h mi sf a c i n gt h en e wc h a l l e n g e h o wt o i m p r o v et h er e a l - t i m ee f f e c to f r e a e d v ep o w e ro p t i m i z a t i o na l g o r i t h ma l r e a d yb e c o l l l e sa s i g n i f i c a n ts u b j e c tt h a ti sn e c e s s a r yt ob es o l v e dt i m e l y a c t u a lp o w e rs y s t e mm o s t l ya d o p tp a r t i t i o nb a l a n c i n go fn 删v ep o w e r v o l t a g e t h r o u g hs o l v i n gd i s t r i b u t e df e a t u r eo f t h ep o w e rs y s t e m , t h i sd i s s e r t a t i o nb r i n g sf o r w a r d t h ep a r a l l e l e dn 删v ep o w e ro p l j l l i 刎o na l g o r i t h mb a s e d0 1 1 1s u b a r e ad i v i s i o no ft h e p o w e rs y s t e m sf r o mt h ep a r a l l e lc o m p u t a t i o na n g l e t h i sa l g o r i t h mr e a l i z e st h e d i s t r i b u t e dp a r a l l e ll e l t c t i v l e p o w e ro p t i n l i 蒯o ni nc o a l r 豫p a r t i c l es i z e ，a n dg r e a t l y i m p r o v e st h ed e g r e eo f l r a r a l l e l i s m h o wt oa l s u 托t h ei n d e p e n d e n c eo fp a r a l l e lc o m p u t a t i o na m o n ga l ls u b a r e a si sa s i g n i f i c a n tp r o b l e m t h e r e f o r et h i sd i s s e r t a t i o na p p l i e s 删x i l i a r yp r o b l e mp r i n c i p l ea n d e o n s t i t u t 簋a u x i l i a r rp r o b l e mt oa v o i da p p e a r i n gc r o s s - p r o d u c tb e t w e e nv a r i e dv a r i a b l e c o n s e q u e n t l ya u g m e n t e dq u a d r a t i ct e r mo fa u g m e n t e dl 唱瑚n g i 趾f u n c t i o nn om o l e i m p a c to i lt h ed i v i s i o no ft h ep o w e rs y s t e m i nt h i sw a yt h ep o w e rs y s t e mc o u l db e d i v i d e di n t os e v e r a lc o m p l e t e l yi n d e p e n d e n t 掀s b u tt h ep a r a l l e lc o m p u t a t i o no ft h e p o w e rs y s t e mc o u l db r i n gm u l t i - b a l a n c eb u sp r o b l e m s o - v a r i a b l ei d e ai si n t r o d u c e d t os o l v et h i sp r o b l e m h e r e e v e r yb u sv o l t a g e p h a s ei sr e g a r d e d 雒a - v a r i a b l ew h i e l a c 趾b ec o o r d i n a t e dt h r o u g hi n t e r m e d i a t ev a r i a b l e i nt h i sw a ya l lb u sv o l t a g ep h a s er e a l i z e u n i f o r m t h ea m e n d m e n ti t e r a t i o nf o r m u l ao fp a r a l l e ll e a g t i v ep o w e ro p t i m i z a t i o ni s a c q u i r e d r h r o u g l ld e d u c t i o n o p t i m i z a t i o no fe a e hs u l ：船t e ai sc o m p l e t e l yi n d e p e n d e n t , s ot h eo p t i m i z a ：t i o n a l g o r i t h mo f e a c hs u b f l l c am a yb ed i f f e r e n th e r e , t h ed i r e c tn o n l i n e a rp r i m a l - d u a li n o f p o i n ta l g o r i t h mi sa d o p t e di ne a c hs l l b f l r e s t h i sa l g o r i t h mh a sm a n ym e r i t s b u ti ti sn o t g o o da th a n d l i n gd i s e l 眦ev a r i a b l e sa n da p p e a r si n f e a s i b l es o l u t i o nc o n s t a n t l y , s ot h e d i s s e r t a t i o ni m p r o v e st h i sa l g o r i t h mf o ri t ss l a o r t e o m i n g s a tf i r s t , d i s c r e t ev a r i a b l e s 勰 h a n d l e dt l l r o u g l au s i n gq u a d r a t i cp e n a l t yf u n c t i o n a n dt h e ns o i lc o n s t r a i n t sa 砖h a n d l e d t h r o u g hf u z z ym e m b e r s h i pf u n e t i o m t h e s el l l c t h o d $ c o u l da v a i l a b l ya v o i d 雄l p r i n g i n f e a s i b l es o l u t i o na n di m p r o v ec o n v e r g e n c er e l i a b i l i t yo f t h e a l g o r i t h m f i n a l l yt h i sa l g o r i t h mi st e s t e db yi e e el l s - b u ss y s t e m t h r o u g ha n a l y z i n gt h e 重庆大学硕士学位论文英文摘要 r e s u l to f o p t m a i z a t i o n ，i ti sp r o v e dt h a tt h i sa l g o r i t h mi sf e a s i b l ea n dp r a c t i c a l k e y w o r d s ：建删v cp o w e ro p t i m i z a t i o n ，s u b a r e ad i v i s i o n ，a u x m a r yp r o b l e mp r i n c i p l e ， a - v a r i a b l e s ，i l l t e r i o rp o i ma l g o r i t h m ，p e n a l t yf x l l 蜘o r t ，f u z z yc o n s t r a i n t m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 珠t l 、珲 签字日期： 7 川年岁月冲日 学位论文版权使用授权书 本学位论文作者完全了解重庭太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重鏖态堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打。”) 学位论文作者签名：环小埠导师签名：绷 签字日期：硼年箩月斗日 签字日期： r 月w 日 i 歹 口 重庆大学硕士学位论文1 绪论 1 绪论 1 1 电力网无功优化 改革开放以来，我国电力工业发展很快，全国发电装机容量、电力设施都以前 所未有的速度在增长但是电力系统无功电源规划设计、建设管理工作仍然比较薄 弱，存在着无功电源容量缺额大、功率因数低、线损率高、电压质量差、无功及电 压控制自动化程度低等问题尤其在现代大电网中，随着电力系统联网容量的增大 和输电电压的提高，输电功率变化和高压线路的投切都将引起很大的无功功率变化， 系统对无功功率和电压的调节控制能力的要求越来越高。为了满足电网的调压要求 和尽可能减少电网的有功功率损耗，希望电网的无功功率要尽量少流动，特别要避 免无功功率的远距离流动，这就出现了电压无功优化问题i i - 3 l 。 电力系统无功优化包括无功最优规划和无功最优运行控制两个方面。无功最优 规划是指在对系统未来一段时间内的负荷发展和网架建设作出预测的前提下，相应 地规划出系统中无功功率电源的装设地点及其容量，以期较好地满足系统未来运行 的要求。而无功最优运行控制则是指在现有网架及无功电源配置的基础上，在某一 负荷水平下进行无功优化，从而给出各无功补偿点补偿容量、变压器分接头位置以 及发电机机端电压等1 - 6 1 。 对电力系统进行无功优化，其目的和意义可概括为以下三方面： ( 1 ) 提高电力系统电压质量电压是电能质量的主要指标，保证电压的偏移都 在规定的范围内，是电力系统规划设计和运行的重要任务。 ( 2 ) 改善电力系统无功功率分布。电力系统中的无功功率本身虽然不消耗能量， 但是无功功率的传输却造成电压波动，引起有功损耗，当系统无功功率不足时将产 生电压水平下降、有功损耗增加的恶果。而在电力网的有功电源布局、网络结构、 负荷分配确定时，则有功功率损耗完全取决于电力系统中输送无功功率的大小 ( 3 ) 提高电压无功控制的自动化水平。现代电力正飞速发展，调度自动化水平 不断提高，这就使得电压无功调度成为可能，而电压无功优化反过来又进一步促进 了调度自动化水平的提高。 可以说电力网的无功电压优化，是一个既直接影响系统电压质量，又关系到电 网经济运行的重要问题。只有对电力网进行电压无功优化调度，使无功负荷就地补 偿，力求达到就地平衡，系统无功达到分层分区平衡，这样才能减少系统中无功功 率的流动，改善和提高电力系统的电压质量，降低线损率，取得更好的经济效益。 重庆大学硕士学位论文 l 绪论 1 2 无功优化算法的发展 从数学角度来看，无功优化是一个复杂的非线性规划问题，具有目标函数与约 束条件的非线性以及控制变量的离散性与连续性相混合等特点。目前，该领域的研 究方法主要有传统优化方法和人工智能方法两大类。 1 2 1 传统无功优化方法 电力系统传统的无功优化方法一般是从某个初始点出发，按照一定的轨迹不断 改进当前解，最终收敛于最优解这类优化方法有线性规划法、非线性规划法、混 合整数规划法以及动态规划法等m 6 1 。 ( 1 ) 线性规划法 在所有规划方法中，线性规划法是发展最为成熟的一种方法，其数学模型简单 直观，物理概念清晰，计算速度快，同时由于线性规划方法本身的完善性，使它的 计算规模受到较少的限制。但由于它把系统实际优化模型作了线性近似处理，并对 离散变量作了连续化处理，使计算结果往往与电力系统实际情况有差异。 ( 2 ) 非线性规划法 非线性规划法的数学模型则比较精确地反映了电力系统的实际，计算精度较高， 但其方法本身需要大量的求导、求逆运算，占用计算机内存多，使得解题规模受到 限制，同时在对不等式约束处理上也有困难，因此限制了在实际系统中的应用。 ( 3 ) 混合整数规划法 混合整数规划法的原理是先确定整数变量，再与线性规划法协调处理连续变量 它解决了线性规划法没有解决的离散变量的精确处理问题，其数学模型也比较准确 的体现了无功优化实际，但是这种分两步优化的方法削弱了它的总体最优性，同时 在问题的求解过程中常常发生振荡发散，而且它的计算过程十分复杂，计算量大， 计算时间属于非多项式类型，随着维数的增加，计算时间会急剧增加，有时甚至是 爆炸性的。所以既精确地处理整数变量，又适应系统规模使其实用化，是完善这一 方法的关键之处 ( 4 ) 动态规划法 动态规划法是研究多阶段决策过程最优解的一种有效方法，它按时间或空间顺 序将问题分解为若干互相联系的阶段，依次对它每一阶段做出决策，最后获得整个 过程的最优解。动态规划法不同于线性规划法和非线性规划法，它不要求目标函数 和约束条件必须严格遵守线性和凸性，所得的最优解也常常是全局最优解。但动态 规划法也存在缺陷，它随状态变量个数增加出现的。维数灾”问题，并且难以构成 一个实际问题的动态数学规划模型，这些都限制了它在更广范围内的推广应用。 1 2 2 现代人工智能方法 传统数学优化方法依赖于精确的数学模型，但精确的数学模型较复杂，难以适 2 重庆大学硕士学位论文 1 绪论 应实时控制要求；而粗略的数学模型又存在较大误差。近年来，人工智能方法在电 力系统无功优化中的研究与应用正处于积极进行中，其中以遗传算法、模拟退火方 法、t a b u 搜索方法、模糊集理论为代表i l ? - 2 4 1 。 ( 1 ) 遗传算法 由h o l l a n d 创建的遗传算法，是一种借鉴生物界自然选择和自然遗传机制的高 度并行、随机、自适应搜索方法此算法用于无功优化就是在电力系统环境下的一 组初始解，受各种约束条件限制，通过适应值评估函数评价其优劣，适应值低的函 数被抛弃，适应值高的才有机会将其特性迭代到下一轮解，最后趋向于最优解。遗 传算法利用某种编码技术作用于称为染色体的字符串，其基本思想是模拟由这些字 符串组成的群体的进化过程，核心操作是选择、杂交和变异在当前电力系统中， 基于遗传算法的无功优化研究也是一个热门课题。 ( 2 ) 模拟退火方法 模拟退火算法是一种随机的启发式搜索方法，适用于处理非线性规划问题，能 以较大概率求得优化问题的全局最优解。该算法在寻优结束时能得到优化问题的最 小值，但其参数的选取比较复杂而且为了使最终解尽可能接近全局最优，退火过 程不能太快，这就使得算法的计算时间过长。 ( 3 ) t a b u 搜索方法 t a b u 搜索方法是近年来受到普遍关注的一种高效率的启发式优化技术。其基本 思想是由g l o v e r 在2 0 世纪6 0 年代末提出的，在近几年得到了很大发展。它是一种 限制性的搜索技术，能通过记录搜索历史，在搜索过程中获得知识，并利用它可知 后续的搜索方向以避开局部最优解。在很多领域中，t a b u 搜索方法已成功地应用于 求解复杂的组合优化问题。 ( 4 ) 模糊集理论 模糊集理论诞生于2 0 世纪6 0 年代，它的产生不仅拓宽了经典数学，而且使计 算机科学向人们的自然机理方面发展取得了重大突破。模糊数学的独特特性使得其 在处理电力系统优化问题中的参数不确定闯题上，具有其他算法不可比拟的优势。 综上所述，前面提到的各种无功优化方法都有一定的优越性和适应性，并己成 功地解决了电力系统无功优化中的许多问题，但对于电压等级多、网络结构和潮流 复杂多变、控制变量的种类和数量较多的大系统仍存在收敛性差、难以给出全局最 优解和计算时间偏长等问题。当然，随着科学技术的发展，新的无功优化方法也是 层出不穷，对无功优化问题的研究也将更加深入 重庆大学硕士学位论文l 绪论 1 3 问题的提出 1 3 1 等级电压控制的出现 近年来，全球连续发生了多起由于电压崩溃所引起的大停电事故，如东京、纽 约大停电等圈电压崩溃的基本原因是由于电网某些地区无功不足，造成局部电压 下降，进而导致全网电压水平下降，最终使系统发生电压崩溃。地区无功不足的原 因来自两方面：一是整个系统无功储备不足：二是系统其他地区尚有较多的无功储 备，但未被利用上第一种情况需要通过增加系统的无功储备来解决，而第二种情 况则需要对系统的无功流动进行合理的协调与分配。在此认识的基础上，产生了对 电力系统采取等级电压控制的思想 等级电压控制集安全性和经济性于一体，实现了闭环控制，被公认为电力调度 自动化系统的最高级形式目前，这种等级电压控制的策略已经在法国、意大利等 多个国家付诸实施，并运行多年，取得了满意的效果。在这种等级电压控制系统中， 其结构分为三层，即一级电压控制、二级电压控制和三级电压控制。其中各级都有 各自的控制目标，下级控制以上级控制的输出作为自己的控制目标。通过分级和分 区，很自然地实现了电压的多目标控制。图1 1 显示了这种等级电压控制的组织模 式【2 嘲。 罡蟪电压 控制墨l ( 辨c 1 ) 优化控翻i 瓢 区域电压ll 嚣麓电压 控制嚣2 ll 控制嚣3 ( s 托动li ( 翱c 3 ) l 电力设备li 电力设备ll 电力设创 陴自动控| i 豹皂幼控l i 韵喜幼控i l 捌装置| i 剁装量i i 捌装置l 图1 1 国外等级电压控制的组织模式 f i 吕1 1t h ef o r e i g n 蛐m 瓣f o rh i c r k c h i c a lv o l t a g ec o n 们l 一级电压控制处于最底层，通常是快速反应的闭环控制。一级电压控制由设置 在各发电厂、用户或变电站的电压无功控制设备组成，为本地控制，只用到本地的 信息。在这级控制中，通过调节发电机组、无功补偿设备等为系统提供所需的无功 支持，以抵消快速负荷波动造成的电压波动，从而维持系统电压的稳定 二级电压控制由多个分布在电力系统各区域控制中心的相互独立的区域电压控 制器组成，通过修改一级控制器的整定值y 一来协调区域内一级控制器的行为控 制的主要目的是保证中枢母线电压等于设定值p y 二级电压控制是一种区域控制， 重庆大学硕士学位论文1 绪论 只用到本区域内的信息。这种分区控制的理论基础是无功电压的区域特性。 三级电压控制处于最高层，也是等级电压控制中最为重要的一层，其主要任务 是利用整个系统的全局信息，以全系统的经济运行为优化目标，并考虑安全性指标， 最后给出中枢母线电压幅值的设定参考值，供二级电压控制使用。任务的启动 一般由电力系统实时拓扑变化来启动任务的完成则由无功电压优化来实现。在线 计算出来的y 可通过局域网发送至二级控制工作站，实现对二级控制的协调和决 策支持，通过二级控制和一级控制最终实现安全约束下的网损最小的经济性目标。 1 3 2 无功优化算法所面临的新挑战 随着等级电压控制在国外应用的巨大成功，国内研究人员也开始对其进行了广 泛的研究，并且取得了一定的成果。目前，江苏、福建等省已经制定了初步的实施 方案，即将进入实用阶段。 但是，等级电压控制方案的实施也对处于关键环节的无功电压优化方法提出了 新的挑战。由上面的介绍我们知道，等级电压控制中的无功电压优化具有全局、实 时和闭环等几个方面的重要特征。这就导致目前的无功优化方法，尚不能在解决等 级电压控制的无功电压优化问题上达到令人满意的效果。因为电力系统计算往往是 解一组代数方程或联解代数方程与微分方程，随着电网规模越来越大，考虑的因素 越来越多，导致方程数日巨大，阶数很高，即使采用了许多先进技术，采用传统的 性能很高的计算机，传统优化方法的计算仍十分耗时，在处理实时性较强的等级电 压控制问题时，就很难在计算速度上体现出优势。如果无功电压优化不能实现快速 的在线计算，等级电压控制也就失去了应有的效果。 缩短无功电压优化计算时间的一种方法是对系统进行简化，如采用简化模型等 值计算等。但过分的简化，计算精度会下降，某些情况误差会大到无法接受的程度 因此，必须研究一种更加高效、更加快速的计算方法，以达到等级电压控制中的实 时在线计算要求。 众所周知，计算机速度大幅度提高的关键在于并行处理技术的采用和发展并 行处理技术自出现以来，已在电力行业中体现出广阔的应用前景，尤其近年来出现 的集群系统是实现并行计算的一种新主流技术，随着高性能价格比的可扩展集群式 计算机研究的逐步成熟及应用，为也更多的科研人员进行电力系统并行计算的研究 提供了物质基础，基于集群系统的大规模电力系统并行计算和分布式仿真已成为可 能。在这种情况下，更加高效的无功电压优化并行算法的研究已成为大规模电力系 统计算与控制的关键，其在计算速度上的优势，必将为等级电压控制在电力系统中 的实施打下坚实的基础 重庆大学硕士学位论文1 绪论 1 4 无功优化并行计算的研究现状 当前，许多学者已经意识到研究实时无功优化并行算法的重要性和迫切性，并 且做了大量研究工作，提出了一些初步的方案。不过这些研究多集中在基于人工智 能方法的并行算法研究，如：遗传算法、粒子群优化算法等，这类算法均具有内在的 并行性，利用这一特点可将不同迭代步的计算任务在同一时刻在不同处理器上同步 进行，必然使算法收敛速度得到提高【舢习但是，这类算法也存在着很多不足： ( 1 ) 人工智能算法本身执行速度较慢，虽然采用并行处理方式，但仍不能产生 质的飞跃，而且伴随着电网规模的增大，这情况将更为严重 ( 2 ) 没有结合电力系统本身分布式的特点。电力系统本身是高度分散、分布的， 这决定了电力系统的运行优化也是高度分散、分布的目前的算法如遗传算法虽存 在本质上的并行性，但并行计算不应只是简单的计算任务的多机分配，而应结合电 力系统的特性，从建立模型出发，实现资源和任务的分布式并行处理 ( 3 ) 不符合电网分区运行的特点电力系统存在着自然分区，各分区只了解自 己区内的模型和数据，而对其它分区则没有必要详细了解。目前的并行算法只是计 算任务上的简单分配，需要至少有一台主机了解全网的数学模型和详细数据，这在 实践上不可行 现在，人们又将目光放在了粗粒度并行算法上，优先考虑电网本身分布式的特 点，争取更大程度上提高算法的并行度。不过目前这方面的研究还不多，远没到达 工程实际应用的要求。基于以上原因，对无功优化并行算法的研究还应该进一步深 入和扩大，这也是本文的研究目的所在。 1 5 本文的主要工作 等级电压控制的出现将极大地提高了电力系统的安全稳定性和经济性，而无功 电压优化作为等级电压控制中极为关键的一环，也使得现有的无功电压优化算法面 临着新的挑战如何提高无功优化算法的实时性、实用性已成为研究的重要课题。 本文从并行计算这一角度出发，对无功优化并行算法的实现进行了深入的研究和分 析，所做的主要工作如下： ( 1 ) 在广泛收集资料的基础上，总结分析目前国内外的无功优化方法，并深入 探讨无功优化算法的并行机理，从粗粒度方面来实现无功电压优化的并行计算，有 效提高无功优化速度； ( 2 ) 研究分析辅助问题原理的基本知识，并将其运用于大电网的分区，同时协 调各子系统之间的耦合影响，实现真正意义上的并行独立计算： ( 3 ) 建立无功优化并行计算的数学模型，并运用p c 集群技术，为无功优化并 行计算提供一个既经济且易于组建的物理平台： 6 重庆大学硕士学位论文i 绪论 ( 4 3 深入探讨多平衡节点处理、离散变量处理以及约束条件处理等问题，使得 算法更具实用价值： ( 5 ) 采用1 e e e 标准算例进行分析，验证算法的有效性和可行性，为工程上的 实时在线应用提供有价值的参考 7 重庆大学硕士学位论文 2 无功优化并行计算的研究基础 2 无功优化并行计算的研究基础 2 1 并行计算理论基础 2 1 1 并行化概述 并行处理是指在同一时刻和同一时间间隔内进行多个数的操作，为并行处理而 设计的计算机称为并行计算机按结构它可分为两类：单指令多数据流( s i m d ) 计 算机和多指令多数据流( m i m d ) 计算机1 3 3 1 。用并行计算机求解问题的过程称为并 行计算 并行计算机的发展，基于人们在两方面的认识：第一，单机性能不可能满足大 规模科学与工程问题的计算需求，而并行计算机是实现高性能计算、解决挑战性计 算问题的唯一途径；第二，同时性和并行性是物质世界的一种普遍属性，具有实际 物理背景的计算问题在许多情况下都可以划分成能够并行计算的多个子任务。针对 某一具体应用问题，我们可以利用它们内部的并行性，设计并行算法，将其分解成 为互相独立但彼此又有一定联系的若干个子问题，分别交给各台处理机，然后由所 有的处理机按并行算法完成初始应用问题的求解。 实现或提高计算机系统的并行性，可以通过时间重叠、资源重复和资源共享等 技术途径来实现网。 时间重叠( t u n es u p e r p o s i t i o n ) 是在并行性概念中引入时间因素，让多个处理 过程在时间上相互错开，轮流重叠的使用同一套硬件设备的各个部分，以加快硬件 周转而赢得速度。 资源重复( r e s o u r c er e p l i c a t i o n ) 是在并行概念中引入空间因素，通过重复设 置硬件资源来提高可靠性或并行性能。在结构上，采用多操作部件和多存储部件， 早期受限于硬件价格，资源重复是以提高可靠性为主，随着硬件价格的减低，资源 重复利用被大量用于提高系统的速度性能，成为提高并行性的一个重要方法。 资源共享( r e s o u r c es h a r i n g ) 是按时间顺序轮流地使用同一套资源，包括c p u 、 主存、外设硬件资源和软件、信息资源，以提高其利用率，从而提高整个系统的性 能。 并行处理技术自出现以来，已显示出广阔的应用前景。目前，并行技术主要用 于有大规模、高性能计算的应用领域。其具有以下几个特点： ( 1 ) 问题求解能力增强：分布式系统使得各解题予节点拥有各自的知识、数 据，概念清晰，设计简化、灵活，整个系统解题能力提高。 ( 2 ) 问题求解效率高：系统中各节点同时并发地求解问题，可开发任务中的 并发性，提高求解效率。处理子节点可置于数据采集和被控对象附近，减少数据输 l 重庆大学硕士学位论文2 无功优化并行计算的研究基础 送量和传输延迟，加快系统响应速度，达到实时性要求 ( 3 ) 降低系统开发成本：整个任务分解为多个较专门的子任务分布到子节点 上，降低了子节点的软件复杂度，各节点进行高层次的信息通信协作，同时采取计 算负荷平衡策略，大大地降低了对通信带宽的要求。 2 1 2 物理问题的并行求解过程 一个物理问题并行求解的最终目的是将该问题映射到并行机或分布式计算网 络上，而映射过程是通过不同层次上的抽象来实现的。一般的映射模型如图2 1 所 示 3 s l 。 图2 1 并行求解过程图 f i g 2 1t h ed i a g r a mo f p a r a l l e ls o l u t i o np r o c e d m 2 1 3 并行计算的性能度量 对于一个给定问题，如果设计了一个新的并行算法，就必须对该算法的性能进 行评价。性能度量的目的就是为并行算法的设计与分析提供一个统一的衡量标准。 在当前并行计算环境中，并行算法的性能度量一般涉及到求解问题的规模与分类、 具体并行机的性能、影响算法的关键因素、并行算法评价准则等方面的问题。本节 主要介绍度量并行算法性能的一些基本概念 ( 1 ) 运行时间冈并行算法的运行时间是指算法在并行计算机上求解一个问 题所需的时间。即表示从算法开始执行到执行结束的这一段时间。如果多个处理机 不能同时开始或同时结束时，则算法的运行时间定义为：从最早开始执行的处理机 开始执行时算起直到最后一台处理机执行完成所经过的时间在计算机上实现一种 9 重庆大学硕士学位论文2 无功优化并行计算的研究基础 算法之前，通常需要对其运行时间进行理论分析。对并行算法运行时间的分析包括 估计它在最坏情况下的计算时间和通信时间，其中的计算时间是用算法所需执行的 基本操作次数或步数表示，通信时间则是根据计算得到的通信次数和每步的通信量， 依据并行计算模型计算得到。理论分析得到的算法运行时间常表示为输入问题规模 的函数。 c 2 ) 并行度与粒度1 3 7 】。算法的并行度d o p 是指该算法中可并行执行的操作数。 若处理机资源无限，则算法的并行度也可以理解为可以利用来作并行运算的处理机 台数。然而很少有并行算法能在整个算法执行过程中保持并行度不变，所以更准确 的说法还应该加上时间范围的限制，即在某时间范围内的并行度。 从直观意义上可以说，并行度是刻画一个并行算法的“并行程度”的量，它反 映了软件并行性与硬件并行性匹配的程度。显然，与算法并行度有关的概念是粒度。 一般而言，大的粒度意味着能独立并行执行的是大任务，算法的并行度小；小的粒 度意味着能独立并行执行的是小任务，算法的并行度大 ( 3 ) 加速比和效率加速比和效率是最传统的并行算法评价标准，它们体现 了在并行机上运用并行算法求解实际问题所能获得的好处。 并行算法的加速比定义为口研： 昂= 互耳 式中：五为最优串行算法在单处理机上的运行时间；乃为并行算法使用p 台处 理机的计算时间 并行算法的效率定义为： e p = s p p 式中：p 为处理机台数。 c 4 ) 可扩展性。可扩展性是设计高性能并行计算机和并行算法所追求的另一 个重要目标由于并行系统的性能与系统规模、问题规模、算法内在并行性以及由 于通信、同步和进程创建等引起的系统开销等因素有关，而这些因素对并行系统的 结构和应用程序的可扩展性都有影响，因此可扩展性也是衡量并行系统性能的一个 重要度量指标。 2 2 并行计算在电力系统中的应用 并行计算自出现以来，已在各个领域得到了广泛的应用，在电力行业也不例外。 目前，电力系统中的潮流计算、暂态稳定分析等学科都已经运用了并行计算技术， 并且取得了一定进展，显示出了并行计算的强大生命力它们的并行机理也为并行 计算在无功优化中的应用起到一定的借鉴作用 1 0 重庆大学硕士学位论文2 无功优化并行计算的研究基础 2 2 1 潮流计算中的应用 潮流计算分析是电力系统规划和运行的基础近年来，潮流问题的并行计算已 取得了长足的发展由于电力系统潮流计算问题通常演化为求解一组稀疏线性代数 方程 3 9 1 ，因此，潮流并行算法的研究也主要集中在稀疏线性方程组的并行求解上， 根据其实现方案的不同，主要有4 类：分块法h q 、多重因子化法h ”、稀疏矢量法【蜘 和逆矩阵法【4 3 】。 基于分块思想的潮流并行算法起源于g k r o n 在上世纪5 0 年代提出的分割理论， 其将表征电力系统网络特性的系数矩阵a 分为通过协调部分互联的多个子矩阵，各 子矩阵可独立求解，从而开发潮流求解的并行性。而潮流并行计算的多重因子化法、 稀疏矢量法和逆矩阵法都是从线性方程组的因子分解和前代回代过程入手来实现其 并行化。 ( 1 ) 基于分块法的潮流并行算法 电力系统潮流的分块并行算法提出于1 9 9 2 年。其基本思想是通过合理的节点 排序策略，将系统的系数矩阵转化为对角加边形式这样，稀疏线性方程组的计算 转换为子系统和协调系统计算两部分，各子系统方程可并行求解。该算法物理意义 明确，程序实现简单，适合于在计算结点数较少，分布存储的并行机上实现。但如 何有效地将系数矩阵转化为各子系统计算量平衡的对角加边形式是本算法的难点 ( 2 ) 基于多重因子化的潮流并行算法 为进一步在潮流线性方程组求解中增大并行度，人们提出了多重因子化的概 念，对原有的l u 矩阵进行连续变换，交换后的矩阵计算中上、下部分矩阵的依存 关系被削弱了，从而增加了并行求解的可能性。该方法特别适合于求解大规模稀疏 代数方程组 ( 3 ) 基于稀疏矢量技术的潮流并行算法 传统的因子分解和前代、回代运算具有严格的依赖关系和由稀疏性所带来的短 向量特性，不易于进行并行求解。稀疏矢量法及其因子表路径法的提出，为探索潮 流的并行算法提供了新的启示这种方法先判断前代、回代运算中所必需的操作， 然后找出运算过程中的因子表路径，以便区分计算操作中的可并行部分。但是这类 算法均为开发元素操作级的并行算法，不适合在消息传递机制的多处理器并行机上 实现 ( 4 ) 基于逆矩阵计算的潮流并行算法( w 矩阵法) w 矩阵方法和稀疏矢量直接法一样是潮流稀疏线性方程组并行计算的主流。它 们各有其优势和不足；稀疏矢量法，能够保持因子表的稀疏性，但操作间依赖关系 较强；w 矩阵法并行性较好，但逆矩阵的使用大大增加了矩阵中的非零元，增加了 计算量因此，要想提高潮流问题求解的并行效率还在于把稀疏矢量直接法和w 矩 重庆大学硕士学位论文2 无功优化并行计算的研究基础 阵方法结合起来 2 2 2 暂态稳定分析中的应用 暂态稳定计算是电力系统分析研究的有力工具，具有计算强度大、时间长的特 点为了实现大规模电力系统的暂态过程实时仿真，人们已经对这方面的并行计算 做了大量研究，并取得了一定的成果。其中空间并行、波形松弛和时空并行三类算 法的研究最为广泛嗍 ( 1 ) 空间并行暂稳算法【4 5 】 这类算法中，有基于微分代数方程联立求解的，也有基于交替求解的，但本质 上都是复线性方程组的并行求解。由于其块对角形式比潮流方程更加显著，维数也 大大提高，许多算法运用了传统的迭代方法，如g u a s s - j a c o b i 、g u a s s - s e i d e l 、s o r 等。其成败关键在于如何将系统网络分成相互问具有较少联系且计算量均衡的子系 统。 ( 2 ) 波形松弛暂稳算法闱 波形松弛法是一种求解微分代数方程的数值积分方法，它基于求解高阶代数方 程组的嘶- - s e i d e l 和g u a s s - - j a c o b i 松弛法。其基本思想是：首先将全系统分为 弱耦合的子系统，各子系统独立求解，并且利用前面的迭代“波形”作为相关其他 子系统的状态变量和其他变量的估计值。这些波形在各子系统问相互传送，而各子 系统则利用有关其他子系统的信息来求解，直至收敛。波形松弛法是任务或程序级 上的并行，它并不直接强调任务的分配，而是注重算法的内在并行性，因此它比串 行算法直接并行化改造更有效。 ( 3 ) 时空并行暂稳算法1 4 7 l 时空并行暂稳算法针主要从离散后的非线性代数方程入手，在多个时间点上并 行求解系统动态过程这样能够极大程度上挖掘出暂态稳定问题本身的并行性。而 它的引入也使暂稳计算具备了高度的时间并行性 可以看出，并行处理技术在暂态稳定计算中的运用，大大缩短了仿真时间，也 为我们进一步认识和利用电力系统的特性，开发更多的优化算法提供了广阔的空间， 特别是暂态稳定并行计算中的分区、多时步、异步、多重网格等关键技术，为我们 研究各种无功优化并行算法提供了很好的借鉴作用。 2 3 辅助问题原理 辅助问题原理能够将一个大的优化问题( 包括极小值问题、鞍点问题等) 分解 成一系列子问题加以解决。1 9 8 0 年，c o h e n 第一次将前人的分解协调法加以归纳、 整理，并进一步推广和概括化，得到了辅助问题原理嗍。辅助问题原理出现以来， 许多学者为它的推广、应用做了大量的研究 重庆大学硕士学位论文2 无功优化并行计算的研究基础 在电力系统的应用中，j b a t u t 与a r e n a u d 于1 9 9 2 年首次将辅助问题原理应用 于日发电计划优化问题，在电网分区前，首先通过变量复制与分解，将优化问题的 可行域分解成笛卡儿积的可行子域，然后将原来的大系统优化问题分解成一些仅靠 线性等式约束联系在一起的子问题，最后，对新的问题应用辅助问题原理加以解决。 这种采用辅助问题原理的分解理念，为我们将大系统分解和并行求解提供了理论依 据，也为以后的分布式无功优化计算奠定了基础。 辅助问题原理的具体算法所包含的情况十分复杂，根据求解问题的需要，本文 对辅助问题原理的研究重点放在如何将原问题进行分解上面，因此，下面仅就对求 解极小值问题和求解鞍点问题进行研究分析。 2 3 1 求解极小值问题 对于主问题( 但) ：n 蜘“0 ) + j 2 ( ”) 构造一辅助问题： m 抑( g ( 扯) + 2 ) ( 2 1 ) 可以证明若存在解“使得当g ，( ”) = 叫( ”+ ) 时，则”也为m p 的解。因此可以 构造g 7 ：扰i - 4 五 ) + 恰好满足g ”妒) = 叫u ) 其中g 7 ) 称 为辅助函数，k ( ) 为核函数， 代表数量积 故有以下算法( a p p ) ： ( 1 ) 选择“o e u ，令七= o ( 2 ) 解辅助问题( a p ) ”“1 = a r g m i n k ( u ) + + e d 2 ) ( 2 2 ) w 4 t ! ( 3 ) 当恤一“1 l 小于一指定阈值时停止，否则转( 2 ) 。 这里以 ) 要求强凸可微，且具有l i p s c h i t z 连续；而以( ) 只要求为凸函数且下 半连续。 2 3 2 求解鞍点问题 求解问题： 蜘 以 ) + 以似) ，s t b ( u ) ；o ( 2 3 ) 其* j l ( u ) 为凸函数，以( 1 ，) 不一定可微；u 7 为闭凸区间，包括等式约束和不 等式约束