基于极大平面图矩形图元布局问题的全局优化算法

󰀁LudongUniversityJournal(NaturalScienceEdition)

2010,26(4):293󰀂296󰀁

基于极大平面图矩形图元布局问题的全局优化算法

翟金刚,张教军

(鲁东大学󰀁数学与信息学院,山东烟台264025)

摘要:以人造卫星仪器舱布局问题为背景,研究了矩形图元不干涉布局优化算法.基于极大平面图,通过逐次降低布局图边连通度的方法,构造了布局问题的全局优化算法,数值结果表明了算法的有效性.关键词:卫星舱布局;布局问题;矩形图元

中图分类号:O224󰀁󰀁文献标志码:A󰀁󰀁文章编号:1673󰀁8020(2010)04󰀁0293󰀁04

󰀁󰀁人造卫星仪器舱布局问题是航天设计中亟需解决的问题,属于组合优化的范畴,具有NP󰀁hard性.文[1]建立了布局优化的数学模型,并证明了目标函数的非凸性.文[2]给出了矩形图元在圆

形区域内的二维布局数学模型,利用图论、群论、对称群对图集的作用、轨道等理论首次提出将布局问题分解为有限个子问题,从而克服了问题由于时断时续性带来的困难,由此构造了布局问题的全局优化算法.文[3]建立了具有性能约束的三维布局优化模型,给出了其主要性质,并证明了性能目标函数为Lipschitz连续函数,且其局部最优解即为全局最优解.文[4󰀂5]给出了布局优化问题中各种图元的确切数学表示,建立了带有多种性能约束的布局优化模型,并给出了模型的一些性质和理论上的算法.由于布局问题中含有隐式不干涉约束,直接构造布局优化问题的下降方向是很困难的.文[6]利用坐标变换和凸集分离定理将隐式约束转化为了显式约束,通过将布局问题分解为有限个子问题,使布局问题的解决成为可能.但随着布局图元规模的增大,其子问题的个数呈指数级增长.尽管文[2]仅考虑连通的布局等价类,但其子问题的规模仍然是巨量的.

󰀁󰀁本文在极大平面图的基础上,通过逐次降低布局图的边连通度,将子问题进行分解并筛选,得到有限个子问题的局部最优解,由此构造了布局问题的全局优化算法.通过比较,得到布局问题的全局最优解.最后,对该算法进行了数值计算,通

󰀁󰀁收稿日期:2010󰀁05󰀁21;修回日期:2010󰀁06󰀁17

过结果对比,验证了算法的有效性.

1󰀁布局问题的数学模型

󰀁󰀁把n个矩形图元Fi,i In,In={1,2,!,n}固定在航天器的载盘上,记圆形载盘为C,以C的

圆心O为原点,建立直角坐标系X1OX2,如图1所示.数学模型

[2]

可表示为:

minf(Y),

s.t.intFi∀intFj=󰀂,i#j,,ij In,(P)

J(Y)=∃

%mx∃

ii

i=1

4n

n

&󰀁,

Y R.

图1󰀁图元布局图

其中,Fi=F(xi,ui,ai)={y=xi+t1ui+t2vi,t1

[-ai1,ai1],t2

[-ai2,ai2]},i

In;f󰀂i=

f󰀂i(xi,ui)=max{∃x∃,x Fi,i In};f(Y)=

󰀁󰀁作者简介:翟金刚(1973󰀂),男,内蒙古满洲里人。副教授,硕士研究生导师,主要研究方向为运筹学、布局、计算智能等。E󰀁mai:lzhaijingang@263.net。

󰀁294

T

鲁东大学学报(自然科学版)

T

T

第26卷󰀁

max{f󰀂i,i In};ai=(ai1,ai2);Y=(x1,u1,x2,u2,!,xn,un);xi表示图元Fi的形心,ui表示图元Fi的方向且∃ui∃=1,vi与ui正交,ui与vi满足右手定则;ai1和ai2分别是矩形图元长边与宽边的一半.设图元Fi的质心与形心重合,质量为mi,i In.󰀁(󰀁>0)为静不平衡量的允许值.对于确定的布局问题,󰀁,n,ai,mi,i In都是已知量,只有xi,ui,i In才是布局问题的优化变量.󰀁󰀁由于问题(P)中不干涉约束intFi∀intFj=󰀂,i#j,i,j In是隐式约束,无法在计算机上实现,因此需要将该隐式约束化为显式约束.令Hij1=|ui(xi-xj)|-aj1|uiuj|-aj2|uiuj|-ai1,Hij2=|vi(xi-xj)|-aj1|viuj|-aj2|vivj|-ai2,Hij3=|uj(xi-xj)|-ai1|uiuj|-ai2|uivj|-aj1,Hij4=|vj(xi-xj)|-ai1|viuj|-ai2|vivj|-aj2.󰀁󰀁文[7]依据坐标变换和凸集分离定理,把隐式不干涉约束化为显式约束,即对任意的图元Fi,Fj,i#j,i,j In,intFi∀intFj=󰀂的充要条件是Hij=max{Hij1,Hij2,Hij3,Hij4}∋0成立.󰀁󰀁从而,改进后的数学模型为:

minf(Y),

s..tHij∋0,i#j,i,j In,

(P1)

󰀁J(Y)=∃

(1)(2)

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

T

(V,E(Y)),称G(Y)为布局方案Y的图.若Y D,则称G(Y)为可行布局图;若Y Dn,则称

G(Y)为不干涉布局图.把问题(P1)的所有可行布局图与不干涉布局图的集合分别记为

G={G(Y),Y D},Gn={G(Y),Y Dn}.󰀁󰀁定义3󰀁若图G(Y1)=(V,,E(Y1))与G(Y2)=(V,E(Y2))满足E(Y1)=E(Y2),Y1,Y2 Dn,则称G(Y1)与G(Y2)为等价布局图,记为G(Y1)=G(Y2).

󰀁󰀁定义4󰀁设Y1,Y2 Dn,若其布局图G(Y1)与G(Y2)为等价布局图,则称布局方案Y1与Y2为同构布局方案,否则称Y1与Y2为不同构布局方案.集合I(Y1)={Y Dn,E(Y)=E(Y1)}称为布局方案Y1 Dn的同构布局等价类,I(Y1)中任一元素称为I(Y1)的代表元.

󰀁󰀁显然,以图元Fi,i In为节点,所有可能的布局方案的图的个数为M=2得到布局子问题如下

minf(Y),(P2)

s..tHij∋0,i#j,i,j In,J(Y)=∃

n(n-1)

2

,可以将问题

(P1)转化为若干个子问题进行分别求解.由此,

%mx∃

i=1

ii

n

&󰀁,

%

n

mixi∃&󰀁,

4n

Y I(Ym0),Ym0是初始点,m0=1,2,!,M.󰀁󰀁由于M随n呈指数增长,因此需要对子问题进行筛选.由于二维布局问题是平面图,因此,非平面图布局方案是无需考虑的,而只需要考虑平

面图.另外,不连通图所对应的布局方案显然不是(聚集)的,所以只需考虑连通平面图即可.为分析布局方案的聚集性,可以借助图的直径来描述聚集程度.

󰀁󰀁定义5󰀁图G中若顶点u与v连通,则G中最短(u,v)󰀁路的长,称为u与v之间的距离,记为d(u,v);任何两点之间距离的最大值称为图G的直径,记为diam(G)=max{d(u,v)|u,v V(G)}.󰀁󰀁定义6󰀁平面图G中,若存在图G的一个边集E∗ E满足G-E∗是不连通的,则称E∗是G的一个边割.边割集合中的每一条边称为割边.󰀁󰀁定义7󰀁使图成为不连通图所需去掉的最小边数,称为图G的边连通度,记为!(G)=min{|E∗|E∗为G的边割},其中,|E∗|为E∗中边的数目.

󰀁󰀁定理1󰀁在图G中,去掉任何一条割边,该图

i=1

Y R.

2󰀁布局方案的图及其性质

󰀁󰀁定义1󰀁若布局方案Y满足不干涉约束(1)和静不平衡约束(2),则称Y为可行布局方案,所有可行布局方案的集合记为D;若布局方案Y只满足不干涉约束(1),则称Y为不干涉布局方案,所有不干涉布局方案的集合记为Dn.显然,D Dn.若D# ,则称问题是适定的.

󰀁󰀁定义2󰀁设Y Dn,若其图元Fi与Fj满足下列条件之一:(i)Fi与Fj有部分边重合;(ii)Fi的某个顶点在Fj的边上;(iii)在保持不干涉的条件下,从Fi的形心xi出发,沿xi与xj的连线作平移或旋转,移动后可满足条件(i)与(ii),则称Fi与Fj在布局方案Y中是相邻图元,记为(Fi,Fj)或(Fj,Fi).

󰀁󰀁对任一布局方案Y Dn,令V={F1,F2,!,Fn},E(Y)={(Fi,Fj)|Fi,Fj V},记G(Y)=󰀁第4期翟金刚,等:基于极大平面图矩形图元布局问题的全局优化算法󰀁295

的直径不减.

󰀁󰀁证明󰀁不妨设P=u1e1v1u2e2v2!unenvn是图G的某一条路径,其长度是图G的直径,e是任意一条割边.若e P,删除e后,P不改变,直径不改变.󰀁󰀁若e P,由于P是u1到un的最短路,删除e后,则u1与un的距离将变大,甚至不连通,从而,该图的直径不减(变大或不变).证毕.

图元布局问题实例,本文和文[9]的目标值分别为18!41和18!487920,静不平衡量分别为4!835e-003和0!049889,计算时间分别为2815s和3!050h,优化结果如表3所示,二维布局图如图4所示.计算结果表明,本文所构造的算法是有效的.

表1󰀁五个矩形图元布局优化结果比较

本文结果(xi1,xi2,∀i)

图

(8,6)

(-4.712,3.783,2.985)

文献[9]结果(xi1,xi2,∀i)(-5.00,3.99,2.857)

3󰀁全局优化算法

󰀁󰀁根据定理1,可以从极大平面图开始,通过逐步删除图的割边,降低图的边连通度,直到子问题

的可行解存在为止,比较子问题的局部最优解即得布局问题的全局最优解.

󰀁󰀁综上所述,构造布局问题的全局优化算法步骤:(i)采用圈加点法找出所有非同构极大平面图,记为G={G1,G2,!,Gm};(ii)令A=󰀂,B=G,C=󰀂,k=0;(iii)i=1;(iv)取Gi B,若图Gi对应的一个布局方案存在可行解Yi,m0,令A=A+Gi,计算f(Yi)=min{f(Y)|Y I(Yi,m0)},得到以Yi,m0为初始布局方案的子问题的局部最优解Yi;否则,依次选取Gi的一条割边,并删除该割边,得到Gi的所有边连通度减1的图Gi1,Gi2,!,Gin.令C=C+{Gi1,Gi2,!,Gin};(v)k=k+1;(vi)i=i+1,如果i&

|B|,转

(iv);(vii)若A=󰀂,令B=C,C=󰀂,转(iii);(viii)比较A中|A|个子问题的局部最优解,找出全局最优解,结束.

*

*

[7]

(8,8)(-0.090,-5.401,1.410)(0.00,-5.68,1.400)

元

(10,6)(2.491,4.512,1.414)(2.73,4.83,1.363)边

(12,4)(6.722,-0.740,1.414)(7.27,-0.96,1.466)长

(6,6)(-6.637,-1.987,2.985)(-6.84,-2.22,2.872)目标值(fmin)静不平衡量计算时间/s

11.021.755e-008

6

11.340.00713

表2󰀁六个矩形图元布局优化结果比较

本文结果(xi1,xi2,∀i)

(8,6)图

(8,8)元(10,6)边(10,8)长(10,10)

(-2.936,-8.97,1.358)(8.484,1.385,1.358)(6.007,-8.045,0.641)(-1.835,-1.024,2.929)(0.629,7.652,2.929)

文献[9]结果(xi1,xi2,∀i)(-3.85,-8.82,1.344)(9.00,1.09,1.289)(4.87,-8.01,0.880)(-1.26,-0.81,2.837)(1.01,8.11,2.839)(-9.62,0.72,1.336)

14.620.00218

(12,6)(-9.408,1.968,1.365)目标值(fmin)13.97静不平衡量计算时间/s

5.578e-007

12

表3󰀁九个矩形图元布局优化结果比较

本文结果(xi1,xi2,∀i)

(8,6)(-6.853,-0.394,13.288)(8,8)(0.960,5.445,-5.405)

(10,6)(-2.125,-4.223,-14.987)(10,8)(-10.006,8.250,-0.690)(10,10)(11.256,-1.383,6.987)(12,6)

(7.392,9.765,8.560)

文献[8]结果(xi1,xi2,∀i)(2.34,11.02,-5.18)(1.25,12.33,3.74)

(1.02,-4.54,11.99)(0.29,4.83,-12.61)(2.75,0.04,-0.84)(2.12,-11.96,-6.99)(2.65,-10.63,4.06)(1.10,4.37,9.96)

18.4879200.0498893.050h

图元边长

(12,4)(-2.825,15.142,-6.099)(1.01,-4.27,-11.35)(12,8)(-10.032,-8.886,5.437)

4󰀁数值结果

󰀁󰀁为验证算法的有效性,用Matlab编程进行计算,并与文[8󰀂9]中采用遗传算法方法的计算结果进行了对比,计算结果见表1󰀂3,所得布局方

案见图2󰀂4.表1表示对5个图元进行优化所得结果比较,本文和文[8]的目标值分别为11!02和11!34,静不平衡量分别为1!755e-008和0!007,计算时间为6s和13s.表2表示对6个图元进行优化所得结果比较,本文和文[8]的目标值分别为13!97和14!62,静不平衡量分别为5!578e-007和0!002,计算时间为12s和18s.图2和图3分别表示5个图元和6个图元的布局图.为了验证算法的有效性,本文引用文[9]中9个(12,10)(5.281,-9.800,-0.866)目标值(fmin)18.41静不平衡量计算时间

4.835e-0032815s

图2󰀁五个图元的二维布局图

󰀁296鲁东大学学报(自然科学版)第26卷󰀁

参考文献:

[1]󰀁王秀梅,冯恩民,滕弘飞.旋转舱布局优化模型的主

要性质及不干涉性算法[J].大连理工大学学报,1995,35(2):125󰀂131.

[2]󰀁FengEnmin,WangXilu,WangXiume,ieta.lAnalgo󰀁

rithmofglobaloptimizationforsolvinglayoutproblem[J].EuropeanJournalofOperationalResearch,1999,114(2):430󰀂436.

[3]󰀁铁军,冯恩民.具有性能约束的三维布局优化模型的

图3󰀁

六个图元的二维布局图

主要性质[J].运筹学学报,2009,13(1):107󰀂112.[4]󰀁冯恩民,许广键,滕弘飞.带性能约束的矩形图元布

局优化模型及不干涉算法[J].高校应用数学学报,1993,8(1):53󰀂60.

[5]󰀁王秀梅,冯恩民,滕弘飞.圆柱空间中长方体群布局

优化的模型、函数凸性及算法[J].应用数学学报,1997,20(1):159󰀂160.

[6]󰀁ZhaiJingang,YuHongyun,LiHongbo,eta.lAglobal

optimizationalgorithmfortwo-dimensionallayoutprob󰀁leminasatellitemodule[J].IntelligentInformationManagementSystemsandTechnologies,2006,2(1):160󰀂167.

图4󰀁九个图元的二维布局图

[7]󰀁王绍文.构造极大平面图的圈加点法[J].北京机械

工业学院学报,2000,15(1):26󰀂29.

[8]󰀁冯恩民,宫召华,刘重阳,等.带性能约束的卫星舱布

局问题改进遗传算法[J].大连理工大学学报,2005,45(3):459󰀂463.

[9]󰀁曾明华,冯恩民.基于改进遗传算法的布局优化子问

题[J].运筹与管理,2005,14(1):13󰀂18.

󰀁󰀁注:本文数值结果在Inter(R)CPU2.80GHzPC机上运行得到,文[8]在IBM586主频166MHz机器上运行得到,文[9]在Inter(R)CPU2.00GHzPC机上运行得到.

AGlobalOptimizationAlgorithmfortheLayoutProblemof

RectangularPiecesBasedontheMaximalPlanarGraph

ZHAIJin󰀁gang,ZHANGJiao󰀁jun

(SchoolofMathematicsandInformation,LudongUniversity,Yantai264025,China)

Abstract:Thenon󰀁interferencelayoutoptimizationalgorithmofrectangularpiecesisinvestigatedforsolvingthelayoutproblemofartificialsatellite󰀁sinstrumentmodule.Basedonthemaximalplanargraph,aglobaloptimiza󰀁tionalgorithmisconstructedbyusingthemethodofreducingtheedge󰀁connectivityoflayoutchartsuccessively.

Thenumericalresultsshowtheeffectivenessofthealgorithm.Keywords:artificialsatellitemodulelayou;tlayoutproblem;rectangularpieces

(责任编辑󰀁王际科)