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

第六章约束优化方法 根据求解方式的不同 可分为直接解法和间接解法两类 机械优化设计的问题 大多属于约束优化设计问题 其数学模型为 直接解法是在满足不等式约束的可行设计区域内直接求出问题的约束最优解 属于这类方法的有 随机实验法 随机方向搜索法 复合形法 可行方向法等 1 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法 由于间接解法可以选用已研究比较成熟的无约束优化方法 并且容易处理同时具有不等式约束和等式约束的问题 因而在机械优化设计得到广泛的应用 间接解法中具有代表性的是惩罚函数法 直接解法的基本思想 在由m个不等式约束条件gu x 0所确定的可行域 内 选择一个初始点x 0 然后确定一个可行搜索方向S 且以适当的步长沿S方向进行搜索 取得一个目标函数有所改善的可行的新点x 1 即完成了一次迭代 以新点为起始点重复上述搜索过程 每次均按如下的基本迭代格式进行计算 2 x k 1 x k k S k k 0 1 2 逐步趋向最优解 直到满足终止准则才停止迭代 3 直接解法的原理简单 方法实用 其特点是 1 由于整个过程在可行域内进行 因此 迭代计算不论何时终止 都可以获得比初始点好的设计点 2 若目标函数为凸函数 可行域为凸集 则可获得全域最优解 否则 可能存在多个局部最优解 当选择的初始点不同 而搜索到不同的局部最优解 3 要求可行域有界的非空集 4 a 可行域是凸集 b 可行域是非凸集 5 间接解法的求解思路 将约束函数进行特殊的加权处理后 和目标函数结合起来 构成一个新的目标函数 即将原约束优化问题转化为一个或一系列的无约束优化问题 新目标函数 加权因子 然后对新目标函数进行无约束极小化计算 6 7 第二节随机方向法 随机方向法的基本思路 在可行域内选择一个初始点 利用随机数的概率特性 产生若干个随机方向 并从中选择一个能使目标函数值下降最快的随机方向作为搜索方向d 从初始点x0出发 沿d方向以一定步长进行搜索 得到新点X 新点x应满足约束条件且f x f x0 至此完成一次迭代 基本思路如图所示 随机方向法程序设计简单 搜索速度快 是解决小型机械优化问题的十分有效的算法 8 9 一 随机数的产生 下面介绍一种常用的产生随机数的数学模型 骤计算 令 10 在任意 a b 区间内的随机数 二 初始点的选择 随机方向法的初始点x0必须是一个可行点 既满足全部不等式约束条件 初始点可以通过随机选择的方法产生 1 输入设计变量的下限值和上限值 即 2 在区间 0 1 内产生n个伪随机数 3 计算随机点x的各分量 11 4 判别随机点x是否可行 若随机点可行 用x代替x0为初始点 若非可行点 转到步骤2 重新产生随机点 只到可行为止 三 可行搜索方向的产生 产生可行随机方向的方法 从k个随机方向中 选取一个较好的方向 其计算步骤为 12 2 取一试验步长a0 按下式计算k个随机点 3 检验k个随机点是否为可行点 除去非可行点 计算余下的可行点的目标函数值 比较其大小 选出目标函数最小的点XL 4 比较XL和X0两点的目标函数值 若f XL f X0 则步长 0缩小 专步骤1 重新计算 直至f XL f X0 为止 如果 0缩小到很小 仍然找不到一个XL 使f XL f X0 则说明X0是一个局部极小点 此时可更换初始点 转步骤1 13 产生可行搜索方向的条件为 则可行搜索方向为 四 搜索步长的确定 步长由加速步长法确定 14 五 随机方向法的计算步骤 第三节复合形法 复合形法是求解约束优化问题的一种重要的直接解法 它的基本思路是在可行域内构造一个具有k个顶点的初始复合形 对该复合形各顶点的目标函数值进行比较 找到目标函数最大的顶点 最坏点 然后按一定的法则求出目标函数值有所下降的可行的新点 并用此点代替最坏点 构成新的复合形 复合形的形状没改变一次 就向最优点移动一步 直至逼近最优点 由于复合形的形状不必保持规则的图形 对目标函数和约束函数无特殊要求 因此这种方法适应性强 在机械优化设计中应用广泛 15 16 初始复合形生成的方法 1 由设计者决定k个可形点 构成初始复合形 设计变量少时适用 2 由设计者选定一个可形点 其余的k 1个可形点用随机法产生 17 3 由计算机自动生成初始复合形的所有顶点 二 复合形法的搜索方法 1 反射 1 计算复合形各顶点的目标函数值 并比较其大小 求出最好点XL 最坏点XH及次坏点XG 即 18 2 计算除去最坏点XH外的 k 1 个顶点的中心XC 3 从统计的观点来看 一般情况下 最坏点XH和中心点XC的连线方向为目标函数的下降方向 19 4 判别反射点XR的位置 若XR为可行点 则比较XR和XH两点的目标函数值 如果f XR f XH 则将 缩小0 7倍 重新计算新的反射点 若仍不行 继续缩小 直至f XR f XH 为止 若为非可行点 则将 缩小0 7倍 直至可行为止 然后再重复可行点的步骤 2 扩张 20 3 收缩 21 22 23 第五节惩罚函数法 惩罚函数法是一种很广泛 很有效的间接解法 它的基本原理是将约束优化问题中的不等式和不等式约束函数经加权后 和原目标函数结合为新的目标函数 惩罚函数 将约束优化问题转换为无约束优化问题 求解无约束优化问题的极小值 从而得到原约束优化问题的最优解 加权转化项 24 惩罚函数法是按一定的法则改变加权因子的值 构成一系列的无约束优化问题 求一系列无约束最优解 并不断地逼近原约束优化问题的最优解 因此又称序列无约束极小化方法 常称SUMT方法 根据它们在惩罚函数中的作用 分别称障碍项和惩罚项 障碍项的作用是当迭代点在可行域内时 在迭代过程中将阻止迭代点越出可形域 惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时 在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面 按照惩罚函数在优化过程中迭代点是否可行 分为 内点法 外点法及混合法 25 一 内点惩罚函数法 内点法将新目标函数定义于可行域内 这样它的初始点及后面的迭代点序列必定在可行域内 采用内点法只能求解具有不等式约束的优化问题 转化后的惩罚函数形式为 障碍项 26 障碍项的作用是阻止迭代点越出可行域 例6 5用内点法求问题 约束最优解 27 28 用内点法求解 首先构造内点惩罚函数 用解析法对函数求极小值 求解得 29 不满足约束条件 舍去 无约束极值点为 30 下面介绍内点法中的初始点 惩罚因子初值及其缩减系数的选取和收敛条件的确定 1 初始点的选取 初始点应选离约束边界较远的可行点 程序设计时 一般 考虑具有人工输入 和计算机自动生成可行初始点的两种功能 2 惩罚因子的初值的选取 惩罚因子的初值选取应适当 否则会影响迭代计算的正常进行 太大会影响迭代次数 太小会使惩罚函数的形态变坏 难以收敛到极值点 1 取r0 1 根据试算的结果 再决定增加或减少r0值 31 2 按经验公式 计算r0值 这样选取的r0 可以是惩罚函数中的障碍项和原目标函数的值大致相等 不会因障碍项的值太大则其支配作用 也不会因障碍项的值太小而被忽略掉 3 惩罚因子的缩减系数c的选取 在构造序列惩罚函数时 惩罚因子r是一个逐次递减到0的数列 相邻两次迭代的惩罚因子的关系为 32 惩罚因子的缩减系数通常的取值范围 0 1 0 7之间 4 收敛条件 33 34 内点法是将惩罚因数定义于可行域内 而外点法与内点法不同 是将惩罚项函数定义于可行区域的外部 序列迭代点从可行域外部逐渐逼近约束边界上的最优点 二 外点惩罚函数法 外点法可以用来求解含不等式和等式约束的优化问题 对于约束优化问题 35 惩罚因子 它是由小到大 惩罚项 由惩罚项可知 当迭代点不可行时 惩罚项的值大于零 当迭代点离约束边界越远时 惩罚项愈大 这可看成是对迭代点不满足约束条件的一种惩罚 转化后的外点惩罚函数的形式为 36 37 例6 6用外点法求问题 约束最优解 首先构造外点惩罚函数 用解析法求解 38 求解得 39 外点法惩罚银子按下式递增 递增系数 通常取c 5 10 与内点法相反计算r0值 选取的r0太大则会使惩罚函数等值线偏心或变形 难以取得极小值 但r0太小 势必增加迭代次数 经验计算一般取r0 1 c 10常常可以取得满意的效果 也可以通过经验公式获得r0值 40 外点法的特点 1 初始点可以任选 但应使各函数有定义2 对等式约束和不等式约束均可适用3 仅最优解为可行设计方案4 一般收敛较快5 初始罚因子要选择得当6 惩罚因子为递增 递增率c有c 1 内点法的特点 1 初始点必须为严格内点2 不适于具有等式约束的数学模型3 迭代过程中各个点均为可行设计方案4 一般收敛较慢5 初始罚因子要选择得当6 罚因子为递减 递减率c有0 c 1 41 三 混合惩罚函数法 1 混合惩罚函数法及其算法步骤 在构造惩罚函数时