（机械设计及理论专业论文）基于proengineer平台的钣金展开件的自动排样系统的开发.pdf

硕士学位论文 摘要 饭金件是机械产品中的一大类，传统的钣金件设计，从展开计算到下料，排样，都 是通过手工完成，虽然能取得较好的结果，但需要较长的周期，劳动强度大。随着c a d 技术的日益成熟本课题成功地借助于c a d 技术，运用软件工程的方法，针对生产实 际中的常见钣金构件，开发出完整的钣金模块。 本文主要讲述了基于p m ，e 】呵g 矾e e r 的钣金展开件自动优化排样的开发过程和开 发方法。 在本文中，先是介绍了钣金排样技术的发展现状，深入讨论了钣金排样技术的相关 理论基础，也详细讨论了目前前沿的人工智能领域中的遗传算法和模拟退火算法等智能 启发式排样算法。 接下来，本文又讲述了p r 矾n g 瑚e e r 的二次开发工具p r o ，i i o o l 日t 的开发形式， 并运用该工具和面向对象的强大开发工具v c + + 6 0 在p r 训团n g 她r 的环境下对 p r 0 】三n g 矾髓r 的钣金排样模块进行二次开发，完成了钣金排样模块程序的编码、调试 工作，并成功运行，工程实践能力得到了提高。 最后将在p r o ，】狲g i n e e r 排样模块基础上改进的排样模块的排样和p m 佃、g 胍e r 原排样模块的排样进行了对比，取得了很好的效果。 关键词：p r o e ，钣金展开，优化排样 基于p 蒯g r n e e r 平台的锰金展开件的自动捧样系统的开发 a b s 缸a c t s h e e tm e t a lw 勰ag 他砒p a r to f m c c b a n i c a lp r o d u c t s a ut h ew o r ki n c l u d i n gc a l c l l l 砸o n ， b 蛐g 蛆dn 船t i gh a db e c nd o n et h r o u g hm a 曲a lla _ b o ri nt h e 订a d 试伽i a ls h e e t m e t a ld 髓i g n a l t h o u g hs 如f i e dr 韶1 1 1 t sc o l l l db ca c l i i e v e d ，i ti 嘴dl o n gw o r l ( i n gc y c l i ca n d 吐蛤h i 出l a ：b o r i n t e n s i t y c o n m u t e dt on l ed e v e l o p m e n to fm ec a dt e c h n o l o g y c o m p l e t es h e e t - 珈e t a l m o d u l a rt o w a r d st h ec o n 蚰o ns h e c t m 咖1c o n s 缸u c t i o ni np r t i c e 、v a ss u c c e s s f h l l yd e v e l o p e d i nt h i ss t u d yu s i n gt h es o 姗a r ee r 培m c 血gw i 也c a d t e c l l n o l o 盯 1 h ep r o c e s sa n dm e t l l o d0 fm ed e v e l o p m e n to fa u t o - o p 6 m 础i o ni ns h e e t - m e t a l l l i l f o l d i n g c s t i 吨b a s e do nt l l ep r o ，e n g d 旺e rt e c h n o l o g yw c r ca 1 1 a l y z e di nt h i sp a p e r f i r s t l y ，t l l ec u r r e n td e v e l o p m e n ts i t u a t i o no ft l l es h e e t m e t a ln e s t h l gt e c l l n o l o g y 啷 i m m d u c c d 洫t h _ i sp a p e r t h ec o h c r e i l t l c o r e c i c a lb a s i sw 觞d i s c u s s e d 如m l e lm e a n w l l i l e ， i m e l l i g e n ta n dh e u r i s t i ca l g o t 1 1 田so fn e s t i g ，s u c ha sg e n e t i c 刖g o r i 也ma n ds i m u l a t e d a n n e a l i n g ，i n 廿l ea d v a n c c da r e ao f a m f i c i a li n t c i l i g e n c ew e r ca l s od i s c u s s e d 1 ，1 ep a t t e mo f 吐圮d e v e l o 珥n e mo fp m 厂r o o l t 血eq i l a d r a l i cd e v e l o p e dt 0 0 lo f p r o 厄n g i n e e r 、v 船趾a l y z e d p r o 厂r 0 0 l l r r 趾d 也ep o 、v e r 如ld e v e l o p h 唱t o o lo f t i 圯o b j e c t o r i c n t c d ( v c + + 6 o ) w c r cl l s e dt od o 也eq 础a t i cd e v c l o p m c n to f 也es h e “m e d a ln e s t i n g m o d l l l a rl l n d e rt l l ec i r c 衄s t a n c eo fp r o e n g i n e e r 1 kc o d m ga n dd e b u g g i n go fm e p r o g r 鼬o f 血cs h c e t - m e d a ln e s 血gm o 叫a rw e r e 觚s h e da n d 眦c e s s 舢yo p e r a t e d t h e a b i l i t yo f e n g i n e e 血gp r a c t i c eh a sb e e ni m p r o v e d f i n a l l 班璺! i s f i e dr e s u h w a sa c l l i e v e dt l l r o u 曲c o m p 西n g 血en e s t i n gl l s i n gn l ei l p m v e d m o d l l l a rb a s 。do n 虹坨 p r o 门巳n g i n e e rt o 吐1 e n e s t i i l gu s h gm em o d u l a ro f m e p 肥n g i n e e r k e yw o r d s ：p m e ，s h e e t - m e t a lu i 墒1 d i n g ，o p t i m i z a t i o n 雎m g i i 插图索引 图2 1 状态空间搜索示意图1 2 图2 2 排样方式一1 4 图2 3 遗传算法流程图2 0 图2 4 模拟退火算法2 4 图3 1 “新建”对话3 2 图3 2m f c 向导对话框3 2 图3 _ 3 添加包含头文件对话框3 3 图3 4 添加库文件对话框3 3 图3 5 工程设置对话框3 4 图3 6v c h 6 o 集成开发环境3 4 图3 7p m 厄属性设置3 8 图3 8 辅助应用程序注册表1 ”3 8 图3 9 辅助应用程序注册表2 3 8 图3 1 0 解锁命令3 9 图4 1 添加的排样菜单4 5 图4 2 通过程序生成新的模型4 6 图4 3 排样的钣金零件4 8 图4 4 钣金零件的排样信息( 角度增量为0 0 1 ) 4 9 图4 5 钣金零件的排样信息( 角度增量为o 0 0 1 ) 4 9 图4 6 凹多边形钣金件5 0 图4 7p r 刚团n g 斟e e r 系统的自动排样5 1 图4 8n 吨n g i n e e r 系统的自动排样信息5 l 图4 9 按照本文方法的排样5 2 图4 1 0 按照本文方法的排样信息5 2 图4 1 lp 删咖e r 系统下多个零件的自动排样5 3 图4 1 2 按照本文方法多个零件的自动排样5 3 图4 1 3p r 0 i e i 屺胍e r 系统下多个零件的自动排样信息5 4 图4 1 4 按照本文方法多个零件的自动排样信息5 4 i 基于p i n n 羽g e t 平台的钣金展开件的自动捧样系统的开发 附表索引 表1 1 钣金件分类4 表3 1 注册文件各字段及意义3 6 i v 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担 作者签名：杨倦华日期沪磊孕叫日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：栖彳鸶鲜日期：加磊铲月莎芦 导师签名：j 苇纫辫f 日期：沙6 年月渤日 i v 硕上学位论文 1 1 概述 第1 章绪论 随着我国成功加入w t o 后，全球市场竞争更加激烈，在机械设计、制造信息化改造 领域中逐渐形成了智能化、集成化、并行化和网络化的发展趋势。在这个大趋势下，研 究和开发计算机c a d 软件系统受到了高度重视。它的丌发利用可以有效地提高企业的劳 动生产率，促进企业的市场竞争能力，对加速我国国民经济的发展和国防现代化具有十 分重要的意义。 1 9 6 3 年美国麻省理工学院的l v a ns u t h e r l a n d 在其博士论文中首次提出了计算机 幽形学、人机交互设计和符号存储分层的概念，奠定了计算机辅助设计的理论基础，从 而揭开了计算机辅助设计的序幕。从六十年代至今，c a d 技术经历了四代发展，分别经 历了基于绘图、基于特征、基于过程和基于知识的四个阶段，基于绘图阶段主要是以二 维为主的数字绘图，基于特征阶段主要是数字化、参数化建模技术，基于过程阶段主要 是数字过程导引技术，基于知识阶段主要是将知识技能、经验原理等结合到c a d 系统当 中。每一过程在前过程基础上提高设计自动化。 在过去三十多年时问内，c a d 技术在理论和应用上都取得了b 跃性的发展。先后推 出了多种应用于大、中、小型计算机和工作站卜的c a d 软件，如u g ，a u t o c a d ，c a t l a ， p r o e n g i n e e r 多种具有自主知识版权的c a d 软件，如c a x a 、大雄机电c a d 等。这些c a d 软件已经广泛应用于机械制造、航空航灭、船舶汽车等各行业，加速和促进了工业国防 现代化。 p r o e n g i n e e r 是美国参数技术公司( p t c ) 研制的三维c a d c a m 软件，于1 9 8 8 年问 世。1 0 多年来，历经2 0 余次的改版，己成为全【吐界及中围地区最普及的3 dc a d c a m 系统。广泛应用于电子、机械、模具、工业设计、汽车、自行车、航天、家电、玩具等 各行业。p r o e n g l n e e l 是全方位的3 d 产品开发软件包，和相关软件p r o d e s i n g e r ( 造 型、发计) 、p r o m e c h a n i c a ( 功能仿真) ，集合了零件设计、产品装配、模具丌发、加工 制造、钣金件设计、铸造件设计、工业设计、逆向工程、自动测量、机构分析、有限元 分析、产品数据库管理等功能，从而使用户缩短了产品丌发的时间并简化了丌发的流程； 国际上有2 7 0 0 0 多家企业采用了p r o e n g i n e e r 软件系统，作为企业的标准软件进行产 品开发。 1 _ 2 钣金件的c a d 现状 在国内外，钣金加工在机械加工领域占3 0 以卜，就中国来说，目前很人一部分的 钣金企业基本上还停留在小作坊的牛产模式，一般只有一两台冲床加一台折弯机，条件 基于p r o e n g i n e e r f 臼的钣盒展开件的自动排样系统的开发 好一点的可能会增添一台激光切割机。目前所见的大部分冲床基本上都还是比较低端的 冲床，没有设置自动落料口，吹气装置等，甚至有些机器的编程软件仍然停留在d o s 时 代，只是在比较大的一些外企以及高新技术企业才会使用f m s 等设备。这些极大地影响 了食业的竞争力。所以开发一套简币、经济、易用、高效的钣金c a d 系统软件，对于国 内那些经济实力较弱的饭金企业，使其技术人员在短期内就能很好的掌握和利用该软件 为其提高工作效率具有很大的工程实际意义。 金属板在被加1 ：成钣金件之前，必须先要按照钣金件展开图的大小进行切割，展丌 图的正确与否直接影响饭金件的最终精度。2 0 世纪8 0 年代之前，钣余件的展开一直采 用放样的方法，即采用1 ：l 的比例划钣金件进行放样，这样做既费时费料、又不精确。 随着科学技术的发展，人们渴望能用计算的方式米作出展丌图，计算法不受场地限制， 只须画出构件的示意图即可，不要求很高的作图技巧，且作出的图精度很高，对于复杂 构件，这种优势更加明显，这些年来，这方面的发展很快，也出版了不少这方而的新书， 如果仔细阅读这方面的资料，就会发现很多的作者都不谈如何用计算法实现复杂相贯构 件展丌图的精确绘制，这就给计算法的应用带来了很大的局限性。事实上，恰恰是复杂 相贯构件最需要这种方法来完成展开计算，如果用图解法，则需要高度的空间想象力和 作图技巧，作图人员如果没有多年的制图经验，很难完成工作。要想充分发挥计算法的 优势，就必须想办法解决如何用计算法实现复杂相贯构件展，r 图的精确绘制问题。”1 排样是钣金c a d 系统的另外一个丰要功能，在计算机出现之前，人们只能采用手动 排样。手动排样是依赖排样人员的经验，直觉和想象，进行判断与试验，受到人为因素 和客观因素的限制，效率低、劳动强度人。因此，人们迫切的需要从繁重的劳动中解脱 出来，丌始借助计算机进行计算机辅助人机交互排样和计算机自动排样。 1 _ 3 钣金件排样的发展概况 金属板制作的钣金件人量应用于幽民经济的各个领域，近年来，随着社会的发展和 科学技术的进步，机械加工自动化水平越来越高，数控机床得到了普遍应用，国内钣金 加工领域也普遍应用了数控机床，因此生产效率大为提高。然而，在众多中小企业中， 钣金加工数控机床的应用却不尽如人意，其主要原因在_ 丁用传统方法绘制展开图浪费时 问而且精确度得不到保证，钣金展丌图的绘制成为从设计到加工过程中的一个“瓶颈” 。众所周知，在设计中，设计人员绘制的通常是零件图，而数控冲床加工所需要下料 图的是零什展开图，从零件图到展丌图这一过程的工作如果全部由人工完成，那就极大 地影响了整体生产效率，延长= 了生，“周期。 目前我国机械c a d 软件市场的软件中包含钣金模块的尚不多见，有的虽包含了钣金 模块，但缺乏专业性，使用效率爿i 高。为此，开发一套适合我国的钣金c a d 系统尤为重 要，我们的目标是设计出方便、实用、更加专业的钣金模块。 2 现在我国的机械c a d 软件市场中虽然已经有基于a u t o c a d 的钣金排样系统问世，如： 钣金自动展开与智能排样( b j c a d ) v 1 0 ，通用自动排样系统p y c a d1 o 等，但因为它们 是基于a u t o c a d 的，所以不能对其排样的制造文件进行后续处理，如自动生成数控代码， 且其排样图形只能是平面二维图形，不能以一个钣金展开零件的形式存在。而我们开发 的系统能在p r o e n g i n e e r 提供的钣金排样模块的基础上对其进行改进，使排样的效果 更好，且排样完成后，生成制造文件，可自动生成数控代码，进行后续处理。 说到底什么是排样昵? 所谓排样，一般是指表示零件二维轮廓的多个相同或不同 的几何图形在原材料平面区域的合理布置，使得几何图形之间不出现重叠并且材料利用 率最高。 排样问题是f 料、布局问题的一种。下料、布局问题可以简单的分为一维、二维和 三维情形。一维情况就是棒料、管材、线材等割断卜- 料并使材料利用率高；三维情况就 是物体如何在空间摆放合理，并使得空间利用率最大，例如卡车、集装箱装货等。排样 问题属于下料、布局问题中的二维情况。 排样方案自2 接影响材料利用率、零件的可制造性和加工效率。在钣金零件制造中， 金属板材足消耗的主要原材料之一，零件的原材料费用在制造成本占有相当大的比重， 提高材料利用率和加工效率是降低零件制造成本的重要措施。因此，高效、优良的排样 技术足钣金零件制造中的关键技术之一。 在钣金件的制造费用中，原材料的费用要超过一一半，要想降低产品成本，提高材料 利用率是个非常重要的手段。钣会件的排样就是按照某种算法合理地在板材上排放要 切割的冲裁件，从而达到节约原材料的目的。把计算机应用于这一领域，为钣金件排样 叫题丌辟了一条有效的途径。 国外在将计算机应用于钣金件的排样方面起步较早，在2 0 世纪6 0 年代中期，就有 人，| ：始这方而的研究，f 1 本在这方面的研究处于领先地位。我国对钣金件的排样研究丌 始于2 0 世纪8 0 年代中期，目前主要集中在算法的研究方面。 1 4 钣金件的分类 对钣金件的分类，目前比较常见的分法是根据其形状特点将其分为若干类，如圆管 类、棱柱、棱锥管类、长网管类、方口曲面管类、圆锥管类、异口形管类、球体类等。 这种分类法的特点足直观、通俗、简洁，但没有将可展类钣金件和不可展类钣金件明显 地区分丌来。本文提出了另一种分类方法，这种方法首先从钣金件是否可展的角度，将 其分成2 个大类，在此基础上继续细分。具体划分请见表1 1 1 5 本文研究的主要内容和意义 本课题来自于实际生j “：的需要，通过本文的研究，探讨钣金展开件在p r o e n g i n e e r 表1 1 钣金件分类 圆管 如：一端斜截成任意角度的圆管 椭网管如：锅炉门 世 圆形管 k 圆管 如：网角方口人小头连接管 圆锥管如：斜圆锥管 个 棱柱管 立u ：成任意角度倾斜的矩形连接管 口j 多边形管 棱锥管如：正四角锥 制 方u 曲面管如：方管弧面9 0 度：弩头 小蛳则形管 异u 形管如：圆顶方底连接管 件 多边形板折巧件如：四边形板折弯什 j 诞 零片板折变件弧形板折弯件如：扇形板折角 混合形板折弯什立u ：圆弧顶直线底蛮板 圆管与网管相贯 如：等径三通管、多节圆管弯义 圆形管1 ，【硒形 同管与同锥管相贯 如：汇圆锥管直交创管 管相贯 圆锥管与圆锥管相贯 如：正圆锥管斜交正圆锥管 相 k 【l ：5 i 管与k 圆管相贳 如：半k 网管两节：头 网形管1 刊- 面圆管与平皿管丰h 贯如：方锥管直交圆管 贯 管相贯圆锥管与、卜面管扣贳 如：矩形管直交正网锥管 衙 、卜面管o 、卜向 制平面管jj r 面管相贯立：方管2 节异向 。i 管柙贯 型铡y 圆形管型钢与圆管相贳如：工钢支撑倾斜圆管 件 相贯型俐l i 圆锥管相贯如：t 字铡平交正圆锥台 带补料的网形管与圆形管干日贯 如：带补料的人小圆管直交三通管 惜补料的制件 带补料的图形管与下面管相贯 如：长图土管方支管三通管 单 封头如：椭圆形判头 小 球体 球瓣 如：球体分瓣展开 个 町 制 球带 如：球体分带胜开 展 团柱螺旋面如：沿圆柱面的螺旋绞龙溜槽 曲 件螺旋面 圆锥螺旋血如：沿网锥面的螺旋绞龙溜槽 血 相贯 相贯制件 球件与同管相贳如：圆甲插热风炉炉帽 制件球体与方管相贳如：方管和圆管斜捅封头 环境下的排样，并针对各种排样算法进行比较，为钣金c a d 模块提供更有效的排样 算法，为实现钣金件c a d c a m 一体化打下基础。 本课题研究的主要内容分为以下三大部分： ( 1 ) 基于p r o e n g i n e e r 的二次开发工具p r o t 0 0 “i t 函数的编制及使用。 ( 2 ) 钣金件优化排样算法研究。 ( 3 ) 针对p r o e n g i n e e r 的钣金排样模块，进步完善，使排样效果更好，并将本 课题的排样和p r o e n g i n e 呲钣金排样模块的排样进行对比。 在实际生产中，传统的饭金件展开图的绘制方法是利用纸板放样、手工画线和手工 下料传统工序，这种方法既费时又费力，且精度较低，随着计算机技术的发展，计算机 4 绘图技术突飞猛进，利用计算机进行钣金件展开图的绘制很有必要，本课题研究的钣金 件展开图可视化、参数化绘图系统，不仅能够缩短生产周期、节约人力资源、提高生产 率和绘图精度，而日还可以降低工人的劳动强度、有效地为企业节省钢材、增加利润。 通过大量的调研，证明比较传统的手工作业，该系统可以提高工效约3 0 0 5 0 0 ，节省 钢材约1 0 2 0 。 另外，在p r o e 环境下对钣金进行展开，为饭金的后续排样和加工等工序的处理提 供了很好的方便条件。这些工序可以直接在p r o e 中进行，无须对展开图再做后续处理。 第2 章钣金件的优化排样 排样问题是一类最优化问题，可描述为在给定的板材内，对所给定形状和数量的钣 金零件进行排布，这些钣金零件互不干涉、重叠，且都处于排样区域之内，同时使得材 料利用率尽量高。对钣会c a d 系统而言，一个好的排样算法至关重要，它往往决定了 钣金c a d 系统的性能和实用性。在本章中依次分析了优化算法的选择、优化问题和算 法复杂性、目前研究的现状并对优化排样算法进行研究等等，最终为钣金c a d 系统开 发提供实用的算法【5 j 。 2 1 优化算法的选择 对于工程中许多优化问题，找到+ 个最优解的唯一可靠方法是穷举法。穷举法对问 题的整个解空间进行搜索，然而对排样这一完全问题来说是不可能的。解决优化难题最 有效的方法之一是局部搜索算法。在局部搜索算法中，传统的方法是用启发式策略，从 某个初始解开始，在它的邻域内寻找更好的解，直到不能再优为止。在局部搜索算法的 应用中，有一些共性问题： ( 1 ) 邻域的选择。 没有理沦指明怎样选择邻域的大小，大多数情况下无法设定恰当的邻域结构。在可 接受的固定的计算机时间里，找到的局部最优解的个数是有限的，在搜索过程中即使允 许偶尔跳到解空间中更远的部分( 变深度寻优算法) ，往往也不能保汪最终解的质量。 f 2 ) 初始解的选择。 最终解的质量依赖于初始解的选择，实用的方法是从有限个不同的初始点出发进行 局部搜索，并选取其巾最优的结果。局部最优解的质量是否依赖于邻域结构是不确定的， 这些起始点的选择往往是随机的，这就可能导致最终得到的是差的解。 f 3 1 搜索方式和搜索方向的选择。 搜索方式和搜索方向的选择也是直接影响最优解的主要因素之一，也很难找到一个 合适方式和方向。针对具体问题，是采用先改进法还是最速下降法进行搜索? 不好确定。 而复杂的问题在搜索空划中会出现许多峰值点，随着参变量空间维数的增大，其拓扑结 构也可能更加复杂，确定搜索方向会变得很困难。 2 2 优化问题和算法复杂性 6 优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的参数称为 变量，对变量取值的种种限制称为约束，表示可行方案衡量为目标函数。从变量形式分 析，优化问题可以分为两类：一类是连续变量的问题，即连续优化问题；另一类是离散 变量的问题，即组合优化问题。优化问题的目标是从该问题有可行解集中求出最优解。 在连续优化问题里，一般是求一组实数，或者一个函数；在组合优化问题里是从一个无 限集或者可数无限集里寻找一个对象典型的是一个整数，一个集合，一个排列或者 一个图。算法是解决优化问题的方法，是由若干条指令组成的有穷序列。评价算法的好 坏主要考虑如下三点： ( 1 ) 执行算法所耗费的时间。 ( 2 ) 执行算法所耗费的存储空问。 ( 3 ) 算法应易于理解，易于编码，易于调试。 可判定问题( 即原则上存在一个算法，可以解该问题的任何一个实例) 在实际中不一 定是可解的，因为算法叫能需要极长的运行时间与极大的存贮空间，以至于根本不可能 在现有计算机上实现。衡量一个算法的效果，最广泛采用的标准是它在得到最终答案前 所用的时间是多少，即时间复杂性，它是该算法所求解问题规模月的函数，丁协) 。当问 题的规模”趋向无穷大时，把时问复杂度丁伽) 的数量级称为算法的渐近时间复杂性。一 个问题的时间复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂 性。按照可判定问题的复杂性可以把优化问题分为两大类：p 类和n p ( 即n o n d e t e h n i n i s t i c p o l y n o m i a l ) 类。p 类表示多项式时间所能解决的问题，n p 类问题是指可在多项式时间里 检验的问题类，至今尚未找到有效的多项式时问算法。 从数学计算复杂性理论看，组合排样优化问题属于具有最高计算复杂性的类问题 完全问题，n p 完全问题是n p 类中最难的问题，具有如下性质： ( 1 ) 任何一完全问题都不能用己知的多项式算法求解。 ( 2 ) 若任何一个完全问题有多项式算法，则一切完全问题都有多项式算法。 难于 计算是完全问题的固有性质，对现存的完全问题至今还没有找到一个问题的多项式时问 算法，一般认为完全问题不存在有效的多项式时间算法。排样问题在很多领域都具有重 大的实际意义，而且在实际问题中有许多约束，因此需要找出兼顾解的质量以及运行时 间的较好算法。 2 3 目前研究的现状 随着工业的发展，对各类板材零件的需求量也越米越大，但目前利用传统的手工 排样，由于其编排速度慢，板材利用率低， 已不能适应生产的发展和需要了。随着计 算机应用的普及，人们也开始使用计算机进行排样设计， 这类方法通常有两种形式， 即人机对岳式排样与计算机自动排样与手工排样相比，人机对话式排样同样要求操 7 作者必须具备高度的排样技巧，计算机仅仅充当了一个基本的辅助手段一图形显示， 即使如此，当排样数日增加时。所需的排样时间也成倍增加，另一类是计算机自动排样， 当输入零件坯料参数、板村尺寸和： 艺参数后，根据指定的规则不需人工干预， 自动、 快速完成， 但由于零件外形复杂多样，使自动排样难以实现。 所以能找到一个好的自动排样系统非常必要的。 钣金排样是一个二维的平面排样问题，目前讨论饭金排样问题的文章很 多”3 ，大体上现，具体分为很多类，按形状分为矩形、单一多边形、凸多边形、规则 多边形、任意多边形，按排列方式分固定方向、可旋转等，按排样要求分为在定宽无限 长板村上排样求最小高度、在无限多定宽定高板材上求最少板材个数等。还有其他多种 分类方式，形成各式各样的排样问题。从数学计算复杂性理论可知，排样优化问题属于 n p 完全问题，存在“组合爆炸”，找到最优解非常困难。因此采用了很多近似算法，比 如矩形算法、遗传算法、模拟退火算法、蚂蚁算法等。 2 4 材料利用率的计算 在排样问题中，人们最关心的就是材料利用率，它主要受两个方面影响： ( 1 ) 零件本身结构、形状，如形状不规则程度高、存在内孔等，将不可避免的产生 废料； ( 2 ) 工艺因素，包括加工方式和排样方式，形成不能再利用的小块边角料等废料。 以上仅仅是从概念上划分两种废料，但实际中很难具体确定。工艺因素引起的废料 可以通过改进工艺降低浪费率。排样问题研究的就是如何采取优化排样策略，尽量避免 工艺性废料，同时通过运用合理的排样方式减少零件本身形状所带来的浪费。 假设有 个待排零件，对于矩形件排样的计算，假设任意一个矩形长和宽一记为厶， 和，则 个待排零件的面积和为： 月 s = ( f x 缈f ) ( 2 1 ) f = l 对于任意多边形排样的计算，我们记录任意多边形的各个顶点，假设某一任意多边 形零件有m 个顶点，则该零件的面积为： s = 兰 ( y f = 1 ( 2 2 ) x ，和y j 为顶点坐标，3 f ，”，1 ， ，n 个待排零件的面积和为： s = ( s f ) j 2 l ( 23 ) 我们将零件排放到宽度一定，不限制长的卷料上，假设排样高度为厅，故而利用 s ，7 3 丙i ( 2 4 ) 8 率为： 2 5 优化排样算法的研究 2 5 1 最优化方法和启发式技术 2 5 1 1 最优化方法 简单地况，最优化问题就是如何在一切的可能方案中寻求最优的方案。最优化问题 的一般定义如下： 一个最优化问题的一个实例是对一对元素( f ，c ) ，其中f 是一个几何或可行点的定 义域，c 是费用函数，最优化问题就是求一个f f ，使得对一切y f ，有c ( d 剀，板材的数量足以排下所有要排的矩形 件所有要排的矩形件共有r 种，第f 种矩形的个数为珥，长度为如宽度为6 2 刀。 则全部要排的矩形件总数为： r = 珥 ( 2 6 ) 基本目标是： 使排样所用的板材数尽可能的少，尽可能的提高材料的利用率。 排样规则为： 每一个矩形零件可按板材的长或宽进行正排( 正排即矩形零件的长或宽总是与板材 的长或宽平行) ，从板材的最左下角开始排至板材的右上角结束。 排样的基本约束条件为： 以板材的左下角点为 捧样坐标系原点( o ，o ) ，且 为排样起点，排样过程中 不得有任何排样点落在此 点左侧；板材的右上角点 皿，b ) ，且捧样过程中不得 有任何排样点落在此点右 侧。我们知道一块矩形件 在板材的位置可以由该矩 形件的左下角点，m j ) 和右上角点o 啦，y 曲确定。 1 4 图2 2 排样方式 碗士学位论文 在般矩形件的正排问题中，通常有四种排样方式如图2 2 所示： ( a ) 图和( c ) 图可归结为横排方式：( b ) 图和( d ) 图可归结为竖排方式。所以矩形件 排样问题实际上就只有横排和竖排两种方式，因此矩形件在排样坐标系上的关系为： 2 = 而i + 工1 2 = x f l + 玩 弘2 = 弘1 + 6 j 取 _ y ，2 = y f i + 其中f _ j ，2 ，n 。前一种为横排，后一种为竖排，见图2 2 。由此可见，对于 决定每一块矩形件的排放，实际上只有三个自由量：砌；期和决定矩形件f 横排还是 竖排的逻辑变量r i ( r f 卸表示横排，n = l 示竖排) 。 则j ，弘j ) 与o 嘧，y 堙) 的关系可由式( 2 7 ) 表示为： 一2 = 而i + ( 1 一) + 岛 。， 舅2 = 乃l + ( 1 一) 6 f + 、。 设r ，和风为排样坐标系上任意两个矩形件，它们的长和宽分别为k 和6 ，以， 它们对应的左下角和右上角的坐标分别为 0 小m ) ( 砌，问) 和 ，弘，) ( 勘，脚 。 所以当下面情况之一出现时，它们互不重叠： ( 1 ) t 1 2 2 ，时矩形s 在t 的右边 ( 2 ) m 1 只2 ，时矩形s 在t 的下方 ( 3 ) 只l 只2 ，时矩形s 在t 的上方 ( 2 8 ) ( 4 ) h 2 ，时矩形s 在t 的左边 对应这四种情况由式( 2 8 ) 得： 式 l 确+ ( 1 一m + 6 r 只i y n + ( 1 一) 以+ j 0 l 只l + ( 1 一，；) 匆+ 而l t 1 + ( 1 一) + 以 要使得任意一个矩形件心与r 均不排出板材范围之外， o s 薯1 工 o 2 工 0 儿i 占 o 茎”2s 丑 由式( 2 8 ) 及( 2 1 0 ) 得： o s i 上一( 1 一) 一，；6 | o s 儿l b 一( i 一) 6 f 一 这样，得到优化排样的目标函数为： i 懈刁( 一2 一耳。) ( 咒2 一只1 ) 目 1 5 ( 2 9 ) 则它的坐标应同时满足下 ( 2 i o ) ( 2 1 1 ) ( 2 1 2 ) 基于n 刚啪瑚觋平台的饭金展开件的自动捧样系统的开发 这里函= o 或1 总结上面的分析，得到优化排样的数学模型为： i 瑚x z 。 一m + 趣) ( ( 1 一地+ 巩) 扣d ( 2 1 3 ) 约束条件为： ( 1 )。一l 一( 1 一m 一良 o ( 2 ) m i y n 一( 1 一) 以一 0 ( 3 ) y n 一儿l 一( 1 一) 以一 0 ( 4 ) 砀一一( 1 一) 一岭o ( 2 1 ( 5 ) o s 薯ls 上一( 1 一) 一巨 、 ( 6 )0 蔓y n b 一( 1 一) 以一 f 7 ) j r ，= 0 或1 ，= f = o 或1 ( 8 ) j ，f ，卢l ，2 ，月 以上约束中，约束( 1 ) h ) 由公式2 9 得，约束( 5 ) ，( 6 ) 由公式2 1 1 得。 从上面数学模型可以看到，该优化问题实际上是一个混合的规划问题；在上面的式子 中，变量而，j 啊。是连续的；n ，乃是离散的。总共有4 玎个变量。此类问题被称为n p c 伽1 p l c t e p r o b l 锄( n _ p 完备问题) ，具有最高计算复杂性，目前在理论上还没有有效的最优解算法， 很难求出最优解。无论国外还是国内对此类问题的有效解决仅限于针对某些实际问题在 满足某些特定条件下的近似算法和启发算法。 2 5 3 常用的几种启发式算法 2 5 3 1 遗传算法 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律 产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优 化算法。 遗传算法口1 】【2 叼概念最早是由b 嘲e yj d 在1 9 6 7 年提出的；而开始遗传算法的理 论和方法的系统性研究的是1 9 7 5 年，这一开创性工作是由m i d 蚯g 阻大学的j h h o l l 锄d 所实行。当时，其主要目的是说明自然和人工系统的自适应过程。 遗传算法简称g 刖g e n 甜ca l g 耐m m ) ，在本质上是一种不依赖具体问题的直接搜索 方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应 控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗 传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算 技术有重大影响的关键技术”。 1 6 l 、遗传算法的基本概念 遗传算法的基本思想是基于d a r 喇n 进化论和m 阻d e l 的遗传学说的。 d 扪) l ，i i l 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环 境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。 在环境变化时，只有那些能适应环境的个体特征才能保留下来。 m e n d e l 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中， 并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每 个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的 后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算 法中要用到各种进化和遗传学的概念。这些概念如下： ( 1 ) 串( s 圩i n 曲 它是个体( i n m v i d u a l ) 的形式，在算法中为二进制串，并且对应于遗传学中的染色体 ( c l l r o m o s o m e ) 。 ( 2 ) 群体 o p u l a n o n ) 个体的集合称为群体，串是群体的元素 ( 3 ) 群体大小o p u i a t i o ns i z e ) 在群体中个体的数量称为群体的大小。 ( 4 ) 基因( g e ) 基因是串中的元素，基因用于表示个体的特征。例如有一个串s = 1 0 1 1 ，则其中的 1 ，0 ，l ，1 这4 个元素分别称为基因。它们的值称为等位基因( a j l 鼬回。 圆基因位置( g 蚰ep o s 弛n ) 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右 计算，例如在串s = 1 1 0 1 中，o 的基因位置是3 。基因位置对应于遗传学中的地点( l o c l l s ) 。 旧基因特征值( g e n ef 强t u 呐 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串s = 1 0 1 1 中，基 因位置3 中的1 ，它的基因特征值为2 ；基因位置l 中的1 ，它的基因特征值为8 。 ( 7 ) 串结构空间s s 在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结 构空问对应于遗传学中的基因型( g e n 吨r p e ) 的集合。 ( 8 ) 参数空间s p 这是串空间在物理系统中的映射，它对应于遗传学中的表现型a p h e n o t y p e ) 的集合。 ( 9 ) 非线性 它对应遗传学中的异位显性仲i s t a s i s ) 1 7 基于p t 洲g i 眦r 平台的饭垒展开件的自动捧样系统的开发 ( 1 0 ) 适应度伊i 恤e 黯) 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念这些概念在介绍遗传算法的原理和执行过程时，再 进行说明。 2 、遗传算法的原理 遗传算法g a 把问题的解表示成“染色体”，在算法中即是以二进制编码的串。并且， 在执行遗传算法之前，给出一群“染色体”，即是假设解。然后，把这些假设解置于问题 的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通 过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后 就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 ( 1 ) 遗传算法的目的 典型的遗传算法c g a ( c 姐o n i c a lg e n e t i c 越鲥n 瑚) 通常用于解决下面这一类的静态 最优化问题： 考虑对于一群长度为工的二进制编码籼，f = 1 ，2 ，一：有6 ， o ，1 ) l 对于给 定目标函数f ，有邪1 ) ，并且，f ( 6 f ) m 同时勋游f p + 1 )求满足下式 m a ) 【 炳) i6 j o ，1 ) l ) 的6 j 。 很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群 中，不断进化产生新的解，最后收敛到一个特定的串玩处，即求出最优解。 ( 2 ) 遗传算法的基本原理 长度为三的玎个二进制串岛( f = 1 ，2 ，而组成了遗传算法的初解群，也称为初 始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执 行的操作有三种： a 选择( s d t i o ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代故有时 也称这一操作为再生( p r o d u c t i o n ) 。由于在选择用于繁殖下一代的个体时，是根据个体 对环境的适应度而决定其繁殖量的，：故而有时也称为非均匀再生( d i ：髓r e 】m a l r c p m d u c d o n ) 。 b 交叉( c m 黯o v e r ) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交 换，从而产生新的个体。 c 变异m u t a 如) 这是在选中的个体中，对个体中的某些基因执行异向转化在串6 中，如果某位基 因为1 ，产生变异时就是把它变成0 ：反之亦然。 遗传算法的原理可以简要给出如下： c ：h o o 柚碰a lp o p u l 撕o n d d 【e r m i n et h