均勻設(shè)計(jì)優(yōu)化方法

1、第11卷 第2期 2011年1月1671 1815(2011)2 0371 03科 學(xué) 技 術(shù) 與 工 程ScienceTechnologyandEngineering11 No 2 Jan 2011 Vol2011 Sci Tech Engng均勻設(shè)計(jì)優(yōu)化方法高 毅 高 尚2*(鎮(zhèn)江日?qǐng)?bào)社1,鎮(zhèn)江212001;江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院2,鎮(zhèn)江212003)摘 要 在網(wǎng)格法的基礎(chǔ)上,根據(jù)均勻設(shè)計(jì)法原理,提出一種解決非線性規(guī)劃的新的直接法。并給出了Matlab源程序,實(shí)例表明該方法是簡(jiǎn)單和可行的。關(guān)鍵詞 均勻設(shè)計(jì) 非線性規(guī)劃 網(wǎng)格法中圖法分類號(hào) TP301.6; 文獻(xiàn)標(biāo)志碼A對(duì)于非線性規(guī)

2、劃,目前還沒有一種適合各種問題的解法,各種方法都有自己特定的適用范圍。對(duì)于解析法,要求目標(biāo)函數(shù)與約束函數(shù)具有連續(xù)性并且其導(dǎo)數(shù)存在。但在某些實(shí)際問題中,由于目標(biāo)函數(shù)很復(fù)雜,有時(shí)甚至無法寫出其表達(dá)式,當(dāng)然更無法求得其導(dǎo)數(shù),這樣解析法就不再適用了。此時(shí)常采用直接法,這類方法的算法也很多,代表性的有網(wǎng)格法,現(xiàn)在在網(wǎng)格法的基礎(chǔ)上,提出一種均勻設(shè)計(jì)法。的點(diǎn),再比較其目標(biāo)函數(shù)的大小,從中選擇小者,并把該網(wǎng)格點(diǎn)作為一次迭代的結(jié)果。然后在求出的點(diǎn)附近將分點(diǎn)加密,再打網(wǎng)格,并重復(fù)前述計(jì)算與比較,直到網(wǎng)格的間距小于預(yù)先給定的精度,終止迭代。網(wǎng)格法方法簡(jiǎn)單,應(yīng)用時(shí)不要求繁瑣的公式推導(dǎo),減少了準(zhǔn)備工作。若對(duì)xj的區(qū)間x

3、ja,xjb分成rj(j=1,2,!,n)等分,在一次迭代要計(jì)算(r1+1)(r2+1)!(rn+1)個(gè)網(wǎng)格點(diǎn)。例如有2個(gè)變量,對(duì)每個(gè)變量分成10等分,則一次迭代要計(jì)算11次。所以說網(wǎng)格法計(jì)算量極大,尤其是高維問題,工作量更大。21 網(wǎng)格法網(wǎng)格法是最簡(jiǎn)單的一種直接法,實(shí)際上它是一種窮舉法。設(shè)非線性規(guī)劃為minf(X)s.tsi(X) 0,i=1,2,!,mXEn2 均勻設(shè)計(jì)優(yōu)化法(1)均勻設(shè)計(jì)法的思想是從大量的網(wǎng)格點(diǎn)中選擇有代表性的幾個(gè)點(diǎn),計(jì)算比較,避免計(jì)算所有網(wǎng)格點(diǎn),選擇代表網(wǎng)格點(diǎn)的要求均勻分散。根據(jù)均勻設(shè)計(jì)的思想,方開泰等給使用者提供了一套均勻設(shè)計(jì)表2,3假定變量的取值范圍為已知:xja#

4、xj#xjb(j=1,2,!,n),如問題無上、下界約束,則可根據(jù)問題的性質(zhì)估計(jì)一下最優(yōu)解的范圍。網(wǎng)格法1就是在變量區(qū)域內(nèi)打網(wǎng)格,在網(wǎng)格點(diǎn)。上求約束函數(shù)與目標(biāo)函數(shù)的值,對(duì)于滿足約束條件2010年10月23日收到第一作者簡(jiǎn)介:高 毅(1959 ),男,高級(jí)工程師。*均勻設(shè)計(jì)優(yōu)化法具體算法如下。(1)給定 >0,估計(jì)xj的區(qū)域xja,xjb(j=1,2,!,n),給定區(qū)間劃分?jǐn)?shù)N(N>2n)。(2)找出均勻設(shè)計(jì)表UN+1(N+1),根據(jù)推薦表使用N列中的n列,這n列數(shù)據(jù)可看成(N+1=(cij)+1)nN通信作者簡(jiǎn)介:高 尚(1972 ),男,江蘇鎮(zhèn)江人,博士,教授,研究方向:模式識(shí)別

5、與人工智能。372(3)計(jì)算xj的間距hj=科 學(xué) 技 術(shù) 與 工 程11卷xjb-xja(j=1,2,!,n)。Nx1a,x1b=-0.4-0.23,-0.4+0.23=-1,0.2,x2的下一次迭代區(qū)間x2a,x2b=0.6-0.23,0.6+0.23=0,1.2,h1=h2=0.12,再計(jì)算下11個(gè)均勻點(diǎn)的目標(biāo)值(表2)。(x1,x2)=(-0.04,0.0)的目標(biāo)值f=0.0016最小,減小迭代區(qū)間,重新計(jì)算均勻點(diǎn),計(jì)算目標(biāo)值與找最小值,重復(fù)上述步驟,直到網(wǎng)格的間距小于預(yù)先給定的精度0.001,進(jìn)過11次迭代,最后得到最滿意解(x1,x2)=(-0.199885,0.398871),f

6、=-0.039999。表2 第二次迭代結(jié)果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)計(jì)算N+1個(gè)均勻點(diǎn),第k個(gè)均勻點(diǎn)坐標(biāo)(xk1,xk2,!,xkn)(xkj=xja+(ckj-1)hj,(j=1,2,!,n),計(jì)算這N+1個(gè)點(diǎn)目標(biāo)值和判斷約束條件,找出比

7、較小的解(x,x,!,x)。(5)若hj# ,(j=1,2,!,n)則終止,否則確定新區(qū)域,變量xj的區(qū)域下界:xja=x-3hj,區(qū)域上界:xjb=xj+3hj,轉(zhuǎn)入(3)。下面舉一簡(jiǎn)單例子說明如何用均勻設(shè)計(jì)表優(yōu)化計(jì)算。例:minf=x+x1x2+0.5x-0.2x2s.t-1#x1#1;-1#x2#1。對(duì)區(qū)間10等分h1=h2=0.2,采用U11(11)表,這里有2個(gè)變量,采用表推薦使用的1、5兩列,這2列數(shù)據(jù)組成的矩陣,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均勻點(diǎn)123456f0.5392000.19120

8、00.2968000.0640000.1264000.0088000.0280000.0256000.0016000.1144000.760000,計(jì)算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個(gè)均勻點(diǎn)的目標(biāo)值(表1)。表1 第一次迭代結(jié)果均勻點(diǎn)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此方法比網(wǎng)絡(luò)法明顯的優(yōu)點(diǎn)是計(jì)算量減少了,如上例中,對(duì)于一次迭代只計(jì)算11次,而采用網(wǎng)絡(luò)法要計(jì)算121次!這種方法迭代一定次數(shù)完全可以滿足精度,而且用此算法

10、很容易編制成計(jì)算機(jī)程序。利用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個(gè)目標(biāo)函數(shù)值中,(x1,x2)=(-0.4,0.6)f-0.02,x12期hx=(xu-xl)/10;hy=(yu-yl)/10;end高 毅,等:均勻設(shè)計(jì)優(yōu)化方法3733 方開泰,馬長(zhǎng)興.正交與均勻試驗(yàn)設(shè)計(jì).北京:科學(xué)出版社,2001:

11、3 34均勻優(yōu)化設(shè)計(jì)的子程序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)表的使用因素?cái)?shù)23111115522275337557710列號(hào)參 考 文 獻(xiàn)1 鮑順光.優(yōu)化方法與電路優(yōu)化設(shè)計(jì).東南大學(xué)出版社,1992:30 472 方開泰.均勻設(shè)計(jì) 數(shù)論方法

13、在試驗(yàn)設(shè)計(jì)的應(yīng)用.應(yīng)用數(shù)學(xué)學(xué)報(bào),1980;3(4):363 372456ResearchonUniformDesigninOptimizationGAOYi,GAOShang12(ZhenjiangDaily1,Zhenjiang212001,P.R.China;SchoolofComputerScienceandEngineering,JiangsuUniversityofScienceandTechnology2,Zhenjiang212003,P.R.China)Abstract Onthebasisofgridoptimizationmethodanduniformdesigntheory,anewoptimizational