（计算机软件与理论专业论文）求解圆形packing问题的过程模拟方法.pdf

求解圆形p a c k i n g 问题的过程模拟方法 专业：计算机软件与理论 硕士生：梁春明 指导教师：姜云飞教授 摘要 p a c k i n g 问题是国际上近年来备受关注的一类问题，在实际的生产生活中有 着广泛的应用，在工程中对应着大量的实例。如果能对这类问题给出最佳解决方 案，将会对众多产业产生深远的影响，取得非常可观的经济和社会效益。然而， p a c k i n g 问题是组合优化问题，属于n p 困难问题，求它的最优解几乎是不可能 的。圆形p a c k i n g 问题作为p a c k i n g 问题的一个部分，具有同样的计算复杂性。 研究者为圆形p a c k i n g 问题提出了各种多项式时间的近似算法。目的是在尽量快 的时间里求得满足工程要求的近似解。这些算法各具特点，在各个领域发挥了重 要作用，但同时这些算法往往源于特定背景，适用范围也局限于很小的领域。另 外，这些算法大多局限在单容器的p a c k i n g 问题范围，对多容器p a c k i n g 问题的 研究还局限在矩形或立方体范围。 本文结合顺特电气有限公司项目展开研究，提出了基于力学过程模拟的圆形 p a c k i n g 问题近似算法。该算法属于随机方法，用模拟力学过程的方法为各个待 布局的圆形找到一个静止位置为最终位置，并允许简化的碰撞和摇晃过程，还使 用占穴过程以减少圆间的空隙。从工程应用和实验模拟结果中可见，基于过程模 拟的圆形p a c k i n g 问题算法能够在可接受的尝试次数中，为各组数据找到较好的 工程满意解，甚至最优解，对多容器情形也能给出令人满意的解。而按此思想开 发的“浇注机空位控制子模块验证予程序”内嵌在顺特公司项目中运行良好，基 本上满足“顺特电气线圈生产车间资源规划系统”日常任务的要求。由此可见， 本文提出的算法为工业生产中解决圆形p a c k i n g 问题提供了一种可行的新思路。 关键词： 圆形p a c i n g 问题、近似算法、力学过程、模拟方法 a n a p p r o x i m a t em e t h o db a s e do ns i m u l a t i o no fm e c h a n i c s p r o c e d u r ef o rc i r c l ep a c k i n gp r o b l e m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l i a n gc h u n m i n g s u p e r v i s o r ：p r o f j i a n gy u n f e i a b s t r a c t p a c k i n gp r o b l e m sa r ec o n c e r n e dm o r ea n dm o r ei nr e c e n ty e a r sa n da r i s ei na v a r i e t yo fa p p l i c a t i o na r e a si ni n d u s t r ya n dr e a ll i f e i fw ec a ns o l v et h e s ep r o b l e m s w i t ho p t i m a ls o l u t i o n ，p r o f o u n de f f e c tw i l lt u r nu pi nm a n yf i e l d sw h i l eg r e a t e c o n o m i ca n ds o c i a lb e n e f i tw i l lb e g o t r e g r e t f u l l y , p a c k i n gp r o b l e m sb e l o n gt o n p - h a r dp r o b l e m a sas u b s e to fp a c k i n g p r o b l e m s ，c i r c l ep a c k i n gp m b l e mk e e p st h e s a m ec o m p u t a t i o n a lc o m p l e x i t y i n v e s t i g a t i o ns h o w st h a tf o rn ph a r dp r o b l e m s t h e r e d o e sn o te x i s ta l la l g o r i t h mt h a ti sb o t hc o m p l e t ea n dr i g o r o u sa n dn o tt o os l o w s o p e o p l et u r nt oe x p l o r eh e u r i s t i cm e t h o d s an u m b e ro f p o l y n o m i a lt i m ea l g o r i t h m sf o r c i r c l e p a c k i n gp r o b l e mw e r ed e v e l o p e d i no r d e rt o w o r k i n g o u ts a t i s f y i n g a p p r o x i m a t es o l u t i o n g e n e r a l l y , t h e s ea l g o r i t h m sb a s e do ns p e c i a lb a c k g r o u n dr u l e s b u tt h er a t i o n a l i t yo ft h e s er u l e se a r m o tb ep r o v e da n dt h e s er u l e si s t r i c tt h e a l g o r i t h m si ns m a l la r e a s o nt h eo t h e rh a n d ，m o s to ft h ee x i s t i n ga l g o r i t h m sd e a l o n l yw i t hs i n g l ec o n t a i n e r , o rd e a lw i t hm u l t i p l ec o n t a i n e r sb u tc o n s i d e ro n l y r e c t a n g l e so rc u b e s t h em e t h o db a s e do ns i m u l a t i o no fm e c h a n i c sp r o c e d u r ei sa n e ws o l u t i o nm e t h o df o rp a c k i n gd i f f e r e n t s i z e dc i r c l e si n t oar e c t a n g u l a rc o n t a i n e r t h a tw ed e v i s e dd u r i n go u rr e s e a r c hp r o c e s so ns h u n t ep r o j e c t ，i t sm a i ni d e ai st o f i n de a c hc i r c l e ss u i t a b l el o c a t i o nb ys i m u l a t i n gt h ed r o p p i n gd o w np r o c e s so ft h e c i r c l ea n dt h ec o l l i s i o nw i t ho t h e rc i r c l e s w ea p p l i e dt h i sm e t h o dt os h u n t e c o m p a n yd a i l yp r o d u c i n gd a t ae i t h e rs i n g l ec o n t a i n e ro rm u l t i p l ec o n t a i n e r s ，a n dg o t g o o dr e s u l t s i ti so b v i o u st h a t ，t h i sm e t h o ds u p p l yan e wa t t e m p tf o rc i r c l ep a c k i n g p r o b l e mi ni n d u s t r y k e yw o r d s ： c i r c l ep a c k i n gp r o b l e m ，a p p r o x i m a t ea l g o r i t h m m e c h a n i c sp r o c e d u r e ，q u a s i - p h y s i c a lm e t h o d 第1 章前言 1 1 选题的背景和意义 自从d o w s l a n d 1j 的综述以来，p a c k i n g 问题近年来在国际上越来越备受关注。 p a c k i n g 问题在实际的生产生活中有着广泛的应用，如果能对这类问题给出最佳 解决方案，会对众多产业产生深远的影响。因此p a c k i n g 问题吸引了许多领域的 许多研究人员对它进行深入的研究，使它成为涉及到数学、管理科学、工程科学 和信息与计算机科学等众多学科的一个重要研究领域。 然而，尽管p a c k i n g 问题有很强的工程代表性，但它属于组合优化问题1 2 ，3 1 ， 其解空间大得惊人，求它的最优解非常困难。即使是最简单的一维不带性能约束 的p a c k i n g 问题( b i n - p a c k i n g 问题) 就已经是n p 完全问题了。复杂工程系统的 p a c k i n g 问题更会涉及到几何形状的复杂性和任意性，涉及到大量的非线性数值 约束和大量的不可形式化的约束，因而目前鲜有实用的自动化的通用p a c k i n g 问 题解决系统问世。 对于n p 完全问题，既然没有准确的多项式时间算法，比较现实的方法是采 用多项式时间的近似算法。近似算法 4 1 分为启发式方法( h e t t r i s t i em e t h o d ) 和随 机方法( r a n d o m m e t h o d ) 两类。与盲耳搜索不同的是：窟发式搜索运用启发信 息，应用某些经验或规则来重新排列节点的顺序，使搜索沿着某个被认为是最有 希望的前沿区段扩展。启发式方法较多韵依赖于对问题构造和性质的认识和经 验，适用于解决不太复杂的问题。随机方法不依赖于问题的性质，从解空间中随 机的选择多个解，检查这些解的可行性，在可行解集中选择目标函数最优的解作 为最优解。基于这种方法的算法简单明了，但因为需要检查相当多的可行解集， 计算非常耗时，尤其对于大范围的搜索，很有可能遗漏最优解。 1 2 本文的研究重点 本文将结合顺特电气有限公司项目来展开研究。 顺特电气有限公司是我国干式变压器生产大型企业，连续十年国内市场占有 率第一，其产品远销国内外。1 9 9 7 年至2 0 0 0 年，顺特公司实施了o r a e t e 的e r p 管理系统，大幅度提高了工作和生产效率，然而该系统对变压器核心部件线 圈生产过程中的各种具体问题并没有一个良好的解决方案。为此，顺特公司自主 开发了“顺特电气线圈生产车间资源规划系统”。该系统涉及线圈生产流程中的 浇注工序：将不同规格的线圈( 圆) 装上小车( 矩形) 再送进浇注炉浇注。 由于线圈规格不定，数量也不定，这个装车闯题，研究的是一组小圆在矩形 大区域内互不重叠的优良布局，看似简单实质非常复杂，属圆形p a c k i n g 问题。 本人将采用一种新的模拟算法来求圆形p a c k i n g 问题的近似解。考虑人类装 填物品时的做法是，不断把待装物体扔进容器。差不多装满时，就摇一摇，让容 器内物体装得更紧密一些以腾出一定空间，再往容器装其它物体。本人的目标是 通过力学知识尽量近似地模拟这个过程，使用随机次序选择线圈进行装填，而线 圈的具体装填位鬣刚用力学方法来确定。 从工程应用和实验模拟结果中可见，基于过程模拟的圆形p a c k i n g 问题算法 能够在可接受的尝试次数中，为各组数据找到较好的工程满意解，甚至最优解。 1 3 本文的结构 本文将在全面阐述p a c k i n g 问题的基础上，比较目前流行的圆形p a c k i n g 问 题解决算法，探讨采用模拟力学过程的方法来构造圆形p a c k i n g 问题高效近似算 法。各章节内容安排如下： 第一章：阐述本论文的选题背景和意义、研究的重点 第二章：全面介绍p a c k i n g 问题 第三章：着重介绍圆形p a c k i n g 问题几个重要算法成果 第四章；阐述基于过程模拟圆形p a c k i n g 问题近似算法的思想及实现 第五章：以实际数据检验基于过程模拟的圆形p a c k i n g 问题近似算法的有效 性 第六章：对研究工作进行总结以并指明进一步研究的重点方向 2 第2 章p a c k i n g 问题 2 1 涉及范围 p a c k i n g 问题研究的是一组小物体在大区域内互不重叠的优良布局，属于布 局优化问题，在物体堆放、运输以及原料下料等领域中有着广泛的应用。从称谓 上看，还有其它许多问题并不叫做p a c k i n g 问题，甚至看起来与p a c k i n g 问题属 于完全不同的类别，而且被很多人当作不同类的问题进行研究。但就本质而言 不少问题与p a c k i n g 问题有着天然的内在联系，以致于很难有一个严格的界限将 他们区分开。比如c u t t i n g 问题、装箱问题、切割问题、裁剪问题和布局优化问 题等。首先，它们都有两组最基本的数据，一组是大的空间或原料，另一组是小 的物体或形状：其次。它们在本质上都是一种几何组合，即将小的物体或形状进 行某种组合，使之能充分利用大的空间或原料。因此，我们把这些问题看作一类 大的问题来讨论，后文也不单独提其它类的问题。 广义地讲，并不仅仅是物理空间才存在p a c k i n g 问题嘲。如果我们把p a c k i n g 问题抽象化，会发现对这类问题地研究广泛适用于其它领域。换句话说，其它很 多领域的问题实际上就是p a c k i n g 问题。这种进一步的理解为探讨这类问题注入 了新的活力。例如，如果将时间参数当作空间p a c k i n g 问题的一维数据，那么计 算机系统结构中的流水线指令处理问题和多处理器的并行处理问题就是一类典 型的p a c k i n g 问题；如果将包内物体的价值当作某一维数据，经典的背包问题实 际也属于p a c k i n g 问题的范畴：计算机存储器的分配从某种意义上看也是一种 p a c k i n g 问题。这类问题可被称做“非空间p a c k i n g 问题”。所有在“空间p a c k i n g 问题”中提出的p a c k i n g 算法都适用于“非空间p a c k i n g 问题”，这使得对p a c k i n g 问题这一领域的研究工作有了更深远的意义。 2 2p a c k i n g 闯题的具体分类 狭义地讲，p a c k i n g 是在一维、二维、三维物理空间中进行的。从这个焦度 出发，按涉及空间的维数可以将p a c k i n g 问题分为：一维p a c k i n g 问题、二维 p a c k i n g 问题、三维p a c k i n g 问题等。上述分类还可按下文几种方法进一步再分 类。这种局限于物理空间内的裁剪装填又可被称为“空间p a c k i n g 问题”。 按应用背景可以将p a c k i n g i 口- j 题分为：单元装箱问题( b i n p a c k i n g p r o b l e m ) 1 7 1 、 各种原材料的裁剪问题( s t o c k c u t t i n g p r o b l e ma n d c o n t a i n e r p a c k i n g ) 、集装箱装 入问题( c o n t a i n e rl o a d i n gp r o b l e m ) 、货盘装填问题( p a u e t l o a d i n gp r o b l e m ) 等。 按p a c k i n g 涉及物体的形状可以将p a c k i n g 问题分为：规则形状p a c k i n g 问 题、不规则形状p a c k i n g 问题。 按是否知道各物体的信息可以将p a c k i n g 问题分为：在线( o n l i n e ) p a c k i n g 问题、半在线( s e m i o n - l i n e ) p a c k i n g 问题、脱线( o f f - l i n e ) p a c k i n g 问题。 按是否考虑空间各维上除空间位置外其它约束作用可以将p a c k i n g 问题分 为：不带性能约束p a c k i n g 问题和带性能约束p a c k i n g 问题。 2 3 目前研究情况 对p a c k i n g 问题的研究，目前主要集中在两个方面：一是对一维经典p a c k i n g 问题( b i n - p a c k i n gp r o b l e m ) 的理论研究；二是探索二维、三维p a c k i n g 闯剐8 l 的高效近似算法。二维、三维p a c k i n g 问题的工程背景往往是空间位置的布置问 题，也常常称为布局问题。 2 4b i n - p a c k i n g 问题的解法 b i n p a c k i n g 问题具有重要的理论意义，对二三维p a c k i n g 问题特别是矩形 p a c k i n g 问题的解具有很好的指导和启发作用。因此，我们在此详细介绍 b i n p a c k i n g 问题的各种解法和理论成果【9 】。 2 4 1b i n p a c k i n g 阔题 经典一维p a c k i n g 问题是：给定n 个物品的序列l 。= ( a l ，a 2 ，a n ) ， 物品a i ( 1 = i - - n ) 的大小s ( a 0 ( 0 ，1 ) ，要求将这些物品装入单位容量的箱子b l ， b 2 ，b 。中，使得每个箱子中的物品大小之和不超过l ，并使所用的箱子数 目l i f t 最小。 对给定的经典p a c k i n g 问题近似算法a ，记a ( l ) 为算法a 对输入物品序列l 操作所使用的箱子数目，o p t ( l ) 是最少必须使用的箱子数目。最坏情况渐近性 能比、最坏情况绝对性能比和在线特性是评测近似算法性能的重要标准。 定义：对于一个近似装箱算法a ，如果存在常数r 使得对于任何输入物品 序列l ，a ( l ) = n 时，a ( l ) o p t ：l ) 呵恒成立) 定义：对于一个近似装箱算法a ，a ( l ) 与o p t ( l ) 比率的上界称为近似算法 a 的最坏情况绝对性能比，记为r a 。即 r a = s u p a ( l ) o p t ( l ) b i n p a c k i n g 问题任意近似算法的最坏情况渐近性能比都不会比最坏情况绝 对性能比更大。大多数的最坏情况下，算法性能比收敛于渐近性能比。但对于相 4 对较短的物品序列，绝对性能比也是算法关心的指标。 定义：如果近似装箱算法a 依序处理各输入物品，当处理当前物品的时候， 不知道任何后续物品信息，并立即给出当前物品的装箱方案，则称这样的近似装 箱算法a 为在线( o n l i n e ) 装箱算法；而首先得到所有物品信息之后，统一处 理所有物品装箱方案的近似算法则为脱线( o f f - l i n e ) 装箱算法。 2 4 2 基本在线( o n l i n e ) 装箱算法 最早提出的在线装箱算法是“下次适应算法”( n e x tf i t ，简称n f ) ，它按顺 序依次处理各物品：首先把物品a l 放入箱子b l 中，再考虑物品a 2 ，如果a 2 能够 放入b j ，则将a 2 放入b 1 中，否则关闭箱子b 1 ，打开一个新的箱子b 2 ，并将a 2 放入b 2 中；然后按照相同的方法依序处理各物品。在处理物品a i 时，假设已经 使用的箱子是b l ，b 2 。，b 。它只考虑箱子b t 中是否放得下物品a i ，而不 管b l ，b 2 ，b l - l 中是否有足够的空间放下这个物品。 下次适应算法的性能较差，对它改进后的适应算法在处理物品8 i 时，如果所 有已经使用的箱子都不能放下物品a i 则打开一个新的箱子并把物品a i 放入这个 箱子中；否则考虑已经使用的箱子b l ，b 2 。，b t 中所有能够放下a i 的箱子 b i ，b 2 ，b 。，使用一种策略从中选出一个箱子并把物品a i 放入该箱子中。 当使用的选择策略分别为选择第一个( 下标最小) 、选择最佳的( 已装载物品大 小的和最大) 、选择最坏的( 已装载物品大小的和最小) 的时候，分别得到 b i n - p a c k i n g 问题的首次适应算法( f i r s t f i t ，简称f f ) 、最佳适应算法( b e s t f i t ， 简称b f ) 和最差适应算法( w o r s tf i t ，简称w f ) 。 对在线b i n - p a c k i n g 算法来说，当物品序列按大小递增有序或者部分递增有 序时，算法性能将受到严重的影响。如对四个物品的序列：0 2 ，0 7 ，o _ 3 ，0 8 ， 无论采用b f 、n f 、f f 还是w f 算法，都需要3 个箱子才能装下。事实上此 四个物品只需2 个箱子就能装下。 四个算法的时间复杂度及最坏情况渐近性能比如下： 2 4 3 基本脱线( o f f - l i n e ) 装箱算法 最基本的四个脱线算法来源于四个在线算法。将物品序列从小到大排列成非 5 递增序列，再对新序列使用f f 、b f 、n f 或w f 策略，得到脱线p a c k i n g 问题的 f i r s tf i td e c r e a s i n g ( f f d ) 算法、b e s tf i td e c r e a s i n g ( b f d ) 算法、n e x tf i t d e c r e a s i n g ( n f d ) 算法、w o r s tf i td e c r e a s i n g ( w f d ) 算法。 j o h n s o n l l o l 证明了f f d 和b f d 算法的最坏情况渐近性能比为1 l ，9 ： s i m c h i - l e v i l l l 则证明，除非p = n p ，否则f f d 和b f d 算法的最坏情况绝对性能 比为3 2 。对于现实问题而畜，最坏情况绝对性能比比最坏情况渐近性能比更有 意义，所以，这个3 2 近似值是我们对装箱问题的近似算法的最好期待。 2 4 4 改进的算法 无论在线还是脱线情形，研究者提出了越来越多的新算法。这些新算法一般 在效果( 渐近性能比) 或效率( 算法复杂度) 方面做了改进，如h a r m o n i c m 算法、m h 算法等在线算法和o f f b p 算法、e p f f 算法 1 2 i 、c f 算法【1 3 】等脱线算 法。 下面( 1 4 1 分别介绍一个脱线算法和一个在线算法。它们同一思想方法，就最 坏情况绝对性能比而言，达到了最优或相对最优。 定义：如果一个物品的尺寸大于0 5 ，则称之为大物品，否则称为小物品。 脱线算法a l ： 1 、将每个大物品放进一个箱子中，给这些箱子编上序号，将他们标志为 “活跃”的。重复下列动作处理小物品a 。 2 、如果存在打开的“活跃”的箱子，选择下标最小的一个，若能装入a 。 则装入，否则关闭此“活跃”箱子考虑“辅助”箱子 ( a ) 如果存在“辅助”箱子并能装入a i ，则将a i 装入 ( b ) 否则关闭“辅助”箱子，打开新的箱子作为“辅助”箱子，将 a 装入 3 、如果不存在打开的“活跃”的箱子，打开新的箱子作为“活跃”箱子， 将a i 装入 a 。是线性时间的算法，最坏情况绝对性能比为3 2 。因此，除非p = n p ，算 法a ，达到了脱线算法的最优情况。 定义：如果一个箱子装入的第一个物品是大物品并且还没有设置成“活跃” 状态，则称为“l 箱子”。 脱线算法a 2 ： i 、将第一个物品放进一个新箱子中，将这个箱子标志为“活跃”的 6 2 、处理物品a i 时，如果存在打开的“活跃”的箱子s j ，并且s j 中有足够 空间接纳a i 的话。将a i 装入箱子b ，。若b j 中没有足够空间接纳a i ： ( a ) 如果a i 是大物品，打开新的箱子放迸a i 。这个箱子这时是“l 箱 子”。如果系统此时共有两个“l 箱子”，关闭它们 ( b ) 如果a i 是小物品，关闭“活跃”的箱子；如果存在打开的“l 箱 子”，将它设为“活跃”的；如果存在打开的“辅助”箱子并能 装入a i ，将a i 装入，否则用一个新的箱子装入a i ，将该箱子设为 “辅助”的 3 、如果不存在打开的“活跃”的箱子，打开新的箱子作为“活跃”箱子， 将a i 装入 算法a 2 仅需常数个辅助空间，其时间复杂度也是0 ( n ) 的，它的最坏情况绝 对性能比为7 4 ，但若没有大物品的话，最坏情况绝对性能比为3 2 。 2 5 布局问题 布局和布置设计问题( p a c k i n gp r o b l e ma n dl a y o u td e s i g n ) 1 1 5 ，6 】是给定一 个布局空间和若干待布物体，将待布物合理地摆放在空间中满足必要的约束，并 达到某种最优指标。布局问题大量地出现在机械制造、皮革服装、造船、玻璃、 交通运输、航空航天、大规模集成电路的设计及医学物理应用等诸多领域，例如 服装下料，车间布局，集装箱货物摆放，仪器舱内仪器布局；飞机、车辆的布置 设计等。 2 5 1 分类 根据布局空间和待布物体的形状，布局问题分为： ( 1 ) 二维规则物体布局问题。待布物和布局空间都是矩形或圆形，如装盘问 题( p a l l e tl o a d i n gp r o b l e m ) ，玻璃下料一刀切问题( g u i l l o t i n ec u t t i n g p r o b l e m ) 等。 ( 2 ) 二维不规则图形布局问题。待布物体和布局空间中至少有一个是二维不 规则图形，如服装裁剪中的划印布置问题( m a r k e rl a y o u tp r o b l e m ) 、造船业板 材切割中的部件拼装问题( p a r t sn e s t i n gp r o b l e m ) 和机械行业冲压落料问题 ( m e t a ls t a m p i n gp r o b l e m ) 等。 ( 3 ) 三维规则物体布局问题。包括长方体、圆柱体及球体布局问题，常用的 是待布物体和布局空间都是长方体，如集装箱布局。 ( 4 ) 三维不规则实体的布局闯题。待布物体和布局空间是三维不规则实体， 如坦克舱布置设计，火箭仪器舱内的仪器布局问题。 迄今为止，关于布局问题大量的理论研究仅限于第( 1 ) 、( 3 ) 类问题的矩形体 7 范围内。这两类问题由于本身是n p 完全问题，随着布局物体数量的增加，解空间 呈指数倍地扩大，出现组合爆炸现象，用动态规划、分支定界等基于穷举思想的 算法都无法解决。因此，关于这两类问题的所有算法都是基于特定应用领域的启 发式算法，它们的解题效果随着具体问题的不同有很大的差别，且都只能找到近 似可行解。至于第( 2 ) 、( 4 ) 类问题，由于布局对象形态的随意性使得问题变得 异常复杂，目前国内外对这类问题的理论研究进展非常小，研究报导也很少见。 2 5 2 研究现状 自1 8 3 1 年g a u s s 研究格的有关布局问题开始，至今已有百余年的历史。 d o w s l a n d 、s w e e n y 等人l l 。”j 对二、三维布局问题做了较为全西的综述。据s w e e n y 等【1 7 j 1 9 9 2 年的统计，从1 9 4 0 年至t j l 9 9 2 年，全球关于布局方面的研究文献达4 0 0 余 篇，涉及1 4 0 多个应用领域，其中涉及非矩形形体的2 7 篇，而涉及三维非矩形形 体的只有3 篇( 布局对象都具有相同的形状和大小，方法大都采用基于矩形体布局 的经验式方法，即工程师根据经验将不规则物体通过合并、简化等手段转化为矩 形体，再利用启发式方法求解) 。到目前为止，关于布局问题的研究文献超过1 5 0 0 篇，而涉及三维不规则实体的布局问题不过1 0 篇。由此可见，虽然布局问题得到 了广泛而深入的研究，但对于复杂布局问题仍没有太多进展。 2 5 3 布局物体的建模方法 布局物体可分为援贝| l 形体( 如矩形、长方体) 和不勰刚形体。由于不觏则形体 的形状复杂性在具体处理上的困难，使得现有的布局算法的处理对象大多局限于 规则形体，两将不规则形体篱化为矩形、圆形等觌刚凡何形体。 唐飞等【1 8 】将航天器中一种复杂插座板上插孔的布局设计问题简化为二维圆 形装填闻题。 随着人们对布局问题本身及其求解理论和方法等认识的逐步深入，以及实际 应用中对不规则物体布局问题有效求解理论祁方法需求的不断增加，不规则物体 的布局问题逐渐引起越来越多的重视。 戴佐、查建中等【1 9 】将八叉树数据结构引入到三维实体的计算机仿真布局及 智能最优布局领域，用以表示任意形状的三维实体及三维布局空间。他们在文献 2 i 】给出了三维实体的实体造型和干涉检验的八叉树方法。利用八叉树数据结 构将三维实体布局对象及空间分布状态表达出来，为布局问题提供了良好的解决 基础。 王爱虎、查建中( 2 铂提出利用- - x 树结构表达矩形物体布局状态空间的方法， 并提出了解决简单多边形裁剪和交并计算的统一的算法。 8 陆一半等”提出2 l 叉树方法使八叉树表达理论得到了扩展，从而为研究和 解决多维布局和抽象布局问题提供了一个通用的方法途径，对其它八叉树应用也 有启发意义。 不规贝物体的表达和干涉检验对布局问题求解是一个重要且关键的方面，已 有相当的进展。与布局问题的其它关键技术相比，它还是较单纯的问题。这一技 术的发展在于对任意形体的几何和非几何特征的充分表达和描述，以及运算、存 储的高效，使得它在工程应用中更实用可行。 2 5 4 布局过程的建模方法 布局阀题知识模型的建立是目前布局领域的一个弱点。复杂布局问题是多约 束多目标的组合优化问题。由于布局知识( 约束、目标) 的多样性，这种组合优化 问题无法用单一的数值优化模型来表达，因而属于一种广义优化问题。布局问题 的模型主要包括数学模型、图论模型、符号知识模型、人工神经网络模型等。 ( 1 ) 数学模型 现有的大部分布局问题的模型，一般都是将原问题进行简化( 包括几何形体、 约束和目标知识) ，建立单纯的数学模型，然后用组合最优化中广泛应用的线性 规划法、整数规划法、动态规划法或分枝定界法等数学方法进行问题的求解。 v a l e r i o d ec a r v a l h o 等融l 将两阶段下料问题抽象为约束优化问题，并用一 简化的线性规划模型来表达该约束优化问题，最后用列生成技术对得到的线性规 划模型进行求解。 e n r i c of a g g i o l i 等【2 5 j 建立了切割排序问题的数学模型，分别用贪婪算法和 禁忌搜索求解。 黄文奇等【2 6 】将布局干涉约束用解析形式表达出来，提出一种求解布局问题 的拟物方法。 滕弘飞等【2 n 以入造卫星舱的布局为背景，建立简化的规则物体布局优化模 型，利用惩罚因子将布局约束转化为目标函数惩罚项，提出了旋转锥体空间中圆 柱体群和长方体群的布局优化算法。 将布局问题抽象简化建立数学模型，为求解提供了便利。但是当原问题涉及 一些不易用数学模型表达的约束条件时，采用各种近似方法得到的数学模型往往 会与原问题产生较大的偏差，并且当问题规模增大、解空间急剧增加时，它们的 求解复杂性变得很强，很难或无法得到有效解。 ( 2 ) 图论模型 以图中的结点代表待布局物体，弧线代表布局物体之间的关联关系，由此将 布局问题转化为在一个已知的连接图中寻找最大独立集或最大权平面子图问题： 9 然后借助于分枝定界、整数规划及动态规划等方法进行问题的求解。 相邻拓扑图模型是用图论方法表示布局的典型方法。 尽管作为组合数学的重要组成部分的图论方法在许多领域有着广泛的应用 并卓有成效，但布局问题的图论方法只限于小规模规则物体布局问题的求解，仍 然不能充分表达布局知识及约束。当布局问题的规模较大且涉及不规则物体时， 布局问题的图论求解方法将不再适用。 ( 3 ) 复合知识模型 复杂布局问题不仅涉及可用数学模型描述的知识，如问题的几何、运动学和 动力学约束和优化目标等，而且涉及无法用数学模型描述的知识，如布局物体的 材料性能以及装卸工艺，特别是人类专家的布局领域知识。由此，任何单一模式 的知识模型( 数学模型、图论模型、人工神经元网络等) 都不足以精确地表达这样 的问题。因此，应该为之建立集成各种单一模型的复合知识模型。 许多研究者 2 8 , 2 9 】都对人机结合解决布局问题进行了探索，为复杂系统布局 求解自动化的建模迈出了关键一步。 2 5 5 布局问题的求解方法 目前布局问题的求解方法主要有： ( 1 ) 数学方法 布局问题被抽象简化为一定的数学模型后，通常采用数学规划或数值优化的 方法求解。 a n t o n i o 等 3 0 l 针对工业切割问题提出了两种基于动态规划的方法，一种倾向 于求解时间的缩短，另一种倾向于解的质量。 t o t h 3 1 】建立了组合优化问题的数学模型，并认为求解的最优化方法是各种 数学规划方法的混合。 数值优化方法只能找到局部最优解，所得解的质量在很大程度上依赖于初始 解的选择，因而一些学者口2 1 致力于研究布局初始方案的自动生成方法。 数学规划方法依赖于数学模型而导致局部最优解。这一局限性为很多研究者 所重视。他们采用具有全局搜索能力的计算智能算法与局部搜索的数学规划算法 相结合，得到较好的结果【3 3 , 3 4 】。在纯数学推导中加入启发式经验，极大地提高问 题求解能力，这一思想值得借鉴。 ( 2 ) 图论方法 以图论为工具建立布局问题的图论模型后，借助图论方法求解。布局问题的 图论方法只限于小规模规则物体布局问题的求解。当布局问题的规模较大且涉及 不规则物体时，布局问题的图论求解方法将不再适用。 1 0 ( 3 ) 专家系统技术 布局问题是一个领域性很强的问题，有不少学者认为利用专家系统与适合于 某一领域的知识模型相结合是解决具体领域计算机布局设计的有效方法，并对布 局知识获取、描述和创造性推理做了很多有益的研究【2 9 ，3 ”。 利用专家系统技术辅助机械产品的南局设计，可以充分利用积累在专家头脑 中的大量布局知识，构造布局设计领域知识库。专家系统的推理机制和人机接口 可以使计算机和用户对比知识，进行处理和利用，在一定程度上完成布局决策工 作。但利用专家系统进行布局设计，在布局知识的获取、表达等方面存在很多困 难，只能按照预定的模式进行推理，缺乏创造性，更缺乏自学习和自适应能力。 由于专家系统技术只能处理单一知识领域范畴的符号推理问题，因此布局专 家系统只能在布局过程的某一阶段起到作用，它的封闭性、领域针对性、缺乏自 适应能力和自学习能力，都使之无法单独承担复杂系统布局的求解任务。 ( 4 ) 人工神经网络方法 自从h o p f i e l d 利用h o p f i e l d 神经网络成功地求解了旅行商( t s p ) 问题以来， 人工神经网络方法在组合优化领域得到越来越多的重视。人工神经网络具有自适 应性、自学习性、强容错性和巨并行性等许多人脑所具有的特性。章炯民等【3 5 】 将人工神经网络的方法和启发式方法结合，构造了求解布局问题的混合算法。然 而常规神经网络( 如h o p f i e l d 网络) 存在局部最小问题，它的解依赖于网络的初始 状态，在许多场合仅能得到次优解。 混沌神经网络是一种新兴的神经网络，由于其混沌动力学特性，易于摆脱局 部极小点。文献【3 6 】将混沌神经网络用于二维布局求解中，得到较好的解。 ( 5 ) 启发式方法 布局问题是应用背景较强的离散组合最优化问题。即使是最简单的规则形体 布局问题，也属于n p 完全问题1 3 】。n p 完全性理论的研究表明：在有限合理的时间 内，不可能求得大规模n p 完全问题的精确解，问题的求解只能依赖于各种启发式 方法。由此，布局问题的研究人员f 一4 0 1 开始注重对各种启发式方法的研究，而 且发展了目前比较流行的计算智能算法，例如遗传算法 4 1 - 4 6 、模拟退火算法 4 7 】、 禁忌搜索【4 8 1 等。 每一个具体的启发式算法都可看作是其中的某一方法或几种基本方法的有 机组合。而且，启发式方法大多基于特定的应用领域，不同的方法在不同的应用 顿域所收到的效果是不同的。因此可以根据布局问题在各个不同的应用领域的具 体特点，结合各领域中的成功经验，设计出具有领域特色的各种启发式布局求解 算法。 第3 章圆形p a c k i n g 问题算法 如果p a c k i n g 问题中待排物品全部为圆形，则我们称之为圆形p a c k i n g 问题 m 】。工程中大量的布局优化问题属于圆形p a c k i n g l b 题，包括填充和裁减两类应 用，吸引了许多研究者为之努力。但圆形p a c k i n g 问题属于n p 难题，求其全局最 优解很困难。目前常用的算法有数学规划法、启发式算法、图论法、人工智能、 计算智能如遗传算法、模拟退火法等，目的是求得一个能满足工程要求的较好解。 应当指出的是，目前对p a c k i n g 问题的研究，大多是针对单容器情形的：针对多 容器装载的研究，一般限于矩形或长方体物件情况，比如集装箱问题。 3 1 等圆p a c k i n g 问题 正方形中的等圆布局问题是在优化领域中被广为研究的一个问题，即在边长 为l 的正方形中无重叠地布置n 个圆，求圆的最大可能半径。这一问题有另外一种 叙述方式是：在单位边长的正方形中找出n 个点，使得这n 个点两两之间距离的最 小值尽可能的大。目前除对少数特殊n 值外，这一问题未能够获得解析摄优解。 近年来，已知的最好解已经从n = 1 0 逐渐增加到了超过5 0 s o 。 对矩形区域内的等圆p a c k i n g 问题，d o w s l a n d 提出了调整行间圆夹角的方法 来求解【5 l 】，f r a s e r 和g e o r g e 利用此方法解决纸卷运输中遇到的问题吲。 3 2 拟人拟物算法 n p 难度问题根本就不存在经典数学所希求的那种既完备严格又不是太慢的 求解算法。于是人们开始到大自然中去寻找智慧，以期得出关于n p 难度问题的非 绝对完整的，但是高速度高可靠度的高效率近似求解算法。其工作路径是，到物 理世界中去寻找出与原始数学问题等价的自然现象，然后观察其中物质运动的演 化规律，从中受到启发以得出形式化的，对于数学问题的求解算法。可以称这个 工作路径为拟物方法。 由于物理状态的演化天然地是按照使其l a g r a n g e i h 数的时间积分达到最小 值的方式进行，这就决定了拟物算法最终在数学上落实为优化闯题。然而用数学 方法求解优化问题，常常会碰到计算落入局部最小值陷阱的困难境地，对于如何 跳出局部最小值陷阱，让计算走向前景更好的区域中去的问题，拟物方法已无能 为力。但是，人类在最近几千年的共同生活中形成了丰富的社会经验，利用这些 经验往往可以启发出好的“跳出陷阱”的策略。我们可以将这种把人类的社会经 验形式化为算法用以求解某些特殊困难的数学问题的方式称为拟人途径 1 2 黄文奇等 s 刀的拟人拟物算法，通过模拟圆与圆、圆与容器之间的弹性势能， 将p a c k i n g 问题转化为对圆心坐标的函数优化问题，再用拟人策略或模拟退火法 逃离局部最优，提高搜索效率： 假设已知一个圆形的空盒子( 容器) ，另外又已知一些不同大小的圆饼，问能 否将这些圆饼互不重叠地放进空盒子中去。 在二维e u c l i d 空间中考虑这个问题。将圆饼想象为光滑的弹性实体；将容器 想象为挖去了一个圆饼之后面剩下的二维无穷弹性实体。设想这些圆饼被挤缩在 容器中，由于各个物体都有要恢复自己形状大小的趋势，它们之间产生了挤压弹 性力的相互作用。在这种挤压弹性力的驱使下，各物体会产生一系列的运动。作 为这种运动的结果，可能就是问题的解的确立各物体到达某种相互合适的位 置。两两互不嵌入。于是，求解圆形容器中圆形物体的p a c k i n g 布局问题就转化 为对圆心坐标的函数的优化问题。这是拟物策略的运用。 拟物算法在执行过程中，当问题在客观上比较困难时，往往会碰到“卡壳” ( g e ts t u c k ) 的情形，即计算落入了局部极小值点的陷阱。 在热闹拥挤的公共汽车中，受挤压最甚者总是设法改换自己的位置，而处境 宽松者往往也会让出一部分空间给予别人。将挤缩在容器内的圆饼以及容纳这些 圆饼的圆盘看成一个公共汽车的车箱，可以通过模拟拥挤的公共汽车上人们的行 为来逃离这个局部最优点。 发生“卡壳”情形时，挑出受挤压最甚的圆饼，将它随机地放到圆盘中的某 一个地方去：有时也可以挑出那个感受最宽松的圆