《约束优化方法》PPT课件

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第5章 约束优化方法,机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为,根据求解方式的不同，约束优化设计问题可分为:,直接解法,、,间接解法,直接解法,通常适用于仅含不等式约束的问题，思路是在,m,个不等式约束条件所确定的可行域内，选择一个初始点，然后决定,可行搜索方向,d,，且以适当的步长 ，沿,d,方向进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。,步长,可行搜索方向,可行搜索方向:当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。常见的方法有坐标轮换法、随机方向法、复合形法等,。,间接解法的基本思路是将约束优化问题中的约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。,5-2约束随机方向搜索法,一、基本原理,约束随机方向搜索法类似与“瞎子爬山”。,在可行域内，任意选择一个初始点，利用随机数的特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为可行搜索方向，记作,d,。从初始点出发，以一定的步长沿,d,方向进行搜索，得到新点。若该点同时满足下降性（ ）和可行性（ ）要求，表示点探索成功，完成一次迭代。并以它作为新的起始点，重复上述过程。直至达到某搜索点不能同时满足下降性可行性要求时停止。此时废弃该搜索点并退回到前一个搜索成功点作为方向搜索中的最终成功点。再产生另一随机方向，重复以上过程，得到沿方向的最终成功点。经过若干次迭代计算后，取得点列必最后逼近约束最优点。,其优点是对目标函数的性态无特殊要求，程序设计简单，使用方便。,随机数的产生,在随机方向法中，为产生可行的初始点及随机方向，需要用到大量的（0，1）和（-1，1）区间内均匀分布的随机数。,在计算机内，随机数通常是按一定的数学模型进行计算后得到的。这样得到的随机数称伪随机数。一般为（0，1）区间，可通过x =a+q(b-a)得到任意区间（a，b）内的伪随机数。,要得到的随机数（保证是两位小数吗？），可以先得到0-30的随机整数，再加上15再除以100不就可以了 。,C语言中产生随机数的函数,RAND 和SRAND,二、初始点的选择,初始点必须是一个可行点，即必须满足全部约束条件。,（一）人为给定,（二）随机选定,当用人工不易选择初始可行点时，可用随机选择的方法来产生。其计算步骤如下：,1）输入设计变量的下限值和上限值，即,2）在区间（0，1）内产生n个伪随机数,3）计算随机点,X,的各分量，即,4）判别随机点,X,是否可行，若随机点,X,为可行点，则取为初始点；若随机点,X,为非可行点，则转步骤2）重新计算，直到产生的随机点是可行点为止。,（1）对于区间（-1，+1）上的n个随机数。其单位向量,其中r,i,=a,i,+q,i,( b,i,-a,i,),可行搜索方向的产生,（2）取一试验步长 ，按下式计算k个随机点,显然，k个随机点分布在以初始点为中心，以试验步长为半径的超球面上。,三、可行搜索方向的产生,随机搜索方向的产生,（3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行随机点的目标函数值，比较其大小，选出目标函数值最小的点,（4）比较 和初始点 两点的目标函数值，若 ，则取 和 的连线方向作为可行搜索方向；若 ，则将步长 缩小，转步骤（1）重新计算，直至 为止。如果初始步长缩小到很小，仍找不到一个 ，使得,则说明初始点是一个局部极小点，此时可更换初始点，重复计算。,综上所述，产生可行搜索方向的条件可概括为，当 点满足,则其搜索方向为,四、搜索步长的确定,可行搜索方向,d,确定后，初始点移至 点，即从 点出发沿,d,方向进行搜索，所用的步长一般按加速步长法来确定。,所谓加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算,步长加速系数，一般可取1.3,（1）给定维数n，初始变量估计的上下限ai ,bi ，初始步长,0,，收敛精度,。,（2）选择一个可行的初始点。,随机产生初始点X(0)。并检验其可行性条件gu (X(0),0 (u=1,2,m),，若可行则进行下一步；否则重新随机产生初始点X(0) ，直到成为可行初始点。,（3）产生k个n维随机单位向量,（5）在k个随机点中找出满足式,的随机点，产生可行搜索方向,（4）取试验步长，计算出k个随机点,（6）从初始点出发，沿可行搜索方向d以步长 进行迭代计算，直至搜索到一个满足全部约束条件，且目标函数值不再下降的新点。,（7）若满足收敛条件，则终止迭代。,否则，新点作为初始点，转（3）,五、随机方向法的计算步骤,复合形法,复合形法是求解约束优化问题的一种重要的 直接解法。,一、复合形法的基本思想,其基本思路是在可行域内构造一个具有,k,个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。,1,2,3,4,5,6,7,8,复合形法,二、初始复合形的构成,要构成初始复合形，实际上就是确定,k,个可行点作为复合形的顶点，顶点数目一般在,n+1,k,2n,范围内。,初始复合形的形成方法：,1）对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。,2）由设计者选定一个可行点，其余k-1个可行点由随机方法产生。,3）构成复合形的随机方法。该方法是先产生,k,个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都成为可行点而构成初始复合形。,复合形法,1、产生,k,个随机点,利用标准随机函数产生在（0，1）区间内均匀分布的随机数,i,，然后产生区间（,a,i,，b,i,）内的随机变量,x,i,，,x,i,=,a,i,+,i,（,b,i,-a,i,），,i,=1，2，,n,。以这,n,个随机变量为坐标构成随机点,x,1,。 同理，再次,产生在（0，1）区间内均匀分布的随机数,i,，然后获得区间（,a,i,，b,i,）内的随机点,x,2,，依次类推，可以获得,k,个随机点,x,1,、,x,2,、,x,3,、.、,x,k,。 可以看出，产生,k,个随机点总共需要产生,kn,个随机数。,构成复合形的随机方法：,复合形法,2、将非可行点移入可行域,用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果,k,个随机点没有一个是可行点，则应重新产生随机点，直至其中有至少一个是可行点为止。,将非可行点移入可行域的方法： 先检查随机点的可行性。将查出的第一个可行点,x,j,与,x,1,对调，则新的,x,1,点为可行点，然后检查随后的各点是否是可行点，若某点属于可行域，继续检查，直至出现不属于可行域的随机点，然后把此点移入可行域内。,复合形法,若已知,k,个随机顶点中前面,q,个点都是可行点，而,x,(q+1),为非可行点，则将,x,(q+1),移入可行域的步骤为： (1)计算,q,个点的点集中心 (2)将第,q+1,个点朝,x,(s),点方向移动，并按下式产生新的点，,x,(p),=x,(s),+0.5(x,(q+1),-x,(s),),此点实际上是,x,(s),与,x,(q+1),两点的连线的中点。若新点仍为非可行点，则按上式再产生一个新点，直至,x,(p),成为可行点为止。,x,(q+1),x,(p),x,(s),复合形法,3、构成初始复合形 将全部顶点变为可行点后，就构成了可行域内的初始复合形。,三、复合形法的迭代步骤,1、构成初始复合形 2、计算个顶点函数值,F(x,(j),), j=1,2,k,，并选出好点,x,(L),与坏点,x,(H),。,x,(L),:,F(x,(L),) =minF(x,(j),), j=1,2,k,x,(H),:,F(x,(H),) =maxF(x,(j),), j=1,2,k,3、计算除坏点外其余各点的中心点,x,0, 4、计算映射点,x,(R),x,(R),=x,0,+,(x,0,-x,(H),),通常取,=1.3，检查是否在可行域，若为非可行点，将映射系数缩半并重新计算映射点，直到进入可行域。,复合形法,5、构成新复合形 计算映射点与坏点的目标函数值并进行比较，若 （1）映射点优于坏点，即,F(x,(R),) F(x,(H),),，可用缩半映射系数的方法把映射点拉近。 6、判定终止条件 复合形在逼近最优点的过程中，当复合形缩得很小时，各顶点的目标函数值必然非常接近。故常用以下终止条件。 （1）各顶点与好点的函数值之差的均方根小于误差限，即,复合形法,（2）各顶点与好点的函数值之差的平方和小于误差限，即 （3）各顶点与好点的函数值之差的绝对值之和小于误差限，即 若不满足终止条件，返回步骤2，否则，可将复合形得好点及其函数值作为最优解输出。,复合形法,四、讨论 在用直接法解决约束优化问题时，复合形法是一种效果较好的方法。 这种方法不需要计算目标函数的导数，也不进行一维搜索，因此对目标函数和约束函数无特殊要求，适用范围广，编程简单。但是收敛速度较慢，不能用于解决具有等式约束的优化问题。,五、复合形法的流程图,可行方向法,原理,：,在可行域内选择初始点，当确定了,可行方向,和适当的步长后，进行迭代计算,x,k+1,=x,k,+,a,d,k,直接,解法，求解,大型约束优化,问题,从可行初始点出发，沿初始点的,负梯度方向,，将初始点移动到,某个约束面（,只有一个起作用约束时,）,或其交集,（,有多个起作用约束时,）上，,根据,约束函数和目标函数的不同性状，分别采用以下几种策略搜索。,可行方向法,一、可行方向法的搜索策略：,1 搜索策略（1）,2 搜索策略（2）,3 沿约束面搜索（3）,只有线性约束的非线性规划问题,非线性约束的非线性规划问题,可行方向法,非线性约束问题，将非可行域的,新点,x,调整到约束面,的方法：,先规定约束面容差，建立新的约束边界，将已离开约束面的,x,点沿起作用约束的负梯度方向返回到约束面上。,其计算公式：,其中调整步长，可用试探法确定。,二、产生,可行方向,的条件：,1 可行条件,一个起作用约束,两个起作用约束,产生可行方向的条件：,2 下降条件,三、可行方向的产生方法：,1 优选方向法,2 梯度投影法,四、步长的确定方法：,1 取最优步长,可行方向确定后，利用迭代公式计算新的迭代点，由于目标函数及约束函数的性状不同，步长的确定方法也不同。,2 取到约束边界的最大步长,若以取最优步长法确定得到的新点为不可行点，应改变步长，使新点返回到约束面上来。,使新点恰好位于约束面上的步长称为最大步长，记作,最大步长 的确定：,（1）取试验步长，计算试验点,（2）判断试验点的位置,将可行域内的点调整到约束面上，确定一个约束允差,（3）将非可行域点调整到约束面上,将试验点调整到违反量最大的约束面上。,A 试探法,B 差值法,可行试验点,非可行试验点,将非可行域试验点调整到约束面上的步长,五、收敛条件,1 设计点及约束允差满足,2 设计点及满足库恩-塔克条件,1） 在可行域内选择一个初始点，给出约束允差及收敛精度,2） 令迭代次数k=0，第一次迭代的搜索方向取,3） 估算试验步长 ，计算试验点,4） 判断试验点的位置，若满足 ，则位于第j个约束面上，转步骤6）； 若位于可行域内，则加大试验步长，直至越出可行域，转步骤5）； 若位于非可行域，直接转步骤5）,5） 确定违反量最大的约束函数 。用差值法计算调整步长 ，使试验点返回到约束面上，则完成一次迭代。再令k=k+1， ，转下步,6） 在新的设计点 处产生新的可行方向。,7） 在 点满足收敛条件，则计算终止。,否则，令 ，再转步骤2）。,六、可行方向法的计算步骤,可行方向法,步骤及流程图：,5.2 惩罚函数法,将有约束条件的优化问题转化为无约束优化问题来求解。,前提：一是不能破坏约束问题的约束条件，二是使其最优解归结到原约束问题的同一最优解上去。,构成一个新的目标函数，称为惩罚函数,求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。按一定的法则改变权因子,r,1,和,r,2,的值，求得一序列的无约束最优解，不断地逼近原约束优化问题的最优解。,r1, r2,r1, r2,r1, r2,r1, r2,根据惩罚项得不同构成形式，惩罚函数法又可分为,外点惩罚函数法、内点惩罚函数法和混合惩罚函数法,1、内点法,这种方法将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优化问题。,对于只具有不等式约束的优化问题：,转化后的惩罚函数形式为：,或：,r,k,是惩罚因子，它是一个由大到小且趋近于,0,的正数列，即,:,由于内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。由“障碍项”的函数形式可知，当迭代点靠近某一约束边界时，其值趋近于,0,，而“障碍项”的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“高墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。,例5-2 用内点法求,的约束最优解。,解: 用内点法求解该问题时，首先构造内点惩罚函数:,用解析法求函数的极小值，运用极值条件：,联立求解得：,时不满足约束条件,应舍去,.,无约束极值点为,当,1）,初始点,x,0,的选取,使用内点法时，初始点应选择一个离约束边界较远的可行点。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.,2） 惩罚因子初值r,0,的选取,惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。无一般性的有效方法。对于不同的问题，都要经过多次试算，才能决定一个适当,r,0,3) 惩罚因子的缩减系数c的选取,在构造序列惩罚函数时，惩罚因子,r,是一个逐次递减到,0,的数列，相邻两次迭代的惩罚因子的关系为,:,式中的,c,称为惩罚因子的缩减系数，,c,为小于1的正数。一般的看法是，,c,值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。,4) 收敛条件,2. 外点法,外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。,外点惩罚函数的形式为：,r,是惩罚因子,外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。由惩罚项的形式可知，当迭代点,x,不可行时，惩罚项的值大于,0,。,例5-3 用外点法求解下列有约束优化问题,解：惩罚函数为：,=,对上式求偏导，得,2,2,无约束目标函数极小化问题的最优解系列为：,当惩罚因子渐增时，由下表可看出收敛情况。,1,r,0.01,-0.80975,-50.00000,-24.9650,-49.9977,0.1,-0.45969,-5.00000,-2.2344,-4.9474,1,0.23607,-0.50000,0.9631,0.1295,10,0.83216,-0.05000,2.3068,2.0001,1000,0.99800,-0.00050,2.6624,2.6582,1,0,8/3,8/3,外点法的初始点X,(0),可任选，故可用于约束较多、初始可行点不易确定的优化问题，且不论等式或不等式约束都适用：外点法的罚因子,r,为递增，随着其不断增大，所得极小点序列可从可行域的外部逐步向真正的极小点,X*,靠拢。因此外点法仅最优解是可行方案，必须迭代到底才能得到唯一的可行解。,内点法的X,(0),必须在可行域内，且只能用于不等式约束，因为对于等式约束，可行域不存在内点与外点，而只有边界点；内点法的罚因子,r,为递减，随着罚因子的减小，所得极小点序列从可行域的内部逐步逼近,X*,。,所以内点法迭代的全过程都在可行域内，且每一个中间结果都是一个较初始点更优的可行方案，故内点法适合于对现有可行设计作改进，可为设计人员提供了更多的选择机会。,3、混合惩罚函数法,由于外点法和内点法各有优缺点，所以将两种方法综合起来，取长补短，这便是混合惩罚函数法。内、外点法可以认为是混合惩罚函数法的特例,混合惩罚函数法对于等式约束和初始点X,(0),所不满足的不等式约束，采用外点法的惩罚项处理；而对初始点X,(0),所满足的不等式约束则采用内点法的惩罚项处理，混合惩罚函数为,混合惩罚函数法可同时处理具有等式和不等式约束的优化问题，对初始点的选择也无特殊要求,5.4 圆柱齿轮减速器的优化设计,单级圆柱直齿轮减速器，以体积最小为设计目标，已知输入功率P58kw，转速n1000r/min, 传动比u5，齿轮的许用接触应力为550MPa， 许用弯曲应力为400MPa。,设计参数：,约束条件:,（1）最小齿数要求；,（2） 齿宽系数要求；,（3）齿轮模数要求；,（4）小齿轮直径要求；,（5）齿轮轴直径取值要求；,（6）轴的支承距离,l,满足条件；,（7）大齿轮满足弯曲强度要求；,（8）小齿轮满足弯曲强度要求；,（9）齿轮副满足接触疲劳强度要求；,（10）齿轮轴的最大挠度不大于许用值；,（11） 齿轮轴的弯曲应力不大于许用值。,s.t.,初始方案：,在第一轮迭代后的最优解和迭代一轮后的计算精度 。,取初始点,练习1 用黄金分割法求函数,f(,x,)=3,x,3,-4,x,+2,的极小点，给定,x,0,=,1,h,=,1,=,0.2,。,练习2 用阻尼牛顿求目标函数,练习3,用鲍威尔法（POWEII）求目标函数,的最优解。迭代二轮后的极值点和下一轮的方向组。已知初始点1,1,T,，迭代精度,（第,轮搜索方向替换条件：,和,，其中,）,