《穷举法的升级-均匀设计优化方法》由会员分享，可在线阅读，更多相关《穷举法的升级-均匀设计优化方法（3页珍藏版）》请在金锄头文库上搜索。
1、第 11卷? 第 2期? 2011年 1月 1671?1815(2011) 2?0371?03? 科? 学? 技? 术? 与? 工 ? 程 Science Technology and Engineering ?Vol ?11? No ?2? Jan?2011 ? ?2011?Sci ?Tech?Engng ? 均匀设计优化方法 高? 毅 1? 高? 尚2 * (镇江日报社1, 镇江 212001 ; 江苏科技大学计算机科学与工程学院2, 镇江 212003) 摘? 要? 在网格法的基础上, 根据均匀设计法原理, 提出一种解决非线性规划的新的直接法。并给出了 M atlab源程序, 实例 表明
2、该方法是简单和可行的。 关键词? 均匀设计? 非线性规划? ? 网格法 中图法分类号?TP301 . 6 ; ? ? ? ? 文献标志码? A 2010年 10月 23日收到 第一作者简介: 高? 毅 ( 1959?), 男, 高级工程师。 * 通信作者简介: 高? 尚 ( 1972?), 男, 江苏镇江人, 博士, 教授, 研 究方向: 模式识别与人工智能。 ? 对于非线性规划, 目前还没有一种适合各种问 题的解法, 各种方法都有自己特定的适用范围。对 于解析法, 要求目标函数与约束函数具有连续性并 且其导数存在。但在某些实际问题中, 由于目标函 数很复杂, 有时甚至无法写出其表达式, 当然
3、更无 法求得其导数, 这样解析法就不再适用了。此时常 采用直接法, 这类方法的算法也很多, 代表性的有 网格法, 现在在网格法的基础上, 提出一种均匀设 计法。 1? 网格法 网格法是最简单的一种直接法, 实际上它是一 种穷举法。设非线性规划为 m in f (X ) s . . tsi(X ) ?0 , i= 1, 2 , ?, m(1) X? E n 假定变量的取值范围为已知: xja? xj? xjb( j= 1, 2 , ?, n), 如问题无上、 下界约束, 则可根据问题的 性质估计一下最优解的范围。 网格法 1就是在变量区域内打网格, 在网格点 上求约束函数与目标函数的值, 对于满
4、足约束条件 的点, 再比较其目标函数的大小, 从中选择小者, 并 把该网格点作为一次迭代的结果。然后在求出的 点附近将分点加密, 再打网格, 并重复前述计算与 比较, 直到网格的间距小于预先给定的精度, 终止 迭代。 网格法方法简单, 应用时不要求繁琐的公式推 导, 减少了准备工作。若对 xj的区间 xja, xjb分成 rj( j= 1 , 2, ?, n)等分, 在一次迭代要计算 (r1+ 1) ? ( r2+ 1)? (rn+ 1)个网格点。例如有 2个变量, 对 每个变量分成 10等分, 则一次迭代要计算 11 2 次。 所以说网格法计算量极大, 尤其是高维问题, 工作 量更大。 2?
5、 均匀设计优化法 均匀设计法的思想是从大量的网格点中选择 有代表性的几个点, 计算比较, 避免计算所有网格 点, 选择代表网格点的要求均匀分散。根据均匀设 计的思想, 方开泰等给使用者提供了一套均匀设 计表 2 , 3。 均匀设计优化法具体算法如下。 ( 1) 给定 ? 0, 估计 xj的区域 xja, xjb ( j= 1 , 2 , ?, n), 给定区间划分数N (N 2n)。 ( 2) 找出均匀设计表 UN + 1( (N + 1) N ), 根据推 荐表使用 N 列中的 n 列, 这 n 列数据可看成 (N + 1) ?n的矩阵, 记为 C= ( cij)(N+ 1) ?n。 ( 3
6、) 计算 xj的间距 hj= xjb- xja N , (j= 1 , 2 , ?, n)。 ( 4) 计算 N + 1个均匀点, 第 k 个均匀点坐标 (xk1, xk2, ?, xkn) ( xkj= xja+ ( ckj- 1) hj, ( j= 1 , 2, ?, n) ), 计算这 N + 1个点目标值和判断约束条件, 找 出比较小的解 (x * 1, x * 2, ?, x * n)。 ( 5) 若 hj? ? , ( j= 1 , 2 , ?, n)则终止, 否则确定 新区域, 变量 xj的区域下界: xja= x * j- 3hj, 区域上 界: xjb= x * j+ 3hj
7、, 转入 ( 3)。 下面举一简单例子说明如何用均匀设计表优 化计算。 例: m inf= x 2 1+ x1x2+ 0 . 5x 2 2- 0 . 2x2 s . . t- 1? x1? 1 ; - 1? x2? 1 。 对区间 10等分 h1= h2= 0 . 2 , 采用 U11( 11 10 ) 表, 这里有 2个变量, 采用表推荐使用的 1 、5两 列, 这2 列 数 据 组 成 的 矩 阵,C11? 2= 1? 2?3? 4? 5?6? 7?8?9? 10?11 5? 10?4?9? 3?8? 2? 7?1? 6?11 T ,计 算 ( - 1 . 0, - 0 . 2), ( -
8、 0 . 8, 0 . 8), ( - 0 . 6 , - 0 . 4), ( - 0 . 4, 0 . 6), ( - 0 . 2 , - 0 . 6), ( 0 . 0 , 0. 4), ( 0 . 2, - 0 . 8), ( 0 . 4 , 0. 2), ( 0. 6 , - 1 . 0), ( 0 . 8 , 0 . 0), ( 1 . 0 , 1 . 0) 11个均匀点的目标值 (表 1)。 表 1? 第一次迭代结果 均匀点 x1x2 f 1- 1. 000 000- 0. 200 0001 . 260 000 2- 0. 800 0000. 800 0000 . 160 000
9、3- 0. 600 000- 0. 400 0000 . 760 000 4- 0. 400 0000. 600 000- 0 . 020 000 5- 0. 200 000- 0. 600 0000 . 460 000 60. 000 0000. 400 0000 . 000 000 70. 200 000- 0. 800 0000 . 360 000 80. 400 0000. 200 0000 . 220 000 90. 600 000- 1. 000 0000 . 460 000 100. 800 0000. 000 0000 . 640 000 111. 000 0001. 000
10、0002 . 300 000 在 11个目标函数值中, (x1, x2) = ( - 0 . 4 , 0 . 6) 的目标值 f = - 0 . 02最小, x1的下一次迭代区间 x1a, x1b = - 0 . 4- 0 . 2 ? 3 , - 0 . 4+ 0. 2 ? 3 = - 1 , 0 . 2, x2的下一次迭代区间 x2a, x2b = 0 . 6- 0 . 2 ? 3 , 0 . 6+ 0 . 2 ? 3 = 0, 1 . 2, h1= h2= 0 . 12 , 再计算下 11个均匀点的目标值 (表 2)。 (x1, x2) = ( - 0 . 04 , 0 . 0)的目标值
11、f = 0 . 001 6最小, 减 小迭代区间, 重新计算均匀点, 计算目标值与找最 小值, 重复上述步骤, 直到网格的间距小于预先给 定的精度 0 . 001 , 进过 11次迭代, 最后得到最满意 解 (x * 1, x * 2) = ( - 0 . 199 885 , 0 . 398 871),f * = - 0 . 039 999 。 表 2? 第二次迭代结果 均匀点 x1x2 f 1- 1 . 000 0000 . 480 0000 . 539 200 2- 0 . 880 0001 . 080 0000 . 191 200 3- 0 . 760 0000 . 360 0000 .
12、 296 800 4- 0 . 640 0000 . 960 0000 . 064 000 5- 0 . 520 0000 . 240 0000 . 126 400 6- 0 . 400 0000 . 840 0000 . 008 800 7- 0 . 280 0000 . 120 0000 . 028 000 8- 0 . 160 0000 . 720 0000 . 025 600 9- 0 . 040 0000 . 000 0000 . 001 600 100 . 080 0000 . 600 0000 . 114 400 110 . 200 0001 . 200 0000 . 760 0
13、00 此方法比网络法明显的优点是计算量减少了, 如上例中, 对于一次迭代只计算 11次, 而采用网络 法要计算 121次! 这种方法迭代一定次数完全可以 满足精度, 而且用此算法很容易编制成计算机程序。 利用 M atlab编制的主程序如下: x l= - 1 ; xu= 1 ; y l= - 1 ; yu= 1 ; hx= ( xu- xl) /10 ; hy= ( yu- yl) /10 ; while ( ( hx 0. 001) |( hy 0 . 001) ) ox , l oxu , oy,l oyu , x, y , ox, oy = unifor m( x,l xu, y,l
14、yu) x l= ox;l xu= oxu ; y l= oy;l yu= oyu ; 372科? 学 ? 技? 术? 与? 工? 程11卷 hx= ( xu- x l) /10 ; hy= ( yu- yl) /10 ; end 均匀优化设计的子程序 unifor m. m 如下: function ox, l oxu, oy, l oyu, x, y, ox, oy, fmin = unifor m( x, l xu, y, l yu) umn= 1 2 3 4 5 6 7 8 9 10 11 ; 5 10 4 9 3 8 2 7 1 6 11 ?; hx= ( xu- x l) /10
15、; hy= ( yu- yl) /10 ; for i= 1 : 11 x( i) = x l+ ( umn( , i 1) - 1)* hx; y( i) = y l+ ( umn( , i 2) - 1)* hy; f( i) = x( i) 2+ x( i)* y( i) + 0 . 5 * y( i) 2- 0 . 2 * y( i); end fmin j = m in( f) ox= x( j); oy= y( j); ox l= x( j) - 3* hx; oxu= x( j) + 3 * hx; oy l= y( j) - 3* hy; oyu= y( j) + 3 * hy
16、; 参? 考? 文? 献 1? 鲍顺光. 优化方法与电路优化设计. 东南大学出版社, 1992: 30? 47 2? 方开泰. 均匀设计? 数论方法在试验设计的应用. 应用数学学 报, 1980; 3( 4): 363? 372 3? 方开泰, 马长兴. 正交与均匀试验设计. 北京: 科学出版社, 2001 : 3?34 附表 1? U11( 1110) 12345678910 112345678910 224681013579 336914710258 448159261037 551049382716 661728394105 773106295184 885210741963 997531108642 1010987654321 1111111111111111111111 附表 2? U11( 11 10 )表的使用 因素数列号 215 3157 41257 512357 61235710 Research on Uniform Design in Optim ization GAO
