约束优化方法课件.pptx
3.2 约束优化方法 3.2.1 约束优化方法概述 3.2.2 约束随机方向法3.2.3 复合型法 3.2.4 约束可行方向法(直接搜索方法)第1页/共24页3.2.1 约束优化方法概述一、约束优化问题的数学模型第2页/共24页二、约束优化方法分类（1).直接法 直接法是在满足约束条件的可行域内直接求出问题的约束最优解，整个求解过程在可行域内进行，因而所得的任一方案都是可行的。原理比较简单，方法比较适用。包括：网格法、分层降维枚举法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。第3页/共24页(2).间接法 间接法是将约束优化问题先转变成一系列无约束优化问题，用无约束优化方法来求解。可见，无约束优化方法是约束优化方法的基础。间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、精确罚函数法、广义乘子法、广义简约梯度法和约束变尺度法。第4页/共24页3.2.2 约束随机方向法 基本原理对于求解 的约束非线性规划问题，第5页/共24页采用约束随机方向搜索法的迭代格式为 式中 第k次迭代的随机搜索方向;所用的步长因子。第6页/共24页 在约束可行域内选取一个初始点x(0)。为了确定本次迭代的搜索方向，以若干个不同方向的向量x进行试验性的探索，若f(x(0)+x)f(x(0)，则以x为搜索方向，取适当步长因子，在不破坏约束条件的情况下，前进一步，取得新点x，若f(x)f(x(0)，则将起始点移至x点，重复前面的过程。否则需将步长因子缩短，直至取得一个好的可行点。如此周而复始，直至迭代步长已经很小时(即相邻二次迭代点已相距很近)，就结束计算过程，取得约束最优解。第7页/共24页第8页/共24页 显然，约束随机方向搜索法的关键是如何确定初始点、搜索方向和搜索步长，而这些都需要涉及随机数问题。一、随机数的产生 在一般计算机上都备有过程或子程序，调用它即可得0，1区间内均匀分布的伪随机数列。若已产生了0，1区间上的伪随机数r，则通过变换可以求得任意区间a，b内的伪随机数R R=a+r(b-a)第9页/共24页二、初始点的选择 通常可以有两种确定方法：(1)决定性的方法 即在可行域内人为地确定一个可行的初始点。当约束条件比较简单时，这种方法是可用的。但当约束条件比较复杂时，人为选择一个可行点就比较困难，建议用下面的随机选择方法。(2)随机选择方法 即利用计算机产生的伪随机数来选择一个可行的初始点x(0)。第10页/共24页需要输入对设计变量估计的上限值和下限值，即 aixibi i=1,2,n这样，所产生的随机点的各分量为 xi(0)=ai+ri(bi-ai)i=1,2,n式中 ri0，1区间内服从均匀分布的伪随机数。第11页/共24页这样产生的随机点不一定满足所有的约束条件。因此还必须经过可行性条件的检验。若是可行点，即可作为初始点x(0)。若为非可行点，则另取伪随机数再产生一个随机点。直到产生一个可行的随机点为止。采用这种方法来产生可行的初始点，对于中等规模的优化设计问题都比较适用。第12页/共24页三、随机搜索方向的产生 利用伪随机数可以用不同的方法产生随机搜索方向s。以二维问题为例，若r1(j)、r2(j)为一1，1区间内均匀分布的伪随机数，则可用下式产生N个随机单位向量 第13页/共24页取得N个随机单位向量后，可按下式产生N个随机试验点x(j)=x(0)+H0 e(j)j=1,2,N式中H0 试验步长因子，一般可取为0.1或0.01，或者更小一点。然后检查试验点是否为可行点，计算可行试验点的目标函数值，比较它们的大小，选出其中目标函数值最小的点x(L)，即 f(x(L)=min f(x(j),j=1,2,N；非可行点除外若f(x(L)f(x(0)，则取x(0)和x(L)的连线方向作为按索方向，即 s=x(L)-x(0)第14页/共24页对于2维问题，其单位向量e(j)的端点分布于单位圆的圆周上。为了尽可能获得较优的搜索方向，应选取适当的步长因子H0。将单位圆缩小或放大，使试验点落在以H0 e(j)为半径的圆周上。H0太小，搜索方向的选择将受目标函数局部性质的影响，若H0太大，同样数量的试验点分布在很大圆周上，降低了密度，取得较优的搜索方向的机会也就减少了，影响了收敛速度。第15页/共24页 对于三维问题，其随机单位向量 e(j)的端点位于以单位长为半径的球面上。对于n维问题，则位于超球面上。在这种情况下，其单位随机向量 e(j)的分量 ei(j)按下式计算：式中 r1(j)、r2(j)、rn(j)1，1区间内的n个伪随机数。第16页/共24页综上所述，在约束随机方向搜索法中，产生随机搜索方向s时应满足的条件是f(x(L)f(x(0)第17页/共24页 四、搜索步长的确定 沿已确定的搜索方向s进行搜索，从而取得一个目标函数值有所下降且满足约束条件的新的迭代点。其计算公式为式中 x(k)已确定的第k一1次迭代点；第k次迭代的随机搜索方向;所用的步长因子。第18页/共24页步长因子的确定有两种方法：（1）定步长法，即步长按规定长度等差递增，只要所得新点的目标函数值是下降的且满足约束条件，就在原基础上增加一个规定的步长向前移动，直至违背了约束条件或目标函数的下降性条件时为止，于是迭代点由起始点移到新点。（2）变步长法，即步长按一定的倍增系数等比递增或递减。例如以1.3倍递增，那么每次向前的移动步长为前一次的13倍。这样做可以减少计算工作量，提高计算效率。第19页/共24页第20页/共24页522算法的步骤 s1 选择初始点 x(0)，检验其是否满足可行性条件。若满足则进行下一步；否则重新选择初始点。s2 产生N个随机单位向量 e(j)(j1，2，N)，然后在设计空间中以 x(0)为中心，H0为半径的超球面上产生N个随机试验点 x(j)，即x(j)=x(0)+H0 e(j)j=1,2,N 检查试验点的可行性、计算可行试验点的目标函数值并选出其中最小值点 x(L)。若满足 f(x(L)f(x(0)条件，则确定可行搜索方向 s=x(L)-x(0)，否则重复上述过程，重新产生N个随机试验点，或者将试验步长缩小到0.7 H0，再确定可行搜索方向s。第21页/共24页s3 从初始点x(0)出发，沿可行搜索方向s先以13 H0的步长移动若新点是可行点，且目标函数值下降，则继续以13加大步长前进。否则以07的步长移动。直到目标函数值不再下降同时又不违背约束条件时为止，即完成了一次迭代，将搜索终点x，作为下次搜索的初始点x(0)。s4 当一次迭代的初始点与终点的函数值达到和其步长达到时，即结束搜索过程。其最优解为：x*=x，f(x*)f(x)。否则转向第2步。第22页/共24页随机方向搜索法的特点（1）随机方向搜索法的优点是对目标函数的性态无特殊要求，程序结构简单，使用方便。另外，由于搜索方向是从许多方向中选择出目标函数值下降最好的方向，再加上随机变更步长，所以收敛速度比较快。若能选取一个较好的初始点，则其迭代次数可以减少。因此，它对于大型机械优化设计问题是一种较为有效的方法。（2）计算精度较低（缺点）。第23页/共24页感谢您的观看！第24页/共24页
