（机械电子工程专业论文）板材下料优化排样系统研究与实现.pdf

板材下料优化排样系统研究与实现 摘要 排样问题在很多工业领域都有广泛的应用，解决好排样问题，可以提高材料 的利用率，节约生产成本，提高效益，从而使企业提高效率，增强竞争力。 本文主要包括两个部分。 第一部分：对优化排样问题进行了较为深入的研究。从数学计算复杂性理论 可知，排样优化问题属于非多项式确定完备问题，存在“组合爆炸”，找到最优 解非常困难。因此论文对当前常用的排样方式进行了详尽的分析，研究比较了各 种实用的排样算法，并在此基础上提出了一个改进的优化算法。 第二部分：在算法研究的基础上开发出了基于w i n d o w s 环境的优化排样系 统。d e l p h i 是一种强大的w i n d o w s 应用程序开发工具，本文使用d e l p h i 7 实现了 排样应用程序。程序中使用了数据库等相关知识，使编制的排样应用程序具有良 好的扩展能力，并使用a u t o c a d 的自动化接口实现了排样结果的输出。在利用 同益发展的计算机信息技术开发研制c a d 软件方面进行了有益的尝试和实践。 关键词：优化排样最优化方法启发式算法 r e s e a r c ha n dr e a l i z a t i o no ft h e o p t i m a ln e s t i n gs y s t e m a b s t r a c t t h en e s t i n gp r o b l e me x i s t si nm a n yf i e l d so fi n d u s t r i a l p r o d u c t i o n ，ag o o d s o l u t i o no ft h en e s t i n gp r o b l e mm a yi n c r e a s em a t e r i a lu m i t y i m p r o v eb e n e f i t a n d m a k e e n t e r p r i s ee f f e c t i v e l ya n dc o m p e t i t i v e l y t h ed i s s e r t a t i o nc a nb em a i n l yd i v i d e di n t ot w o p a r t s i nt h ef i r s tp a r t ac l o s e l y s t u d yi sd o n eo nt h en e s t i n gp r o b l e m f r o mm a t h e m a t i c s c a l c u l a t ec o m p l e x i t y t h e n e s t i n gp r o b l e mb e l o n g st on o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e dp r o b l e m i ti s h a r dt of i n dt h eo p t i m u m s o l u t i o n t h r o u g hi n v e s t i g a t i o na n da n a l y s i st oag r e a tr a n g e o fa r t i c l eo nt h en e s t i n gp r o b l e m ，t h ep a p e rp u tf o r w a r dt oa ni m p r o v e do p t i m u m a l g o r i t h m i n t h es e c o n d p a r t ，t h eo p t i m a ln e s t i n gs y s t e m b a s e do nw i n d o w e n v i r o n m e n ti sd e v e l o p e d t h r o u g hag r e a tr e s e a r c ho n t h eo p t i m u ma l g o r i t h m d e l p h i i sa p o w e r f u l w i n d o w sa p p l i c a t i o n d e v e l o p i n g t o o l ，u s i n gd e l p h i 7t h e n e s t i n g a l g o r i t h m i sr e a l i z e d a n dn e s t i n gd a t am a n a g e ，l a y o u tc a l c u l a t i o n ，l a y o u tr e s u l t e x p o r t i n g t oa u t o c a da p p l i c a t i o n a r ea l s or e a l i z e d b yd a t a b a s e ，s e l f - d e f i n i n g c o m - i n t e r f a c e a u t o c a da u t o m a t i o ni n t e r f a c er e s p e c t i v e l y k e y w o r d s ：n e s t i n g ，o p t i m a lm e t h o d ，h e u r i s t i ca l g o r i t h m 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学 硕士学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 主席： ) 、 、 絮乏 j “、 冬1 天散砖 甄籀俞令瓣衙刊弓乙 橱翩色7 世犬孳畚摇 璇糍慧裟+班l 参懈p 乙勿、l 捌k 独创性声明 本人声明所量交的学位论文是本人住导师指导卜进行的研究f ：作及取得的研究成果。据 我所知除了文中特别加咀标志和致谢的地力外，论文中不包含其他人已经发表成撰写过的 研究成果，也不包含为获得金8 曼：1 = 、业占堂或其他敦百机构的学位或证书而使用过的材 料。与我一同i 佧的同忠对率研究所做的任何贡献均已在论文中作了明确的说明井表示谢 意。 学饨论史作者签字 划：加q 月1 s 学位论文版权使用授权书 本学位论文作者完全了解垒幽：业厶：差有关保留、便州学位论文的规定，有权保留 并向国家有关部门或机构送变论文的复印件和磁盘，允许论文被奇阅或借阅。本人授权盒 9 酬业大学可以将学位论文的全部或部分论文内辑编入有关数据库进行检索，蚪采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适h | 本授权 5 ) 学何论文者签名 签字日 学何论文作者毕业后去向 l ：作单竹： 通讯地址： 妒 导师签名：多缈荨 o 。 签字日期：y 年7 月 = i l 电话 邮编 批 致谢 值此沧文完成之际谨向我的导师王卫荣教授表示最真诚的感谢和深深的 歉意。王老师对我研究生阶段的学习及论文撰写工作自始自终都倾注了大量的 心血，对我论文的选题，修改直至定稿一直给予精心的指导。不仅如此，导师 严谨求实的学风孜孜不倦的教导，平易近人的作风和无微不至的关怀都给我 留下了终身难忘的印象，使我受益匪浅。 工老师严于律己，宽以待人，还教给了我许多做人的道理。他诲人不倦， 严谨治学的作风，令人钦佩，是我今后学习和工作的榜样。 在这里还要十分感谢合肥工业大学机械与汽车学院的郭亚、唐玮、徐小军、 毕传兴、蒋克荣、李多扬、徐朝胜等同学，他们在我论文撰写过程c i 给了我很 大帮助，他们的建议和鼓励令我受益颇多。 感谢合肥工业大学机械与汽车学院和研究生部的老师们所付f “的辛勤工 作，特别感谢机设教研室的黄康老师，他对我的论文提出了大量的修改意见， 对我帮助很大。同时也对由于自己的原因而不能按时答辩，辜负了老师和同学 们的期望而表示深深的歉意。 作者：吴杰君 2 0 0 4 年6 月 1 1 优化排样简介 第一章绪论 所谓排样是指在给定的材料区域内找出被排零件的全局最优排布，使得耗 材最少，且零件不能重叠。排样技术的发展具有相当的长的历史，并广泛的应 用于许多行业和工业。如表1 1 表1 1 排样的麻_ i _ j 领域 麻刖分类举例 业用各种钣金件，厨房用具，家_ 【 j 电器瑚钣金件，打字机，电子 钣金什加r 元什埘钣金件，锁，链条链板，电动机州硅钢片，造船业钣金f j ：等。 各种布料，皮革排样。衬衫，萌服，鞋袜，降落伞等：布料皮革定 服装行业 级中的优化排样等。 纸业与玻璃业办公_ l f ；| 纸，财务川纸的裁制。 小材制品备种家具。 印刷业排版各种1 5 刊的排版。 集装货物将货物优化地装入有限空间的集装箱中。 绳棒的裁剪建筑业中钢筋的裁州，机械一1 ：业中棒料的合理裁用等。 微电子l ：业集成电路的排布等。 军事国防蚓形目标的搜索等优化问题等。 从上表可以看出，既有一维排样( 如圆棒剪裁) ，也有二维排样( 如钣会 件排样) ，三维排样( 如集装货物) ；有规则几何排样( 如玻璃裁制，圆硅钢 片排样下料) ，也有不规则几何形状排样( 如服装载料) 叱 排样问题可分为多种类型，主要与排样类别，被排零件，排样区域，优化 标准和附加约束等5 个方面密切相关。表1 2 使这五个基本方面的具体变化情 况。 排样问题大体分为两类：连续排样和非连续排样。按一定步距规律性重复 排列固定数目的一个或多个零件，称为连续排样。例如在批量生产中，链条内 外链板的连续冲裁。除连续排样之外的其它排样方式归为非连续排样。非连续 排样一般是一次性地将所有零件全部排放在原材料上，零件的排样规律不尽相 同。 从表1 2 可以看出，排样问题涉及众多变化因素，这些因素组合将形成多 种复杂情况，排样问题的特点也就随之发生变化。当原材料按给定的长宽尺寸 提供时，零件的排放就必须考虑两二维各个方向，位置的变化，排样问题就属 二维排样问题。 表1 2 排样问题的分类 分类依据具体变化情况 排样类别连续排样：非连续排样 形状规j j ! | j ( 圆、三角形、矩形、正多边形) ：不规 被排零什情况 则 种类单一品种；多品种 数量单仆( 多为矩形) ：不规则 形状规则( 多边形) ：不规j j l ! | 种类单一品种；多品种 排样区域情况 数茸单块、长度有限；单块、妖度不限；多块 材质均匀；非均匀 残料可利_ l = i一律弃川；一定形状、面积以上作重利心 性 优化标准 排样后续处考虑后续处理；不考虑j l i 彳续处理 理 不规则混合排列 e 列 位置关并排( 普 摆放形式 系通) ：对头 规则排聚合关单个；成对： 列系两个以上 有约束 附加约束 排列行单排；烈排： 数多排 排样间隙有间隙；无间隙 方向有方向限制：无方向限制 有纹理( 或图案、材质等) 要求； 位置 无要求 无约束 例如，当多品种零件任意放在一起排在多块矩形材料上，就称为多零件二 维混合排样。如果原材料宽度可选，长度不限，但宽度较窄，例如工业用可选 宽卷料，这种排样在决定了零件的排放角度后，只在一个方向上排列，转化为 一维半排样。又如在冲裁加工中，为了提高生产率和材料利用率，并使冲压力 对称，一般在卷料上进行单个零件的普通单排，普通双排，对头单排和对头双 排等。在皮革行业中原材料是兽皮时，其轮廓形状不规则，且一般都有孔洞， 裂纹等缺陷，这是排样就必须在轮廓形状不规则，带内孔，材质不均匀的排样 区域上进行，排样将很复杂。 在板材上进行钣会件排布，或在布料上排布服装片料是典型的二维排样问 题。因为这些零件可以抽象为几何图形，因此称为几何排样。又因为排样时可 忽略零件厚度而视作二维形状，所以称为二维排样问题。总之排样问题研究的 就是如何采取优化排样策略，一方面如何避免工艺性废料，另一方面通过运用 合理的排样方式来减少零件本身形状不规则性所带来的影响，使得材料的利用 率最高l “。 1 2 优化排样方法的发展及本课题研究的意义 金属板材是机械制造业的主要原材料之一，随着我国国民经济的快速发 展，企业对板材的消耗量同益增大。一个中等规模的企业每年要消耗的金属板 材多达数吨，因此提高金属板材的下料利用率，就具有特别重要的经济意义。 统计资料表明，在加工钣金零件的成本中材料支出占6 0 以上，在大批量生产 中，即使材料利用率仅提高1 ，其经济效益也相当可观，因而对排样技术的 研究具有重要意义。企业为了在激烈的市场竞争中生存、发展并立于不败之地， 一个十分重要的任务就是尽一切力量提高企业的经济效益，而提高效益的个 重要环节就是降低生产成本。 然而现实情况却不尽如人意，虽然板材的下料方式决定了材料的利用率， 但是许多制造企业实际生产中大量采用的还是人工排样和借助计算机的辅助 排样。人工排样时排样工人预先用一些材料如皮革、硬纸板等作出零件模型， 当需要在板料上加工某些零件时，把这些零件的模型尽可能紧密地放在板料 上，沿模型的轮廓把形状画出来，然后再进行切割。排样工人通过反复排放、 比较来寻求较好的排放方案，劳动强度很高。同时出于零件形状不规则，仅凭 排样工人的直观感觉和经验很难提高排样效率。计算机辅助排样即在图形处理 软件的支持下进行排样，与人工排样相比它降低了工人的劳动强度，提高了工 作效率但它需要工人在计算机上进行零件布局，还是需要人工来判断各种排样 形式的优劣。由上可以看出目前生产中的排样方法受人为因素影响大，材料利 用率，尤其表现在大批量下料中，而且缺乏确定的材料利用率统计，不利于生 产统计管理和排样布局优劣的比较等缺点。 目前市场对产品的需求趋于多样化、个性化，为了适应这种需求，企业必 须将其生产模式转变为多品种、小批量的柔性生产方式，相应的要排样的零件 的数量大大增加，零件形状更加多种多样，因此排样的工作量和难度都极大增 加，原来的排样方式越发不能适应企业的需求。 随着计算机的出现和发展，计算机技术越来越广泛地应用到生产、生活的 各个方面。计算机辅助设计( c a d 一一c o m p u t e ra i d e dd e s i g n ) 和计算机辅助 制造( c a m 一一c o m 口u t e ra i d e dm a n u f a c t u r i n g ) 在钣金加工中的进一步应用发 展。而优化排样系统是钣金加工c a d c a m 系统的一个重要的子系统，优化排 样算法的研究是当前钣会c a d c a m 技术研究的热点，完成该子系统的开发对 完成整个钣会加工c a d c a m 系统有重要意义。由于国内的c a d c a m 系统研 究和开发与国外相比还有很大差距，所以开发计算机自动排样系统，也有利于 推动我国计算机集成制造技术的发展。在这样的形势要求下，对排样方法进一 步研究并开发出使用方便的优化排样系统是一项非常有意义的工作。 从数学上讲，排样问题属于非多项式确定完备( n o n d e t e r m i n i s t i cp o l y n o m i a l c o m p l e t ep r o b l e m ，简记n p c ) 问题。这类问题是通过拟物方法，将优化布局 转化为弹性势能函数来描述，求解函数的极值，即获得最优布局。但是到现在 这类n p c 问题至今仍无法找到其解析算法。排料问题一般表述为：寻找平面 最优布局的优化问题，即将一系列二维不规则形状的零件，p l ，p 2 ，只合 理的排放在原料p 中，使原料的利用率最高，并要满足下列约束条件： ( 1 ) p i ，p j 互不重叠：i ，= 1 , 2 ， 且i ， ( 2 ) p i 必须放在p 内；f = 1 , 2 ，n ( 3 ) 满足一定的工艺要求。 因此排料问题可以归结为数学规划问题，也可以归结为以零件排放状态为 起点，以废料增加为权值的带权有向图中的最短路径问题。但是，出于约束条 件很难用可操作的数学公式表达，使得排料问题的求解不能套用现有的数学规 划求解算法。另外，图论中最短路径问题的己有算法，只对图的结构固定且清 晰，一个状态结点的后继结点个数有限的情况有效，然而这对于不规则形状零 件的排料是不适用的1 3 | 。 对于大规模的排料，即使采用计算机也必须开发出高效的算法彳能实现利 用率高的优化排样。因而二维几何排样问题一直是热点，许多研究工作者也都 对优化排样进行了较深入的研究，相继提出了一些近似算法并应用到优化问题 中去，如线性规划算法，动态规划算法，启发式布局算法，加密点算法，平行 线分割一步平移法，最小包络法，高度函数法，动画寻优法，多边形顶点算法， 遗传算法最优化数学模型及算法1 5 l ，模拟退火算法【6j 等。 在进行理论研究的同时，随着计算机技术、优化技术的飞速发展，已经出 现了一些计算机排样的商用软件包。国外的有英国r a d a n 公司的n e s t i n g ，美 国的u n i g r a p h i c ss o l u t i o n 公司的u g s h e e tm e t a ln e s t i n g 等。零件排样是钣金 c a d c a m 系统的重要子系统，如英国j e t c a m 公司推出的智能钣金 c a d c a m 软件包括零件排样自动优化模块。国内也有很多家高校、科研机构 和软件公司在进行排样软件丌发，清华大学、上海交通大学、华中理工大学等 学校一直从事排样算法的研究及软件系统的开发，如华中理工大学的集成钣金 优化排料系统a u t o c u t 系统m 】；武汉三屹高兴有限公司的通用排样系统等。 1 3 课题的主要内容 本课题是板材下料优化排样系统研究和开发。正如上节所述，这些年来 许多研究工作者在优化排样上进行了较为深入的研究，特别是计算机技术的发 展为优化排样开辟的新的途径。有的提出了数学模型和理论方法，进行理论上 的探讨：有的算法虽然好，但开发成应用系统难度高，有的虽然开发成系统， 但存在计算时间和空间呈指数增长等缺陷；有的虽然丌发成系统但在排样过程 中还需要人工干预。总的来说国内外的已有一些关于不规则形状排料的算法和 软件多半提供交互排料和自动排料两种功能，但是从排料效果上来看，自动排 料并未形成相对人工排料的明显优势，这说明对不规则形状自动排料算法进一 步深入研究是必要的。 本课题就是在前人的基础上参考了大量资料进行进一步的深入研究并通 过对实际的排样过程的分析，提出一种新的优化排样算法：基于过程的动念综 合矩形法；并开发出了效率高，资源占用小的优仡排样系统。 课题主要研究了以下内容为： ( 1 ) 对优化排样进行了深入的研究分析。对零件的排样问题进行了研究， 详细地分析了各种排样方式的二维板材排样的优化问题，建立了排样优化的数 学模型。 ( 2 ) 针对优化排样提出了一种新的解决方法。对各种相关的排样算法进 行了详细的综合分析，提出了以矩形包络和状态搜索两步法，利用启发式策略 解决排样问题。并进行了详细的算法分析。 ( 3 ) 应用面向对象的编程语言根据算法丌发出了相应的优化排样系统。 建立了排样系统的功能结构模型，以面向对象的开发技术，利用a c t i v e x a u t o m a t i o n 工具包，在d e l p h i 7 的丌发环境下，对算法进行了实现并得到了排 样结果。 系统的预计目标为： ( 1 ) 兼容性好，运行于w i n d o w s 等常用操作系统环境下： ( 2 ) 用户界面友好，使用简便，使用户在短时间内掌握系统的操作； ( 3 ) 算法效率应比较高，以满足多品种，单件小批数量的零件混合排样 要求： ( 4 ) 优化效率高，材料利用率符合要求； ( 5 ) 排样结果用标准数据交换格式文件输出； ( 6 ) 输出材料利用率和排样效果图。 第二章优化排样模型及方法原理分析 2 1 优化排样的模型和性质 2 1 1 模型简化和优化目标 实际生产中，要求的各种零件规格不一样，而板材的规格也都不一样。另 外加工方式和设备的要求也都影响着排样，这就要求在进行排样研究鲋要对实 际的情况进行抽象简化，作一些假设和规定： ( 1 ) 不考虑板材的厚度影响，假定零件厚度和板材一样，研究在板材个数不 限的情况下，排样所需零件的优化排样。 ( 2 ) 不考虑板材在下料中的应力影响及零件的扎制纤维方向的因素。 ( 3 ) 假定零件外形光顺，把零件外形的一些很小的凹槽除去，使零件外形尽 量简化。 ( 4 ) 对生产实际中必须考虑的一些因素( 如切割的割距和冲压中的搭边值 等) 统一通过一种权值对零件外形预处理来解决，排样直接考虑经过预 处理的零件。 优化排样的是以提高材料的利用率作为目标函数，使材料利用率最大。材 料利用率是零件的实际面积只与原材料面积f 的百分比 9 1 。即 叩= ( 2 1 ) 由于排样区域可以是板材，也可以是条料，也可以是无限上卷料。而且根据排 样方式的不同，材料利用率的公式( 即目标优化函数) 可以进步的转化。 2 1 2 二维零件排样的数学模型 把矩形原材料长度方向定义为坐标轴横轴，以矩形的左下角顶点，建立直 角坐标系。只为零件i 的图形，其初始位置在q 1 ，如图2 1 所示。当一个零件 在原材料上的初始位罱已知，那它在原材料上的最终位置定位实际只要三个参 数它们是该零件的摆放角度。和ax ，ay 。当这三个参数都确定后，该零件 的所有顶点都可由这三个参数计算出来。设p ( f i ，i 为零件集合) 为零件i 的图形，则该零件在板材上的最终定位可以表述为这样一个过程：先将该零件 绕坐标原点逆时针旋转0 ，至位置q 2 ，然后再左平移( a x ，a y ，) ，到最终位置 6 q 3 。这时零件i 在原材料上的位置可表示为g ( o 积，则通常的优化排样问题的数学模型可表示为 k m a x 似a i = l f p , ( a xr ，每t ) c l p j ( a x ，y - ) = 。 j ， 0 石。( 只，t ，4 y 。) 三 1 0 y 。( b ，缸，h ) w 缸，每，) 。设a 。为零件i 的面 f ， m = 1 2 ，厅 m = 1 , 2 ，n ( 2 2 ) 其中目标函数表示的优化目标是使零件在原材料上所占的面积最大。公式 中变量f 。取值为0 或1 ；第一个约束“( a x ，缈，) np ，( a x ，缈，) = 中f ，”表示 零件i 与j 互不重叠；x 。和y 。为零件i 上第m 个顶点的坐标；l 为原材料的长， w 为原材料的宽；第二和第三条约束是表示所有的零件不能排在原材料之外。 由于面积a 是一个与位置无关的参数，因此上面的优化排样模型中，其决策变 量为臼。，缸。缈。和f ，( i ，) 。 图2 1 二维零件排样的模型示意图 2 1 3 二维排样问题的性质 上述零件优化排样的数学模型是一个数学规划问题，也可以归结为以零件 排样状态为结点的，以废料增加为权值的带权有向图中的最短路径问题。上述 数学模型虽然已经准确地描述了二维不规则几何零件的优化排样问题，但这近 乎语言化的描述不能提供以数学方法解决零件优化排样问题的任何线索。由于 约束条件很难用可操作的数学公式来表示，所以排料问题的求解不能套用现有 的数学规划求解算法。0 。，a x ，妙。这三个决策变量都是实数，试想如果直接将所 有零件的这三个参数都离散化后直接再加上变量r ，进行排列组合，则会发生“组 合爆炸”。所以若单纯用数学方法，目前大多数数学方法都对它不怎么有效。 二维不规则零件排样问题是典型的n p 完备问题，目前比较认同的解决方 法是启发式搜索。另外，解决该问题时必须要花费大量的时间去作约束条件可 行性的判断，这种判断构成了零件优化排样的难点。因此，如何在保证排样可 行性的条件下，提出合理的优化排样方法和算法是二维不规则排样问题的研究 重点所在【2 i 。 2 2 最优化方法和启发式技术 2 2 1 最优化方法 简单地说，最优化问题就是如何在一切的可能方案中寻求最优的方案。最 优化问题的一般定义如下： 一个最优化问题的一个实例是对一对元素( f ，c ) ，其中f 是一个几何或 可行点的定义域，c 是费用函数，最优化问题就是求一个f f ，使得对一切y f ，有c ( f ) c ( y ) 。这样一个点f 称为给定实例的整体最优解。 也有定义为： 这类要求最优化方案的问题，用数学模型描述，可以归纳为：求n 元函数 ，伍) 忸= “，b ，吒ye d c r “) 在条件组 g ，( z ) 0( j = 1 , 2 。，埘) 下的极小值( 或极大值) 问题。其中，) 称 为目标函数( 或评价函数) 。x = b ，也，_ 。) 7 称为设计变量。 g ，) 0u = 1 , 2 ，卅) 称为约束条件。r ”为n 为欧氏空间，t 表示为转置符号。 从数学上讲，选择最优方案的问题，就是要在设计变量允许的范围d 内， 找出一组参数值( 一点) x = k ，x 。：y 使m i n 慨m a x ) f 似) = ，伍+ ) 成立， 即x 为厂) 在d 上的极小( 大) 点。我们称x 为最优设计方案。解决求厂) 的极小( 大) 点x ( 近似值) 的方法，就是所谓的“最优化计算方法”。 排样问题的解决就是得到较好的排样结果，排样问题属于最优化问题。前 面所建立的数学模型表明二维不规则零件排样是n p 一完备问题。n p 一完备( y p 即n o n d e t e r m i n i s t i cp o o l y n o m i n a l ) 是指尚未找到有效算法的问题。虽然不 能证明n p 一完备不能在多项式时间内得到解决，但大家都认为这已是一个事实。 n p 一完备问题具有以下两个性质： ( 1 ) 任何n p 完备问题都不能用任何已知的多项式算法解决； ( 2 ) 若任何一个n p 一完备问题找到了一个多项式算法，则一切n p 一完备问题 都有多项式算法。 难计算是n p 一完备问题的固有性质，它们不可能用有效的算法求解。任何 可以正确地求解n p 一完备问题的算法，在最好情况下也需要指数量级的时间， 从而除规模很小的实例外，是不实用的。 解决n p 一完备的主要方法有近似算法( 给出的不是最优解，而是保证偏离 真正最优解在一定范围内的解) ，概率算法( 假定某个问题的各实例有某种概 率分布，并根据概率分布设计出实用的有效算法) ，针对特例的算法，指数算 法( 指一些算法复杂性是指数量级，但实际应用的算法，如拟多项式算法，分 支定界法等) ，局部寻优法和启发式方法( 算法并不能保证得到最优结果，但 通常所得结果与最优解相差无几) 等。由于局部寻优法和启发式方法是能比较 有效地求解n p 一完备问题的常用方法。本文即通过这两种方法的改进来解决排 样优化问题。 2 2 2 启发式技术 1 启发式算法 启发式算法( h e u r is t i ca l g o r i t h m ) 是相对于最优算法提出的。启发式算 法可以这样定义： 一个基于直观或经验构造的算法，在可接受的花费( 指计算时间，占用空 间等) 下给出待解决组合优化问题每个实例的一个可行解，该可行解与最优解 的偏离程度不一定事先可以预计i ”1 。 另一种定义为：启发式算法是一种技术。这种技术使得在可接受的计算费 用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数 情况下，无法阐述所得解同最优解的近似程度。 在某些情况下，特别是实际问题中，最优算法的计算时间是人无法忍受或 因问题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过 启发式算法求得问题的一个可行解。启发式方法是对启发式算法的综合应用。 上述启发式算法的砥个定义中，一个共同的特点是不考虑算法所得解与最 优解的偏离程度。如果采用分析最坏情况的误差界限的概念柬评价启发式算法， 则可以将近似算法定义为： 设a 是一个问题，记问题a 的任何一个实例i 的最优结合启发式算法h 解 的目标值分别为z 。，( ，) 和z 。( ，) 。于是对于某个s 0 ，称h 是a 的s 近似算法 ( s a p p r o x i m a t i o na l g o r i t h m ) 当且仅当 p ( ，) 一z o p 7 ( ，) i 占l z d p 7 ( ，) l ，v ie a ( 2 3 ) 这样的定义给出启发式算法和近似算法两个概念的联系和区别。启发式算 法概念定义的算法集合包含了近似算法概念定义的算法集合。近似算法强调给 出算法最坏情况下的误差界限，而启发式算法不需要考虑偏差程度。出于很多 组合优化问题算法的最坏情况误差界限估计需要很强的数学基础和较强的技 巧，甚至一些问题很难或无法给出最坏情况误差界，而实际问题又迫切嚣要求 解的方法，因此，只能通过启发式算法解决问题。 出于实际问题的需要，人们已提出些解决实际问题的快捷有效的启发式 算法。启发式算法能迅速发展是因为它有以下长处： ( 1 ) 数学模型本身是实际问题的简化，或多或少地忽略一些因素；数据 采集具有不精确性：参数估计具有不准确性；以上因素可能使最优算法所得解 比启发式算法所得解产生更大误差。 ( 2 ) 有些难的组合优化问题可能还没有找到最优算法，即使存在，由算 法复杂性理论，得知它们的计算时间是无法接受或不实际的。 ( 3 ) 一些启发式算法可以用在最优算法中，如在分支定界算法中，可以 用启发式算法估界。 ( 4 ) 简单易行；比较直观；以备使用者接受。 ( 5 ) 速度快，在实时管理中非常重要； ( 6 ) 多数情况下，程序简单，因此易于修改。 虽说有诸多好处，但启发式算法也有其短处，这些不足往往称为争论的焦 点。 ( 1 ) 不能保证求得最优解； ( 2 ) 表现不稳定：启发式算法在同问题的不同实例计算中会有不同的效 果，有些解很好，而有些则很差，在实际应用中，这种不稳定性造成结果不可 信。 ( 3 ) 算法的好坏依赖于实际问题，经验和设计者的技术，这一点很难总结 规律，同时使不同算法之间难以比较。 启发式算法可简单地分为以下几类： ( 1 ) 一步算法该算法的特点是：不在两个可行解之间选择，在未终止的 迭代中，有可能不是一个可行解，算法结束时得到一个可行解。 ( 2 ) 改进算法改进算法的迭代过程是从一个可行解到另一个可行解，通 常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直到满 足一定的要求为止。因此也称为迭代算法。 ( 3 ) 数学规划算法数学规划算法主要指用线性规划的方法求解组合优化 问题，其中包括一些启发式规则。此类方法中，典型的是线性规划及对偶理论 在网络流中的应用，产生标号算法等一系列最优算法93 1 4 j ；其次是基于整数规 划分支定界的启发式算法，只搜索一些特殊分支，或是基于整数规划的割平面 法，产生的考虑部分割平面的算法。 ( 4 ) 解空间松弛算法一类方法是线性规划松弛；另一类是拉各朗闩 ( l a g r a n g e ) 松弛法。 ( 5 ) 现代优化算法现代优化算法是8 0 年代初兴起的启发式算法。这些 算法包括禁忌搜索( t a b us e a r c h ) ，模拟退火( s i m u l a t e da n n e a l i n g ) ，遗 传算法( g e n e t i ca l g o r i t h m s ) ，人工神经网络( n e u r a ln e t w o r k s ) ，它们主 要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面都得 到了较大的发展，无论这些算法是怎样产生，它们有一个共同的目标一求 n p h a r d 组合优化问题的全局最优解。虽说有这样的目标，但n p h a r d 理论限 制它们只能以启发式算法去求解实际问题。 ( 6 ) 其它方法启发式方法包含的类型很多，有些方法是根据实际问题而 产生，如解空间分解、解空间的限制等。另一类算法是集成算法，这些算法是 诸多启发式算法的合成。 2 启发式搜索 人工排样从进行排样的方法策略上来说，与计算机自动排样相比，有无可 比拟的优越性。要把人工排样时的排样策略应用于计算机自动排样，通常就要 应用人工智能方法。人工智能是计算机科学中涉及研究，设计和应用智能计算 机的一个分支。在人工智能所采用的基本方法中，问题求解及搜索是人工智能 研究的一大课题。问题求解状态空间搜索是排样问题研究中常使用的人工智能 方法，状态空间搜索算法比较有效的是启发式搜索。 ( 1 ) 状念空间搜索 所谓“问题求解”就是在广义途中寻找一条从初始状态出发，到达目的状 态的解树。图是数据结构的一种，是由结点( 数据元素) 及连接结点的弧的集 合，而树是两个结点之间有且仅有一条路径的图。问题状态是指问题求解时对 每一个步骤中问题状况的描述，用一种数据结构来表示。所谓状态空间包含一 个状态集和一个将己状态转为另一状态的算子集。人工智能中常以图为基础来 表示状态空间，从扔始状念出发所有可达到状念的集合可视为一有向图，其中 结点对应状态，边对应于算子。问题求解技术包括状态空间的表示和搜索两方 面的内容。状态空间搜索就是要在问题状态空间中找到条问题求解途径。 状态空问搜索基本方法分为两类：广度优先搜索和深度优先搜索，在广度 优先搜索中，树上结点( 问题状态) 的扩展是沿着结点深度的“断层”进行的， 即结点的扩展是按它们接近起始结点的程度依次进行的。而深度优先搜索则优 先扩展与前一扩展结点连接的予结点，在找不到某结点的子结点时才扩展到它 的兄弟结点。 起始节点 一一p 自一r _ ：磊孓、霸 一一一! ? j 一歹j 一 fn 卜t p 一fr c 6 】 卜j1 fh )1 ， i 1 l 【j 。广度优先搜索示意图 f 、， 译j j f 7 t l ； 驴霉 图2 2 状态空间搜索不意图 ( 2 ) 启发式搜索 广度优先搜索和深度优先搜索都属于无信息( 盲目) 搜索，这种搜索方法 在寻找一条通向目标结点的路径时耗费巨大。虽然它们在原则上提供了一个路 径寻栈的解答，但是在应用上则往往是行不通的。 有关具体问题领域的信息常常可以用来简化搜索。一般情况下，一个具体 问题的初始状态，目标状态和一个问题状态转化到另一个问题状态的方式是确 定的，他们决定了一个搜索空间。这个问题的求解就是如何有效地搜索这个空 间。进行这种搜索的技术一般需要某些有关该具体问题领域的特性信息，这些 信息就被称为启发信息。利用启发信息进行搜索的方法就叫做启发式搜索。 启发式搜索策略一般在以下两个基本下运用： 一个问题由于在问题陈述和数据获取方面固有的模糊性而可能使它没 有一个确定的解。 一个问题可能有确定解，但是求解过程由于计算代价太大而不能实施。 排样问题就属于第二种情况。对一个问题空间进行搜索时，提高搜索效率 需要有与被解问题的解有关的大量控制性知识作为搜索的辅助性策略。有两种 极端的情况：一种是没有任何控制性知识作为依据，因而搜索的每一步选择完 全是随机的；另一种是有充分控制性知识( 启发信息) 作为依据，因而搜索的 每一步选择都是正确的，这种搜索较最佳搜索。 较常用的启发时搜索算法是局部择优搜索法( 瞎子爬山法) 和有序状态空 间搜索( 也称最佳优先搜索) 法。局部择优搜索法在搜索过程中扩展当前结点， 最优的子结点被选择并进一步扩展：该子结点的兄弟结点和父结点都不再保 留。当搜索到某个结点时所处状态优于它的所有子结点状态时，搜索停止。 ( 3 ) 排样的启发信息 基于排样的启发式搜索的启发信息确定的依掘是模仿人工排样的过程。通 过对人工排样过程的分析对比和总结。我们可以确定以下信息： 对形状特征对的可吻合性和吻合程度进行判断，比较，实现凹凸互补和 对排样零件的挑选； 对零件面积和复杂程度进行估计后排序，排样运算时先找大的零件，与 人工排样处理方法一致； 利用对排放方向的限制，实现优先从原材料的一侧丌始摆放： 确定“排样质量好”的衡量标准，在试摆后进行判断，符合要求则确认 为最终摆放，否则变换摆放位置或选择其它零件重新摆放。 2 3 优化排样的方法和原理分析 2 3 1 矩形件排样数学模型和寻优过程原理分析 矩形件排样是指在矩形的板材上，要排放多种不同类型的矩形零件，每种 矩形零件所需多个。如何在这些矩形零件既不相互重叠，也不超出板材范围的 条件下，尽可能多地在板材上排下这些矩形零件，以使材料被最大限度的利用， 达到降低成本减少浪费的目的。 设排样所用的板材的长为l ，宽为b ( l b ) ，板材的数量足以排下所有 要排的矩形件。所有要排的矩形件共有t 种，第i 种矩形的个数为t l i ，长度为 1 。宽度为b i ( 1 i t ) 。则全部要排的矩形件总数为： 7 n = ”， ( 2 4 ) 基本目标是：使排样所用的板材数尽可能的少，尽可能的提高材料的利用 率。排样规则为：每一个矩形零件可按板材的长或宽进行j 下排( 正排即矩形零 件的长或宽总是与板材的长或宽平行) ，从板材的最左下角开始排至板材的右 上角结束。排样的基本约束条件为：矩形件之间不能有相互重叠的区域，并且 矩形件不能有排出板材之外的部分”j 【1 9 】。 排样坐标系的选取：以板材的左下角点为排样坐标系原点( o ，o ) ，且为 排样起点，排样过程中不得有任何排样点落在此点左侧；板材的右上角点( l ， b ) ，且排样过程中不得有任何排样点落在此点右侧。我们知道一块矩形件在 板材的位置可以由该矩形件的左下角点( 一，y 。) 和右上角点( x 。y ，：) 确定。在一 般矩形件的正排问题中，通常有四种排样方式如图2 3 所示： 旦缸 ( a ) ( b ) ( c ) ( d ) 图2 3 排样方式示意图 ( a ) 图和( c ) 图可归结为横排方式；( b ) 图和( d ) 图可归结为竖排方式。所以矩形 件排样问题实际上就只有横排和竖排两种方式，因此矩形件在排样坐标系上的 关系为： 髓y j 2 = - y , 或髓x j 2 ：x s l 亿s ， 其中i = l 2 n 前一种为横排，后一种为竖排，见图2 3 。由此可见，对 于决定每一块矩形件的排放，实际上只有三个自由量：x y ，：和决定矩形件i 横排还是竖排的逻辑变量( ，f = o 表示横排，= l 示竖排) 。 则x 。y 。) 与0 。y ：) 的关系可由式( 2 5 ) 表示为： x ，2 = x n + ( 1 一 ，j + ，6 j ( 2 6 ) l y ，2 = y ，1 + ( 1 一) b ，+ r , l ， 。 设胄，和r ，为排样坐标系上任意两个矩形件，它们的长和宽分别为，。和 以，b ，：它们对应的左下角和右上角的坐标分别为融，y 。) ，g ，y ，：) 和 融。y 。l g 。y ，：) 。所以当下面情况之一出现时，它们互不重叠： ( 1 ) x 。) x ，时矩形s 在t 的右边 ( 2 ) y ，1 ) 儿2 时矩形s 在t 的下方 ( 3 ) y ，) y ，2 时矩形s 在t 的上方 ( 4 ) f x 。2 时矩形s 在t 的左边 对应这四种情况由式( 2 6 ) 得： x ，1 + ( 1 一，、) ，+ 6 。( x ，1 麓i ) x t l ，二暑二意嚣 眨， y 一( 1 一) 6 ，一r , l ，) _ y “ 4 要使得任意一个矩形件r 。与r ，均不排出板材范围之外，则它的坐标应同时 满足下式： o 翌三上。量；三 (28)0 y l2 sb 0 y r l b 、。“7 由式( 2 5 ) 得： o 翟 b 的矩形件，显然对于这类矩形 件必须横排即f = o ，如图2 4 所示： 图2 4 横捧的两种方式 而在所有f ， b 中选最长的f 。，横排k ，行，这里k 。应满足： m i n 三一k i t z 。，占一k n b 。 ( 2 1 3 ) l 一七；1 7 ，0 或b k i 2 b ；2 0 ，且1s k 。l ，t 2 蔓n ， 否则排到后面可能会发生不可排的情况。 对于所有，