第六章-约束优化方法ppt课件.ppt

第六章约束优化方法,6.1 概 述,6.2 随机方向法,6.3 复合形方法,6.4 可行方向法,6.5 惩罚函数法,6.6 增广乘子法,6.7 遗 传优化 算 法,机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为,6.1 概述,6.1 概述,直接解法：随机方向搜索法、复合形法、可行方向法 间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法,一.有约束问题解法分类：,二.直接解法的基本思想：,合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭代，收敛至最优点。xk+1=xk+kdkdk:可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下 降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题,6.1 概述,特点：由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点;若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。,凸可行域,非凸可行域,6.1 概述,原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的 目标函数(x,r1,r2)，成为无约束优化问题。通 过不断调整加权因子，产生一系列函数的极小点 序列 x(k)*(r1(k),r2(k)k=0,1,2，逐渐收敛到原目标 函数的约束最优解。,其中：新目标函数：,三.间接解法的基本思想：,惩罚因子：r1,r2,6.2 随机方向法,一.基本思想：,随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：新迭代点在可行域中 目标函数值的下降性。,x(0),x(L),x(1),x*,二.初始点的选择,随机方向法的初始点x0必须是一个可行点，既满足全部 不等式约束条件。,初始点可以通过随机选择的方法产生。,1）输入设计变量的下限值和上限值，即,2）在区间（0，1）内产生n个伪随机数,3）计算随机点x的各分量,4）判别随机点x是否可行，若随机点可行，用x0 x 为初始点；若非可行点，转到步骤2）重新产生随 机点，直到可行为止。,6.2 随机方向法,三.可行搜索方向的产生,从k个随机方向中，选取一个较好的方向。,2)取一试验步长a0，按下式计算k个随机点,6.2 随机方向法,3）检验k个随机点是否为可行点，除去非可行点，计算 余下的可行点的目标函数值，比较其大小，选出目标 函数最小的点xL。,4)比较xL 和x0两点的目标函数值:若f(xL)f(x0)，则 取xL 和x0连线方向为可行搜索方向；若f(xL)f(x0)，则缩小步长0，转步骤1）重新计算，直至f(xL)f(x0)为止。0 缩小到很小仍然找不到一个xL，使 f(xL)f(x0),则 说明x0是一个局部极小点，更换初始点转步骤1）。,6.2 随机方向法,产生可行搜索方向的条件为：,则可行搜索方向为：,四、搜索步长的确定,步长由加速步长法确定：,为步长加速系数，一般取1.3,6.2 随机方向法,五.计算步骤 1)选择一个可行的初始点x0;2)产生k个n维随机单位向量e j(j=1,2,k);3)取试验步长0，计算出k个随机点x j;4)在k个随机点中，找出可行的的随机点xL,产生可行搜索 方向d=xLx0.5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计 算，直到搜索到一个满足全部约束条件，且目标函数值 不再下降的新点x。6)若收敛条件满足，停止迭代。否则，令x0 x转步骤2。,例6-1 求下列约束优化问题的最优解 解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=0.0027 3.0T,f(x*)=3,6.3 复合形法,一.单纯形法：,基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。,二维空间中映射法比较单纯形x(1)x(2)x(3)的顶点，f(x(1)f(x(2)f(x(3),x(1)为最坏点，称为x(H)，通过映射得到新点x(R)，x(R)x(S)a(x(S)-x(H)以x(R)来代替x(H)，组成新的单纯形x(R)x(2)x(3)。其中f(x(R)1；称为映射因子；,X(1)=X(H),X(2),X(3),X(S),X(R)=X(4),X(5),X(6),定义：在n维空间中，由n+1个点组成的图形称单纯形。,X*,除x(H)外，其它顶点的几何中心,二.复合形法：,定义：在n维空间中，由 kn+1 个点组成的多面体称为复合形。,基本思想：,以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。,说明：,单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。,三.迭代方法：,1.映射法：,例：二维空间中，k=4，复合形是四面体 x(1)x(2)x(3)x(4)，计算得：f(x(1)f(x(2)f(x(3)f(x(4),确定最坏点 x(H)=x(4)，次坏点 x(G)=x(3)，最好点x(L)=x(1)。x(S)为除x(H)以外，各点的几何中心。,映射迭代公式：x(R)=x(S)+(x(S)-x(H)搜 索 方 向：沿x(H)x(S)的方向。步长因子（映射系数）：1，建议先取1.3。若求得的x(R)在可行域内，且f(x(R)f(x(H)，则以x(R)代替x(H)组成新复合形，再进行下轮迭代。,X(S),X(R),X(H),变形法一 扩张：若f(x(R)f(x(L)，则扩张失败，以x(R)代替x(H)组成新复合形,X(S),X(R),X(H),X(E),变形法二 收缩：若在映射法中f(x(R)f(x(H),则以a0.5a重复采用映射法 若直至a10-5仍不成功，考虑采用收缩法 取 若f(x(K)f(x(H),则成功，以x(K)代替x(H)组成新复合形。,X(S),X(R),X(H),X(K),4.变形法三 压缩：如采用上述方法均无效，还可以将复合形各顶点向最好点 x(L)靠拢，即采用压缩的方法改变复合形的形状。取,X(L),四.初始复合形的形成：,人工选择初始复合形2.随机产生初始复合形：先在可行域内确定一个初始顶点；确定xi的上下界：ai、bi；产生区间0,1中的k-1组伪随机数ri(j)；产生k-1个顶点，x i(j)=i+ri(j)(bi-ai)检查k-1个顶点的可行性，若有q个顶点满足 约束，求q个顶点的几何中心：以x(q+1)=x(t)+(x(q+1)-x(t),a=0.5 将不满足 约束的顶点移向可行域,若可行域是非凸集，可能失败，需减小上、下界再进行。,步骤：1.形成初始复合形 2.计算各顶点的函数值,找到最坏点x(H)、次坏点x(G)和最好点x(L)3.计算除最坏点外，其余顶点的形心:检查形心是否在可行域内 4.则可行域为非凸集，取 aiminai(L),ai(S),bimaxai(L),ai(S)作为上下界；计算x i(j)=i+ri(j)(bi-ai)，重新构成复合形，转 步骤2 5.计算映射点：x(R)=x(S)+a(x(S)-x(H)检查是否在可行域内,是，a=1.3,转步骤5否，转步骤4,是，转步骤6否，a=0.5a,重新计算反射点,6.计算f(x(R)，若 7.若a:检查终止准则 若,f(x(R)f(x(H)，以x(R)代替x(H)重构复合形后转步骤2f(x(R)f(x(H)，转步骤7,是，则a=0.5a，转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤2,是，则迭代结束，以此复合形的x(L)为x否，则以重构的复合形转步骤2,六.方法评价：,计算简单，不必求导，占内存小；随着维数的增加，效率大大下降；不能解含等式约束的问题；,建议：初始取1.3。n+1 k 2n，当 n 5 时，k取值接近 2n；当 n 5 时，k 取值可小些。,6.4 可行方向法,一.基本思想：,在可行域内选择一个初始点x(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：x(k+1)=x(k)+ad 通过不断的调整可行方向，使迭代点逐步逼近约束最优点。,6.4 可行方向法,二.搜索策略：,根据目标函数和约束函数的不同性态，选择不同的搜索策略。,边界反弹法：第一次搜索为负梯度方向，终止于边 界。以后各次搜索方向均为适用可行方向，以最大 步长从一个边界反弹到另一个边界，直至满足收敛 条件。,x(1),x(2),x(3),x*,x(0),6.4 可行方向法,最优步长法：第一次搜索为负梯度方向，终止于边 界。第二次搜索沿适用可行方向作一维搜索以最优 步长因子求得最优点。反复以上两步，直至得到最 优点x*。,x(1),x(2),x(3),x*,x(0),6.4 可行方向法,贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。,x(1),x(2),x*,x(0),6.4 可行方向法,若约束面是非线性时，从x(k)点沿切线（面）方向d(k)搜索，会进入非可行域。,容差带：,建立约束面的容差带+，从 x(k)出发，沿d(k)方向搜索到 d(k)方向与g(x)+=0 的交点x后，再沿适时约束的负梯度方向返回约束面的x(k+1)点。,x(k),x(k+1),g(x),g(x)+,x,-g(x),d(k),6.4 可行方向法,调整步长因子1：x(k+1)=x-a1g(x)将g(x)在x点泰勒展开，取一阶近似式：g(x)g(x)+g(x)T(x-x)进而得到：g(x(k+1)g(x)+g(x)T-a1g(x)为了让x(k+1)到达约束面，令g(x(k+1)=0得:,6.4 可行方向法,三.可行方向的确定,可行方向应该满足设计点可行及目标函数值下降两个条件 可行条件:gj(xk)T dk 0 j=1,2,J(起作用约束的个数),g(xk),dk,g1(xk),g2(xk),dk,6.4 可行方向法,三.可行方向的确定,目标函数值下降条件:f(xk)T dk 0,f(xk),dk,6.4 可行方向法,三.可行方向的确定,gj(xk)T dk 0 保证在可行域内f(xk)T dk 0 保证目标函数值下降,可行方向,6.4 可行方向法,优选方向法,四.可行方向产生方法,式中：d为求解变量，gj(xk)T、f(xk)T为定值，可用线性规划方法求解,6.4 可行方向法,梯度投影法：可行方向:其中:p为投影算子,J-起作用的约束个数,6.4 可行方向法,取最优步长,五.步长的确定,若x(k+1)为可行点，a作为本次迭代步长,x(k+1)=x(k)+ad,ad,x(k+1),6.4 可行方向法,取最大步长aM,五.步长的确定,ad,aMd,x(k+1),x(k+1)=x(k)+ad,收敛条件,2）设计点xk满足库恩-塔克条件,1）设计点xk及约束允差 满足,例 用可行方向法求约束优化问题的约束最优解。Min f(x1,x2)=x12+2x22-10 x1-x1x2-4x2+60 s.t.g1(x)=x1 0 g2(x)=x2 0 g3(x)=x1 6 0 g4(x)=x2 8 0 g5(x)=x1+x2 11 0 解：取初始点x0=0 1T，为约束 边界g1(x)=0上的一点。第一次迭代用优选方向法确定可行方向。首先计算x0点的目标函数f(x0)和约束函数g1(x0)的梯度,为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=d1 d2T为设计变量的线性规划问题，其数学模型为：,最优方向是d*=0.984 0.179T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。,第一次迭代的可行方向为d0=d*。若步长取0=6.098，则 可见第一次迭代点x1 在约束边界g3(x1)=0上。,第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-f(x1)=0.092 5.818T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上，计算投影算子P本次迭代的可行方向为,显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*则得约束最优解,将有约束的优化问题转化为无约束优化问题来求解。前提：一是不能破坏约束问题的约束条件，二是使它归结到原约束问题的同一最优解上去。,构成一个新的目标函数：,6.5 惩罚函数法,惩罚项,惩罚因子,惩罚函数,从而保证,惩罚项必须具有以下极限性质：,根据惩罚项的不同构成形式，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法,6.5 惩罚函数法,一.内点惩罚函数法,基本思想内点法将新目标函数(x,r)构筑在可行域D内，随着惩罚因子r(k)的不断递减，生成一系列新目标函数(xk,r(k)，在可行域内逐步迭代，产生的极值点xk*(r(k)序列从可行域内部趋向原目标函数的约束最优点 x*。,例：min.f(x)=x s.t.g(x)=1-x 0,X1*,X2*,X*,2.惩罚函数的形式,其中：惩罚（加权）因子 降低系数 c：0 c 1,当x在可行域内远离约束边界时：,当x由可行城内靠近约束边界时：,障碍项,3.几个参数的选择,惩罚因子初始值 r(0)的选择：,过大、过小均不好，建议考虑选择r(0)=1或者：,2.降低系数 c 的选择：,c 的典型值为0.10.7。,3.初始点 x(0)的选择：,要求：在可行域内；不要离约束边界太近。,方法：人工估算，需要校核可行性；计算机随机产生，也需校核可行性。,搜索方法：,任意给出一个初始点；判断其可行性，若违反了S个约束，求出不满足约束中的最大值：,应用优化方法减少违反约束：,以求得的设计点作为新初始点，继续其判断可行性，若仍有不 满足的约束，则重复上述过程，直至初始点可行。,判断是否收敛：,4.步骤：,选取合适的初始点 x(0)，以及 r(0)、c、计算精度 1、2，令 k=0；,构造惩罚（新目标）函数；,调用无约束优化方法，求新目标函数的最优解 xk*和(xk,r(k)；,若均满足，停止迭代，有约束优化问题的最优点为 x*=xk*；若有一个准则不满足，则令 并转入第 3 步，继续计算。,例：用内点法求下列问题的最优解：,构造惩罚函数,1,1,2,二.外点惩罚函数法,1.基本原理外点法将新目标函数(x,r)构筑在可行域 D 外，随着惩罚因子 r(k)的不断递增，生成一系列新目标函数(xk,r(k)，在可行域外逐步迭代，产生的极值点 xk*(r(k)序列从可行域外部趋向原目标函数的约束最优点 x*。,新目标函数：,例：求下述约束优化问题的最优点。min.f(X)=x x R1 s.t g(X)=1-x 0,惩罚函数可取为,2)惩罚因子,1)当设计点在可行域内时,惩罚项为0,不惩罚;当设 计点在可行域外 时,惩罚项大于0,有惩罚作用.,外点法可以用来求解含不等式和等式约束的优化问题。,衰减项,3.几个参数的选择,r(0)的选择:r(0)过大，会使惩罚函数的等值线变形或偏心，求极 值困难。r(0)过小，迭代次数太多。r(0)1或者,x(0)的选择：基本上可以在可行域内外，任意选择。,递增系数c的选择：通常选择 5 10，可根据具体题目，进行试算调整。,内点法特点：（1）初始点必须为严格的可行点（2）不适于具有等式约束的数学模型（3）迭代过程中各个点均为可行设计方案（4）一般收敛较慢（5）初始惩罚因子要选择得当（6）惩罚因子为递减，递减率c有01,三.混合惩罚函数法,1.基本思想,采用内点法和外点法相结合的混合惩罚函数法，以发挥内点法和外点法的特点，处理既有等式约束，又有不等式约束的优化设计问题。,2.惩罚函数的形式,一般既包括障碍项，也包括衰减项。,惩罚函数法优点：原理简单，算法易行，适应范围广，可利用无约束最 优化方法资源。缺点：（1）初始惩罚因子r(0)取值不当可导致惩罚函数变得病态，使无约束优化计算困难。（2）理论上讲，只有惩罚因子 r(k)0（内点法）或 r(k)趋于无穷（外点法）时，算法才收敛，因此序 列迭代过程收敛速度慢。增广乘子法 外点惩罚函数拉格朗日函数 计算过程稳定，计算效率超过惩罚函数法,拉格朗日函数,一、拉格朗日乘子法（升维法）,6.6 增广乘子法,l+n个方程l+n个未知变量,具有相同的最优解X*,例:用拉格朗日乘子法求下列问题的最优解,解 构造拉格朗日函数,令L=0,得到,求解得：,构造拉格朗日函数,构造外点惩罚函数,二.等式约束的增广乘子法,采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态,此法的思路是把两者结合起来。其增广拉格朗日函数为:,等式约束增广乘子法,不论r(k)取何值，增广乘子函数与原函数具有相同的约束极值点X*，与拉格朗日函数有相同的拉格朗日乘子向量。,等式约束增广乘子法,等式约束增广乘子法,增广乘子法中的乘子迭代,等式约束增广乘子法,参数选取,惩罚因子初始值r(0)按照外点法取。,从第二次迭代开始，惩罚因子按下式递增：,惩罚因子递增系数，C=10,判别数，通常取0.25,等式约束增广乘子法计算步骤：选取设计变量的初始点x0，惩罚因子初值r0，增长系数，判别数，收敛精度，乘子向量p0=0(p=1,2,l),迭代次数k=0；构造增广乘子函数M(x,r)，并用无约束方法求 min M(x,r)，得无约束最优解xk=x*(k,rk)计算校正乘子向量如果，迭代终止，约束最优解为x*=xk，*=k+1;否则转步骤6计算惩罚因子 再令k=k+1，转步骤2,例:用拉格朗日乘子法求下列问题的最优解,解 构造增广乘子函数,确定初始参数：C2,0=0,r0=0.1，,利用解析法求min M(X,r)，令 M(X,r)0，可得最优解：,迭代6次得到最优解,迭代结果如下:,精确解:X*=0.25,0.75,f(X*)=0.125,不等式约束增广乘子法,用于求解不等式约束优化问题。,引入松弛变量Zz1,z2,zmT,并且令,则不等式约束优化问题转化为等式优化问题,不等式约束增广乘子法,构造增广乘子函数,由于引入松弛变量Z，使原有的n维极值问题扩充为n+m维问题，计算工作量和求解难度增大，可简化。,不等式约束增广乘子法,同时具有等式和不等式约束的增广乘子法,Powell法、梯度法随机方向法、复合形法、惩罚函数法,常规优化算法,启发式算法(现代优化计算方法),适于求解高非线性、多约束、多极值问题,遗传算法（Genetic algorithms）神经网络优化算法（Neural networks optimization）混合优化算法（Hybrid optimization）,6.7 遗传优化算法,一.背景：,生物进化基本循环图,依据生物进化论的“适者生存”规律而提出：,6.7 遗传优化算法,6.7 遗传优化算法,遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。（2）自然选择规律决定优秀的染色体产生超过平均数的后代。遗传算法通过优化目标构造适应函数以达到好的染色 体超过平均数的后代。（3）染色体结合时，双亲的遗传基因结合使得子女保持父母 的特征。（4）当染色体结合后，随机变异会造成子代与父代不同。,6.7 遗传优化算法,二.基本思想：,遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体 进行结合（选择、交配和变异），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。,例 用遗传算法求min f(x1,x2)=x1+x2，当x1和x2为整数时 的整数解，且,解：若用4位二进制编码表示一个设计变量 xi，则一个 解(x1,x2)需用8位二进制编码表示：,遗传算法4个组成部分：编码和解码、适应函数、遗传算子和控制参数,若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、N3和N4点，其交配方式如下：,通过分别交换基因，实现了交配，得到了4个新个体N1、N2、N3和N4。,若对某个个体（例如N2）进行基因变异（10），可得N2”:0 0 1 0 0 0 0 1(=3),6.7 遗传优化算法,三.算法的基本步骤：,S.1 选择优化问题求解的一种编码；S.2 随机产生N个染色体的初始群体 pop(k),k=0；S.3 对群体中的每个染色体popi(k)计算适应函数 f i=fitness(popi(k)S.4 若满足终止规则，则转向S.9，否则计算概率S.5 以概率 pi 从 pop(k)中随机选一些染色体构成一个新群体（其中可以重复选 pop(k)中的元素）newpop(k+1)=popi(k),i=1,2,N,6.7 遗传优化算法,三.算法的基本步骤：,S.6 通过交配，按交配概率 pc 得到一个有 N 个染色体的交配群体crosspop(k+1)；S.7 以一个较小的变异概率 pm，使得一个染色体的基因发生变异，形成变异群体mutpop(k+1)；S.8 令 k=k+1 和 popi(k)=mutpop(k+1)，返回S.3；S.9 终止计算，输出最优结果。,6.7 遗传优化算法,四.算法实现的几个技术问题 编码和解码,编码由设计空间向编码空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码由编码空间向设计空间的映射。,6.7 遗传优化算法,几种常见的编码方式,四.算法实现的几个技术问题 编码和解码,6.7 遗传优化算法,对于求极大化的目标函数（max f(x)），可通过下面转换建立与fitness(x)的映射关系:,四.算法实现的几个技术问题 适应函数 fitness(x),对于求极小化的目标函数（min f(x)），可通过下面转换建立与fitness(x)的映射关系:,Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。,适应函数用于对个体进行评价，即反映个体对环境适应能力。是优化进程发展的依据。其值必须大于等于零,6.7 遗传优化算法,群体规模 N 是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。,四.算法实现的几个技术问题 算法参数,交配概率 pc 用于控制交配操作的频率，通常取0.40.9之间。概率太大，种群更新过快，会使高适应函数值的个体过快被破坏；概率太小，交配操作很少进行，搜索速度慢，耗时长。,变异概率 pm 加大种群多样性的重要因素，通常取0.0010.1之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小，产生新个体的机会太小。,6.7 遗传优化算法,复制、交配、变异,四.算法实现的几个技术问题 遗传算子,复制(选择)选择用于繁殖后代的双亲。体现“适者生存”，适应 度高，生存概率大。依据选择概率 pi=fi/fi 进行。,交配(交叉)两个相互配对的染色体（双亲）按某种方式相互交换其 部分基因而生成两个新的个体。,6.7 遗传优化算法,四.算法实现的几个技术问题 遗传算子,一点交配（二进制）：,多点交配（二进制）：,6.7 遗传优化算法,四.算法实现的几个技术问题 遗传算子,变异 在交配之后进行。将个体染色体编码字符中的某些基因 用其他等位基因替换，从而生成新的染色体。作用：保持群体中个体的多样性，有效地防止算法早熟收敛。方法：按位进行，以概率 pm 改变字符串上某一位基因。,例：变异（二进制）,6.7 遗传优化算法,四.算法实现的几个技术问题 算法终止准则,事先规定出一个最大的进化步数，到达此步数时终止(一般取100-500代)。判断当前最好的解已连续若干步没有变化。算法已找到了一个可接受的最好解。,遗传算法应用举例,例1:利用遗传算法求解区间0,31上的二 次函数y=x2最大时的整数解。,解:(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=01101,s2=11000 s3=01000,s4=10011(2)定义适应度函数:f(x)=x2(3)计算各代种群中每个个体的适应度值,并相应对其染色体进行遗传操作。,首先计算种群S1中各个体的适应度f(si)。s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)容易求得 f(s1)=f(13)=132=169 f(s2)=f(24)=242=576 f(s3)=f(8)=82=64 f(s4)=f(19)=192=361,再计算种群S1中各个体的选择概率。,选择概率的计算公式为,由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31,赌轮选择示意,赌轮选择法,在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机 数r。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其 中的qi称为染色体xi(i=1,2,n)的积累概 率,其计算公式为,选择-复制,设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503,交配(交叉)设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）,于是，经复制得新群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）,变异:变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。,于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）,第二代种群S2中各染色体的情况,假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：,s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）,做交配(交叉)运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）,这一轮仍然不会发生变异。,第三代种群S3中各染色体的情况,于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）,设这一轮的选择-复制结果为：s1=11100（28）,s2=11100（28）s3=11000（24）,s4=10011（19）,做交配(交叉)运算，让s1与s4，s2与s3 分别交换后两位基因，得,s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）,这一轮仍然不会发生变异。,显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。,于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）,Y,例2:求下列函数的最大值。max f(x1,x2)=100(x12-x22)2+(1-x1)2 s.t.-2.048 xi 2.048(i=1,2),该函数有两个局部极大点，分别是:f(2.048,-2.048)=3897.7342 和 f(-2.048,-2.048)=3905.9262其中后者为全局最大点。,解：第一步：确定编码方法。用长度为l0位的二进制(最大可表示1023)表示一个变量。从离散点-2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。再将分别表示x1和x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。例如 X：00001 10111 11011 10001 就表示一个个体。,第二步：确定解码方法。解码时先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据前述个体编码方法相对定义域的离散化方法可知，将代码 yi 转换为变量xi的解码公式为：,例如，对前述个体 X：0000110111 11011 10001 它由这样的两个代码所组成：y1=55 y2=881 经上式的解码处理后，得到：x1=-1.828 x2=1.476,第三步：确定个体评价方法。由式 f(x1,x2)=100(x12-x22)2+(1-x1)2 可知值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，并且不再对它作其他变换处理，即有：F(x)=f(x1,x2)第四步：设计遗传算子。选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。第五步：确定遗传算法的运行参数。对于本例，设定基本遗传算法的运行参数如下：群体大小:M80 终止代数:T200 交叉概率：pc0.6 变异概率：pm0.001,收敛情况,初始群体分布情况,大量的个体分布在最优点和次最优点附近。,第5代群体分布情况,次最优点也被淘汰。,第10代群体分布情况,更加集中在最优点附近。,100代群体中个体的分布情况,6.7 遗传优化算法,五.遗传算法与其他传统搜索方法的比较,遗传算法不是直接作用在解空间上，而是作用在解的某种编码上遗传算法从一个群体解（即多个解）而不是一个解开始搜索，这是它能以较大概率找到全局最优解的主要原因。遗传算法对搜索空间无任何特殊要求（如连通性、凸性），只利用适应度信息，而传统搜索算法一般要使用导数等其他辅助信息。遗传算法使用随机转移规则而不是确定性的转移规则。遗传算法耗费机时太多,需要解决计算精度与效率的问题选择、交叉及变异的形式与参数选择一般工程人员难以掌握。,本章结束,Thank You！,