（运筹学与控制论专业论文）具有拓扑结构布局优化的理论及算法.pdf

大连理工大学博士学位论文 摘要 本文以人造卫星仪器舱布局设计为背景，研究具有拓扑结构的布局优化问题主要 包括不同图元的布局优化模型、子问题的最优性条件、最优性函数和优化算法、判断不 干涉性算法及改进的遗传算法。本文取得的主要结果可概括如下： l 、研究矩形图元在圆形区域内的二维布局优化问题，建立了半无限优化模型。改进 了相邻图元的定义，使不同构布局方案与图建立了一一对应的关系。应用文 1 0 8 与 1 0 9 1 中提出的理论，得到有限多个在同构布局等价类中求解的半无限优化子问题。论述了目 标函数的连续性，及子问题最优解的存在性。构造子问题对应的松弛子问题，并讨论了 两子问题最优解之间的关系，证明求解松弛子问题同样能得到原问题的全局最优解。 2 、改变松弛子问题中约束条件的形式，将其合并为一个极大函数咖( y ) 。利用极大 函数的相关理论证明砂( y ) 是连续函数，并给出它的方向导数及次梯度的表达式，同时 证明次梯度是外半连续的。 3 、构造了与松弛子问题局部等价的极小极大问题 ( m m p )m i n 户( y ) y r 4 “ 论述了松弛子问题的极小点与对应的极小极大问题( m m p ) 的极小点之间的关系，证明 了松弛子问题有局部最优解的一阶必要条件，以及对应的极小极大问题有最优解的充分 条件。由于所构造的问题( m m p ) 涉及到松弛子问题的一个局部极小点，因此在构造算法 时，无法利用一阶必要条件作为终止准则为了解决这个问题，构造一个函数f ( z ，y ) ， 如果y 是松弛子问题的一个局部极小点，那么对v y 砰”，f ( y ，y ) = f ( y ) 。给出函 数目y + h ) 的一阶凸逼近，由此得到了最优性函数。证明该函数是一个非负的连续函 数，并且在其零点使一阶必要条件成立。 4 、依照卫星仪器舱砸局问题的实际应用状况，讨论多种图元的布局优化模型首先 给出圆形、三角形及一般凸多边形图元的明确表达式。不但建立了圆形、三角形等单一 图元的优化模型，而且给出了矩形图元、圆形图元、三角形图元等多种图元组合后的布 局优化模型为了使布局模型更加完善，分别以聚集性函数和静不平衡量为模型的目标 函数。针对以聚集性函数为目标，矩形与三角形两种图元的布局优化问题，研究其松弛 子问题的最优性条件。 5 、研究布局问题的优化算法针对布局问题的特殊性，改变最优性函数的形式，构 造了求解半无限优化模型松弛子问题的优化算法，以最优性函数为该算法的终止准则， 并证明其收敛性。为了判断布局方案是否可行，本文构造了判断矩形图元之间、三角形 图元之间、圆形图元与矩形图元以及矩形图元与三角形图元的不干涉性算法。最后构造 大连理工大学博士学位论文 了改进的遗传算法，该算法采用实数编码，并将不干涉算法作为其子算法，经数值计算 表明了算法的有效性。 关键词：二维布局优化；半无限优化模型；最优性条件；最优性函数；不干涉算法； 遗传算法 i l 大连理工大学博士学位论文 a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e st h ep a c k i n gp r o b l e mc h a r a c t e r i z e db yt o p o l o g i c a ls t r u c t u r e w i t ht h el a y o u to p t i m i z a t i o no fa ua r t i f i c i a ls a t e l l i t em o d u l ei nt h e b a c k g r o u n d t h ec o n - t e n t si n c l u d et h el a y o u to p t i m i z a t i o nm o d e l so f t h ed i f f o r mg r a p h e l e m e n t s ，t h eo p t i m a l i t y c o n d i t i o n s ，t h eo p t i m a l i t yf u n c t i o n s ，t h eo p t i m i z a t i o na l g o r i t h m sf o rt h es u b p r o b l e m s ， t h ea l g o r i t h m sf o rt h en o n - o v e r l a pc o n s t r a i n t sa n dt h ei m p r o v e dg e n e t i ca l g o r i t h m t h e m a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r t a t i o n ，m a yb es u m m a r i z e da sf o l l o w s ： 1t h et w o - d i m e n s i o n a ll a y o u to p t i m i z a t i o np r o b l e ma b o u tp l a c i n gt h er e c t a n g u l a r g r a p he l e m e n t so nar o u n d b o a r di si n v e s t i g a t e da n dt h es e m i i n f i n i t eo p t i m i z a t i o nm o d e l i s p r e s e n t e d t h ed e f i n i t i o no ft h ea d j o i n i n gg r a p he l e m e n t si si m p r o v e d ，s u c ht h a tt h e o n 争- t o o n ec o r r e s p o n d e n c eb e t w e e nt h en o n i s o m o r p h i cl a y o u ts c h e m e sa n dt h ef a p h s i se s t a b l i s h e dt h ef i n i t es u b p r o b l e m so ft h es e m i i n f i n i t eo p t i m i z a t i o na r eo b t a i n e db y v i m l eo ft h et h e o r i e sp r e s e n t e di nr e f e r e n c e 【1 0 8 a n d 【1 0 9 ，w h e r et h es u b p r o b l e m sa r e s o l v e do ne v e r ye q u i v a l e n tc l a s so fi s o m o r p h i cl a y o u t t h eo b j e c t i v ef u n c t i o ni nm o d e li s p r o v e dt ob ee o t t t i n n o u sa n d i tf o l l o w st h a tt h eo p t i m a ls o l u t i o n so ft h e s u b p r o b l e m s e x i s t ， t h e c o r r e s p o n d i n g r e l a x e ds u b p r o b l e mf o re a c hs u b p r o b l e mi sc o n s t r u c t e da n dt h er e l a t i o n o ft h el o c a l l yo p t i m a ls o l u t i o n sb e t w e e nt h es u b p r o b l e ma n di t sr e l a x e ds u b p r o b l e ma r e d i s c u s s e d i ti sp r o v e dt h a tt h eg l o b a lo p t i m a ls o l u t i o nc a i lb eo b t a i n e dt h r o u g hs o l v i n g t h er e l a x e ds u b p r o b l e m s 2 t h ec o n s t r a i n t so f t h er e l a x e ds u b p r o b l e mc o m b i n et om a k eam a xf u n c t i o n 咖( y ) t h i sm a x f u n c t i o n 砂( y ) i sp r o v e dt ob ec o n t i n u o u sa n dt h ed i r e c t i o n a ld e r i v a t i v ea n d s u b g r a d i e n ta r ep r e s e n t e db yv i r t u eo ft h ep r o p e r t i e so fm a x f u n c t i o n a tt h es a m et i m e ， i ti sp r o v e dt h a tt h es u b g r a d i e n ti so u t e rs e m i c o n t i n u o u s 3am i n i t n s xp r o b l e mw h i c hi sl o c a l l ye q u i v a l e n tt ot h er e l a x e ds u b p r o b l e mi s c o n s t r u c t e d ， ( m m p ) m i n f ( y ) y r 4 “ i ti sd i s c u s s e dt h a tt h er e l a t i o no ft h el o c a u ym i n i m i z e rb e t w e e nt h er e l a x e ds u b p r o b l e m a n dt h ec o r r e s p o n d i n gm i n r f l e k xp r o b l e m t h ef i r s t o r d e rn e c e s s a r yc o n d i t i o n sf o rt h e r e l a x e ds u b p r o b l e ma n dt h es u f f i c i e n tc o n d i t i o nf o rt h ec o r r e s p o n d e n tm i n - m a xp r o b l e m a r ep r o v e d b e c a u s et h ec o n s t r u c t e dm i n m a xp r o b l e mr e q u i r e st h ea d v a n c ek n o w l e d g e o f al o c a l l yn f i n i m i z e ro ft h er e l a x e ds u b p r o b l e m ，t h ef i r s t o r d e rn e c e s s a r yc o n d i t i o n sc a n t b ed i r e c t l yr e g a r d e da st h et e r m i n a lc r i t e r i ao fa l g o r i t h m s t oo v e r c o m e t h i sd i f f i c u l t y ，a u l 大连理工大学博士学位论文 f l m c t i o nr ( z 、y ) i sc o n s t r u c t e dw h e r ef o ra l l y r 札，p ( 9 ，y ) = 户( y ) ，i fp i sal o c a l l y o p t i m a l s o h l t i o no ft h er e l a x e ds u b p r o b l e m t h e o p t i m m i t yf u n c t i o ni sp r e s e n t e db yu s i n g t h ef i r s t o r d e rc o n v e xa p p r o x i m a t i o nt ot h ef u n c t i o nf ( y + ) ，t h e o p t i m a l i t yf u n c t i o n i sn o n n e g a t i v ec o n t i n u o u sa n dt h ef i r s t o r d e rn e c e s s a r yc o n d i t i o ni ss a t i s f i e da tap o i n ti f a n do n l yi ft h i sp o i n ti saz e r oo ft h eo p t i m a l i t yf u n c t i o n 4 a c c o r d i n gt ot h ep r a c t i c a li n s t a n c eo ft h ea p p a r a t u sm o d u l e so fa r t i f i c i a ls a t e l l i t e ， t h el a y o u to p t i m i z a t i o nm o d e l so ft h ed i f f o r mg r a p he l e m e n t sa r ed i s c u s s e d f i r s t b t h e e x p r e s s i o n so ft h ec i r c l e ，t h et r i a n g l ea n dt h eo r d i n a r yc o n v e xp o l y g o ng r a p he l e m e n t s a r ep r e s e n t e d i ti sn o to n l yt h a tt h eo p t i m i z a t i o nm o d e l so fo n ek i n do fg r a p he l e m e n t s s u c ha st h ec i r c l e so rt r i a n g l e sa r ee s t a b f i s h e d ，b u ta l s ot h eo p t i m i z a t i o nm o d e l so ft w o k i n d so fg r a p he l e m e n t sa r ep r e s e n t e d ，w h i c hi n c l u d et h ec o m b i n a t i o no ft h er e c t a n g l e s a n dt h ec i r c l e s ，o rt h et r i a n g l e s t oo b t a i nt h eb e t t e rm o d e m ，t h ec a p a c i t yf l m c t i o na n d t h es t a t i cn o n e q u i l i b r i u mq u a n t i t ya f e r e g a r d e da st h eo b j e c t i v ef u n c t i o n so ft h em o d e l s r e s p e c t i v e l y f o rt h el a y o u tp r o b l e m o ft h er e c t a n g u l a ra n d t r i a n g l eg r a p he l e m e n t s ，w h e r e t h ec a p a c i t yf u n c t i o ni s r e g a r d e da st h eo b j e c t i v ef u n c t i o n ，t h eo p t i m a l i t yc o n d i t i o n so f i t sc o r r e s p o n d i n gr e l a x e ds u b p r o b l e ma r es t u d i e d 5 t h eo p t i m i z a t i o na l g o r i t h m sf o rs o l v i n gt h ep a c k i n gp r o b l e ma r es t u d i e d f o r t h ep a r t i c n l a r i t yo ft h el a y o u tp r o b l e m ，t h ep a p e rc h a n g e st h ef o r mo ft h eo p t i m a l i t y f u n c t i o na n dc o n s t r u c t st h ea l g o r i t h mf o rs o l v i n gt h er e l a x e ds u b p r o b l e mo ft h es e m i i n f i n i t eo p t i m i z a t i o nm o d e l ，w h e r et h eo p t i m a l i t yf l m c t i o ni s r e g a r d e da 8t h et e r m a n a l c r i t e r i at h ec o n v e r g e n c eo ft h ea l g o r i t h mi sp r o v e d t oe s t i m a t et h ef e a s i b i l i t yo ft h e l a y o u ts c h e m e s ，i ti sn e c e s s a r yt oc o n s t r u c tt h en o n - o v e r l a pa l g o r i t h m s t h e s ea l g o r i t h m s n o to n l y j u d g e i ft h er e c t a n g l e so rt h et r i a n g l e st h e m s e l v e so v e r l a pb u ta l s oi ft w ok i n d so f t h eg r a p he l e m e n t sm u t u a l l yo v e r l a ps u c ha st h er e c t a n g l e sa n dc i r c l e s o rt h er e c t a n g l e s a n dt r i a n g l e s a tl a s t ，ag e n e t i ca l g o r i t h mi si m p r o v e dw h i c hi sf l o a tc o d i n ga n dt a k e st h e n o n - o v e r l a pa l g o r i t t m a sa ss u b p r o g r a m m e t h en u m e r i c a lr e s u l t ss h o w t h a tt h ea l g o r i t h m i se f f e c t i v e k e yw o r d s ：t w o - d i m e n s i o n a ll a y o u tp r o b l e m ； s e m i - i n f i n i t eo p t i m i z a t i o n m o d e l ；o p t i m a l i t yc o n d i t i o n ；o p t i m a l i t yf u n c t i o n ；n o n - o v e r l a pa l g o r i t h m ； g e n e t i ca l g o r i t h m l v 第一章绪论 第一章绪论 泰章介绍布局优化问题的工程背景、问题分类、发展历史以及现状。着 重阐述了以卫星仪器舱布局为例，带有性能约束的拓扑布局优化问题，说明求 解该类问题的困难性及巨大的实用价值。同时列出本文所研究的问题以及取 得的主要结果 1 1 布局问题的工程背景 布局问题( p a c k i n gp r o b l e m ) t 1 】是给定一个布局空间和若干待布物体，将待布物合理 地摆放在空间中满足必要的约束，并达到某种最优指标。该类问题涉及现实生活中的许 多方面和行业，如板材切割、集成电路设计、建筑设计、交通运输、造船、纺织、航空航 天工业等。布局结果的好坏对于以上行业生产的合理性、经济性、安全性具有重要影响 和意义。随着近几十年来在工业、交通、国防等方面高技术的发展，更多高层次的复杂 布局问题：大型、高维、动态复杂布局优化设计问题提上日程，成为亟待解决的重大课 题。该类问题的主要应用背景为航天器、坦克、潜艇、航空母舰、海下悬浮工程、摆式高 速列车等内部的待布物( 仪器、设备、装置等) 的总体布局优化方案设计。原有的布局问 题一般只要求待布物之问、待布物与容器之间不干涉，并尽量提高空间利用率。而对于 动态复杂的布局优化问题，还要格外考虑性能特性的约束，如惯性、平衡性、稳定性、振 动、电磁场、温度场等约束，我们称其为带性能约束的布局问题。 现实生活中的布局问题往往用人工方式来勰决，即由布局设计人员按照实际布局要 求，利用布局模型或样板根据自身经验进行试凑或摆放，经过反复多次，最后找出一个 可行的布局方案。由于受到问题复杂性和求解时问的限制，许多更好的方案在布局设计 时往往无法被发现。当布局规模较大、布局物体形状复杂、约束条件增多时，人工往往 需要花费相当多的时间进行布局求解，即使如此也会出现最后所得布局方案不能满足要 求的情况，更不用说最佳方案了，显然人工布局根本无法适合现代生产的需要。 航天器( 卫星、飞船、空间站) 由有效载荷、结构、热控制、姿态与轨道控制、电源、 跟踪遥测与遥控数据管理等分系统所组成，分系统又由各自的仪器、设备和部件组成； 部件形式多样、数量繁多；设备与设备之间、分系统与分系统之间有各种不同的机、电、 液、气接口，并有传动、管线、缆线相连，所以航天器是一个复杂工程系统以载人飞 船为例，它是一个多舱段的大型航天器，十多个复杂子系统，上千个待布物( 仪器、设 备等) ，它们之问并配有许多气、液、电缆线。其总体布局方案设计的目的是在选定构造 类型( 组件或子系统) 基础上将航天器的仪器设备布置在各舱段的合适位置，对于再入 过程中使用的和需要返回地面的仪器设备应当布置在返回舱，仅在再入前使用的设备可 以布置在轨道舱或仪器设备舱，以降低卫星或飞船的结构质量。在进行总体布局方案设 计之前要对航天器的功能要求进行分析，选择组件或子系统，然后确定组件或子系统之 大连理工大学博士学位论文 间的相互位置关系，并使总系统具有一个协调完善的结构，然后再进行航天器的总体布 局。这时不但要考虑航天器各组件或子系统之问的各种约束，还要考虑航天器同各种外 部因素( 如空问环境) 之间的约束，尽量达到功能合理、结构紧凑、层次清晰、比例协调 等要求。该问题具有高度复杂性，需要航天、机械、计算机、数学、力学等各学科知识的 综合运用。 美国从8 0 年代起就致力于计算机技术解决航天器舱的待布物总体布局问题的研究， 其关键理论、方法、技术至今仍处于保密状态。航天器舱布局设计属于带性能约束的三 维布局优化问题，具有不确定性、高度非线性、知识不完备性、既需定量计算叉需定性 分析等特点。布局问题的n p 一困难性和航天器设计本身的工程系统复杂性使得该问题的 解决既存在理论上的开拓性和挑战性，又存在工程实践上的艰难性和复杂性因此解决 航天器布局问题具有重大的经济和社会效益。 1 2组合优化问题与计算复杂性 由于布局问题的复杂性，其研究进展相当缓慢。随着数学理论的发展，特别是组合 优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 理论的发展，使我们对几何布局问题有了进一步的了 解，也为求解布局闻题提供了一些新的手段，可以把布局问题看成是组合优化问题。 1 组合优化问题 众所周知，数学规划乃至最一般的优化问题都有通用的数学模型，然而组合优化问 题至今还没有人能给出一个通用的数学模型。组合优化主要是研究那些伴随着有组合结 构的一类确定某种最优方案的问题，往往涉及布局、排序、分类、筛选等问题，是运筹学 的一个重要分支。组合优化问题的目标是从组合问题的可行解集中求出最优解。通常可 描述为：令 q = u 1 ，叻，w n ( 1 2 1 ) 为所有状态构成的解空间，c ( 咄) 为状态对应的目标函数值，要寻找最优解u + ，使 得对任意的岫n ，c + ) = m i nc ) 。因此一个组合优化问题可以表示为以下形式： ( g ) m i n c ( 咄) s t q ( 1 2 2 ) ( 1 23 ) 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m - t s p ) 、加工讽度 问题( s c h e d u l i n gp r o b l e m ) 、背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i np a c k i n g p r o b l e m ) 、图着色问题( g r a p hc o l o r i u gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 等。 这些问题描述都很简单，也具有很强的工程应用背景。从理论上讲，组合优化问题可以 在o ( l n i ) 时问内求得最优解，但是对于大多数实际问题来说，在计算机可能的运行时间 内求得最优解是无法实现的其主要原因是求解这些问题的算法需要极长的运行时间与 2 第一章绪论 极大的存储空间，以致根本不可能在现有的计算机上实现，这就是所谓的“组合爆炸”。 组台爆炸产生的原因有以下两个方面：第一是由于问题本身太难，譬如问题中的变量特 别多，随着输入规模的扩大，计算呈指数级增长，从而对大规模问题需要指数时间才能 找到解，使得算法失去其实用价值；第二是要求解问题本身太庞大，一般人们解决该类 问题的穷举搜索，不可能摆脱指数的时间限制丽得到问题的解。由于这两个原因，对于 有组合爆炸现象存在的问题，人们只髓运用某些技巧，如n p 问题的近似解，解决中小 规模的算例，进一步的研究需要在理论及方法上都必须有较大的突破。 目前一般采用逼近法求解组合优化问题。对于组合优化问题( c ) ，假设是任意的 实例，u ”( nu + ( j ) i f ：q ，一( ，) 表示由算法h 得到的可行解，u + ( ) 是最优解，如果 c 啦( 川sp c ( c o + ( 纠，那么称算法h 是t o 逼近算法( p 1 ) 。这里p 是算法h 的性能保 证( p e r f o r m a n c eg u a r a n t e e ) 。逼近算法主要包括直接逼近法( d i r e c ta p p r o x i m a t i o n ) 、动 态规划逼近法( d p b a s e da p p r o x i m a t i o n ) 、线性规划松弛法( l p - r e l a “x a t i o na p p r o a c h ) 、 随机算法( r a n d o m i z a t i o n ) 等。这些算法的主要目标就是使p 的值减小，目前已证明随机 算法性能保证p 4 3 1 2 1 。 2 计算复杂性 算法对时间和空间的需要量称为算法的时问复杂性和空间复杂性，它们对计算机的 求解能力有重大影响。问题的时间( 或空间) 复杂性是指求解该问题的所有算法中时间 ( 或空间) 复杂性最小的算法的时间( 或空间) 复杂性。算法或问题的复杂性一般表示为问 题规模n 的函数。时问复杂性记为t ( n ) ，空间复杂性记为s ( n ) 。 在分析复杂性时，可以求出算法的复杂性函数，( n ) ，也可以方便地用复杂性函数主 要项的阶0 ( ，( n ) ) 表示。若算法a 的时间复杂性是乃( n ) = 0 ( p ( n ) ) ，p ( n ) 是 的多 项式函数，则称算法a 是多项式时间算法时间复杂性不属于多项式时间的算法统称为 指数时间算法例如对n 个元索，二分搜索一个元素的时间复杂性是0 ( n l g n ) ) ，就是 多项式时间算法。而用动态规划解旅行商问题的时间复杂性是o & 2 “) ，它是指数时间 算法。 早在1 9 6 5 年，e d m o k d s 提出如果一个算法在最坏的情况下也可以根据初始量的一 个多项式给定的上界，来限定计算量，以确定计算量的界限，则称这个算法是“好”的 算法【3 】，或称为有效算法。一个问题如果可以设计一个有效的算法，求出它的一个解或 无解则称该问题属于p ( p o l y n o m i a l ) 类p 类问题是指有多项式时闻算法的问题类。 n p 类问题是指可在多项式时间里检验的问题类，至今尚未找到多项式时间算法。1 9 7 1 年c o o k 证职了有一类阅题，一旦它们之一有有效算法，则此类中的所有问题都有有效 算法【4 l ，这就是n p c ( n p - c o m p l e t e ) 问题。到目前为止，求解n p c 问题的算法都不是 多项式时问算法，大多数这类闻题能够从可能的组合或序列中选取一个答案，不过组合 或序列的范围很大，其计算量将随初始数据量的增大而成指数方式递增。 n p c 这一概念是对应于判断问题定义出来的，作为与此类似的概念，对应于规划阃 3 大连理工大学搏士学位论文 题和判断问题这两方面内容的就是n p h a r d 。它们是“难度与n p c 相同或更高的组合 问题”例如，已知“在给定矩形区域内是否能装填入n 个给定矩形群体”这个判定问题 就是n p c 类；与此对应，为了能在多项式算法时问里求得4n 个给定矩形群体布局的最 小外包络矩形”这种规划问题的解，至少要求前面所说的判断问题能在多项式算法时间 内求解。从这个意义而言，后一同题的难度与前者相同，甚至更高，因而也是n p h a r d 问题。上述四类问题的关系可用图1 表示。 pn pn p - cn p h a r d 图1 ：四类问题的关系图 目前普遍猜想n p c 问题是难解的，但在证明或否定该猜想方面没有取得什么进展。 但是，知道一个问题是n p c 的，至少说明了要想用多项式算法求解该问题必须要求有重 大突破。 1 3 布局问题的研究现状 自1 8 3 1 年g a u s s 研究格( l a t t i c e ) 的有关布局问题开始，至今已有百余年的历史。 前人已经证明即使是最简单的一维布局也属于很难解的n p c 问题，因此长期以来关于 布局问题的理论研究进展不大。下面首先介绍布局的分类 1 3 1布局问题的分类 从理论上讲，布局问题可分为装填布局( p a c k i n gl a y o u t ) 和结构拓扑布局( s t r u c t u r e t o p o l o g i c a ll a y o u t ) 1 装填布局问题 按照布局问题的可布空间和待布物体的形状，装填布局问题又可分为： ( 1 ) 一维布局问题 典型的例子是在给定长度的棒料上，切割长度不等的若干短棒，通常称为切段( c u t t i n g s t o c k l 问题 f 2 ) 二维布局问题 4 第一章绪论 包括一刀切问题( g u i l l o t i n ec u t t i n gp r o b l e m s ) ，即将二维矩形块按照“一刀切”原则 切成一组大小不同的矩形块，使面积浪费最少；底盘装载问题( p a l l e t l o a d i n g p r o b l e m s ) ， 如集装箱的配载问题；矩形集合布置问题( r e c t a n g l ep a c k i n gp r o b l e m s ) ，如大规模集成 电路中的掩模设计问题；圆装填问题( c i r c l ep a c k i n gp r o b l e m s ) ，这类问题大量的存在 于几何、化学和生物学中；还有二维不规则图形布局问题，如板材下料、服装裁剪等 f 3 ) 三维布局问题 包括无性能约束的三维布局问题和带性能约束的三维布局问题无性能约束三维布 局问题( 3 - dl a y o u tp r o b l e m sw i t hn o n - b e h a v i o r a lc o n s t r a i n t s ) ，就是将尽可能多的不 同形状、尺寸的三维物体放入一个长方体( 如集装箱) 或圆柱体( 如卫星舱) ；带性能约束 的三维布局问题( 3 一dl a y o u tp r o b l e m sw i t hb e h a v i o r a lc o n s t r a i n t s ) ，指将任意形状、 大小和性能的三维实体摆放在一个任意形状、大小的三维容器中，以满足某些约束或是 某些目标最优，如航天器仪器舱设备布局闷题、汽车驾驶舱布局问题等。本文研究的问 题就属于该类问题 2 结构拓扑布局问题 结构设计的过程一般是根据结构的功能要求和可利用的材料情况，首先确定结构的 类型、拓扑，再确定几何形状，最后确定构件的尺寸。由此结构优化大体上分为以下几 个层次：截面( 尺寸) 优化、形状( 几何) 优化、拓扑优化、布局优化和类型优化。这类优 化问题在力学与机械上研究较多，有效可行的拓扑布局优化算法不仅具有很高的理论价 值与学术价值，而且具有广阔的应用前景 1 3 2 布局问题研究概况 有关布局问题的文献始见于1 9 3 0 年k a n t o r o v i c h 的俄文文章，后来该文在1 9 6 0 年 译为英语刊登在m a n a g e m e n ts c i e n c ei s 】上。根据s w e e n y 等【6 】1 9 9 2 年的统计，从1 9 4 0 年到1 9 9 2 年，全球关于布局方面的文献达4 0 0 余篇，涉及1 4 0 多个应用领域，其中涉及 非矩形形体的2 7 篇，丽涉及三维非矩形形体的只有3 篇( 布局对象都具有相同的形状和 大小，方法大都采用基于矩形体布局的经验式方法，即工程师根据经验将不规则物体通 过合并、简化等手段转化为矩形体再利用启发式方法求解) 。而到了近两年，关于布局问 题的研究文献超过了1 5 0 0 篇，而涉及三维不规则实体的布局问题不超过l o 篇由此可 见，虽然布局问题得到了广泛而深入的研究，但对于复杂布局问题仍没有太多进展 1 国外研究现状 从理论进展看，布局优化问题的奠基性工作是由g i l m o r e 等在6 0 年代完成的 z - l o l 。 他用线性规划建立了一刀切问题的数学模型，并把线性规划的求解转化为一个背包子问 题，然后构造求解背包问题的有效算法。主要用到了线性规划、动态规划与背包函数， 该算法可用于求解无阶段限制的无约束一二维切割问题。此后对问题的研究从一维发展 到二、三、四维( 引入时间维) ，研究的重点则是建立特定问题的数学模型和寻求有效的 5 大连理工大学博士学位论文 求解途径 g i l m o r e l l l 】，h i 岫a n i i 2 l ，p y w a a _ l g 1 3 1 ，w b d o w s l a n d b s ，d y c k h o i 平f 1 6 h a e s s l e r t ”】，ka d o w s l a n d 【1 j 1s w e e n e y 6 ，b i s c h o 耐，l o d i 2 0 - 2 1 等人的综述性文章主要 是针对与应用相关的布局问题，基本上概括了此类闻题的主要研究成果。其中d y c k h o f f 首次依据问题的维数、目标要求、材料分类及工件分类给出了布局问题较为详尽的分类。 f a g g i o l i 圳利用启发式算法提出了切段排序问题的数学模型和一个三步解法。切段 排序问题的一个可行解是1 ，2 ，n 的一个队列，它给出了各个元件的处理次序，其中 n 为元件总数。算法第一步用贪婪算法产生一个好的初始解；第二步通过禁忌搜索或一 般的局部搜索过程改进初始解；第三步用所得的最好解为上界，通过一个精确计算过程 寻求最优解v 拈k o 矧和n i t s c h e 2 q 分别利用树搜索算法和松弛算法来解决一维切段问 题。p e t r i d i sv a s s i l i o s 等口q 利用遗传算法以动态的方式把问题的约束合并到适应度函数 中在遗传算法初期，惩罚因子很小。目的是使搜索简化，并使遗传算法能更有效的搜索 空间在遗传算法进行过程中，惩罚因子随着遗传代数的增加而线性增加，以便在运行终 止时，它们达到相当大的值，从而使可行解与不可行解分开，该算法与模拟退火算法有相 似之处b e l o v f 2 q 针对多种尺寸切段( m u l t i p l es t o c kl e n g t h s ) 问题，将c h v a t a l - g o m o r y 割平面法与列生成( c o l u m ng e n e r a t i o n ) 算法结合，构造了新的割平面法，并提出了舍入 启发式( r o u n d i n gh e u r i s t i c ) 算法，用该算法计算了单一切段问题和多尺寸切段问题，并 且将单一切段问题的数值结果与分枝定界法计算的结果相比较，同时对多尺寸切段问题 的数值结果进行了多种参数的敏感性分析。v a l e r i o l 2 q 回顾了经典的一维和二维布局问 题的线性规划模型，分析了这些模型对应的松弛线性规划之间的关系，并利用这些模型 的特性构造求解布局f 司题精确解的分枝定界法。j o h n s t o n l 2 s t 采用一个新的0 - 1 变量建立 了切段问题的数学模型，该模型不需要预先确定切割模式，并将可行约束隐含在其中 这个新模型解决了变量模式与采用模式次数的非线性问题，并将该模型应用于四个商业 实例。 二维布局问题中一刀切问题占有重要位置。所谓一刀切是指切割总是从矩形板材的 一边开始一直切到其对边，即每切一刀都将一个矩形分割成两个小矩形。这是剪床落料、 玻璃切割、纸张切割中遇到的主要问题。这类问题往往根据每个小矩形的个数是否限定 分为无约束一刀切问题( 每种小矩形的个数无限) 和约束一刀切问题( 每种小矩形个数 有限) 对此类问题的早期研究可以看作是切段问题的推广，但所有的研究只处理规模很 小的问题。1 9 6 5 年g i l m o r e 和g o m e r y 采用动态规划技术研究了无约束一刀切问题。 但是在实际生产中，各种类型工件的数量并不是无限的，而是有限的因此无约束一刀 切问题并不实用，切合生产实际的是约束一刀切问题 d u ，p a n 和s h i n g 2 9 j 首次用m l g r p ( m i n i m u ml e n g t hg u i l l o t i n er e c t a n g u l a rp a r t i t i o n ) 逼近m e l r p ( m i n i m u me d g e - l e n g t hr e c t a n g u l a rp a r t i t i o n ) 问题，对于特殊的例 子，逼近算法的性能比小于等于2 。m i t c h e l l 3 0 3 1 l 将上述结果推广到一般情况，相应 的将g u i l l i t i o nc u t 推广为1 - g u i l l o t i n ec u t ，该闯题可利用动态规戈l j 求解，运行时间为 6 第一章绪论 o ( n ”) 。随后他进一步推广为m g u i l l o t i n ec u t 3 “，同样用动态规划求解，运行时间变为 o ( n l o 川6 ) 。g h a n d f o r o u s hp a r v i z ”】将启发式算法用于一刀切问题。该启发式算法利用 第归和和返回的特性，来加快匹配操作的过程。w a n g ”1 提出了组合法，其基本思想是 不断地用当前的矩形或几个矩形组合成的矩形形成更大的矩形。由于可构成的组合非常 多，尽管采用阀值限定组合矩形中的废料率，可大大减少组合矩形的数目，但完全穷举 法势必会引起求解时间和存储空间的问题。o l i v e r i a a 4 1 于1 9 9 0 年对其进行了改进，但 是求解效率和存储空间问题仍很突出。e l e n i 3 5 1 等提出了一种新型的树搜索算法。该算 法通过利用上限限制了搜索树的尺寸，此上限由o _ 1 整数规划公式的l a g r m t g e a n 松弛法 决定。这种算法对于解决中等规模的一刀切问题很有效。l