华中科技大学工程优化设计-约束直接法

1、工程优化设计内容提要 工程优化问题建模工程优化问题建模 优化数学理论优化数学理论 一维搜索方法一维搜索方法 无约束问题直接搜索方法无约束问题直接搜索方法 无约束问题间接接搜索方法无约束问题间接接搜索方法 约束问题直接搜索方法约束问题直接搜索方法 线性规划与二次规划问题求解线性规划与二次规划问题求解 约束问题间接搜索方法约束问题间接搜索方法 启发式算法启发式算法 优化软件系统优化软件系统约束直接搜索方法直接法直接法: : 利用迭代过程已有信息和再生信息进行试探和求优利用迭代过程已有信息和再生信息进行试探和求优, ,不需要用到函数导数和分析性质。不需要用到函数导数和分析性质。 适用于仅含不等式约束

2、的优化问题适用于仅含不等式约束的优化问题. . 新的迭代点必须限新的迭代点必须限制在不等式约束构成的可性域内制在不等式约束构成的可性域内, ,且保证目标函数的稳定下降且保证目标函数的稳定下降. .随机实验法随机实验法随机方向法随机方向法复合形法复合形法1.1. 实验设计法实验设计法约束直接搜索方法一一. .随机实验法随机实验法( (Monte-CarloMonte-Carlo法法) )(1) (1) 算法思想算法思想通过逐步随机取样通过逐步随机取样, ,逼近最优解逼近最优解. .每步随机取样得到一组点上的函数值每步随机取样得到一组点上的函数值, ,通过比较确定最优解通过比较确定最优解的较小范围

3、的较小范围. .下一步在上一步确定的范围内再随机取样下一步在上一步确定的范围内再随机取样, ,确定确定更小的最优解范围更小的最优解范围, ,如此下去如此下去, ,不断逼近最优解不断逼近最优解. .不断缩小最优解不断缩小最优解的范围的范围随机实验法随机实验法( (Monte-CarloMonte-Carlo法法) )(2) (2) 算法算法随机实验法随机实验法( (Monte-CarloMonte-Carlo法法) )(3) (3) 算法分析算法分析约束直接搜索方法算法简单算法简单, , 容易实现容易实现. .依概率收敛依概率收敛, ,即以概率为即以概率为1 1收敛到最优解收敛到最优解, ,但采

4、样点需要无穷多但采样点需要无穷多. .采样点多采样点多, ,运算量大运算量大, ,效率低效率低. .约束直接搜索方法二二. .随机方向法随机方向法(1) (1) 算法思想算法思想通过在当前点的附近随机采样，确定最速下降方向，进行有通过在当前点的附近随机采样，确定最速下降方向，进行有约束的一维搜索，找到新的点。约束的一维搜索，找到新的点。约束直接搜索方法二二. .随机方向法随机方向法(2) (2) 算法算法- -初始点生成初始点生成约束直接搜索方法二二. .随机方向法随机方向法(2) (2) 算法算法- -搜索方向生成搜索方向生成约束直接搜索方法二二. .随机方向法随机方向法(2) (2) 算法

5、算法- -步骤步骤约束直接搜索方法二二. .复合形法复合形法(1) (1) 算法思想算法思想对于对于n n维变量空间维变量空间, ,单纯形是单纯形是n+1n+1个顶点个顶点. .复合形法是多个单纯形合并成的超多面体复合形法是多个单纯形合并成的超多面体, ,顶点数顶点数 n+1.n+1.复合形法与复合形法与单纯形无约束直接搜索法单纯形无约束直接搜索法极为相似极为相似, ,其不同之处其不同之处: :1.1.复合形法不限制顶点个数为复合形法不限制顶点个数为n+1,n+1,复合形法顶点个数是复合形法顶点个数是k, k, 2n 2n k k n+1.n+1.2.2.复合形法需要检查顶点的可行性复合形法需

6、要检查顶点的可行性, , 即是否满足约束即是否满足约束. .初始复合形法生成初始复合形法生成复合形法复合形法(2) (2) 算法算法XcXl转（转（3）复合形法复合形法(2) (2) 算法算法约束直接搜索方法二二. .复合形法复合形法(3) (3) 算法分析算法分析1.1.适应性强适应性强, ,无需导数无需导数. .2.2.程序较简单程序较简单. .3.3.当变量与约束较多时当变量与约束较多时, ,计算效率显著降低计算效率显著降低. .4.4.当当n n 5 5时时, ,可取可取k=2n,k=2n,当当n5n5时时, ,可取可取k2n.k2n.约束直接搜索方法三三. .实验设计法实验设计法(

7、(Design Of Experiments, DOE)Design Of Experiments, DOE)(1) (1) 算法思想算法思想通过合理的采样和统计分析通过合理的采样和统计分析, ,得到优化问题总体变化趋势得到优化问题总体变化趋势, ,为进一步搜索提供基础为进一步搜索提供基础. .试验设计试验设计试验设计试验设计1234 1 1 1 3 2 2 2 1 1 1 3 3 1 2 3 4 1 2 2 1 5 2 2 3 3 6 3 2 1 2 7 1 3 1 3 8 2 3 2 2 9 3 3 3 1在一列中每一水平值出现频率相等：在一列中每一水平值出现频率相等： 出现次数出现次数

8、= =实验数实验数/ /水平数水平数; ; 1 1出现次数出现次数 =9/3=3 =9/3=3在两列中每两水平值组合在两列中每两水平值组合( (L L1 1,L,L2 2) )出现出现频率相等：频率相等： 出现次数出现次数= =实验数实验数/(/(列列1 1水平数水平数* *列列2 2水水平数平数);); (2,1) (2,1)出现次数出现次数=9/(3=9/(3* *3)=13)=1试验设计试验设计试验设计ANOVA （Analysis of Variance）变差分析变差分析:红色红色: : 负影响负影响蓝色蓝色: : 正影响正影响影响幅度大影响幅度大影响幅度小影响幅度小试验设计试验设计试

9、验设计试验设计试验设计试验设计试验设计ANOVA 分析结果分析结果:1616次实验次实验, , sfc sfc 的两个的两个水平上各计算水平上各计算8 8个点个点, ,8 8个点上的平均个点上的平均RangeRange值变化如右图值变化如右图, , 是是sfcsfc对对RangeRange的主效应图的主效应图. .在在8 8个点中，个点中，sfcsfc相同，但相同，但其他设计变量的变化，引其他设计变量的变化，引起起RangeRange变化。变化。试验设计ANOVA 分析结果分析结果: :单因子主效应图单因子主效应图多因子主效应图多因子主效应图试验设计PricemfrrangePricemfrr

10、angeInteraction effectsrange 的变化对的变化对mfr-price 关系有影响关系有影响试验设计试验设计试验设计在在range相同的条件下相同的条件下, 计算计算Mfr的均差的均差.计算不同计算不同range的的Mfr 效果的变化效果的变化.在短航程中在短航程中,Airbus比比Boeing贵平贵平均均$4.8M在长航程中在长航程中,Airbus比比Boeing贵平贵平均均$0.45M随着航程的增加随着航程的增加, Airbus比比Boeing高高出的价格在减小出的价格在减小试验设计试验设计WingArea=LowWingArea=HighCruiseVelCruis

11、eVelAircraftRangeCruiseVelWingArea1.1.评估设计变量对目标性能的影响评估设计变量对目标性能的影响, ,确定确定最有影响的设计最有影响的设计变量变量. .2.2.找出设计变量之间的找出设计变量之间的重要相互作用重要相互作用. .3.3.对设计空间作大致的分析对设计空间作大致的分析, ,找出最优解在设计空间中的找出最优解在设计空间中的大致位置大致位置, ,为优化搜索算法为优化搜索算法提供初始搜索起点提供初始搜索起点. .4.4.通过粗略计算分析通过粗略计算分析, ,剔除对性能目标函数不取作用的设剔除对性能目标函数不取作用的设计变量计变量, ,使得优化使得优化搜索空间减小搜索空间减小. .5.5.为为响应面近似响应面近似计算原始数据计算原始数据. .约束直接搜索方法DOE的作用的作用约束直接搜索方法约束直接搜索方法总结总结Monte-CarloMonte-Carlo法法-程序简单，程序简单，应用较广应用较广；但但随机采样效率较低。随机采样效率较低。复合形法复合形法-继承传统无约束问题精确搜索计算的特点。继承传统无约束问题精确搜索计算的特点。随机方向法随机方向法结合随机采样与精确搜索的优点。结合随机采样与精确搜索的优点。DOEDOE法法-简单实用简单实用, , 在优化设计中具有重要作用。在优化设计中具有重