优化设计第八次课PPT课件.ppt

第五章 约束优化方法 1 第三节复合形法 复合形法是约束优化设计问题的另外一种重要的直接解法 它来源于用于求解无约束优化设计问题的单纯形法 实际上是单纯形法在约束优化设计问题中的发展 由于复合形法的形状不必保持规则的图形 在迭代过程中也不必计算目标函数的一 二阶导数 同时无需进行一维搜索 因此 对目标函数和约束函数的性态无特殊要求 程序较简单 所以 该方法的适应性强 在机械优化设计中得到广泛应用 但随着设计变量和约束条件的增多 其计算效率显著降低 2 一 复合形法的基本思想 3 二 初始复合形的建立 复合形是由个顶点组成的一个多面体 每个顶点都必须满足所有的约束条件 例如当时 即在可行域内构成一个三角形或四边形 如下图所示 4 生成初始复合形的方法有以下几种 1 由设计者试选个可行点 构成初始复合形 当设计变量较多或约束函数较复杂时 由设计者决定个可行点常常很困难 只有在设计变量少 约束函数较简单的情况下 这种方法才被使用 0 1 区间内均匀分布的伪随机数 式中 复合形顶点的标号 设计变量的标号 表示点的坐标分量 第个设计变量的下限值和上限值 5 这样产生的个顶点虽然能满足设计变量的边界约束条件 但不一定就能满足性能约束条件 因此 就要设法将非可行点移到可行域内 具体采用的方法是 首先求出已经在可行域内的P个顶点的形心点 即 后将非可行点向中心点移动 即 只要形心点为可行点 且系数选择得当 一般取 总可以使新点满足全部约束条件 即满足 6 事实上 只要可行域为凸集 其中心点必为可行点 用此方法可以成功地在可行城内构成初始复合形 如果可行域为非凸集 如下图所示 中心点不一定在可行域之内 则此方法可能失败 这时可以通过改变设计变量的下限值和上限值 重新产生各项点 经过多次试算 有可能在可行域内生成初始复合形 通过对随机产生的各个顶点进行这种处理后 最后可取得个初始可行顶点 从而构成初始复合形 7 3 由计算机自动生成初始复合形的全部顶点 其方法是首先随机产生一个可行点 然后按上述第二种方法产生其余个可行点 这种方法对设计者来说最为简单 但因初始复合形在可行域内的位置不能控制 可能会给以后的计算带来困难 8 三 复合形法的寻优过程 9 若为除去以外个顶点的中心点 在下图中是和连线的中心 则通常是由最差点指向中心点的方向 为目标函数值下降的方向 故在和连线的延长线上取一点 这一步称为反射 称为最差点的反射点 即 式中 反射系数 一般取 可取 10 检查反射点是否为可行点 若在可行城内 且 11 综上所述 反射成功的条件为 12 基本的复合形法 只含反射 的计算步骤如下 四 复合形法的计算步骤 1 选择复合形的顶点个数 按所选生成初始复合形的方法构成具有个顶点的初始复合形 2 计算复合形个顶点的目标函数值 选出其中的最差点 即 最好点 即 13 3 计算除去最差点外其余个顶点的中心点 即 检验中心点是否在可行域内 若在可行域内 则继续进行第 4 步 否则 转到第 5 步 一般取反射系数 若超出可行域 为非可行点 则将其退回 即将反射系数减半 令 重新计算反射点 直至反射点成为可行点为止 如下图所示 14 15 5 如果中心点不在可行域内 则可行域可能是一个非凸集 如下图所示 按上式计算的反射点不可能是可行点 此时利用中心点和最好点重新确定一个区间 在此区间内重新按所选生成初始复合形的方法构成具有个顶点的复合形 新的区间如下图中虚线所示 此时设计变量的下限值与上限值为 若 则取 若 则取 重新构成复合形后再重复第 2 3 步 直至成为可行点为止 16 6 计算反射点的函数值 如果 则用反射点替换最差点 构成新的复合形 完成一次迭代计算 返回第 2 步 否则继续进行下一步 8 若收敛条件 得到满足 计算终止 此时约束最优解为 否则返回第 2 步 17 18 19 复合形法的特点 1 不用计算目标函数一阶 二阶导数 2 不用一维最优化方法 3 对目标函数和约束函数性态无特殊要求 4 程序简单 适用面比较广 5 当维数n较多时 效率较低 6 复合形 多面体 会退化 降维 为防止退化 顶点数k可取多一点 20 21 第四节可行方向法 可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法 也是求解大型约束优化设计问题的主要方法之一 其收敛速度快 效果较好 适用于大中型约束优化设计问题的求解 但程序比较复杂 22 一 可行方向法的基本思想 可行方向法的基本思想是在可行域内选择一个初始点 当确定了一个可行方向和适当的步长后 按下式 进行迭代计算 在不断调整可行方向的过程中 使迭代点逐步逼近约束最优点 23 二 可行方向法的基本搜索过程 24 第一种情况如图 a 所示 在约束面上的迭代点处 产生一个可行方向 沿此方向进行一维搜索 得到的新点在可行域内 即令迭代点 再沿点的负梯度方向继续进行搜索 25 第二种情况如图 b 所示 沿可行方向进行一维搜索 得到的新点在可行域外 则设法将新点移至约束面上 即取和约束面的交点作为新的迭代点 26 27 对于具有非线性约束函数的非线性规划问题 沿约束面的切线方向进行搜索时 新点又将进入非可行域 如下图所示 此时 须将进入非可行域的新点设法调整到约束面上 然后才能进行下一次迭代 解决这个问题的办法是先规定允许进入非可行域的 深度 即建立约束容差的边界 然后沿目标函数的梯度方向或起作用约束函数的负梯度方向 将新点返回到约束面上 其计算公式为 式中 调整步长因子 可用试探法决定 或用下式估算 28 尽管可行方向法有几种不同的搜索策略 但其基本的是以下两个决策 1 产生一个可行方向 29 三 可行方向法产生可行方向的条件 可行方向是指沿该方向做微小移动后 所得到的新点是可行点 且目标函数值有所下降 显然 可行方向应满足可行和下降两个条件 1 可行条件 30 若在J个起作用约束面的交集上 如下图 b 所示 要求和J个起作用约束函数在点的梯度的夹角均应大于或等于 其向量关系式为 31 2 下降条件 32 同时满足可行条件和下降条件的方向称可行方向 如下图所示 它位于约束曲面在点的切线和目标函数等值线在点的切线所围成的扇形区域内 该扇形区域称为可行下降方向区 33 34 四 可行方向法产生可行方向的方法 如上所述 满足可行 下降条件的方向位于可行下降方向区内 在可行下降方向区内寻找一个最有利的方向作为本次迭代的搜索方向 这个方向的产生方法主要有随机产生法 线性规划法和梯度投影法 1 随机产生法 35 2 线性规划法 由于和为定值 上述各函数均为设计变量的线性函数 因此这是一个线性规划问题 可以用线性规划法求解 求得的最优解 即为本次迭代的可行方向 即 36 3 梯度投影法 37 梯度投影法就是取该方向作为本次迭代的可行方向 其计算公式为 起作用约束函数的个数 38 由于目标函数及约束函数的性质不同 步长的确定方法也不同 不论是用何种方法 都应使新的迭代点为可行点 且目标函数值具有最大的下降量 确定步长主要有最佳步长和试验步长两种方法 五 可行方向法搜索步长的确定 可行方向确定后 按下式计算新的迭代点 即 1 最住步长 39 2 试验步长 如下图所示 若从点出发 沿方向进行一维搜索 得到的新点为不可行点 此时应根据可行方向法的搜索策略 改变步长 使新点返回到约束面上来 得到新的迭代点 使新的迭代点恰好位于约束面上的步长称为最大步长 记作 则本次迭代的步长取为 40 由于不能预测出发点到另一个起作用约束面的距离 最大步长的确定较为困难 一般按试验法确定 其步骤如下 1 取一试验步长 计算试验点 应适当选取试验步长 太大 会导致计算困难 也不能太小 太小会使计算效率降低 根据经验 试验步长的值能使试验点的目标函数值下降5 10 为宜 即 41 2 在可行域外 即为非可行点 由此可得试验步长的计算公式为 2 判别试验点的位置 由上式确定的试验点可能存在三种情况 1 在约束面上 3 在在可行域内 42 的条件时 就认为试验点已位于约束面上 事实上 只要试验点不在约束面上 就要设法将其调整到约束面上来 要想使试验点准确地到达约束面是非常困难的 为此 先确定一个约束容差 当试验点满足 若试验点位于非可行域 则转步骤 3 43 44 将试验点调整到的约束面上的方法有试探法和插值法两种 1 试探法的基本思想是当试验点位于非可行域时 将试验步长缩短 当试验点位于可行域内时 将试验步长增加 即通过不断调整的大小 将试验点调整到约束面上 45 2 插值法是利用线性插值将位于非可行域的试验点调整到约束面上 设试验步长为时 求得可行试验点 即 当试验步长为时 求得非可行试验点 即 并设试验点和的约束函数分别为和 它们的位置关系如下图所示 46 47 六 可行方向法的终止准则 可行方向法的迭代终止准则有以下两种 条件时 迭代终止 1 设计点及