均匀设计优化方法

1、第11卷 第2期 2011年1月1671 1815(2011)2 0371 03科 学 技 术 与 工 程ScienceTechnologyandEngineering11 No 2 Jan 2011 Vol2011 Sci Tech Engng均匀设计优化方法高 毅 高 尚2*(镇江日报社1,镇江212001;江苏科技大学计算机科学与工程学院2,镇江212003)摘 要 在网格法的基础上,根据均匀设计法原理,提出一种解决非线性规划的新的直接法。并给出了Matlab源程序,实例表明该方法是简单和可行的。关键词 均匀设计 非线性规划 网格法中图法分类号 TP301.6; 文献标志码A对于非线性规

2、划,目前还没有一种适合各种问题的解法,各种方法都有自己特定的适用范围。对于解析法,要求目标函数与约束函数具有连续性并且其导数存在。但在某些实际问题中,由于目标函数很复杂,有时甚至无法写出其表达式,当然更无法求得其导数,这样解析法就不再适用了。此时常采用直接法,这类方法的算法也很多,代表性的有网格法,现在在网格法的基础上,提出一种均匀设计法。的点,再比较其目标函数的大小,从中选择小者,并把该网格点作为一次迭代的结果。然后在求出的点附近将分点加密,再打网格,并重复前述计算与比较,直到网格的间距小于预先给定的精度,终止迭代。网格法方法简单,应用时不要求繁琐的公式推导,减少了准备工作。若对xj的区间x

3、ja,xjb分成rj(j=1,2,!,n)等分,在一次迭代要计算(r1+1)(r2+1)!(rn+1)个网格点。例如有2个变量,对每个变量分成10等分,则一次迭代要计算11次。所以说网格法计算量极大,尤其是高维问题,工作量更大。21 网格法网格法是最简单的一种直接法,实际上它是一种穷举法。设非线性规划为minf(X)s.tsi(X) 0,i=1,2,!,mXEn2 均匀设计优化法(1)均匀设计法的思想是从大量的网格点中选择有代表性的几个点,计算比较,避免计算所有网格点,选择代表网格点的要求均匀分散。根据均匀设计的思想,方开泰等给使用者提供了一套均匀设计表2,3假定变量的取值范围为已知:xja#

4、xj#xjb(j=1,2,!,n),如问题无上、下界约束,则可根据问题的性质估计一下最优解的范围。网格法1就是在变量区域内打网格,在网格点。上求约束函数与目标函数的值,对于满足约束条件2010年10月23日收到第一作者简介:高 毅(1959 ),男,高级工程师。*均匀设计优化法具体算法如下。(1)给定 >0,估计xj的区域xja,xjb(j=1,2,!,n),给定区间划分数N(N>2n)。(2)找出均匀设计表UN+1(N+1),根据推荐表使用N列中的n列,这n列数据可看成(N+1=(cij)+1)nN通信作者简介:高 尚(1972 ),男,江苏镇江人,博士,教授,研究方向:模式识别

5、与人工智能。372(3)计算xj的间距hj=科 学 技 术 与 工 程11卷xjb-xja(j=1,2,!,n)。Nx1a,x1b=-0.4-0.23,-0.4+0.23=-1,0.2,x2的下一次迭代区间x2a,x2b=0.6-0.23,0.6+0.23=0,1.2,h1=h2=0.12,再计算下11个均匀点的目标值(表2)。(x1,x2)=(-0.04,0.0)的目标值f=0.0016最小,减小迭代区间,重新计算均匀点,计算目标值与找最小值,重复上述步骤,直到网格的间距小于预先给定的精度0.001,进过11次迭代,最后得到最满意解(x1,x2)=(-0.199885,0.398871),f

6、=-0.039999。表2 第二次迭代结果x1-1.000000-0.880000-0.760000-0.640000-0.520000-0.400000-0.280000-0.160000-0.0400000.0800000.200000x20.4800001.0800000.3600000.9600000.2400000.8400000.1200000.7200000.0000000.6000001.200000*(4)计算N+1个均匀点,第k个均匀点坐标(xk1,xk2,!,xkn)(xkj=xja+(ckj-1)hj,(j=1,2,!,n),计算这N+1个点目标值和判断约束条件,找出比

7、较小的解(x,x,!,x)。(5)若hj# ,(j=1,2,!,n)则终止,否则确定新区域,变量xj的区域下界:xja=x-3hj,区域上界:xjb=xj+3hj,转入(3)。下面举一简单例子说明如何用均匀设计表优化计算。例:minf=x+x1x2+0.5x-0.2x2s.t-1#x1#1;-1#x2#1。对区间10等分h1=h2=0.2,采用U11(11)表,这里有2个变量,采用表推荐使用的1、5两列,这2列数据组成的矩阵,C112=1 2 3 4 5 6 7 8 9 105 10 4 9 3 8 2 7 1 6 T10122*j*1*2*n均匀点123456f0.5392000.19120

8、00.2968000.0640000.1264000.0088000.0280000.0256000.0016000.1144000.760000,计算7891011(-1.0,-0.2),(-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 第一次迭代结果均匀点1234567891011x1-1.000000-0.800000-0.600000-0.400000-0.2000000.0000000.

9、2000000.4000000.6000000.8000001.000000x2-0.2000000.800000-0.4000000.600000-0.6000000.400000-0.8000000.200000-1.0000000.0000001.000000f1.2600000.1600000.760000-0.0200000.4600000.0000000.3600000.2200000.4600000.6400002.300000此方法比网络法明显的优点是计算量减少了,如上例中,对于一次迭代只计算11次,而采用网络法要计算121次!这种方法迭代一定次数完全可以满足精度,而且用此算法

10、很容易编制成计算机程序。利用Matlab编制的主程序如下:xl=-1;xu=1;yl=-1;yu=1;hx=(xu-xl)/10;hy=(yu-yl)/10;while(hx>0.001)|(hy>0.001)ox,loxu,oy,loyu,x,y,ox,oy=uniform(x,lxu,y,lyu)xl=ox;lxu=oxu;yl=oy;l在11个目标函数值中,(x1,x2)=(-0.4,0.6)f-0.02,x12期hx=(xu-xl)/10;hy=(yu-yl)/10;end高 毅,等:均匀设计优化方法3733 方开泰,马长兴.正交与均匀试验设计.北京:科学出版社,2001:

11、3 34均匀优化设计的子程序uniform.m如下:functionox,loxu,oy,loyu,x,y,ox,oy,fmin=uniform(x,lxu,y,lyu)umn=1234567891011;5104938271611%;hx=(xu-xl)/10;hy=(yu-yl)/10;fori=1:11x(i)=xl+(umn(,i1)-1)*hx;y(i)=yl+(umn(,i2)-1)*hy;f(i)=x(i)2+x(i)*y(i)+0.5*y(i)2-0.2*y(i);endfminj=min(f)ox=x(j);oy=y(j);oxl=x(j)-3*hx;oxu=x(j)+3*h

12、x;oyl=y(j)-3*hy;oyu=y(j)+3*hy;1234567891011附表1 U11(1110)112345678910112246810135791133691471025811448159261037115510493827161166172839410511773106295184118852107419631199753110864211101098765432111附表2 U11(1110)表的使用因素数23111115522275337557710列号参 考 文 献1 鲍顺光.优化方法与电路优化设计.东南大学出版社,1992:30 472 方开泰.均匀设计 数论方法

13、在试验设计的应用.应用数学学报,1980;3(4):363 372456ResearchonUniformDesigninOptimizationGAOYi,GAOShang12(ZhenjiangDaily1,Zhenjiang212001,P.R.China;SchoolofComputerScienceandEngineering,JiangsuUniversityofScienceandTechnology2,Zhenjiang212003,P.R.China)Abstract Onthebasisofgridoptimizationmethodanduniformdesigntheory,anewoptimizational