（机械制造及其自动化专业论文）计算机优化排样研究与系统设计.pdf

p 3 7 3 1 9 2 计算机优化排样研究与系统设计 摘要 小义埘如何将种新的优化办法m e b m l 心川j i ：维f i 规! j | j 图形排样进i 】：j ，深入研究：m e b m l ( m in de v 0 1 ul i o n b a s e dm a c h in el e a r n i n g ，基1 ：思 维进化的机器。爿) 足模仿人类思维进化而提小的 种新型机器学爿算法。m e b m 。町应用于各种优化领域 及非数值问题。本文将m e b m l 引入剑机械领域的优化 排样中，提出j ，一种有效的图形编码方案及趋同与异 化策略。运用c + + 语言编制1 厂使用m e b m l 进行二维 不规则图形排样的优化程序，并取得了明显效果。并 在理论分析基础上，通过实验研究得出二维不规则图 形排样 i 最优参数的选取范闱及选择原! j ! | j 。 此外，本文将该乃泄、与j 他力。法进行了试验对 比。 关键词：优化 i 群堪丁思维进化的机器学习 v t h e s t u d ya n ds y s t e md e s i g n o f c o m p u t e r a i d e do p t i m u ml a y o u t a b s t r a c t i nt h i s p a p e r ，h o w t o a p p l y an e w o p t i m u m m e t h o di nt h e n e s t i n g o f t w o d i m e n s i o n a l i r r e g u l a rs h a p e s i s d e e p l y s t u d i e d m e b m l ， m i n d e v o l u t i o n ，b a s e d m a c h i n el e a r n i n gi san e wt y p eo fm a c h i n e l e a r n i n ga l g o r i t h mw h i c hi m i t a t et h e f o r m u l a o fa n i m a l s e v o l u t i o n m e b m lh a sm u c h s u p e r i o r i t yf o rs o l v i n gp r e m a t u r ec o n v e r g e n c e p r o b l e m o f g e n e t i ca l g o r i t h m a n d n o n - n u m e r i c a l o p t i m i z a t i o n w e u s e dt h e a l g o r i t h m s t o o p t i m a l a y o u t ac o m p u t e r p r o g r a m t h a t i m p l e m e n t s t h i sm e t h o di s d e v e l o p e d i n “c + + ”，a n dg o ts a t i s f i e dr e s u l t s a c c o r d i n gt o t h e s e e x p e r i m e n t s ，t h es e l e c t i n g m e t h o do ft h eb e s tf a c t o r ss u i t a b l ef o rv a r i o u s c o n d i t i o n si sc o n c l u d e d i n a d d i t i o n ，i n t h i s p a p e r ，a s e r i e so f c o m p a r a t i v e t e s tw i t ho t h e rm e t h o d sw e r e m a d e k e yw o r d s ：o p t i m u mn e s t i n g m e b m l 1j r ；1 ；z a t i o nr a t eo fm a t e r i a l 太原理t 人学 i j 究生毕业论立用纸第1 页 第一章引论 第一节概述 企业为了在激烈的市场竞争之中生存，发展并立于不 败之地，一个十分重要的任务就是尽一切力量提高企业的经 济效益，而提高效益的一个重要环节就是降低生产成本。在 机械制造中，许多行业要进行板材下料。进行板材下料的首 要任务是如何在满足一定的约束条件下合理、有效地在原材 料上安排各工件毛坯的位置、方向以及排放个数，力求下料 过程中在满足工件要求的前提下，使用的原材料最少，也就 是所谓的优化排样。 一般做法是根据需要先做出样板( 预先放大了切口余 量) ，在原材料( 轧制钢板，铝板等) 上人工排样，使其尽 可能紧密，最后进行工件的分离。由于下料的零件各异，人 工排样费工费事，且难以得到最佳效果。在这样的形势要求 下，开发出实用，方便的计算机辅助优化排样系统是一项非 常有现实意义的工作。当今世界计算机技术在不断发 展，c a d c a m 技术已进入越来越多的领域在钣金切割，模具 设计，制鞋，服装裁剪等行业，计算机对二维零件图形的辅助 排样已成为c a d c a m 系统不可分割的组成部分，其目的和意 义在于提高质量，降低成本，提高生产效率。 国外自六十年代中期起研究计算机优化排样，目前有 些公司提供软件产品。我国在机械制造行业中，开展计算 太原删t 人学驯究生毕业论殳用巩第2 贝 机优化排样的研究较晚，但是生产厂家为了提高自己在市场 经济中的竞争力，已经越米越重视对优化排样的研究。 不同的行、眦，分离零件的方式也不同，这主要是由于 不同行业所加工的板料零件的形状和尺寸不同而决定的。分 离零件的方式不同，决定计算机优化排样系统采用的处理方 法和算法也不相同。按计算机优化排样系统的应用范围，可 以分为下面三种类别： 主要应用于外形复杂、不规则的零件的计算机优化 排样系统。 应用于冲裁模加工各种冲裁件的条料，带料计算机 优化排样系统。 主要应用于以加工矩形零件为主的板料柔性加工 系统的计算机优化排样系统。 最初的排样是针对棒料、钢筋或型材的下料，属于一 维排样。而在下料过程中，我们遇到的更多的是板材的下料 问题，这涉及到二维排样。由于二维排样需要从两个方向上 考虑如何组合排列图形，所以远比一维排样复杂。最常见的 二维排样是矩形件的优化下料，人们先是根据零件的毛坯形 状把零件转化为最小包围矩形，然后利用一些按比例缩小的 样形进行最优化下料的试排。为了能够有效地利用裁剪下来 的边角余料，人们再利用它们来制作较小的毛坯。很显然， 这种工作方式效率较低。材料利用率也不尽人意。 尽管如此，人们还是从排样中得到了效益，也从中看 到了排样在生产中的重要性。因此众多技术人员一直对排样 技术进行着大量而又坚持不懈的研究。近年来，随着计算机 技术的日新月异，人们已不再满足于速度慢、精度差的人工 太原胖t 人学划l 究生毕、论立用纸第3 砸 排样，丌始利用计算机进行优化排样，并且在样形的输入以 及优化排样后的图形输出上做了大量的工作，使下料过程变 得高效而又富有吸引力，下料工人的劳动强度大大减轻。 九十年代以来，人们已经开始计算机下料集成系统的 研究与丌发。这方向的成果将使下料生产中的优化排样以及 零什毛坯的切割、冲裁过程实现全面自动化。毫无疑问，这 代表着现代化生产的一个重要发展方向，也是有待于我们努 力探索的具有现实意义的一项重要课题。 第二节计算机优化排样的发展与现状 以计算机作为主要技术手段来生成和运用各种数字信 息与图形信息进行产品设计和制造的计算机辅助设计( c a d ) 和计算机辅助制造( c a m ) 的出现，给现代生产注入了极强的 生命活力。六十年代，伴随着交互式图象显示设备的出现以 及计算机图形学的迅速发展，发达国家己开始利用计算机进 行产品设计和数控生产。各行业内部及其之间的激烈竞争促 使生产者在产品的设计制造以及组织生产的传统模式上进 行深刻的菠革。它改变了工程技术人员的工作方式，缩短了 产品研制剧期，显著改善了产品的生产质量和生产效率，使 工人的劳动强度大大降低。由于生产方式的改变，产品的成 本在市场竞争中显得至关重要，投资者开始把降低成本放在 生产组织中的首要位置。管理经验表明：提高生产效率、降 低原材料浪费是降低产品成本的有效手段。出于上述考虑， 排样工作，尤其是计算机优化排样便应运而生。排样，使下 料工人可以最大限度地提高材料利用率；计算机的高速、精 太原理下人学l i f 究生毕业论艾用纸第4 负 确运算又使得排样结果最优，时间极短。 1 、国内外发展状况 由于计算机图形学、优化技术、以及自动化高效生产 的迅猛发展，国内外许多工程技术人员及科研学者对各类材 料的排样工作做出了不小的贡献。在造船、飞机、服装等许 多行业中，下料工人和技术人员已经找到了不少的排样方 法，并对排样算法进行了大量研究，编制出一些简便有效的 计算机排样程序。从计算机优化排样的发展上讲，大体上经 历了如下几个阶段： 第一阶段是一维下料的排样。由于一维图形的排放方 式比较简单，因此确定排样方式和下料方式的算法较为简 单，人们已编制出了结果较为满意的优化程序，只是在计算 机人机界面上比较简陋。 第二阶段主要是对矩形材料或是较为规则的图形进行 排样。最初的二维排样多为手工排样，它利用计算机的交互 式图形技术，首先通过图形输入工具将所排样形输入计算机 并将图形存储，然后利用计算机图形的旋转、平移等功能进 行人为的排样，通过人机对话完成排样利用率的计算和比 较，当获得较为满意的排样时将结果保存并输出到图形打印 设备。 第三阶段为自动排样。随着计算机程序语言的不断发 展，人们将优化算法与计算机图形技术结合在一起，编制出 一些计算机优化排样程序，实现了自动排样。但由于二维图 形约束条件多、边界信息复杂等问题，程序在全局范围内自 动寻优的效果并不太理想，仍需根据排样工人的意图以及上 一次的排样结果，通过人机交互方式完成较为满意的优化排 太原理t 人学研究生毕业论义用纸第5 页 样。优化领域中新的优化技术的出现，在全局范围内寻优的 优化算法不断被工程技术人员和科研人员提出，计算机优化 排样过程步入全自动阶段。在这个阶段，排样过程变得简便、 迅速；优化效果较好；图形的输入方式简便易学，并可以直 接读取c a d 图形软件中的图形：图形输出内容也有所增加， 除包含排样方式外，还包括各图形尺寸、下料路径及下料过 程中的一些技术要求等。此时的排样过程已经象一个黑匣 子，我们只需将图形输入系统，系统便可把最优的排样结果 和其它有价值的内容输出到外围设备。 在此之后，人们开始进行下料集成系统的开发和研制， 优化排样和自动下料过程将集成在该系统之中。这一系统的 研制成功将使产品设计、生产组织、产品制造集成一体成为 现实，为计算机集成制造系统( c i m s ) 和自动化工厂( a f ) 等的 实现提供可能。 2 、国内外应用 如今，计算机优化排样已开始进入各制造工业，对于 一维图形的排样下料和二维规则材料的排样，国内外已经研 制出一些较为成熟的软件。在图形的输入转换、数据兼容性、 操作界面以及图形输出等方面人们做了许多卓有成效的工 作，并且大部分软件不仅仅具有通用性而且可针对产品具体 情况增加特殊功能，为使用者提供了极大方便。如门窗优化 设计软件中在输入窗体轮廓尺寸之后，系统将对该窗体所需 的型材( 一维) 、玻璃( 二维) 等材料进行优化计算，并输 出排样图及下料方式，而且将该窗体生产所需的把手、螺钉 等各种辅料的配套数量列以明细，为组织生产提供了便利条 件。 太原理工大学研究生毕业论义用瓤第6 史 在我国，不少生产厂家已开始使用计算机进行优化排 样，但在普及程度及技术水平上，与发达国家相比仍有较大 差距。对现有资料的分析表明，我国对计算机排样技术的研 究虽起步较晚，但在单一冲裁件及矩形材料的优化排样上已 取得很大成绩，如冲裁件排样的最优化数学模型及算法、矩 形件套裁人工智能优化排样及优化剪切下料c a p p 软件的 开发等。对于二维不规则图形的通用优化排样问题，也有部 分学者对其进行了深入的研究并取得了一定的效果。但是仍 然存在着某些缺陷，因此探索一种更加有效合理的排样方 法，具有重要的意义。 第三节课题内容 对于优化排样，现有的资料大部分是对于规则图形( 矩 形) 进行的排样，这样就先限制了该方法的使用范围。而实 际的生产过程中绝大部分进行的是不规则工件的排样，不规 则图形的排样由于要排放的样件形状不规则，数量较多，要 达到最佳排样，非常困难。首先对一个样件来说，可以有无 数个取向；对于所有要排放的样件，先排那一个后排那一个， 由于排放的顺序不同，产生的解空间非常巨大。两者组合在 一起，计算量非常之大，即使用高速计算机，耗时也很惊人。 这就需要找到一种可行的算法，来解决这个问题。找一种通 用有效的算法完成其优化计算较为困难。但是在生产实践 中，二维不规则形状的排样是极其常见的，因此解决这一难 题势在必行。近年来，国内外些学者在对模拟生物遗传工 程进化过程进行全局寻优的遗传算法( 简称g a ) 进行大量 太原理工人学究生毕业论义用纸 第7 页 研究的基础上，提出使用该算法进行二维不规则图形排样优 化的新方法。有关资料对遗传算法及其在优化排样过程中的 应用进行了初步探索，尽管在方法的实现和应用上仍不成 熟，但这一算法的提出无疑为排样技术开辟了新的思路，为 解决二维不规则图形的优化排样问题奠定了基础。但g a 在 许多问题上的早熟( 即过早收敛于局部最优解而非全局最优 解) 始终未得到很好的解决，在将g a 应用于优化排样时有 时得不到最优解，即存在遗传欺骗问题。 m e b m l 是受g a 中“群体”与“进化”的启发，从模 仿人类思维进化的角度出发，提出了不同于g a 操作方法的 “趋同”与“异化”操作。“趋同”增强了算法搜索的目的 性，而“异化”则避免了算法陷于局部最优不能自拔的情况。 m e b m l 大大提高了g a 的某些性能。本文将m e b m l 引 入到机械领域的优化排样中，提出了一种适合于优化排样的 m e b m l 编码方案及提高优化效率的辅助算子( 蠕动) ，较 好地解决了排样搜索空间的组合爆炸问题，可以在较短时间 内求得接近最优的排样方案。 1 、课题确定 本文将在现有资料的基础上，对基于思维进化的机器 学习算法的运算过程及其运用于二维排样的实现方法进行 深入研究，利用此算法不必列出数学模型的特点，力图寻找 适用于多行业、多样形的优化排样方法，并编制使用 m e b m l 进行二维不规则图形的计算机优化排样软件。本文 主要工作如下： 1 、介绍种新型的算法：m e b m l 2 、 探索m e b m l 适应于优化排样的编码方式，从而 太原理丁人学_ ! j f 究生毕业论史用纸第8 页 得出m e b m l 应用于优化排样之中的具体方法。 3 、 编制实现该算法的计算机程序，分析优化结果。 4 、 利用程序对优化排样过程进行实验研究，分析运 算参数对优化结果的影响及其选择原则。 5 、 将该方法与运用遗传算法编制的排样方法进行 排样效果对比。 太原理丁人学叫究生毕业论义用纸 第9 页 第二章优化排样介绍 第一节优化排样简介 在现有的有关优化排样的资料中，将排样分为一维排 样和二维排样，其中二维排样又可分为矩形排样、冲裁件套 排及不规则图形排样等。 一维排样是指条料、棒料等的下料方式的确定，它仅 需考虑一个方向的变化，相对来说比较容易。 二维排样是在利用率约束条件下寻求二维图形的最佳 排样方式。最常见的二维排样是矩形材料的排放，由于矩形 材料只需考虑位置和两个方向的变化，因此问题较为简单。 在板材等的二维不规则图形排样过程中，由于二维不规则图 形的形状千差万别，寻找一种适用性广、优化结果好的算法 较为困难。因此对于不规则形状，常常首先把不规则图形转 化为矩形，然后进行矩形排样。 冲裁件套排是一种特殊的排样过程，它所面对的对象 往往是一个或两个相同样件。人们针对冲裁件排样的普通单 排、普通双排、对头单排、对头双排等四种方案，提出了许 多算法，如人机交互法、解析函数法、矩形包络法等。 在现阶段的排样研究中，人们的注意力集中到多个不 规则图形的优化排样上。由于不规则图形的边界信息较多， 排放位置和方向变化复杂，因此在多个不规则图形的排样中 可产生的排样方式极其多样，寻求一种搜索方法来包含全部 太原理工夫学研究生毕业论文用纸第1 0 页 的排样方式比较费时甚至不太可能。在这种大的搜索空间 中，寻找一种通用有效的算法完成各种排样方式的搜索和判 断较为困难。近年来，在优化领域中新近发展起来的遗传算 法等优化方法，为多变量、大空间、多峰值、多目标等优化 问题的解决提供了新的行之有效的途径。能否运用这些新方 法解决不规则、多样形的优化排样问题，显然值得研究探讨。 第二节几种常用的排样方法 当今社会是知识经济的时代，尤其是计算机的出现， 给社会带来了无穷的变化，随着计算机技术的迅猛发展，排 样在生产实际中为生产者带来的巨大效益越来越引起人们 的注意，人们在不断地开发着越来越有效的优化排样程序。 现阶段使用的方法主要有以下几种： 1 普通单排与对头双排 这两种方法常用于对于单一工件样形的排样，即在一 个给定的板料中放入尽可能多的同种工件。 普通单排：将零件图形以一定的步距角在o 。9 0 。的 范围旋转，每旋转一次，将两零件图形的区域按水平或垂直 方向靠近，得到单排时的水平或垂直布局。最后比较各种角 度下的材料利用率，取其中最高者作为最佳方案。 对头双排：在对头双排过程中，两个角度相差1 8 0 。的 相同零件以以下几个方向来考虑对排组合： ( 1 )第2 个零件从第1 个零件的左上方沿右 下方对排组合； ( 2 )第2 个零件从第1 个零件上方沿下方对 太原理工人学f l j f 究生毕业论史用纸 排组合： ( 3 ) 第2 个零件从第1 个零件的右上方沿左 下方对排组合： ( 4 ) 第2 个零件从第1 个零件的由变向左边 对排组合。 对于某类具体零件，事先不知道应沿哪个方向对排组 合，于是就按上述4 个方向分别进行组合，取其中利用率最 高者为最佳方式。将对排组合后的零件图形作为一个整体， 再将该对排整体按普通单排策略就可得到最后优化排样结 果。 2 矩形排样法 矩形件排样优化通常是指在长为l 和宽为w 给定的板 材上，尽可能多地排放所需要的矩形件，从而使得所需要的 板材尽可能地少，以达到节省材料的目的。对于非矩形件的 不规则装配件的排样下料问题，可以通过计算机的图形处理 技术转化为矩形件的下料问题。目前国外的一些学者就是采 用这样方法处理不规则装配件的排样问题的。矩形排样首先 将所排样形进行最小包围矩形转换，然后进行最优排放，等 排定之后，再恢复其原始图形。矩形的排放方式有多种，为 了使材料利用率达到最佳，应用每种方式试排，然后找出材 料利用率最高的排法作为最终结果。通常情况下，可以先用 一种方法试排，如满足要求，则以此为排样结果。否则，换 用另一种方法试排，直到结果令人满意为止。如果所有的方 法都已试用后所得的结果仍不理想，则选取其中利用率最高 的排样作为最终结果。 矩形排样一般按面积大小顺序排放，同时兼顾长宽相 太腺理t 人学州究生毕业论艾用纸第1 2 页 同的矩形在x 、y 两个方向上的排法变化。为使利用率更高， 可进行空余块的填塞。空余块是指最小包围矩形与实际样形 之间的差余。为简化起见，空余块的填充也用工件样形的最 小包围矩形按面积由小到大的顺序进行填塞。 但这样做排样速度慢，而且在样形较多时，寻找各种 排放方式比较困难。另外，这种做法的本身就有一定的缺陷。 因为，该方法将不规则排样零件用一个其面积最小的包络矩 形来替代，自动布局时只针对这些包络矩形进行，材料利用 率较难达到最优。假如两个工件可以很好的紧密结合，但是， 根据矩形优化法，首先需要将他们分别进行矩形包络，然后 才进行优化排样，这样就造成了本来可以紧密结合的部分却 不能结合，方法本身就造成了一定程度的不必要的浪费。具 体实例可见下图： 太原理1 ：人学训究生毕业论文用纸 第13 页 上图为矩形排样法的结果，下图为实际排样。 3 启发式搜索算法 启发式搜索法是将计算机的运算和人的直觉判断相结 合的一种寻优方法。它通过人机交互方式，由人对计算机的 排样结果进行选择和修改，以获得最优结果。通常，由计算 机根据所给出的样形参数，按照一定的排放规律将样形以一 定的方式排列，然后由人利用排样系统的图形平移、旋转等 功能对排好的方式进行人为的改变。计算机根据此排放方式 对目标函数进行计算，如果排放结果优于上一方式，则选取 此结果继续位置或方向上的变化以寻求更好的方式。这种方 法通过人的参与，使计算机免于考虑优化过程中的某一个参 数的变化( 如位置参数由人来控制，这时人可以根据经验或 直觉来改变各样形的位置) ，这样可以实现计算机和人的优 势互补，易于获得好的优化效果。 用启发式搜索法求得的结果并不一定是最优解，但在 一般生产实际中它能同时满足时间和效率等方面的要求，因 此比较实用。但该方法中由于有人的参与，排样结果必然受 人的素质和技术水平限制，且不利于通用程序编制。 4 遗传算法 g e n e t i ca l g o r i t h m ( g a ) 是由美国密西根大学的 太原理丁人学研究生毕业论文用纸 h o l l a n d 教授于1 9 7 5 年提出的一种随机优化算法。他是在 达尔文的优胜劣汰，适者生存理论的基础上，模拟生物遗传 过程中自然进化的优化过程而提出的。算法通过分离或结合 产生解空间中的最优特征来建立新的较好、较优良的解。遗 传算法使用大量的随机规则对那些很难用数学方法代替或 很难有效得到优化的问题产生最优解或次优解。 已经有越来越多的学者将其应用于各个领域的优化 问题。它已经做为一种较有效的方法，以其搜索空间大这一 优点在众多工程应用中为解决多变量、多目标、多峰值等约 束优化问题发挥了作用。 与传统的优化算法相比，遗传算法主要有以下几个不 同之处： ( 1 ) 遗传算法不是直接作用在参变量集上，而是利用参 变量集的某种编码； ( 2 ) 可同时搜索解空问多个点，而非一点。 ( 3 ) 遗传算法只需要一个性能指标，而不需其他可微、 连续等辅助信息。 ( 4 ) 采用生物中“物竞天演，适者生存”的原理，使算 法具有一定的自适应性。 遗传算法的一个突出特点就是能把注意力集中到搜索 空间中期望值最高的部分，这是遗传算法中交叉算子作用的 直接结果。交叉过程是模拟生物界中的有性繁殖，是遗传算 法中最重要的部分。很多遗传算法研究者都认为，如果从一 个遗传算法中去掉交叉算子，则不再是遗传算法；而对变异 算子则不这样看待。事实上，利用交叉算子是遗传算法区别 于其它所有优化算法的根本所在。某些优化算法，例如演化 太原理工大学州究生毕业论文用纸第1 5 页 规则，它也是模拟生物演化过程，与遗传算法相比，仅仅是 该算法中没有使用交叉算子。 但g a 在许多问题上的早熟( 即过早收敛于局部最优解 而非全局最优解) 始终未得到很好的解决，在将g a 应用于 优化排样时有时得不到最优解，即存在遗传欺骗问题。 除上述几种算法外，在计算机优化排样中，还有一些 其他排样的算法或方法。由于篇幅和课题范围所限，本文不 再一一列举。 太原理t = 人学研究生毕业论史用纸第1 6 页 第三章m e b m l 讨论 传统的排样方法凭借人工经验及技能采用模板试切的 方式来完成，受到人为因素和客观坏境的限制，远远不适合 大批量生产的要求。般优化算法是将优化布局问题转化为 数学方法来描述，利用位置约束关系，建立零件之间的弹性 势能函数，然后利用优化算法求弹性势能函数的极值，来确 定最优布局。这些方法只能求出一些零件之间的约束条件较 简单的布局问题，当物体形状和位置约束关系较为复杂时， 零件数量越多时，难以抽象出精确的数学模型来描述，同时 计算复杂度也会显著提高，因而不能完全满足实际需要。因 此需要寻求一种算法解决这一问题。 第一节m e b m l 概述 计划计算是解决复杂系统优化及机器学习等问题的有 效途径之一。已出现许多代表性方法，如遗传算法，遗传规划 和计划策略等，且在许多实际问题中得到了成功的应用。但 计划计算所出现的早熟及收敛过慢等问题虽然一直是该领 域的一个研究热点，仍未有大的进展。 m e b m l 是最近由我国孙承意教授提出的一种新型机器学 习方式，它借鉴了遗传算法的“群体”与“进化”概念，引 入了“趋同”与“异化”过程，在解决遗传算法求解时存在 早熟的优化问题时显示出了优越性。 太原理t 人学研究生毕业论义用纸 第1 7 页 其框架如图1 所示。 图1 下面简要概述一下m e b m l 思想与算法过程： 初始化群体： 在m e b m l 中，群体被划分为若干子群体，子群体 又有优胜与临时之分，优胜子群体用来保存叠代中性能较优 的子群体。在整个解空间均匀散布个体，对所有子群体进行 初始化。 趋同： 趋同是模拟人类思维进化的学习过程子群体内个体的 相互竞争遵循优胜劣汰，适者生存的原则。我们知道，在人类 太原理t 大学研究生毕业论史用纸第1 8 页 的一个局部子群体的进化过程中，劣者的生存概率很小。但， 优者则以较大的概率生存，闷时将产生较多子孙。如果模拟 此过程，在趋同的每一代，在优者( 即得分大于平均得分的个 体) 周围随机散布适当数量的个体从而构成新的一代群体， 这样既保证了适者生存的原则，又保证了子群体的多样性。 同时根据优者的优秀程度决定所散布个体的数量。上述思想 符合人类局部群体进化过程所呈现的性态，在优者周围要团 结一些个体，而随着进化的进一步进行，会在多个优者之间 相互转移，同时产生新的优胜者。 一个子群体在趋同过程中，若不再产生新的胜者，则 称该子群体已经成熟。子群体从诞生到成熟的期间叫做子群 体生命期。 子群体的替代与废弃( 全局竞争) ： 子群体之间进行全局竞争。在每次叠代中，若某临时子 群体得分超过任何个优胜子群体得分，且该优胜子群体成 熟，则该优胜子群体被得分较高的临时子群体替代；若某临 时子群体成熟，且得分低于任何一个优胜子群体得分，则其 被废弃。 异化： 异化是模拟人类思维进化过程中的创造行为。而人类的 创造行为是在总结和学习前人已有的知识和成果的基础上 的创造思维。 被废弃和被替代的子群体中的个体在整个解空间重新 散布。组成新的临时子群体重新参与趋同与全局竞争，这个 过程叫做异化。 一一 步的循环运行，便可对问题进行优化。 太原型丁人学研究生毕业论文用纸 第1 9 页 第二节趋同与异化策略 m e b m l 的趋同是模拟人类思维进化的学习过程。我们知 道，在遗传算法中模拟是群体特征的一个主要表现。若在趋 同过程中，能充分利用子群体优良群体的模式特征，以模式 信息来指导个体间的学习，势必是趋同操作的一种有效形 式。 异化是模拟人类思维进化过程中的创造行为。而人类的 创造性行为是在总结和学习前人已有知识和成果的基础上 的创造性思维。f 是基于该思想，产生了以下几种不同的异 化策略： 1 基于优化群体最大模式的异化策略： 异化操作是根据进化信息在解空间重新产生m r + t 个 临时子群体。而进化信息是由知识抽取系统依据各自群体进 化信息而产生的。 对于成熟子群体，将其优胜者纪录于全局公告板，形成 一个规模为n m ，一t 。的优胜群体，将该群体的最大模式作为 知识提取系统提取的进化信息，用于指导m r + t 个临时子群 体的产生。 异化策略可描述为：以优胜子群体的最大规模为参考， 在解空间中随机产生+ t 个个体作为优胜者( 要求新的优 胜者不能与优胜群体的个体相同) ，然后以每优胜者为中 心，服从正态分布产生规模不等的m ，+ t 。个临时子群体。各 临时子群体中进行趋同操作，参与局部竞争。 异化过程是在优胜群体最大规模指导下进行，避免了临 太强理丁大学研究生毕业论义用纸第2 0 负 时子群体产生的完全随机性。类似于人类的发明创造是在前 人知识的基础上进行，而又突破前人的工作。 2 单纯型异化策略： 假设优胜子群体为i q + 1 个，当n + 1 个优胜子群体均成熟 后，则其最好个体就形成一个单纯型。由于单纯型寻优法可 以由n + 1 个点产生一个更好的点，所以，可以n + 1 个点形成的 单纯型依据单纯型直接寻优法确定新的临时子群体的优胜 者，再以优胜者为中心，服从了f 态分布产生新的临时子群体。 当无法产生更好的个体时，认为达到最优，停止进化。 单纯型直接寻优法在理论上保证了其收敛性。在应用异 化过程时，由于单纯型点由局部最优点构成，则避免了陷入 局部最优点的危险性，从而保证了全局最优性与收敛性。 3 启发式异化策略： 趋同操作保证了在优胜者周围已进行了精细搜索，也就 是说，在优胜者周边产生更好个体的概率很小。或者说，若存 在更好个体，则在更大概率上存在于远离优胜者的区域。为 此，构造如下启发式异化策略： 1 ) 求出任意相邻两优胜个体的中心点，并删除与已有优 胜个体相近的个体； 2 ) 以中心个体为中心，服从正态分布产生若干个体； 3 ) 计算每一个体得分，找出最高得分个体，作为新i 临时 子群体的优胜者； 4 ) 以优胜者为中心，服从正态分布产生新的临时子群 体； 4 区域收缩异化策略： 基于启发式异化策略的基本思想。将以优胜者为中心的 太原理工人学研究生毕业论文用纸第2 1 页 小区域从可行域中割去，逐步缩小异化区域，以便在更小的 区域内寻找更好的个体。 区域收缩异化策略对于仅有上下限约束的一类全局优 化问题特别有效，能提高收敛与全局最优解的概率。 m e b m l 继承了g a 中“群体”与“进化”的精髓，从模拟人 类思维进化的角度出发，提出了不同于g a 操作的“趋同” 与“异化”操作。“趋同”是指子群体在局部区域互相学习，搜 索最优解，它增加了算法搜索的目的性。“异化”为算法在整 个解空间重新散布新的子群体，淘汰已成熟的子群体，以搜 索全局最优解，它避免了算法陷于局部优解不能自拔的情 况。“趋同”与“异化”的交替与结合，使得m e b m l 的性能除涵 盖g a 所能处理的问题外，又有重大扩展和创新，如：可处 理非数值问题，进行群体社会行为仿真等。 我们将这一章所述算法称为n e b m l 算法。 太原理工大学研究生毕业论文用纸第2 2 页 第四章优化排样程序的设计 优化排样所需要解决的问题是如何确定各样形的排放 位置和方向以获得最大的材料利用率。使用计算机进行优化 排样不仅可以减少下料工人的劳动强度，节省排样时间，更 重要的是使用计算机可以对大范围的搜索空间进行测试，从 而获得令人满意的排样结果。 计算机优化排样的过程应该充分体现操作简便、运算 准确、显示清晰、输出图形迅速方便等优点。在利用m e b m l 进行二维不规则图形的优化排样中，如何利用计算机程序来 实现排样的各个环节，如何使各个环节有机联接实现有效的 优化排样，是本课题研究的重点。 计算机优化排样大体上可分为三部分。一为图形输入 过程，主要完成所排样形的的图形输入。二为优化排样过程。 这一过程包含对图形信息的分析计算以及优化运算的各个 过程。三为图形输出部分，主要完成排样结果的图形输出以 及排样结果的一些具体参数的输出。 本章提出使用m e b m l 算法进行二维排样的实现方法，并 编制程序实现优化排样的全部过程。 第一节排样过程的简化 对于二维不规则图形的优化排样，由于工件形状复杂， 任意工件每变化一个角度，排样方式和结果都将发生变化， 太原理工大学 j 究生毕业论史用纸第2 3 页 所以对于工件任意角度旋转的变化都将产生排样方式数量 巨大的增长，因此搜索空间将呈现几何级数的增长，解空间 将发生爆炸性的扩充。因此使用任何一种算法在考虑到工件 的任意角度的变化的情况下的优化排样，都将是不太现实 的。同样对于使用e b d l 算法进行优化排样，也要考虑到此 种情况。为了在保证排样具有较好的结果的基础上又要尽量 缩短运算时间，在使用m e b m l 算法进行排样的程序设计中， 我们需要进行一系列的简化操作。 1 ) 工件旋转方向的简化 在矩形件优化排样中，样形的方向变化仅包含9 0 度方 向的旋转。在不规则形状的排样中，任一角度的旋转变化都 会引起排样方式的变化。但假如考虑连续的旋转，则会使搜 索空间成几何级数增长从而大得无法计算。为简化运算，在 程序设计中，仅旋转9 0 度。因为根据工件的输入顺序不同， 各工件之间相邻的方位也不同，所以旋转9 0 度就相当于将 旋转1 8 0 度，2 7 0 度的情况也包含了进去。这样，排样搜索 空间即可满足不规则形状的不对称性而引起的排放方式的 多样性，又使搜索空间不很复杂。这样的简化对于算法的运 算简化以及排样时间的缩短非常关键( 在计算机速度的不断 提高的情况下，以后可以将工件旋转的角度逐步缩小，以求 得工件排样更高的利用率) 。 2 ) 排样区域的简化 为便于计算机对图形和排样空间的识别，程序将排样 空间作进一步简化。排样空间由矩形网格构成。网格元素的 大小与图形网格大小相对应，即其大小也随排样所要求的精 度有所变化。这样，排样问题就简化为如下过程：一系列由 太原理丁大学研究生毕业论文用纸 第2 4 页 相同大小网格构成的图形在一个由同样大小网格构成的平 面内进行移动、旋转和排列。这一过程中，图形网格与排样 区域的网格保持对齐，各样形在排样过程中的移动步长与网 格边长一致，能在保证排样精度的情况下大幅度减少优化搜 索空间。 通过以上简化，二维图形的排样问题转换为确定图形 在排样区域上的位置以及排放方向以获得最小占用面积。这 样的简化使排放位置的变化步长与排样精度紧密联系起来， 而且使判断图形之问是否有搭边变得相当简单。在程序中判 断搭边时只需在各图形位置和方向确定之后对排样区域的 每一个网格进行扫描，确定各个网格上是否有超过一个的实 元存在。若存在，则表示图形之间有搭边。 第二节优化排样过程 在进行了上述过程的简化之后，就可以进行下一步对于 优化排样来说最为重要的步骤，即：算法在优化排样中的实 现。本节将详细讨论使用m e b m l 对于二维不规则工件图形排 样的实现过程及程序编制方法。 将m e b m l 应用于优化排样需如下几个步骤： 1 图形转换，即输入工件图形，并建立图形数据文件 2 进行图形编码 3 图形走步方式 4 图形搭边的判断 5 运用m e b m l 算法求解 6 得出结论 太j 泉理t 人学f j | _ 究生毕业论_ ! = 【= 用纸第2 5 页 下面就各个步骤进行详细讨论： 图形转换 计算机图形转换是利用计算机进行图形的自动转换。 该转换方法的图形信息可以通过多种方式输入计算机。例如 采用顶点信息来表示图形：也可以通过交互式图形输入方法 完成图形信息的输入：还可以利用计算机自动转换由现有计 算机绘图软件所产生的图形。 在计算机优化排样过程中，首先将所排工件图形信息 输入计算机，并进行图形转换并进行图形的编码，使图形信 息适应于所采用的优化算法。在不规则图形的优化排样中， 图形的边界信息较为复杂，与矩形等规则图形相比，每个样 形的输入所需的数据量大得多。为此应寻找一种较为简单的 方法，来表示图形。 计算机图形转换的方法因图形输入方法的不同而有所 差异。在计算机图形学中，人们在多边形转换、填充及剪裁 等方面己研究出了多种利用顶点及边界信息进行图形转换 的方法。计算机图形转换方法主要有边标志算法、种子填充 算法等多种方法，在此由于篇幅所限不一一列举，有关此类 方法可参阅计算机图形学的有关文献。 在使用m e b m l 算法进行不规则图形的优化排样中，对 图形的转换没有特殊的要求，下面介绍一下图形转换主要过 程： a 、首先，确定二维图形的最小包围矩形。最小包 围矩形的确定方法较为容易。一般先用水平线扫描 图形，找出两条图形的水平切线，再用垂线扫描图 形，找出两条图形的垂直切线。四条线相交便可形 太原理工大学研究生毕业论立用纸第2 6 页 成图形的最小包围矩形。 b 、 找出所有矩形中最长的一条边，以其为边作一 个正方形。在j 下方形上叠印由相同矩形元素构成的 网格，网格元素的最大个数n m a x 可根据问题或计 算需要精度自行确定。网格元索的大小对排样精度 以及排样所需时间有一定的影响，而且对这两个因 素的影响相反。网格越大，计算机扫描、记录图形 所需的时间就短，但排样过程中将样形中更多空白 部分当作实元来处理，势必使排样精度降低。反之， 运算时间增加。因此对于网格大小来说，运算时间 和排样精度是一对矛盾，在选择网格大小时应该权 衡这两个因素达到问题统一。 c 、 图形扫描。将所要排样的工件图形绘制在步骤 b 所描绘的正方形中，工件图形的颜色与正方形的 颜色不同，在水平方向及垂直方向上对每个网格进 行扫描，获取每一网格中心点的颜色，如果所取颜 色与工件图形的颜色相同，就意味着网格中全部或 部分包含图形实体，那么将该网格定义为实元，否 则定义为虚元。 d 、 数据存储。工件形状将由两个数组来表示，一 个数组存储x 方向的数据，另一个存储y 方向的数 据他们只是存放图形的轮廓的数据。在运算过程 中两组数据结合便可获得图形所占的区域。原点定 为与图形最近的x 方向及y 方向的两条网格线的交 点。下面举一具体实例： 太原理丁人学州究生毕业论史用纸第2 7 页 y 向 x 向 o ；， ；2 ；3 ；4 ；5 ，；l 网 ： l ，；! 。z ，； i i； ； x 方向：( 3 ，3 ) ( 2 ，4 ) ( 2 ，5 ) ( 2 ，5 ) ( 1 ，5 ) y 方向：( 5 ，5 ) ( 2 ，5 ) ( 1 ，5 ) ( 2 ，5 ) ( 3 ，5 ) 图形位置初始化 排样运算之前，要确定各工件样形在输入板料图形中 时首先要放置的位置，以便进行下一步的各工件的凑近过 程。下图为各工件的初始位置，每一个小正方形的大小为上 面图形转换步骤中b 所描绘的正方形大小。将图形的原点与 下图各位置中每一正方形的左上角顶点重合。图形初始位置 参数为图形原点与板料的左上角顶点的x 向、y 向距离。 太原理工大学研究生毕业论文用纸第2 8 页 l25 1 0 3461 1 7891 2 1 31 41 51 6 图形的走步 在优化过程中，因为工件是一件一件地输入板料图形 中的，每输入一个图形，此图形便以特定的走步方式向前面 放入且已经凑紧的图形靠近，直到图形搭边为止。走步时， 图形的位置参数x ( i ) ，y ( i ) 值按网格的边长大小不断递减或 递增。 图形搭边的判断： 在一定的图形区域内，对一个已经定位好的多边形，求 另一个多边形与它正好碰撞但不互相重叠的位置，称为 n f p ( n o f i t - p o l y g o n ) 问题。这个问题实质上是图形的求交 ( 即判断该图形是否与别的图形重叠) 和定位问题，零件图形 的求交和定位贯穿整个排样过程的始终，它们构成了自动排 样算法的技术问题。能否很好地解决这一问题，直接关系到 太原理丁人学 i 究生毕业论文用纸第2 9 页 排样结果的优劣，排样时间的长短以及排样自动化程度的高 低等。 经过深入研究，从纷繁复杂的二维图形中抽象出它们 的共性，本研究提出了“图形区域”的概念。二维零件在 板材上总是要占据一定的面积的，它反映在计算机屏幕上就 是二维图形要占据一定的图形区域。于是，在排样过程中， 一旦建立了零件的图形区域，求交和定位的过程就不再与图 形的具体元素( 直线段或圆弧) 有关，而通过判断图形区域 之间的几何关系，就可以快速地求交，有效地定位。为此， 本研究提出了一种“基于图形区域的动态定位法”。 工件图形在板料中所放的位置由横竖坐标确定，横竖 坐标和工件本身的图形参数数组共同作用可以得出板料中 某位置是否为实元( 即是否已被工件所占) ，假如某处已 被某一工件所占，则当另一工件运动到此时，根据他们的横 竖坐标和工件本身的图形参数数组便可判断出两工件相交， 后工件需要退后一步，从而避免了图形的搭边。 目标函数的确定 首先，根据所研究问题的具体情况构造目标函数。目 标函数代表优化过程所要达到的目标。通过运算结果与目标 函数的接近程度来判定优化结果的优劣。 目标函数是指在排样过程中用于判定优化结果的计算 式。在排样过程中，目标函数用图形面积与排样所占用面积 的比值来表示，由下式得出： 太燎理工大学叫究生毕业论艾用纸第3 0 页 n = 譬 z s ，：各工件图形的面积之和 s ：包围优化排样后所得图形的最小矩形的面 积 图形编码： 对若干工件进行优化排样，其排列方式的数目将非常巨 大，为了运用算法将其中最好的排列方式求出，首先需要一 个较好的图形编码方式，这将在很大程度上关系到后面的算 法应用的好坏，所谓图形编码就是对图形的所有排列方式逐 一进行编码，以便m e b m l 能对其进行识别，并从中找出最优 的排列方式。 具体编码方式如下所示： 每输入一个工件图形，我们依次按顺序给其一个l n 之间的编号，l 、2 、3 、以此类推，假设有9 种图形，则 各为l 、2 、3 、4 、5 、6 、7 、8 、9 号。编号后，各个工件图 形的代号在以后的运算中将不再发生变化。 由于程序是将一个个工件图形逐一放入板料图形中，每 放入一个工件，则此工件图形按特定方式向已有的图形凑 紧，当工件凑紧不再发生位置的变化时，放入下一个工件， 工件所走的路径依据前面图形己排好的样形而定，因此，工 件放入顺序不同，则排列方式不同。所以，所有的排列方式 数就是所有工件的全排列数( 这其中不包括图形的翻转) ， 每一种排列可由一个十进制数表示。我们的目的就是要利用 m e b m l 找出这所有排列中利用率最高的排列方式 太原理工大学研究生毕业论文用纸第3 1 页 设有9 种工件，则共有91 种排列方式( 这其中不包括 图形的翻转) 。本文用一个o 一91 之间的十进制数表示某种 特定的图形输入顺序，即一种排列方式。例如：3 就代表 下面这种排列方式： 对于任意散布的一个0 一n ! 之间的整数x ，它代表一 种排列方式，将其