基于进化算法的水火电力系统联合优化调度求解设计

基于进化算法的水火电力系统联合优化调度求解设计张景瑞2013-6-27第一页，共八十四页。成绩说明课堂小设计20%求解设计60%答辩20%第二页，共八十四页。提纲解题优化问题基本概念优化问题传统解法及其弊端基于智能进化算法的解决方案课堂小设计水火联调问题描述基于进化算法的水火联调解决方案求解设计第三页，共八十四页。解题

建模与仿真优化调度水火电力系统联合优化调度智能进化算法基于进化算法的水火联合优化调度第四页，共八十四页。优化问题优化问题，亦称最优化问题。最优化问题，主要是指以下形式的问题：给定一个函数，寻找一个元素使得对于所有A中的，（最小化）；或者（最大化）。这类定式有时还称为“数学规划”（譬如，线性规划）。许多现实和理论问题都可以建模成这样的一般性框架。最优化，是应用数学的一个分支。典型的，A一般为欧几里德空间中的子集，通常由一个A必须满足的约束等式或者不等式来规定。A的元素被称为是可行解。函数f被称为目标函数，或者费用函数。一个最小化（或者最大化）目标函数的可行解被称为最优解。第五页，共八十四页。如图所示，如何截取x使铁皮所围成的容积最大？xa第六页，共八十四页。1.

食谱问题某人每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素单位奶中含量单位蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。第七页，共八十四页。1.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：优化工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解第八页，共八十四页。2

运输问题设某种物资有m个产地A1,A2,…Am,各产地的产量是a1,a2,…,am;有n个销地B1,B2,…,Bn.各销地的销量是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。第九页，共八十四页。令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2

运输问题（续）第十页，共八十四页。设某电力系统由3个电站组成，三电站共同向同一母线供电300MW电站i单位MW出力煤耗成本为fi(Pi)元，求最小成本的电站负荷分配fi(Pi)为Pi（出力）的二次多项式函数3

经济调度问题第十一页，共八十四页。某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？

设备产品ABCD利润（元）

甲21402

乙22043

有效台时12816124

生产计划问题第十二页，共八十四页。解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第十三页，共八十四页。优化问题小结在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.上述问题的异同第十四页，共八十四页。优化问题小结最优化问题可写成如下形式:第十五页，共八十四页。优化问题小结Df1.1

设f(x)为目标函数，S为可行域，x0S,若对每一个xS,成立f(x)f(x0),则称x0为极小化问题min

f(x),xS的最优解（整体最优解）则称x0为极小化问题min

f(x),xS的局部最优解Df1.2设f(x)为目标函数，S为可行域，第十六页，共八十四页。优化问题传统解法及其弊端费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=0欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m第十七页，共八十四页。以经济负荷分配问题为例第十八页，共八十四页。第十九页，共八十四页。第二十页，共八十四页。第二十一页，共八十四页。等微增率准则图2‑2输入-输出特性第二十二页，共八十四页。第二十三页，共八十四页。第二十四页，共八十四页。第二十五页，共八十四页。第二十六页，共八十四页。Lambda迭代法等微增率准则是进行经济负荷分配的最基本的准则，然而它更适合于理论分析，而Lambda迭代法是适合计算机求解的负荷最优分配方法。下面将详细介绍Lambda迭代法求解经济负荷分配问题的原理与步骤。第二十七页，共八十四页。图2‑5经济负荷分配图示求解法第二十八页，共八十四页。Lambda调整方法第二十九页，共八十四页。Lambda迭代法经济调度流程第三十页，共八十四页。第三十一页，共八十四页。第三十二页，共八十四页。第三十三页，共八十四页。基于进化算法的求解方案

--以粒子群算法为例粒子群算法产生背景粒子群算法由来粒子群算法基本原理第三十四页，共八十四页。粒子群算法介绍设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。第三十五页，共八十四页。算法介绍第三十六页，共八十四页。粒子群算法介绍

抽象：鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)．每个粒子都有一个由目标函数决定的适应值(fitnessvalue)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi．这个可以看作是粒子自己的飞行经验．除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)．这个可以看作是粒子同伴的经验．粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

第三十七页，共八十四页。基本粒子群算法(1)式(2)式在式(1)、(2)中，i＝1，2，…，M，M是该群体中粒子的总数PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest,gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。第三十八页，共八十四页。基本粒子群算法Vi是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi是粒子的当前位置。c1和c2是学习因子，通常取c1＝c2＝2在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的Vmax

，那么这一维的速度就被限定为Vmax

。（Vmax>0）以上面两个公式为基础，形成了后来PSO的基本形式第三十九页，共八十四页。基本粒子群算法从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了后来PSO的标准形式第四十页，共八十四页。标准粒子群算法1998年shi等人在进化计算的国际会议上发表了一篇论文《Amodifiedparticleswarmoptimizer》对前面的公式(1)进行了修正。引入惯性权重因子。（3）式非负，称为惯性因子。公式(2)和(3)被视为标准pso算法。第四十一页，共八十四页。标准粒子群算法Gk为最大进化代数，ini为初始惯性权值，

end为迭代至最大代数时惯性权值。典型取值

ini＝0.9，end＝0.4。的引入使PSO算法性能有了很大提高，针对不同的搜索问题，可以调整全局和局部搜索能力，也使得PSO算法能成功的应用于很多实际问题。第四十二页，共八十四页。标准粒子群算法

值较大，全局寻优能力强，局部寻优能力弱；值较小反之。初始时，shi将取为常数，后来实验发现，动态能够获得比固定值更好的寻优结果。动态可以在PSO搜索过程中线性变化，也可根据PSO性能的某个测度函数动态改变。目前，采用较多的是shi建议的线性递减权值(linearlydecreasingweight,LDW)策略。第四十三页，共八十四页。粒子群算法求解流程标准PSO算法的流程：Step1:初始化一群微粒(群体规模为m)，包括随机位置和速度；Step2:评价每个微粒的适应度；Step3:对每个微粒，将其适应值与其经过的最好位置

pbest作比较，如果较好，则将其作为当前的最好位置pbest;Step4:对每个微粒，将其适应值与其经过的最好位置

gbest作比较，如果较好，则将其作为当前的最好位置gbest;Step5:根据(2)、(3)式调整微粒速度和位置；Step6：未达到结束条件则转Step2。第四十四页，共八十四页。粒子群算法求解流程迭代终止条件根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。第四十五页，共八十四页。全局PSO与局部PSO算法方程(2)和(3)中pbest和gbest分别表示微粒群的局部和全局最优位置，当C1＝0时，则粒子没有了认知能力，变为只有社会的模型(social-only):被称为全局PSO算法.粒子有扩展搜索空间的能力，具有较快的收敛速度，但由于缺少局部搜索，对于复杂问题比标准PSO更易陷入局部最优。第四十六页，共八十四页。全局PSO与局部PSO算法当C2＝0时，则粒子之间没有社会信息，模型变为只有认知(cognition-only)模型：被称为局部PSO算法。由于个体之间没有信息的交流，整个群体相当于多个粒子进行盲目的随机搜索，收敛速度慢，因而得到最优解的可能性小。第四十七页，共八十四页。参数分析参数有：群体规模m，惯性因子，学习因子c1和c2最大速度Vmax，迭代次数Gk。群体规模m一般取20～40，对较难或特定类别的问题可以取到100～200。最大速度Vmax决定当前位置与最好位置之间的区域的分辨率(或精度)。如果太快，则粒子有可能越过极小点;如果太慢，则粒子不能在局部极小点之外进行足够的探索，会陷入到局部极值区域内。这种限制可以达到防止计算溢出、决定问题空间搜索的粒度的目的。第四十八页，共八十四页。参数分析权重因子包括惯性因子和学习因子c1和c2。使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。C1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。第四十九页，共八十四页。参数分析参数设置：如果令c1＝c2＝0，粒子将一直以当前速度的飞行，直到边界。很难找到最优解。如果＝0，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得w的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。较大时，具有较强的全局搜索能力；较小时，具有较强的局部搜索能力。第五十页，共八十四页。参数分析通常设c1＝c2＝2。Suganthan的实验表明：c1和c2为常数时可以得到较好的解，但不一定必须等于2。Clerc引入收敛因子(constrictionfactor)K来保证收敛性。其中第五十一页，共八十四页。参数分析通常取为4.1,则K＝0.729.实验表明，与使用惯性权重的PSO算法相比，使用收敛因子的PSO有更快的收敛速度。其实只要恰当的选取和c1、c2，两种算法是一样的。因此使用收敛因子的PSO可以看作使用惯性权重PSO的特例。恰当的选取算法的参数值可以改善算法的性能。第五十二页，共八十四页。优化问题的计算机解法一般步骤第五十三页，共八十四页。课堂小问题求解设计（1）用基本粒子群算法求解：第五十四页，共八十四页。课堂小问题求解设计（2）用标准粒子群算法求解：第五十五页，共八十四页。课堂小问题求解设计（3）用标准粒子群算法求解前述经济负荷分配问题，并与Lambda迭代法比较第五十六页，共八十四页。第五十七页，共八十四页。课堂作业回顾第五十八页，共八十四页。无约束优化问题求解关键步骤明确速度、位置、适应值明确粒子、个体最好、全局最好明确粒子飞行速度更新方式明确适应值计算方法明确速度、位置越界处理方法明确个体最好和全局最好更新方法明确迭代结束条件确定决策变量和适应值第五十九页，共八十四页。约束优化问题第六十页，共八十四页。1.

食谱问题某人每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素单位奶中含量单位蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。第六十一页，共八十四页。1.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：优化工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解第六十二页，共八十四页。2

运输问题设某种物资有m个产地A1,A2,…Am,各产地的产量是a1,a2,…,am;有n个销地B1,B2,…,Bn.各销地的销量是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。第六十三页，共八十四页。令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2

运输问题（续）第六十四页，共八十四页。设某电力系统由3个电站组成，三电站共同向同一母线供电300MW电站i单位MW出力煤耗成本为fi(Pi)元，求最小成本的电站负荷分配fi(Pi)为Pi（出力）的二次多项式函数3

经济调度问题第六十五页，共八十四页。某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？

设备产品ABCD利润（元）

甲21402

乙22043

有效台时12816124

生产计划问题第六十六页，共八十四页。解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12第六十七页，共八十四页。优化方法约束优化->无约束优化约束处理办法-罚函数法直接罚函数法二次罚函数法。。。第六十八页，共八十四页。小作业第六十九页，共八十四页。小作业第七十页，共八十四页。小作业第七十一页，共八十四页。水火电力系统联合优化问题描述水火电力系统优化调度是电力系统经济调度中普遍存在的重要优化问题，其短期优化调度是指一段时期内（多为一天）在满足水、火电各种复杂约束条件的情况下，合理确定各电站的调度方案使整个系统运行费用最小。第七十二页，共八十四页。问题描述水力联系上游泄流量为下游入库流量的组成部分水库库容约束库区防洪、供水等机组物理特性额定流量、额定出力、最小技术出力等负荷约束电量平衡泄流量约束下游防洪、灌溉、航运等第七十三页，共八十四页。优化模型总成本火电发电量火电耗量函数库容上限库容下限发电流量下限发电流量上限区间径流弃水量上游电站集合水流时滞泄流量下限泄流量上限第七十四页，共八十四页。优化模型火电时段电量下限火电时段电量上限水电时段电量下限水电时段电量上限负荷需求网损期初库容期末库容第七十五页，共八十四页。优化模型时段初库容发电流量火电电量火电量发电量最小值第七十六页，共八十四页。优化方法由于水、火电子系统间存在电力联系，水电子系统内部存在复杂的水力联系和综合利用要求，其发电优化调度实际上是一个高维、非线性强约束优化问题。为求解此类问题，国内外研究者提出了不同的求解方法，如交互式多目标决策法、动态规划法，网络流法，非线性优化，线性优化，分解协调法等。这些方法取得了一定的效果，但在处理约束时大都作些不合实际的假设。只有动态规化法虽可以方便处理复杂约束条件但易出现“维数灾”问题。近年来出现的智能进化算法(如遗传算法、差分进化、微粒群算法等)由于其不要求目标函数连续可微，且灵活、易于扩展、鲁棒性好等优点被应用于水火电力系统优化中，其中