均匀设计优化方法

第11卷 第2期 2011年1月1671 1815(2011)2 0371 03

科 学 技 术 与 工 程

ScienceTechnologyandEngineering

11 No 2 Jan 2011 Vol

2011 Sci Tech Engng

均匀设计优化方法

高 毅 高 尚

1

2*

(镇江日报社1,镇江212001;江苏科技大学计算机科学与工程学院2,镇江212003)

摘 要 在网格法的基础上,根据均匀设计法原理,提出一种解决非线性规划的新的直接法。并给出了Matlab源程序,实例表明该方法是简单和可行的。

关键词 均匀设计 非线性规划 网格法中图法分类号 TP301.6; 文献标志码

A

对于非线性规划,目前还没有一种适合各种问题的解法,各种方法都有自己特定的适用范围。对于解析法,要求目标函数与约束函数具有连续性并且其导数存在。但在某些实际问题中,由于目标函数很复杂,有时甚至无法写出其表达式,当然更无法求得其导数,这样解析法就不再适用了。此时常采用直接法,这类方法的算法也很多,代表性的有网格法,现在在网格法的基础上,提出一种均匀设计法。

的点,再比较其目标函数的大小,从中选择小者,并把该网格点作为一次迭代的结果。然后在求出的点附近将分点加密,再打网格,并重复前述计算与比较,直到网格的间距小于预先给定的精度,终止迭代。

网格法方法简单,应用时不要求繁琐的公式推导,减少了准备工作。若对xj的区间[xja,xjb]分成rj(j=1,2,!,n)等分,在一次迭代要计算(r1+1)∃(r2+1)!(rn+1)个网格点。例如有2个变量,对每个变量分成10等分,则一次迭代要计算11次。所以说网格法计算量极大,尤其是高维问题,工作量更大。

2

1 网格法

网格法是最简单的一种直接法,实际上它是一种穷举法。设非线性规划为

minf(X)

s..t

si(X) 0,i=1,2,!,m

X∀E

n

2 均匀设计优化法

(1)

均匀设计法的思想是从大量的网格点中选择有代表性的几个点,计算比较,避免计算所有网格点,选择代表网格点的要求均匀分散。根据均匀设计的思想,方开泰等给使用者提供了一套均匀设计表

[2,3]

假定变量的取值范围为已知:xja#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 ),男,江苏镇江人,博士,教授,研

究方向:模式识别与人工智能。

372

(3)计算xj的间距hj=

科 学 技 术 与 工 程11卷

xjb-xja

(j=1,2,!,n)。N

[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)的目标值f=0.0016最小,减小迭代区间,重新计算均匀点,计算目标值与找最小值,重复上述步骤,直到网格的间距小于预先给定的精度0.001,进过11次迭代,最后得到最满意解(x1,x2)=(-0.199885,0.398871),f=-0.039999。

表2 第二次迭代结果

x1

-1.000000-0.880000-0.760000-0.640000-0.520000-0.400000-0.280000-0.160000-0.0400000.0800000.200000

x20.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个点目标值和判断约束条件,找出比较小的解(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列数据组成的矩阵,C11∃2=1 2 3 4 5 6 7 8 9 10

5 10 4 9 3 8 2 7 1 6 T

10

2

1

22

*

*j

*1

*2

*n

均匀点123456

f0.5392000.1912000.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 第一次迭代结果

均匀点

[1**********]11

x1

-1.000000-0.800000-0.600000-0.400000-0.2000000.0000000.2000000.4000000.6000000.8000001.000000

x2

-0.2000000.800000-0.4000000.600000-0.6000000.400000-0.8000000.200000-1.0000000.0000001.000000

f1.2600000.1600000.760000-0.0200000.4600000.0000000.3600000.2200000.4600000.6400002.300000

此方法比网络法明显的优点是计算量减少了,如上例中,对于一次迭代只计算11次,而采用网络法要计算121次!这种方法迭代一定次数完全可以满足精度,而且用此算法很容易编制成计算机程序。

利用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,x1

2期

hx=(xu-xl)/10;hy=(yu-yl)/10;end

高 毅,等:均匀设计优化方法

373

3 方开泰,马长兴.正交与均匀试验设计.北京:科学出版社,

2001:3 34

均匀优化设计的子程序uniform.m如下:

function[ox,loxu,oy,loyu,x,y,ox,oy,fmin]=uniform(x,lxu,y,lyu)

umn=[[1**********]11;[1**********]11]%;hx=(xu-xl)/10;hy=(yu-yl)/10;fori=1:11

x(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);end

[fminj]=min(f)ox=x(j);oy=y(j);oxl=x(j)-3*hx;oxu=x(j)+3*hx;oyl=y(j)-3*hy;oyu=y(j)+3*hy;

[1**********]11

附表1 U11(1110)

[1**********]011

[1**********]911

[1**********]811

[1**********]711

[1**********]611

[1**********]511

[1**********]411

[1**********]311

[1**********]211

[**************]

附表2 U11(1110)表的使用

因素数23

11111

55222

7533

755

77

10

列号

参 考 文 献

1 鲍顺光.优化方法与电路优化设计.东南大学出版社,1992:

30 47

2 方开泰.均匀设计 数论方法在试验设计的应用.应用数学学报,1980;3(4):363 372

456

ResearchonUniformDesigninOptimization

GAOYi,GAOShang

1

2

(ZhenjiangDaily1,Zhenjiang212001,P.R.China;SchoolofComputerScienceandEngineering,Jiangsu

UniversityofScienceandTechnology2,Zhenjiang212003,P.R.China)

[Abstract] Onthebasisofgridoptimizationmethodanduniformdesigntheory,anewoptimizationalgorithmfornonlinearprogrammingisputforward.TheMatlabsourcecodeisgivenandthepracticalcalculationshowsthemethodissimpleandfeasiblebyexamples.[Keywords]

uniform design nonlinear programming gridoptimizationmethod

第11卷 第2期 2011年1月1671 1815(2011)2 0371 03

科 学 技 术 与 工 程

ScienceTechnologyandEngineering

11 No 2 Jan 2011 Vol

2011 Sci Tech Engng

均匀设计优化方法

高 毅 高 尚

1

2*

(镇江日报社1,镇江212001;江苏科技大学计算机科学与工程学院2,镇江212003)

摘 要 在网格法的基础上,根据均匀设计法原理,提出一种解决非线性规划的新的直接法。并给出了Matlab源程序,实例表明该方法是简单和可行的。

关键词 均匀设计 非线性规划 网格法中图法分类号 TP301.6; 文献标志码

A

对于非线性规划,目前还没有一种适合各种问题的解法,各种方法都有自己特定的适用范围。对于解析法,要求目标函数与约束函数具有连续性并且其导数存在。但在某些实际问题中,由于目标函数很复杂,有时甚至无法写出其表达式,当然更无法求得其导数,这样解析法就不再适用了。此时常采用直接法,这类方法的算法也很多,代表性的有网格法,现在在网格法的基础上,提出一种均匀设计法。

的点,再比较其目标函数的大小,从中选择小者,并把该网格点作为一次迭代的结果。然后在求出的点附近将分点加密,再打网格,并重复前述计算与比较,直到网格的间距小于预先给定的精度,终止迭代。

网格法方法简单,应用时不要求繁琐的公式推导,减少了准备工作。若对xj的区间[xja,xjb]分成rj(j=1,2,!,n)等分,在一次迭代要计算(r1+1)∃(r2+1)!(rn+1)个网格点。例如有2个变量,对每个变量分成10等分,则一次迭代要计算11次。所以说网格法计算量极大,尤其是高维问题,工作量更大。

2

1 网格法

网格法是最简单的一种直接法,实际上它是一种穷举法。设非线性规划为

minf(X)

s..t

si(X) 0,i=1,2,!,m

X∀E

n

2 均匀设计优化法

(1)

均匀设计法的思想是从大量的网格点中选择有代表性的几个点,计算比较,避免计算所有网格点,选择代表网格点的要求均匀分散。根据均匀设计的思想,方开泰等给使用者提供了一套均匀设计表

[2,3]

假定变量的取值范围为已知:xja#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 ),男,江苏镇江人,博士,教授,研

究方向:模式识别与人工智能。

372

(3)计算xj的间距hj=

科 学 技 术 与 工 程11卷

xjb-xja

(j=1,2,!,n)。N

[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)的目标值f=0.0016最小,减小迭代区间,重新计算均匀点,计算目标值与找最小值,重复上述步骤,直到网格的间距小于预先给定的精度0.001,进过11次迭代,最后得到最满意解(x1,x2)=(-0.199885,0.398871),f=-0.039999。

表2 第二次迭代结果

x1

-1.000000-0.880000-0.760000-0.640000-0.520000-0.400000-0.280000-0.160000-0.0400000.0800000.200000

x20.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个点目标值和判断约束条件,找出比较小的解(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列数据组成的矩阵,C11∃2=1 2 3 4 5 6 7 8 9 10

5 10 4 9 3 8 2 7 1 6 T

10

2

1

22

*

*j

*1

*2

*n

均匀点123456

f0.5392000.1912000.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 第一次迭代结果

均匀点

[1**********]11

x1

-1.000000-0.800000-0.600000-0.400000-0.2000000.0000000.2000000.4000000.6000000.8000001.000000

x2

-0.2000000.800000-0.4000000.600000-0.6000000.400000-0.8000000.200000-1.0000000.0000001.000000

f1.2600000.1600000.760000-0.0200000.4600000.0000000.3600000.2200000.4600000.6400002.300000

此方法比网络法明显的优点是计算量减少了,如上例中,对于一次迭代只计算11次,而采用网络法要计算121次!这种方法迭代一定次数完全可以满足精度,而且用此算法很容易编制成计算机程序。

利用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,x1

2期

hx=(xu-xl)/10;hy=(yu-yl)/10;end

高 毅,等:均匀设计优化方法

373

3 方开泰,马长兴.正交与均匀试验设计.北京:科学出版社,

2001:3 34

均匀优化设计的子程序uniform.m如下:

function[ox,loxu,oy,loyu,x,y,ox,oy,fmin]=uniform(x,lxu,y,lyu)

umn=[[1**********]11;[1**********]11]%;hx=(xu-xl)/10;hy=(yu-yl)/10;fori=1:11

x(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);end

[fminj]=min(f)ox=x(j);oy=y(j);oxl=x(j)-3*hx;oxu=x(j)+3*hx;oyl=y(j)-3*hy;oyu=y(j)+3*hy;

[1**********]11

附表1 U11(1110)

[1**********]011

[1**********]911

[1**********]811

[1**********]711

[1**********]611

[1**********]511

[1**********]411

[1**********]311

[1**********]211

[**************]

附表2 U11(1110)表的使用

因素数23

11111

55222

7533

755

77

10

列号

参 考 文 献

1 鲍顺光.优化方法与电路优化设计.东南大学出版社,1992:

30 47

2 方开泰.均匀设计 数论方法在试验设计的应用.应用数学学报,1980;3(4):363 372

456

ResearchonUniformDesigninOptimization

GAOYi,GAOShang

1

2

(ZhenjiangDaily1,Zhenjiang212001,P.R.China;SchoolofComputerScienceandEngineering,Jiangsu

UniversityofScienceandTechnology2,Zhenjiang212003,P.R.China)

[Abstract] Onthebasisofgridoptimizationmethodanduniformdesigntheory,anewoptimizationalgorithmfornonlinearprogrammingisputforward.TheMatlabsourcecodeisgivenandthepracticalcalculationshowsthemethodissimpleandfeasiblebyexamples.[Keywords]

uniform design nonlinear programming gridoptimizationmethod