（机械设计及理论专业论文）基于目标和空间正交分解的布局启发式算法的研究.pdf

摘要 布局问题源于现代生产和生活的许多领域并表现为多种形式，由于布局问 题是应用背景较强的离散组合最优化问题，属于n p 完全问题，而n p 完全问题 的解决，只能依赖于各种应用广泛的局部寻优的启发式算法。沿着这一优化问 题解决的路经，在研究分析现有布局启发式算法的基础上，通过大量布局实验 并不断地总结，提出了基于目标和空间正交分解的布局启发式算法，解决布局 过程中的非一刀切布局问题。算法可概括为，“在布局过程中，构造最合适的物 体，放入最适合的位置，达到最基本的布局目标”。论文的主要内容如下： 首先分析了布局问题中的空间分解方式，论述了满足非一刀切要求的布局 空间正交分解的过程，说明了组成剩余布局空间的第一和空间、第二和空间的 正交分解的方法和步骤。 其后论述了实现算法的各种策略，包括差空间( 第一差空间、第二差空间) 策略、群组策略、回溯策略、收敛空间策略等并详细阐述了群组的定义、方 式、约束及算法等；各种布局策略的综合运用，使布局能按空间正交分解的方 式持续进行。 通过对多阶段布局过程及局部最优解与全局解之间关系的分析，提出了解 决布局问题的目标策略。布局之前确定布局目标，布局过程中使在一定约束下 的每一个局部最优解达到布局目标，从而得到全局好的解，也保证了布局算法 的可靠性和稳定性。 针对基于传统定序规则的布局启发式算法，提出了布局过程的阶段性原理， 分析了布局余量产生的方式及特点，并将这些原理与特点用于布局算法的设计 之中。 介绍多模式生成法以及在基于空间正交分解的布局启发式算法中的应用， 以满足一定约束条件的布局问题的需要或解决太规模的布局问题。 最后，对全文的工作进行了总结并展望迸一步的研究方向。 关键词：布局，启发式算法，正交分解，和空间、差空间、群组、模式生成法 a b s t r a c t p a c k i n gp r o b l e m s w i t ht h e i r n p - c o m p l e t ec o m p u t a t i o n a lc o m p l e x i t i e s a r e c a t e g o r i z e da sd i s c r e t ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sw i t hs t r o n ga p p l i c a t i o n b a c k g r o u n d ，a n dt h e yo c c u ri nav a r i e t yo fs i t u a t i o n so fm o d e mi n d u s t r ya n dl i f e h e u r i s t i ca l g o r i t h m sa r en e e d e dt os o l v et h en p - c o m p l e t ep r o b l e m s ，w h i c hi st h e m e t h o do ft h i sp a p e rt os t u d yt h ep a c k i n g p r o b l e m s o nt h eb a s i so f l o t so ft e s t sa n d t h ew i d er e s e a r c ho nt h ep a c k i n gp r o b l e m s ，ah e u r i s t i ca l g o r i t h mb a s e do n o b j e c t i v e a n do r t h o g o n a ld e c o m p o s i t i o no fs p a c ei s d e v e l o p e dt o s o l v et h e n o n g u i l l o t i n e p a c k i n gp r o b l e m 。t h ep a p e r c a l lb eo u t l i n e da sf o l l o w s ： i t b e g i n sb ya n a l y z i n g t h e d e c o m p o s i t i o nf o r m s o fs p a c ei nt h e p a c k i n g p r o b l e m s t h ep r o c e s s o fo r t h o g o n a l d e c o m p o s i t i o n o ft h e p a c k i n gs p a c e i s a d d r e s s e dt o s a t i s f yt h en o n - g u i l l o t i n ep a c k i n gp r o b l e m ，w h i c hd e c o m p o s e st h e r e s i d u a ls p a c ei n t ot h e1 s ts u n l - s p a c ea n dt h e2 n d s u m s p a c e s e v e r a l s t r a t e g i e si n c l u d i n gs t r a t e g y o fd i f f e r e n c e s p a c e ，s t r a t e g y o fg r o u p w h i c hi sd i s c u s s e di nd e t a i l ，s t r a t e g yo f b a c k d a t i n g ，s t r a t e g yo f c o n v e r g e n c e ，a r eu s e d s y n t h e t i c a l l y t o i m p l e m e n tt h ep a c k i n ga l g o r i t h ma n dt or e a l i z et h ec o n t i n u o u s o r f h o g o n a ld e c o m p o s i t i o n o f t h e p a c k i n gs p a c e t h e s t r a t e g y o fo b j e c t i v ei s d e v e l o p e dt h r o u g ht h e a n a l y s i s o ft h e l o c a l o p t i m i z a t i o na n dt h e 百o b a lo p t i m i z a t i o n i ts e t sa l l 删e c t i v ew h i c hi st h el o w e s t s o l u t i o nt ot h el o c a lo p t i m i z a t i o na tt h eb e g i n n i n g ，t h u s ，t h i s a l g o r i t h mc a ng e tav e r y g o o dg l o b a ls o l u t i o n p h a s i ct h e o r yo ft h ep a c k i n gp r o c e s sa n dt h ec h a r a c t e r i s t i c so ft r i ml o s sa l e a p p l i e d t od e s i g nt h e p a c k i n ga l g o r i t h m m m t i p l ep a t t e mo r i e n t a t e da p p r o a c hi su s e d i nt h eh e u r i s t i ca l g o r i t h mb a s e do n o b j e c t i v ea n do r t h o g o n a ld e c o m p o s i t i o no fs p a c e t os o l v et h el a r g e - s c a l e p a c k i n gp r o b l e m f i n a l l y , c o n c l u s i o n so ft h ew h o l ed i s s e r t a t i o na r em a d ea n df t l r t h e rr e s e a r c h d i r e c t i o n sa l eg i v e n k e y w o r d s ：p a c k i n g ，h e u r i s t i c a l g o r i t h m ，o r t h o g o n a f d e c o m p o s i t i o n ，s l i m s p a c e ， d i f f e r e n c es p a c e ，g r o u p ，p a t t e r no r i e n t a t e da p p r o a c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得墨盗盘茎一或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：衔j 秘 签字日期： 一弓年千月r 日 学位论文版权使用授权书 本学位论文作者完全了解盘奎盘堂有关保留、使用学位论文的规定。 特授权叁鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：箭弗雾p 导师签名： 乏会远屯 签字日期：二9 p 弓年斗月参d 日签字日期：舻三7 年 争月1 日 第一章绪论 1 1 课题的提出 第一章绪论 布局问题是设计领域的一个重要组成部分，在工程实践中有着广泛的应用 和重要的实用价值。布局问题最初主要表现为下述两种形式n ：第一，将一些 给定形状及大小的区域分割成若干所需要的形状及大小的几何体，总目标为使 区域所限定空间的利用率最高，即浪费最少，此类问题通常称为切段问题( c u t t i n g s t o c kp r o b l e m ) ；第二，互不叠迭地放置一些已知形状和大小的几何群体，使得 所有群体所形成的外包络区域的测度( 即长度，面积或体积) 最小，或者将这些几 何体组成为若干组，要求每组的外包络区域之测度不得大于某一给定值，总目 标为所形成的组数最少，此类问题称为装填( p a c k i n gp r o b l e m ) 问题。虽然这两类 问题表现的形式不同，前者为“切”，后者为“装”，但其本质是一样的，都可 以理解先将空间进行满足约束条件的划分，然后进行“切”和“装”，所以这两 类问题在研究内容上都属同一个问题，称之为布局问题，h a r a l d t 2 称之为c u t t i n g a n d p a c k i n gp r o b l e m 。 布局问题来源于实际生活及生产的许多方面，广泛出现在出版印刷、纺织、 服装、皮革、玻璃、造船、交通运输等传统工业，以及城市规划、模式识别、 航空航天、机器人、大规模集成电路设计等现代科技领域。布局问题在各方面 的表现形式不同，例如，在造船业、纺织业及玻璃加工业中，表现为从确定规 格的二维原材料中裁剪出一定数量的产品，并最大程度地降低原材料的损耗； 在交通运输业中，表现为在不同形状的运输工具中，合理地摆放各种大小的货 物，以保证货物运输安全和装卸方便的情况下尽可能减少所需要的运输工具； 在建筑和城市规划设计中，表现为建筑物的地址位置合理布置，以满足生活和 生产的实际需要。 布局问题是复杂的离散组合最优化问题，同其它诸多组合最优化问题，如 图的划分问题、最短通路问题( 研究较多的有旅行商问题、中国邮路问题等) 等一样都属于n p 完全问题。m s g a r e y 和d s j o h n s o n t a 在其关于n p 完全性 理论的专著中已明确指出：在有限合理的时间内不可能求得n p 完全问题的精 一1 第一章绪论 确解，问题的求解只能依赖于各种启发式算法。从s w e e n e y 等h 有关布局问题 文献的统计发现，绝大多数实用布局算法都是启发式的。各领域布局问题中寻 找布局物体在布局空间中的合理布局这一首要目标是共同的，因此求解布局问 题的理论和方法大多可以互用；但同样的布局问题在不同的行业和应用背景下 有着不同的约束条件和不同的目标，所以试图找到一种用于求解布局问题的通 用算法是不可能的，应针对不同的工业背景，研究相应的专用算法。 布局问题在许多行业是一个重要的生产环节，如果应用快速有效的布局问 题的解决方法，则可以大大地降低生产成本，提高生产效率。长期以来，布局 问题吸引了国内外众多的学者，一些研究在一定条件下取得了较好的结果。纵 观近几年对布局问题的研究以及布局问题在实际中的应用，有以下几点值得注 意。 ( 1 ) 行业中存在的大量人工布局现象。随着全球对资源消耗问题的日益重 视及降低消耗也是环境问题治本措施等新观念的出现，制造系统资源优化利用 的研究已愈来愈重要。制造过程中的下料问题就是制造系统中资源优化利用问 题之一。如在冲压生产中，材料费占生产成本的6 0 左右【5 l ，因而提高材料利 用率一直是降低成本提高效益的重要措施之一，材料利用率的高低由冲裁排样 所决定，目前，我国生产中多用人工排样，当排样规模变大或约束条件增多时， 排样工作繁杂且费时，同时很难找到材料利用率较高的排样方案。 ( 2 ) 布局算法的复杂程度增高。一方面，布局算法的研究是随着数学中优 化理论的发展而深入的，数学理论水平愈高、可接受的人群愈少，不利于算法 的推广和使用；另一方面，某些算法采用类穷举搜索的方法，尽管计算机计算 速度增加迅速，但由于布局问题的n p 完全性，这类算法的时间复杂程度高， 例如对于时间复杂性为2 ”的算法，如果计算机运算速度提高1 0 0 0 倍，在一个小 时内可解的最大的问题的规模仅增加1 0 倍，而对于托5 算法，这个规模增加不到 4 倍【3 。 ( 3 ) 基础启发式算法研究的降温。纵观近几年对布局问题的研究发现，专 家系统技术、人工神经网络方法及各种智能启发式算法如遗传算法、模拟退火 算法、禁忌搜索法等比较流行【6 ，对基础启发式算法的研究则有些降温。而布 局问题的求解只能依赖于各种启发式算法，加强对基础启发式算法的研究意义 重大。 由于上述几方面的考虑，本文提出了基于目标和空间正交分解的布局启发 式算法，即通过不断地分解空间、构造合适物体来实现布局目标，解决布局中 一2 一 第一章绪论 的非一刀切布局问题。该算法过程简单、复杂程度低、布局效果令人满意，便 于实际操作和推广使用。 1 2 国内外研究综述 自1 8 3 1 年g a u s s 研究格的有关布局问题开始，至今已有百余年的历史，在 文献上始见于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 e m 上) 。据s w e e n y 等 4 1 1 9 9 2 年的统计，从1 9 4 0 年到1 9 9 2 年， 全球关于布局方面的研究文献达4 0 0 余篇，涉及多种算法及1 4 0 多个应用领域， 其中关于非矩形形体的2 7 篇，关于三维非矩形形体的有3 篇。 布局问题是复杂的组合优化问题，同其它领域的研究与应用一样，布局问 题也存在理论研究与实际应用的差距。理论研究人员偏重于将布局问题抽象成 一定的数学模型，然后用各种优化方法进行问题的求解，并认为这些基于严谨 的数学推导的优化方法才是布局问题求解的正统方法；而实际工作人员则偏重 于各种布局启发式算法的研究，认为纯理论的布局求解方法不能解决实际问题。 这种状况直到七十年代末由于m s g a r e y 和d s j o h n s o n 的出色工作而在八十 年代初才有所好转，关于n p 完全性理论的研究表明，在有限合理的时间内， 不可能求得大规模n p 完全问题的精确解，问题的求解只能依赖于各种启发式 算法，同时人们惊异地发现实际应用中的许多问题都是n p 完全问题，而在组 合最优化领域中尤其突出。m s g a r e y 和d s j o h n s o n 的工作使组合最优化领 域的理论研究人员开始注重对各种启发式算法的研究，在其纯理论的搜索策略 中巧妙地加入各种启发式经验，使得基于优化理论的各种布局问题的求解方法 更加适合实际问题的求解；同时实际工作人员也开始重视各种优化方法的应用， 使得各种启发式的布局求解方法更加系统化【8 。经过几十年的研究，人们提出 了解决布局问题的各种方法，归纳起来可分成如下几类。 1 2 1 启发式算法 由于布局问题具有n p 难度，所以布局问题的解决大都采用启发式算法。 其构造方式一般遵循的模式为：从一个简单的但显然是合理的算法开始，分析 其性能，论证所服从的性能比，既要保证在最坏的情况下有什么样的界限，又 要找出反例说明这个界限不可能再改进了。在此分析的基础上，进一步洞察这 个原始算法的弊端，着手构造新的算法，并继续进行旨在提高其性能的分析， 第一章绪论 最终得到比较满意的算法。常用的启发式算法有： ( 1 ) 构造式算法 构造式算法通过逐步增加解中的构造元素而得到问题的可行解。由于构造 式算法的循环次数与解中构造元素的数目成正比而与解空间的大小无关，所以 其问题求解的速度是相当快的。 构造式算法主要由定序规则和定位规则组成。d o w n s l a n d 9 1 和g e h r i n g 等 在总结前人工作的基础上，归纳出许多有效的定序规则；b i s c h o f f 1 1 】，c o f f m a n 【1 2 1 ， h a e s s l e r t l 3 1 等均对布局过程中的定位规则进行了研究。 王金敏等 1 4 在研究现有布局求解方法的基础上，提出了基于约束、利用定 序定位法的布局求解算法，并改进了八叉树用于布局空间的描述和不干涉计算： 戴佐 1 5 】对现有布局启发式算法进行合理分析、分类和总结，找出了现有的构造 式布局启发规则产生的根源，进而建立了面向任意形状物体布局求解的一致性 评价函数。 ( 2 ) 改进式算法 改进式算法式从一个可行解开始，通过在其邻域内进行交换、合并、增加 和删除结构元素等操作来逐步改进解的质量，直到解的质量不能再提高时为止。 t a m v m c e n t 利用改进的g e n e t 模型来解决图形布局中的结点和边界重叠 问题，通过最小冲突启发式算法来修正变量，并利用启发式学习规则跳出局部 极小点。m e l l e rd 通过重新定义二进制变量，对m o n t r e t t i l 模型公式加以改进， 并用于解决设备布局问题。a l b a n o l l 6 开发了一个基于改进思想的人机交互布局 系统，系统首先产生一个初始布局方案，如果用户已对方案满意则布局结束并 输出该布局方案，否则用户给出修改信息用以指导系统更改、删除不合理的部 分或保留合理的部分，反复进行这个过程，直到用户对得到的布局结果满意时 为止。 国内对约束布局设计问题的研究较早的应推黄文奇等，黄文奇等h 7 1 提出的 拟物法主要是利用弹性势能公式来衡量两物体之间的挤压程度，即干涉程度， 对挤压程度最深的物体，重新布局调整，直到无不干涉，且聚集性最高。拟物 法还将人类的社会经验化为算法来求解某些数学问题。 滕弘飞等( 1 8 】提出了主布模式、模式叠换、敏度分析、拟卫星总装实验的综 合启发式算法，并采用模拟模装及实验仿真的实用化策略，用于卫星飞船舱的 布局优化设计。 第一章绪论 1 2 2 数学方法 布局问题被抽象简化为一定的数学模型后，用组合最优化中广泛使用的数 学规划法如线性规划法、整数规划法、动态规划法等求解。 ( 1 ) 线性规划法( 1 i n e a rp r o g r a m m i n g ) v a l e r i od ec a r v a l h 0 1 1 9 等将两阶段下料问题抽象为约束优化问题，并用简化 的线性规划模型来表达该约束的优化问题，最后用列生成技术对得到的线性规 划模型进行求解。 周俊健“4 1 提出了基于饱和布局的线性规划法，证观最优解的充分必要条件 是饱和布局，同时也证明了一种递推算法和f l o o d s 算法的正确。 ( 2 ) 整数规划法( i n t e g e rp r o g r a m m i n g ) b e a s l e y 2 0 1 将布局问题抽象为0 - 1 整数规划模型，用一个二值变量表示某类 型特定物体的可行位置，代表布局容器的长方形则可表示为可行位置左上角点 的坐标分割成的网格。只要每个网格位置仅被不多于一个的布局物体所占据， 得到的一组布局物体的位置便是可行的。 分枝定界法( b r a n c ha n db o u n dm e t h o d ) 是一种可用于求解纯整数或混合整数 规划问题的方法，在上世纪六十年代初由l a n dd o i g 和d a k i n 等人提出的【2 1 1 ， 由于这个方法灵活且便于用计算机求解，所以现在它已是解整数规划问题的重 要方法。分枝定界法由分至和定界两个操作步骤组成，分枝操作用于将规模较 大的原始问题逐步分解为规模较小且易于求解的子问题；定界操作主要用于评 价各分枝的优劣，以便删除质量不好的分支，重点分解那些质量较好的分枝， 从而减小搜索的范围，加速问题的解决。通常一个子问题的上界对应于该子问 题的一个可行解，因此分枝定界法的问题求解过程可用树的构造过程来表示。 c h r i s t o f i d e s 雎萄和w a n g 等将分枝定界法用于一刀切布局问题的求解； a r e n a l e s 1 等将分枝定界法用于非一刀切布局问题的求解。 ( 3 ) 动态规划法( d y n a m i cp r o g r a m m i n g ) 动态规划法是解决决策过程最优化问题的一种数学方法。1 9 51 年美国数学 家r b e l l m a n 根据一类多阶段决策闻题的特点，把多阶段决策问题变化为一系列 互相联系的单阶段问题，然后逐个加以解决；他提出了解决这类问题的“最优 化原理”，并研究了许多实际闷题，创建了动态规划法。j u i e aa n t o n i o 等1 2 习针对 工业切割问题提出了两种基于动态规划的方法，一种倾向于求解时间的缩短， 另一种倾向于求解质量的提高， 第一章绪论 数学规划方法因依赖于数学模型解析性而导致局部最优解的局限性为很多 研究者所重视，他们采用具有全局搜索能力的计算智能算法与局部搜索的数学 规划算法相结合，得到较好的结果。在纯数学推导中加入启发式经验，极大地 提高问题求解能力。 1 2 3 图论方法 图论作为组合数学的重要组成部分，在许多领域有着广泛的应用。该方法 一般将布局问题分两步来求解：首先求出相邻拓扑关系的无尺寸的平面布局， 即根据待布物体之间的确定位置关系构造一个图，图中节点代表各待布物体， 连接节点的边表示待布物体之间的确定位置关系；然后根据确定的布局图，利 用优化算法求出待布物体之间的具体尺寸。 m i t c h e l l ，r o t h 和d o w s l a n d 等先后研究了图论法的布局表示与生成，由于该 方法涉及图的平面化问题，难以将其扩充用于3 d 布局。 吴慧中等嗍提出了一个长方体布局问题的立体正交结构图模型，王英林等 在此基础上发展建立了约束图模型( 包括规范约束图和层次约束图) 。 冯恩民等嵋7 j 以人造卫星返回舱布局设计为例，应用图论、群论以及轨道与 等价关系等刻画各种布局方案的同构、等价类等内在性质，从而给出了带有性 能约束2 d 布局设计问题的一种全局优化算法。 1 2 4 模拟退火算法 模拟退火算法源于对固体退火过程的模拟，采用m e t r o p l i s 接受难则，并用 一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近 似最优解。k i r k p a t r i c k 等唧1 于1 9 8 2 年将模拟退火思想引入优化领域，由于模拟 退火算法可能求得布局问题的全局最优解，所以迅速发展为一种求解大规模组 合优化问题、特别是解n p 完全问题的有效的近似算法。 s z y k l n a n 2 9 等将模拟退火算法和空间约束条件结合起来，对3 d 组件的布局 进行求解。这些组件需满足组件之间的最近、最远距离约束及相互位置约束和 组件的旋转方向约束。空间约束条件包括组件之间的距离，坐标轴内整个空间 组件的平移和旋转，以及其它组件的位置和方向。 段国林蜘将模拟退火算法用于具有强约束的三维传动件的钟手表机芯布局 设计中。 第一章绪论 1 2 5 遗传算法 遗传算法是一种建立在自然选择和群体遗传机理基础上的自适应概率性搜 索算法，它根据“适者生存，优胜劣汰”等自然进化规则演化而来，从随机产 生的一组候选解开始，通过模拟自然选择和遗传过程中发生的交配和基因突变 等现象，在候选解中搜索最优解并充分利用原有优良解的已知信息加快收敛过 程。 李智等口伽采用遗传算法对到达港1 2 1 的矿物布局进行了优化仿真计算，并提 出了遗传算法换位交叉方法。唐飞口”等提出了以人造卫星舱布局为背景的十进 制编码控制参数自适应遗传算法，缓解了“组合爆炸”和遗传算法的早熟收敛 问题。 1 2 6 人工智能 人工智能是十九世纪五十年代中期为适应知识密集型工业决策自动化的需 要而产生的一门关于知识的自动化处理和使用的新兴工程学科。人工智能主要 有两大类，一是基于实例的推理：根据问题的特征，从实例库中检索出相似的 实例、然后以知识库中的领域知识和经验为指导，根据问题的实际情况对检索 到的实例加以调整、修补、综合，使之达到当前问题的求解需要。二是基于约 束的推理：设计人员通过约束描述了产品设计的要求，这种描述是一种形式化 的面向符号的方法，因而需要一种机制将这些形式化的描述转化为具体的具有 精确数值信息的产品几何外形信息，这个转换过程就是基于约束的推理和求解 过程。 在人工智能走向实用化的进程中，专家系统的发展走在最前列，不少学者 认为用专家系统与适合于某一领域的知识模型相结合是解决具体领域布局设计 的有效方法，并对布局知识获取、描述和创造性推理做了很多有益的研究。l i e w w 利用回馈解产生的信息与专家系统方法结合，从而产生更好的解，进行超大 规模集成电路( v l s i ) 设计。晏敏等口刁阐述了基于方图平面知识的表达、获取和 推理的方法与布局的智能生成原理，设计了平面布局专家系统的一种结构框架， 证明了有关方图尺寸计算的五个定理、构造了基于方图的尺寸推理机。 1 2 - 7 神经网络方法 基于人工神经网络与人脑的结构相似性及人工神经网络的并行算法、高速 第一章绪论 光计算及高容错性能等强大硬件支撑前景，人工神经网络在模式识别、智能控 制、传感技术及生物医学工程等领域得到了广泛的研究和应用，而作为其主要 应用之一的最优化领域，已成功地廨决了旅行商问题、图的划分问题等组合优 化问题。戴佐【15 】在组启发式布局问题规则集的基础上，将两维矩形布局问题 映射到h o p f i e l d t a n k 神经网络模型上，利用合适的能量方程确定各神经元之间 的权重，然后通过某些迭代策略来求得能量方程的近似最优解，从而得到布局 问题的求饵。 1 。3 本文研究内容 本文主要对正交布局中非一刀切问题进行研究，提出了基于目标和空阁正 交分解的布局启发式算法，内容如下： 第二章论述基于空间正交分解布局算法的基础，分析了空间正交分解的过 程，制定了待布物体相对布局空间的定序规则和布局物体的定位规则，提出了 第一和空间、第二和空间、第一差空闯、第二差空间、收敛空间的概念以及相 应的布局策略。 第三章介绍布局问题中的模式生成法，分析了布局问题的阶段性，针对传 统的布局物体顺序分配启发式算法存在的问题，提出了解决此类问题的群组策 略，并详细阐述了群组的方式、群组的约柬等，指出群组实质上是一种变化的 单模式生成法；最后将多模式生成法应用于空间正交分解的布局算法，以解决 大规模布局问题。最后通过大量实验验证基于空间正交分解的布局启发式算法 及其相应策略的有效性。 第四章是第二章和第三章的深入和扩展，介绍了多阶段布局过程及优化问 题中局部最优解和全局解的关系，分析了传统局部最优启发式算法的特点，提 出了基于目标的启发式算法，该算法将布局过程中的局部最优解设定一个下界， 以确保布局目标的实现，保证基于空间正交分解布局算法的稳定性。 第五章给出了全文的总结并指出今后的研究方向。 第二章布局空间的正交分解及其布局算法 第二章布局空间的正交分解及其布局算法 2 1 正交布局问题 布局问题属于组合几何学范畴，关于布局问题的研究论文散布于运筹学、人 工智能、计算机图形学、计算几何、组合最优化等领域。根据布局空间和待布 物体的形状，布局问题分为 3 3 】： ( 1 ) 二维规则布局问题 待布物体和布局空间都是矩形或圆形，如底盘装载问题( p a l l e tl o a d i n g p r o b l e m ) ，一刀切问题( g u i l l o t i n ec u t t i n gp r o b l e m ) 及非一刀切问题( n o n g u i l l o t i n e c u t t i n gp 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 s n 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 ) 三维规则布局问题 包括长方体、圆柱体及球体布局问题，常见的是待布物体和布局空间都是 长方体，如集装箱布局问题( c o n t a i n e rl o a d i n gp r o b l e m ) 。 ( 4 ) 三维不规则布局问题 待布物体和布局空间是三维不规则实体，如坦克舱布置设计，火箭仪器舱 内的仪器布局问题。 本文研究的二维正交布局问题( o r t h o g o n a lp a c k i n gp r o b l e m ) 属于矩形物体非 一刀切布局，根据d y c k h o f f 分类方法删，可归纳为2 b o m ，f l p _ 二维空间( 2 ) ， 布局空间有一个( o ) ，从大小不同的待布物体f m ) 中选择多个物体( b ) 进行布局。 正交布局问题的研究涉及布局对象、布局约束、布局模型等几个方面。 2 1 1 布局对象 布局对象包括布局空间和布局物体，形状都为矩形，约定长边为长度方向、 第二章布局空间的正交分解及其布局算法 短边为宽度方向。 2 1 1 1 布局空间 布局空间的形式有两种：第一种形式是布局空间的大小固定，矩形的长度 和宽度已知；第二种形式是布局空间一个方向的尺寸固定，称为布局空间的宽 度，另一个方向的尺寸大小相对宽度来说大得很多，可以看作不做任何限制， 要求布局时使高度尽可能地小。由于本文研究布局空间的数量为1 个、尺寸固 定的情况，因此在研究第二种形式的布局问题时，可根据布局物体的总面积预 先确定布局空间的高度，这样就将第二种形式的布局问题转化成了第一种形式。 布局空间的初始状态，即没有放置布局物体的空间，称为原始布局空间； 放人物体后剩余的空间称为剩余布局空间；将剩余布局空间分解成几个小的布 局空间，这些小的空间称为布局子空间；欲放人物体的布局子空间称为当前布 局空间。 2 1 1 2 布局物体 布局物体为若干种大小不同的物体， 同者，视为不同物体，以序列号来区分。 没有放人布局空间的物体为待布物体。 2 1 2 布局约束 一种物体的数量为一个；若有尺寸相 为区别于已放入布局空间的物体，称 布局问题就是要把一些布局物体按一定的要求合理地放置在一个布局空间 内。从布局问题的定义可以看出，它是由布局空间、布局物体及其相互之间的 关系和要求组成的，这些关系、要求都可认为是布局的约束口5 1 。当所有的约束 都被满足时，布局问题才算得到解决。与正交布局问题有关的约束主要有： 2 1 2 1目标约束 目标约束是对布局问题所追求的设计目标的限定。目标约束往往被综合( 或 表达) 为布局目标，如本文研究的基于目标的布局启发式算法，就是在布局开始 前设定希望达到的布局目标即布局物体在布局空间的覆盖率，运用各种策略逐 步实现目标。目标约束是布局问题中很重要的一种约束，是评价布局方案好坏 的依据，较常见的目标约束有：对于某些布局物体，要求包含它们的布局空间 的长度或宽度或面积最小；对于某些布局物体，要求包含它们的布局空间的数 目最少；对于某些布局空间，要求它们所包含的布局物体的总面积最大。 1 0 第二章布局空间的正交分解及其布局算法 2 1 2 2 模式约束 模式约束是对布局模式的限定，它包括布局物体之间的摆放顺序、摆放位 置、布局物体的数量及组合方式、布局容器的数量等关系的限定。模式约束既 可为硬约束又可为软约束，当模式约束发生变化时，布局问题也将产生相应的 变化。如当布局物体的数量已知而布局容器的个数未知，要求用尽可能少的容 器装下所有的布局物体时，问题为箱子布局问题( b i np a c k i n gp r o b l e m ) ；如果已 知布局容器的数量，布局物体的数量未知，要求每个布局容器装下尽可能多的 布局物体，则问题为背包问题( k n a p s a c kp r o b l e m ) 。布局物体之间的组合方式对 布局问题的解决也有很大的影响。如在底盘装载问题中，如果将布局物体以利 于装卸的方式( 即装卸物体的次数最少) 组合起来，则问题将成为以不同尺寸 的布局物体填满布局容器的布局问题。布局容器的数量有两种情况，一种情况 是只有一个布局容器，另外一种情况为有若干( 数目大于i ) 个布局容器。布局 求解的过程也就是不断调整布局物体使之满足模式约束的过程。一旦布局方案 确定下来，模式约束也就随之确定。 2 1 2 3 几何约束 对形状及尺寸的约束统称为几何约束。形状约束是对布局容器、布局物体 形状的限制；尺寸约束是对空间及物体具体大小的限定。几何约束是不易处理 的一种约束，它对布局问题的求解将产生较大的影响。对复杂形体来讲，它们 的形状约束很难表达，往往与尺寸约束密切相关，必须借助几何约束来表达。 2 1 2 4 位置约束 位置约束是对布局物体之间相对位置关系或布局物体相对布局空间的位置 关系的限定。正交布局问题要求已布局物体之间不存在干涉，已布物体的边界 平行或垂直布局空间的边界。 2 1 3 布局模型 正交布局问题的布局目标是尽可能多地放入布局物体，并使布局物体占据 的布局空间尽可能地大。布局问题的数学模型可描述为： m a x i l w l ；0 s t x j l i + x i 或x i l j + x j 或y j w i + y i 或y i w j + 而 1 1 第二章布局空间的正交分解及其布局算法 其中： 上式表示为布局目标；下式表示为约束条件，即布局物体间不发生干涉； l ，w 为布局空间的长度和宽度，令l w ； l i ，w i 为待布物体集r = ( 尺1 ，恐，r 。) 中第i 个待布物体的长度和宽度( 1 f ，1 ) ，令l i w f ；且待布物体在布局空间中可作9 0 0 的旋转； 当冠放人布局空间时，有口f - l ；否则，a l = o ； ( 而，y t ) 为待布物体忍在布局空间的坐标。 2 2 布局空间的分解 2 2 1 布局空间的分解问题研究 布局问题属于复杂的组合最优化问题，常用的解题方法不是对问题的解空 间而是对布局空间进行分解和构造 4 ”。大部分布局启发式算法都是顺序分配式 方法，而且现有的研究主要集中在对布局物体的搜索策略上，按定序规则确定 布局物体，逐一放入布局空问，并按定位规则确定布局物体的位置，直到布满 整个布局空间或没有布局物体可放人为止。这种方法重点考虑布局物体间的拚 合，仅将布局空间作为一个约束条件，只要布局物体不超出布局空间就行。然 而，每放人一个布局物体，布局空间的状态就发生了一定的变化，这些变化必 将对剩余布局物体的放入产生一定的影响，很少有人对布局过程中布局空间的 状态变化进行分析，因此对这方面进行深入的研究是必要的。 综合现有布局问题中的空间分解形式，本文将布局过程中的空间分解分成 三大类。 第一类是将原始布局空间分解。在布局开始之前，根据一定约束条件将布 局空间分解为多个布局子空间，然后对布局子空间求解，将待布物体往各子空 间进行布局。多模式生成法的布局空间分解即是如此。 第二类是将剩余布局空间分解。物体布局的顺序或位置未确定，通过虚拟 地比较剩余布局空间来完成物体的定序或定位。如文献 1 5 1 ，待布物体放入几个 可行的位置后，将剩余布局空间分解成埠阶凸形，通过比较n 阶凸形的面积及 连通度来确定布局物体的最佳位置。 第三类是将当前布局空间分解。物体放入布局空间后，生成新的布局空间， 将其作为当前布局空间，对当前布局空间进行满足约束要求的分解，如一刀切 第二章布局空间的正交分解及其布局算法 分解和正交( 非一刀切) 分解。 对当前布局空间分解的大部分算法主要集中在一刀切空间分解上，而且这 种方法被广泛运用到一刀切布局问题中，如板材、玻璃切割上：但对当前布局 空间进行非一刀切分解的研究甚少。 2 2 2 布局空间的一刀切分解 c h r i s t o f i d e s 和w h i f l o c k 2 2 1 提出了一种分解空间，利用树搜索来解决布局中 一刀切问题的算法。该算法将动态规划和运算规则融于树的搜索之中，通过施 加使布局模式最优化这一限制条件来缩小搜索树的大小，适用于中等规模的一 刀切问题优化布局方案的确定。 w a n g 2 3 1 通过不断地进行布局空间水平构造和垂直构造，矩形a i = p l * q l 和a 2 = p 2 4 口2 的水平构造是包含a l 和a 2 的矩形s - - m a x ( p l ，p 扩( q l + q 2 ) ，垂直构造 是包含a l 和a 2 的矩形s v = 0 l + p 2 ) * m a x ( q 1 ，q 2 ) ，每次构造尽量使切割损耗最小， 这样通过连续构造，得到布局问题的最优解。该方法的一个变化形式是通过连 续的布局空间水平和垂直构造，将布局物体定位于布局空间左上角，在左上角 构造逐渐增大的矩形，每次构造在布局空间的右面和下面形成一个j 形区域。 h o d g s o n ( 1 9 8 2 ) 和h o d g s o n 等( 1 9 8 3 ) 通过将j 形区域分成两个矩形区域，分 别对这两个矩形区域应用一维背包公式，进而利用局部最优的方法解决了这两 个矩形区域的优化布局问题。尽管这个算法仅限于一刀切问题，但它后来逐步 被扩展并应用到非单一产品的底盘装载问题上。 a a 2 a 1 ( a ) 垂直分解 aa 2 a 1 图2 - 1一刀切空闻分解 b ) 水平分解 一刀切布局空间分解常按深度优先的原则将布局空间逐步进行水平或垂直 分割，每次放入相对于当前布局空间来说满足定序规则的最优布局物体，并将 该布局物体定位于当前布局空间的左上角，依次完成不同大小矩形物体的布局。 - 1 3 第二章布局空间的正交分解及其布局算法 一刀切布局空间分解过程普遍采用二叉树数据结构来表示。用一个根结点 表示布局空间的矩形区域，按定序规则从待布物体中选择一个相对于该矩形区 域来说最优的布局物体a ，并将其定位在该矩形区域的左上角，这样原布局空 间就变成了一个j 形区域。将这个j 形区域按规则或约束条件进行如图2 1 ( a ) 所示的垂直分解或图2 - 1 c o ) 所示的水平分解，各自形成两个矩形区域舢和a 2 ， 分别用根结点的左、右两个子结点表示。这样，剩余布局空间就变成了两个独 立的布局子空间。按深度优先的原则分别对这两个布局子空间重复上述过程进 行 t 次分解，形成2 “个布局子空间，直至没有可选布局物体满足要求时停止分 解。 2 - 2 3 布局空间的正交分解 布局空间正交分解的方法是将剩余布局空间分解成两个相交的布局子空 间，以满足正交布局的要求。布局过程中使用一定的策略，始终保持布局子空 间数为2 。正交布局过程中布局空间有两种空间状态。 2 2 3 1 矩形空间分解 矩形布局空间出现在布局初始状态，另外在布局过程中也有可能出现剩余 布局子空间为一个矩形空间的情形。如图2 - 2 ( a ) 所示，布局空间为一个矩形，按 p 1 r 1 2 a ) 布局空间为矩形 p 2 p 1 】b ( b ) 布局空间为j 形 图2 - 2 布局空间的正交分解 定序规则从待布物体中找出最优物体p 1 ，调整物体的方向，使之满足定序要求， 定位于矩形左上角，此时剩余布局空间变为一个j 形区域，将这个j 形区域分 解成两个正交的矩形区域r ，和r 1 2 ，这两个矩形区域称为和空间。比较这两个 矩形区域的面积，将大面积的和空间称为第一和空间，小面积的和空间称为第 二和空间。 第二章布局空间的正交分解及其布局算法 2 2 3 2 正交空间分解 布局空间为两个正交的布局子空间，也就是第一种情况产生的剩余布局空 间。这时布局空间为子空问r 1 l 和r 1 2 的并集，比较r l l 和r 1 2 的面积，取大者 为当前布局空间，