第六章-约束优化的直接搜索法PPT课件.pptVIP

机械优化设计 太原科技大学张学良 1 第六章约束优化的直接搜索法 数学模型 minf X X Rns t gj X 0 j 1 2 m hk X 0 k 1 2 p 6 1概述 根据对约束函数处理方法的不同 约束优化方法可以分为 直接法和间接法 2 直接法通常适用于仅含不等式约束的优化问题 当有等式约束时 该等式约束函数不能是复杂的隐函数 而且容易实现消元过程 直接法的基本思想 在m个不等式约束条件所确定的可行域内 选择一个初始点X 0 然后决定可行搜索方向S 0 且以适当的步长 0 沿S 0 方向进行搜索 得到一个使目标函数值下降的可行的新点X 1 即完成一次迭代 再以新点为起点 重复上述搜索过程 满足收敛条件后 迭代终止 3 迭代公式为一般公式 X k 1 X k k S k k 0 1 2 S k 为可行搜索方向 k 为步长 可行搜索方向是指 当设计点沿该方向作微量移动时 目标函数值将下降 且不会超出可行域 直接法的特点是 原理简单 方法实用 但计算量大 收敛慢 效率低 适于维数低 精度要求不高但目标函数较复杂的问题 4 间接法的基本思想 将约束优化问题中的约束函数进行特殊的加权处理后 和目标函数结合起来 构成一个新的目标函数 即将约束优化问题转化成为一个或一系列的无约束优化问题 再对新的目标函数进行无约束优化计算 从而间接地搜索到原约束优化问题的最优解 常用的直接法有 网格法 约束随机方向搜索法和复合形法 5 间接法的特点 1 其基础是无约束优化方法2 可以有效处理具有等式约束的约束优化问题3 其存在的主要问题是 选取加权因子较为困难 加权因子选取不当 不但影响收敛速度和计算精度 甚至会导致计算失败 6 6 2网格法 网格法的基本思想 适于解决如下数学模型 minf X X Rns t gj X 0 j 1 2 m ai xi bi i 1 2 n 其基本思想是 在设计变量的界限区域内作出网格 逐个计算各个网格点上的约束函数值和目标函数值 然后舍去不满足约束条件的网格点 对满足约束条件的网格点 7 比较其目标函数值的大小 从中找出目标函数值最小的网格点 若此网格点之间的距离hj均小于给定的控制精度 j 通常取 j i 1 2 n 则该网格点就是所要求的最优点的近似点X 否则 以该点为中心缩小寻优区间 即在该点附近作较密的网格 继续求目标函数值最小的网格点 如此循环往复 直至找到满足精度要求的最优点的近似点X 网格的划分可以是等间距的 也可以是非等间距的 8 计算步骤及算法框图 略 9 6 3约束随机方向搜索法 基本思想 它是约束优化问题中经常采用的一种直接求解方法 它适于解决如下数学模型 minf X X Rns t gj X 0 j 1 2 m 其基本思想是 在不破坏约束条件的前提下 从选定的初始可行点X 0 出发 相继沿着N个随机产生的搜索方向e k k 1 2 N 10 以定步长 0搜索得到N个试验点Xk k 1 2 N 然后计算比较N个试验点处的函数值f Xk 找出其中的最小点XL 若f XL f X 0 则缩短步长 0 或重新产生N个随机方向 重复前面的过程 若f XL f X 0 则继续沿方向S XL X 0 并令X 0 XL 以适当步长 向前跨步 得到新点X 1 X 0 S 若f X 1 f XL 则将新的起始点移到X 1 重复前面的过程进行新一轮搜索 11 若f X 1 f XL 则应缩短步长 直至取得一个好的可行点作为新一轮搜索的起始点 如此周而复始 当迭代步长 已经很小时 说明搜索已逼近约束最优点 达到精度要求时 即可终止迭代计算 方法1 决定性方法当问题的约束条件比较简单 可凭判断人为地在可行域内选定一个初始点 确定初始可行点 方法2 随机投点方法当问题的约束条件较为复杂时 靠判断选择初始可行点较困难 这时可借助计算机中的随机数发生器 产生随机但可行的初始点 12 设给定设计变量的上下限值为 ai xi bi i 1 2 n 则产生的随机点的各分量为xi 0 ai ri bi ai i 1 2 n 其中 ri为 0 1 区间上的随机数 还需对点X 0 进行可行性检验 即是否满足gj X 0 0 j 1 2 m 若满足 X 0 可作为初始点 否则 则应另取随机数重新产生随机点 直到得到一个可行的随机点为止 13 构造随机搜索方向 利用计算机中的随机数发生器 在区间 1 1 上产生一组随机数方法r1 r2 rn n为变量的维数 则随机搜索方向为e e1e2 en T r1r2 rn T ri2 0 5 e 1 e是一个单位向量 要产生N个随机搜索方向e k k 1 2 N 需要产生N组随机数ri k i 1 2 n k 1 2 N 14 计算步骤及算法框图 略 15 基本思想 6 4复合形法 它是约束优化问题中经常采用的一种重要的直接求解方法 它适于解决如下数学模型 minf X X Rns t gj X 0 j 1 2 m ai xi bi i 1 2 n 其基本思想是 在可行域内构造一个具有K1个顶点的初始复合形 n 1 K1 2n 16 或叫多面体 对该复合形各顶点的目标函数值进行比较 去掉目标函数值最大的顶点 或称最坏点 然后按一定的法则求出目标函数值有下降的可行的新点 并用此点代替最坏点 构成新的复合形 复合形的形状每改变一次 就向最优点移动一步 直到逼近最优点 初始复合形的形成 复合形法是一种在可行域内搜索最优点的直接解法 要求初始复合形必须在可行域内生成 即初始复合形的K1个顶点都必须是可行点 17 构造初始复合形是复合形法的关键内容之一 其方法和步骤如下 1 给定K1值 n 1 K1 2n 2 生成初始复合形 有两种方法 由设计者试选K1个可行点 构成初始复合形 当设计变量较多或约束函数较复杂时 由设计者决定K1个可行点常常很困难 只有在设计变量少 约束函数简单的情况下 才用这种方法 18 记K 1 由设计者选定一个可行点X1或用随机投点法确定X1 其余的 K1 1 个可行点用随机法产生 各顶点按下式计算 XK a rK b a K 1 2 K1 其中 rK 0 1 区间上的随机数 a b 设计变量的上下限 XK 复合形中的第K个顶点 由上式计算得到的 K1 1 个随机点不一定都在可行域内 因此要设法将不可行点移到可行域内 19 在随机产生每个随机点时 要检查其可行性 若可行转3 否则计算前 K 1 个可行点所成复合形的中心 或形心 点XF XF Xj K 1 然后将非可行点XK向中心点XF移动 即XK XF 0 5 XK XF 新的XK是由原XK向XF退缩得到的 再检查是否为可行点 若仍为非可行点 则继续按上式使XK向XF退缩 直到成为可行点 如果目标函数是凸函数 可行域是凸集 则 20 XF总是可行的 故由XK向XF退缩 总可以找到可行点XK 若XF不可行 则可行域必为非凸集 这种情况下为保证初始复合形在可行域内 应缩小随机投点的边界域 重新产生初始复合形的各顶点 3 判断K K1否 如果K K1 则令K K 1并转2 的 直至产生K1个可行点 构成初始复合形X1X2 XK1 21 复合形法的计算步骤及算法框图 图6 13 1 构造初始复合形 2 计算并比较复合形各顶点的目标函数值f XK 找出最坏点XH 最优点XL 次坏点XG f XH max f XK K 1 2 K1 f XL min f XK K 1 2 K1 f XG max f XK K 1 2 K1 K H 22 3 检验迭代终止条件 计算复合形K1个顶点的函数值的平均值fm fm f XK K1计算容差DF 并判别是否满足DF f XK fm 2 K1 1 2 若满足 迭代计算终止 并输出最优解 X XL f f XL 否则 转下一步 23 4 计算除去最坏点XH以外的 K1 1 个顶点的中心XC XC Xj K1 1 判别XC是否可行 若XC为可行点 则转5 若XC为非可行点 则重新确定设计变量的下限和上限值 即令a XL b XC或a XC b XL然后转1 重新构造初始复合形 5 计算反射点XRXR XC XC XH 反射系数 一般取 1 1 3 24 6 检验反射点XR的可行性 若可行 转下一步 若不可行 则令 0 5 转5 再求反射点 此时又称退缩点 直至XR可行 再转下一步 7 计算f XR 若f XR f XH 则转下一步 25 8 检验反射系数是否满足 为一小的正数 若满足 则转下一步 若不满足 则令 0 5 转5 9 改变反射方向 即改求次坏点XG的反射点XR 公式为XR XC XC XG 并转6 直至找到新的复合