电力系统优化规划2-智能优化算法I-遗传算法.ppt

电力系统优化规划2-智能优化算法I-遗传算法.ppt

《电力系统优化规划2-智能优化算法I-遗传算法.ppt》由会员分享，可在线阅读，更多相关《电力系统优化规划2-智能优化算法I-遗传算法.ppt（56页珍藏版）》请在冰点文库上搜索。

电力系统规划中的智能优化算法,智能优化算法,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。

这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。

常用的智能优化算法,遗传算法（GeneticAlgorithm，简称GA）模拟退火算法（SimulatedAnnealing，简称SA）禁忌搜索算法（TabuSearch，简称TS）群体智能优化算法蚁群鱼群粒子群,智能优化算法的特点,它们的共同特点：

都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。

由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。

遗传算法起源,遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

遗传算法,进化过程,优化过程,生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过”“优胜劣汰”及遗传变异来达到进化（优化）目的的。

遗传算法,生物的进化机制,自然选择适应环境的个体具有更高的生存能力，同时染色体特征被保留下来杂交随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体突变随机改变父代的染色体基因结构，产生新染色体,2、基本遗传算法,基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

基本遗传算法的组成,

（1）编码（产生初始种群）

（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数,编码,GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。

正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。

SGA使用二进制串进行编码。

函数优化示例,求下列一元函数的最大值：

x-1,2，求解结果精确到6位小数。

SGA对于本例的编码,由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。

又因为2213106222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。

几个术语,基因型：

1000101110110101000111,表现型：

0.637197,编码,解码,个体（染色体）,基因,初始种群,SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。

初始种群中个体的数量称为种群规模。

适应度函数,遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。

适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。

选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：

适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。

选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。

SGA中选择算子采用轮盘赌选择方法。

轮盘赌选择方法,轮盘赌选择又称比例选择算子，它的基本思想是：

各个个体被选中的概率与其适应度函数值大小成正比。

设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：

轮盘赌选择方法的实现步骤,

（1）计算群体中所有个体的适应度函数值（需要解码）；

（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。

轮盘选择的原理：

图中指针固定不动，外圈的圆环可以自由转动，圆环上的刻度代表各个个体的适应度。

当圆环旋转若干圈后停止，指针指定的位置便是被选中的个体。

从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中。

交叉算子,所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。

交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。

SGA中交叉算子采用单点交叉算子。

单点交叉运算,交叉前：

00000|0111000000001000011100|00000111111000101交叉后：

00000|0000011111100010111100|01110000000010000,交叉点,变异算子,所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。

遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。

交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。

SGA中变异算子采用基本位变异算子。

基本位变异算子,基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。

对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。

基本位变异算子的执行过程,变异前：

000001110000000010000变异后：

000001110001000010000,变异点,运行参数,

（1）M：

种群规模

（2）T：

遗传运算的终止进化代数（3）Pc：

交叉概率（4）Pm：

变异概率,SGA的框图,3、遗传算法的特点,

（1）群体搜索，易于并行化处理；

（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。

2.3基本遗传算法应用举例基本遗传算法在函数优化中的应用。

例Rosenbrock函数的全局最大值计算。

maxf（x1,x2）=100（x12-x22）2+（1-x1）2s.t.-2.048xi2.048（xi=1,2）,如图所示：

该函数有两个局部极大点，分别是:

f（2.048,-2048）=3897.7342和f（-2.048,-2.0048）=3905.9262其中后者为全局最大点。

下面介绍求解该问题的遗传算法的构造过程：

第一步：

确定决策变量及其约束条件。

s.t.-2.048xi2.048（xi=1,2）第二步：

建立优化模型。

maxf（x1,x2）=100（x12-x22）2+（1-x1）2第三步；确定编码方法。

用长度为l0位的二进制编码串来分别表示二个决策变量x1,x2。

lO位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。

从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000（0）到1111111111（1023）之间的二进制编码。

再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。

例如X：

00001101111101110001就表示一个个体的基因型。

第四步：

确定解码方法。

解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。

依据前述个体编码方法相对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：

例如，对前述个体X：

00001101111101110001它由这样的两个代码所组成：

y1=55y2=881经上式的解码处理后，得到：

x1=-1.828x2=1.476,第五步：

确定个体评价方法。

由式f（x1,x2）=100（x12-x22）2+（1-x1）2可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：

F（x）=f（x1,x2）第六步：

设计遗传算子。

选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。

第七步：

确定遗传算法的运行参数。

对于本例，设定基本遗传算法的运行参数如下：

群体大小:

M80终止代数:

T200交叉概率：

pc0.6变异概率：

pm0.001,下图为其进化过程示例及运行结果。

图中两条曲线分别为各代群体中个体适应度的最大值和平均值。

（a）,下图所示分别为初始群体、第5代群体、第10代群体和第100代群体中个体的分布情况。

在图（a）中各个个体分布得比较均匀。

在图（b）中大量的个体分布在最优点和次最优点附近。

（b）,从图（c）中可以看出，次最优点也被淘汰。

（c）,从图（d）中可以看出，个体更加集中在最优点附近。

（d）,由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。

遗传算法的收敛性分析,遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。

与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。

种群规模对收敛性的影响,通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。

选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。

如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。

交叉概率对收敛性的影响,交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。

交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。

变异概率对收敛性的影响,变异操作是对种群模式的扰动，有利于增加种群的多样性。

但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。

遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。

通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。

3、遗传算法的改进,遗传欺骗问题：

在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。

遗传算法的改进途径,

（1）对编码方式的改进

（2）对遗传算子的改进（3）对控制参数的改进（4）对执行策略的改进,对编码方式的改进,二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。

格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。

对遗传算子的改进,排序选择均匀交叉逆序变异,

（1）对群体中的所有个体按其适应度大小进行降序排序；

（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。

对遗传算子的改进,排序选择均匀交叉逆序变异,

（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；

（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：

若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。

对遗传算子的改进,排序选择均匀交叉逆序变异,变异前：

348|7965|21变异前：

348|5697|21,对控制参数的改进,Schaffer建议的最优参数范围是：

M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

对控制参数的改进,Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰。

对执行策略的改进,混合遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法,