（计算机系统结构专业论文）基于遗传算法的二维排样研究.pdf

r e s e a r c ho nt w o - - d i m e n s i o n a ln e s t i n g ba s e do nt h eg e n e t i ca l g o r i t h m c a n d i d a t e ：s o n gk a i s h e n g s u p e r v i s o r ：p r o f y a on i a n m i n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra r c h i t e c t u r e d a t eo fs u b m i s s i o n ：m a r c h ，2 010 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y j 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承起 作者( 签字) ：外h l j 望 日期：d d 年月“日 ， 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可回在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：环哥k 阻 导师( 签字) ：挑念民 日期：口d 年；月j 咽 o l d 年寻月心日 v 哈尔滨丁程大学硕士学位论文 i i i i r l i i i i i i i i i i i i i i i i i i 摘要 近年来我国制造行业飞速发展，钣金、制衣、玻璃、造纸等行业均涉及 到切割工艺。排样问题是在有限的原材料上寻求科学、有效的方法切割出更 多的零件。优化设计排样可以降低企业生产成本、提高企业核心竞争力、最 大化企业经济效益。 本文首先介绍了遗传算法的相关知识，核心思想是利用染色体具有遗传 进化的功能，通过交叉、变异、选择等操作，期间应用优胜劣汰法则，经过 几代进化，有可能产生优秀的个体。接下来介绍了遗传算法在排样问题上的 应用，染色体的编码设计、初始化种群、各种遗传算子和算法的终止条件等。 其次本文介绍了目前常用的排样启发式算法，有b l 算法、下台阶算法、 最低水平线算法和基于最低水平线的搜索算法。本文对这些算法进行了描述 和排样效果分析。文中接下来对最低水平线搜索算法进行了改进并引入阈值， 提出了新的搜索算法。算法通过搜索全部零件，择优录取实现更优。在择优 插入排放的时候，考虑两个矩形的长度或宽度之和与最低水平线的差值。 最后，本文引入协同进化的思想，对遗传算子进行了改进。根据排样方 式树状图，文章提出了一种全新的染色体编码方案。染色体基因的第一位是 树状图中第一层节点的数量，剩余的基因位表示每个节点包含零件的个数。 本文接着针对改进后的遗传算法引入搜索优化策略，提高了遗传算法的局部 寻优能力。最后本文根据改进的遗传算法设计出了一套排样优化系统。该系 统选取了有代表性的排样数据，经过测试证明其拥有良好的效果。 入 关键词：矩形排样；遗传算法；染色体；树 1 、 k 哈尔滨工程大学硕十学何论文 a b s t r a c t i nr e c e n ty e a r s ，t h ec h i n am a n u f a c t u r i n gi n d u s t r yh a sd e v e l o p e dr a p i d l y a n d 1 it h ei n d u s t r i e so fs h e e tm e t a l ，c l o t h i n g ，g l a s s ，p a p e r m a k i n ga n ds oo na r ei n v o l v e d i nc u t t i n gp r o c e s s t h ea i mo f n e s t i n gw h i c hi sb a s e do n t h el i m i t e dr a wm a t e r i a l s i sl o o k i n gf o rt e c h n i c a la n de f f e c t i v ew a y st oc u tm o r ep a r t s o p t i m a ld e s i g no f n e s t i n g c a l lr e d u c ep r o d u c t i o no fc o s ta n de n h a n c ec o r ec o m p e t i t i v e n e s so f e n t e r p r i s e st om a x i m i z ee c o n o m i ce f f i c i e n c yo fe n t e r p r i s e s f i r s t ，t h i sa r t i c l ei n t r o d u c e ss o m ek n o w l e d g eo fg a ( g e n e t i ca l g o r i t h m ) ，a n d t h ec o r ei d e ai st om a k eu s eo fag e n e t i ce v o l u t i o n a r yf u n c t i o no fc h r o m o s o m e s d u r i n gt h ea p p l i c a t i o no fs u r v i v a lo ft h ef i t t e s tr u l ea n da f t e rs e v e r a lg e n e r a t i o n s o fe v o l u t i o n ，t h e r em a yb ee x c e l l e n ti n d i v i d u a l s s e c o n d ，t h ea r t i c l ed e s c r i d e st h e g e n e t i ca l g o r i t h ma p p l i c a t i o no nn e s t i n g ，t h ec o d i n gd e s i g no fc h r o m o s o m e s ， i n i t i a l i z e dp o p u l a t i o na n dt h et e r m i n a t i o nc o n d i t i o no fa l lk i n d so ft h eg e n e t i c o p e r a t o r sa n da l g o r i t h ma n ds oo n a tp r e s e n t ，t h em o s tc o m m o n l yu s e dn e s t i n ga l g o r i t h m sa r eb la l g o r i t h m ，t h e n e x ts t e pa l g o r i t h m ，t h em i n i m u mh o r i z o n t a la l g o r i t h ma n ds e a r c h a l g o r i t h m b a s e do nt h el o w e s th o r i z o n t h i sa r t i c l ed e s c r i b e st h e s ea l g o r i t h ma n da n a l y s e s t h ee f f e c t i v e n e s sn e s t i n g n e x t ，t h em i n i m u mh o r i z o n t a lt e x ts e a r c ha l g o r i t h mh a s b e e ni m p r o v e da n dt h et h r e s h o l d sh a v eb e e ni n t r o d u c e d i tr a i s e san e ws e a r c h a l g o r i t h m t h ea l g o r i t h ma c h i e v e st h eb e t t e ro n e sb ys e a r c h i n ga l lt h ep a r t sa n d m e r i t b a s e da d m i s s i o n s c o n c e r n e dw i t ht h es e l e c t i o no ft h eb e s tt od i s c h a r g e ，t h e d i f f e r e n c eo ft h es u mo ft h el e n g t ho rw i d t ho ft h et w or e c t a n g l e sa n dam i n i m u m h o r i z o n t a ls h o l db et a k e ni n t oc o n s i d e r a t i o n a tl a s t ，t h ea r t i c l ei n t r o d u c e st h ei d e ao fc o e v o l u t i o na n di m p r o v e st h eg e n e t i c o p e r a t o r s a c c o r d i n gt ot h en e s t i n gt r e eu n d e rw a y ，t h ea r t i c l ed e s i g n san e w c h r o m o s o m ec o d i n gp r o g r a m t h ea m o u n to ft h ef i r s tc h r o m o s o m e si st h eo n eo f 、 k i 一、 哈尔滨工程大学硕十学位论文 目录 第1 章绪论”l 1 1 课题研究背景与意义1 1 2 排样问题分类3 1 3 矩形件排样问题的复杂性理论4 1 4 排样问题国内外研究动态5 1 5 本文主要工作与组织结构7 第2 章遗传算法简介及其在排样问题上的应用9 2 1 简介9 2 2 基本遗传算法的实现技术lo 2 3 基本遗传算法的研究进展13 2 4 遗传算法在矩形排样问题上的应用16 2 4 1 基因编码1 6 2 4 2 初始化种群l7 2 4 3 染色体的交叉1 7 2 4 4 染色体变异l8 2 4 5 适应度函数19 2 5 本章小结1 9 第3 章启发式排样算法2 0 3 1 启发式算法2 0 3 1 1 排样方式分类2 0 3 1 2b l 准则“2 1 3 1 3 下台阶准则2 2 3 1 4 最低水平线准则2 3 3 2 基于最低水平线的改进向后搜索算法2 4 3 3 拟人拟物与启发式算法相结合2 6 哈尔滨t 程大学硕十学位论文 3 4 协同进化策略2 9 3 5 遗传算子改进方案2 9 3 6 本章小结3 1 第4 章改进遗传算法解决矩形排样问题”3 2 4 1 剪切切割树状关系3 2 4 2 启发式策略3 4 4 3 基于树状关系的改进遗传算法“3 6 4 4 搜索优化策略4 2 4 5 本章小结”4 5 第5 章性能分析4 7 5 1 优化排样系统4 7 5 2 面向对象设计5 0 5 3 优化排样数据实验51 5 4 本章小结5 5 结论5 6 参考文献“5 8 攻读硕士学位期间发表的论文和取得的科研成果6 3 致谢“ 哈尔滨工程大学硕士学位论文 i m i l 第1 章绪论 1 1 课题研究背景与意义 中国入世以来，我国的大部分制造行业，特别是涉及到下料排料、切割 技术的企业都面临着很激烈的国内外市场竞争。在这样迅猛的商业氛围下， 如何去提升工厂的加工速率和减小工厂耗材的规模，这体现着企业的市场反 映决策能力以及维持长久生命力的象征。排样问题，是指在给定一个布局空 间和不确定数量待排物件，将待排物件科学的放置在布局空间中，同时满足 必要的约束条件，并使材料有效利用率达到最高 1 】。一种好的切割模式在现 实加工环境中不仅能够减少耗材还能适当提升加工速度，更显著的是直接巨 大的经济利益。任何一个加工型企业工厂，要想从技术上减少成本并提高利 润，就必须科学利用耗材，加工过程中用尽可能少的原材料规划设计出尽可 能多的产品，使废料最少，降低生产成本。排样问题有着极高的学术价值和 现实价值，一直受到国内外学者广泛的重视和研究，研究方法结合了计算几 何学、人工智能、组合优化等各种方法理论。本文研究的切割排样问题【2 】就 是根据生产中抽象出来的。国民经济迅猛发展的同时，排样问题的适用范围 也将越来越广阔。相似的问题如运输装配问题、箱堆问题、背包问题等都有 一些较好的算法【3 1 。近几年，在机械加工、皮革服装加工、汽车、造船、玻 璃、交通运输、航天航空、大规模集成电路板设计等领域，排样问题均被多 次研究重视。如何进行合理的、最优的下料排样成为国内外各学者争相研究 追求的热点问题。 计算机辅助排样，又称为c a n ( c o m p u t e r a i d e dn e s t i n g ) ，是广泛应用 的计算机辅助技术之一【4 1 。在现代加工工艺条件下，数控下料铣、数控裁剪 机、数控气割机、激光切割机、高速冲床等设备的应用领域很广泛，这些设 备显示了高效率、高精度的切割手段，价格昂贵，所以必须配合以高效科学 的排样方法。在某些行业中，如矩形板类的零件在汽车、客车的加工过程中 应用很广。所以，节约原材料能够降低整个行业的生产成本。计算机技术的 1 哈尔滨工程大学硕士学何论文 i 置i i i i i i i i i i i i i i i i i i i i i i i 置i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 鼍i l li n i i 迅猛发展，特别是c a d 技术应用领域越来越广泛，迫切要求一种能够适应 现代化大生产的优化排样系统，这种系统可以在相关行业发挥巨大的作用。 在以前的企业中，机械师通常是根据以往的经验，再根据现有的原材料和所 需的零件，近似的进行计算，然后手工制图进行下料。这样做不仅会造成大 量的原材浪费，同时需要的时间较长，而且浪费人力资源。极大地影响了生 产效率。在实际加工过程中，原材料的大小及形状有可能多样化，也可能品 种非常多，这就导致排样算法非常复杂。根据复杂度分析，排样问题属于 n p c o m p l e t e 组合优化问题，n p 完全问题 5 】。在现实生产工艺中，手工排样 不可能做到真正的优化，即使采用计算机辅助排样也必须配合相应高效的算 法，才能实现利用率相对较高的优化切割。 计算机辅助设计与制造 6 1 ( c o m p u t e ra i d e dd e s i g na n dm a n u f a c t u r i n g ，简 称c a d c a m ) 是计算机技术、电子信息技术与现代制造技术相结合的产物。 在工程和产品设计中，计算机可以帮助设计人员担负计算、信息存储和制图等 工作，如图1 1 所示。在设计中通常要用计算机对不同方案进行大量的计算、 分析和比较，然后再决定最优方案。对排样问题的重视可以尽可能的减少材料 耗费，降低生产成本。利用计算机的快速、准确运算可以使得排样结果尽可能 最优，时间较短。排样问题是c a d c a m 领域内重要的分支，进行计算机自 动排样系统的研发工作可以有效的推动我国计算机集成制造技术的发展。所以 对排样方法进一步研究并开发出使用方便的优化排样系统是一项非常有意义 的工作。 图1 1 系统结构图 2 哈尔滨工程大学硕士学伊论文 1 2 排样问题分类 1 一维排样问题 此类问题可以称作一维线材排样问题，是指在排样过程中只考虑一个方 向的尺寸【7 1 ，在空间上是一维的。例如，将较长的型材、管材等切割成所需 要的各个长度不一的零件型材，同时需要满足加工工艺条件和尽可能的切割 次数较少，这样从时间和耗费上都起到节省的目的。此类问题的应用主要在 钢管下料，包括门窗下料、金属样品、交通运输设备、电气机械等制造行业， 因为这些行业在加工过程中都需要将较长的型材切割成所需的型号长度。例 如，有m 种型号的原材料，长度和数量分别为厶和口，需要切割成n 种长度 为，；和数量为d ，的零件。如何分割截取是要合理解决的问题。 2 二维排样问题【8 1 此类问题称作板材排样问题，是指将二维平面的板材切割出各种所需形 状不一的零件。零件的形状可以是矩形、圆形、以及任何所需的特殊形状。 二维排样主要应用在木材加工业、金属加工、家具业、交通运输设备、普通 机械制造业等等。由于矩形的普遍化，不规则图形可以用矩形来包络解决， 所以矩形排样问题逐渐成为研究热点。 矩形排样问题通常是在比较大的矩形板材上进行排放布局数量大小不一 的小矩形零件。同时需要注意的是要尽可能保证在排放零件之后剩余的废料 最小，而且零件不能重叠，这样可以节省原材料，降低生产成本。例如在板 材r 上，需要排放1 1 个小矩形零件1 ，吃，吩，= i ，需要满足下列条件： ( 1 ) f ，尸，必须互不重叠，l i n ，1 j n 。 ( 2 ) r i 必须在r 边界以内。 ( 3 ) 加工上符合一定的工艺要求。 根据生产加工工艺的约束，矩形排样问题可以归类为以下2 个方面。 第一方面就是将给定的矩形零件在长度和宽度都固定的矩形板材上 进行布局排放，判断所需的矩形零件是否超过了板材的范围和如何排放能最 大化的利用板材，减少废料，降低成本。在实际生产过程中，有很多同样规 哈尔滨工程大学硕士学位论文 j ti f il i id lr a l l i 格的板材。需要解决的问题是所需的矩形零件都排放完毕之后，利用了多少 张板材，越少则越节省，这也是排样的目的。同时矩形排样也是不规则图形 排样的基础，采用对不规则图形的最小矩形包络，再对矩形进行排放布局， 这样就间接的实现了对不规则图形的排样。 第二方面就是待排零件的数量固定，板材的宽度固定，长度不固定。 问题转化为将所有待排零件排放完毕后所占用的板材的长度，称之为矩形带 排样。将板材看做是底部长度固定，高度无限的带状板材。将所有的待排矩 形零件排放完毕后，求出板材的最小占用高度，得出的高度越小，则排样效 果越好。例如纸张加工、金属切割等行业均使用上述模式。 两个方面在算法上有相同性，但是都没有找到多项式时间算法，所以只 能采用启发算法和智能算法进行解决。正是由于矩形件排样问题在实际应用 中的广泛性，使矩形件优化排样问题成为众多学者研究的热点。 1 3 矩形件排样问题的复杂性理论 大规模的矩形排样问题非常复杂，计算量上存在组合爆炸的情况，隶属 于n p 完全问题，是组合优化的一个典型应用。目前所有的算法都不能在多 项式时间内给出有效的解，理论上还没有突破排样问题。在算法的复杂度分 析上，问题难度依次递增顺序为p 类、n p 类和n p c 类。n 表示非确定性，p 表示多项式算法，c 表示完全。p 类问题是指具有多项式时间求解算法的问 题类。衡量一个算法的时间复杂度往往用渐进复杂度p 】，将算法所需要的时 间抽象成一个函数f ( n ) ，其中n 表示输入规模，当n 渐进无穷大的时候， 用f ( n ) 表示算法的复杂度。换言之，需要了解的是随着输入规模n 的增加， f ( n ) 的增长速度。一般来说，能够在多项式时间内解决的问题，称这个问 题是能够有效解决的。有这样一个例子，对m 个矩形零件进行排样优化布局， m 个矩形的排列顺序数是m ! 。每个矩形都有2 个方向，横放和竖放，也就是 2 ”。所以解空间就是2 ”m ! 。对于其中某些矩形的长度和宽度相等，横放和 竖放是一样的情况，造成解空间有可能小于2 ”m ! 。当m 的数值比较大的时 4 哈尔滨t 程大学硕士学位论文 候，解空间也随之急速变大，解空间爆炸式的增长，所以一般的排样算法很 难在人们接受的时间之内寻找到最优解。例如当m = 4 0 的时候，对4 0 个零件 进行排样时，解空间的规模为2 4 0 x 4 0 1 ，这是非常巨大的。穷举法很难遍历所 有解空间，当m 的值更大的时候，这种问题就是n p 完全问题。n p 完全问 题是n p 类中最难的问题，目前的科学水平，n p 完全问题不可能在多项式时 间内寻得最优解，目前对其解决方案主要有2 个方面：第一方面是力求在多 项式时间内寻找具有精确解，第二方面是确定某些规则，使用启发式算法【lo 】。 第一方面有理论指导意义，第二方面在实践中利用比较多。目前，启发式算 法的应用比较广泛，而且在大部分领域都取得了不错的效果。启发式算法首 先是舍弃了寻求最优解的理念，定义了某些规则之后，将解空间适当缩小， 采用适当的算法，对结果进行统计分析，这样解决问题的时间复杂度和空间 复杂度就取决于选取的算法。排样算法的研究至关重要。当m 的值比较小的 时候，一些算法能在较短的时间内求出最优解，但是在实际的生产加工过程 中，m 的取值有时比较大，所以人们目前主要研究通过启发式算法来应对大 规模排样优化问题，主要是权衡时间和排样效果来寻找人们可接受的算法。 1 4 排样问题国内外研究动态 排样问题历史悠久，1 8 3 1 年高斯首次提出了排样的概念。但是由于诸多 原因，例如大规模排样的理论复杂性，理论与生产实践不能良好结合，生产 成本等。迄今为止，科学家们还没有发现非常有效的通用性强的排样算法。 但是经过人们孜孜不倦的追求，对于一般的排样问题，人们在理论上有了一 定的突破并且这些成果也被应用到了实践当中。国外学术者对排样问题关注 的比较早，早在2 0 世纪5 0 年代就有国外学者对排样问题进行了研究，但是 所研究提出的一些算法在生产实践中存在着许多问题】【1 2 】 13 1 。例如成本过大， 时间不能接受等等。人们最早关注的是一维排样问题，在1 9 3 9 年国外学者 k a n t o r o v i c h 针对管材切割，维排样问题给出了简单的数学模型【14 1 。根据不 同一维问题的数量规模性，所要切割零件的复杂性，相应的给予变化，取得 哈尔滨工稃大学硕十学何论文 了一定的成绩。一维排样较为简单，且最优化的结果主要来自于建立的数学 模型是否符合实际和是否科学性。从某些方面解决了一维排样问题，给二维 排样问题奠定了一个良好的基础。一维排样问题的数学模型一般情况下是一 个整数规划问题【1 5 】。用分割平面法和分支定界法解决。后来，人们向二维排 样问题发起了研究【1 6 j ，二维排样主要是针对于矩形排样【1 7 1 8 】，许多人提出了 自己的想法。主要有线性规划( l p ) 、动态规划( d p ) 、启发式算法( h a ) 以及人工智能( a i ) 等方、法【1 9 】【2 0 】【2 1 1 。在1 9 8 5 年，国外学者b e a s l e y 给出了0 1 整数规划方法解决矩形排样问题【2 2 1 ，配合以拉格朗日算法得出最优解的上届 区间，但是由于时间复杂度的存在，这种算法只能对1o 种不同的零件进行 切割。否则复杂度急剧上升，时间非人们能够接受。后来，国外学者g i l m o r e ， g o m o r y 等人针对生产实践中的切割模式进行研究，给出了多级切割模式的 概念【2 3 】。每次切割都是从板材的一边垂直到另一边，第一级表示第一次切割 方向，第二级垂直于第一次切割的方向，当第一次切割的方向确定以后，以 后每个级别的方向就都确定了。采用多级切割模式并结合动态规划解决排样 问题，应用最多的就是2 级切割和3 级切割。如果选取的级数过多，则计算 量也随之增大。h i f i 针对两级和三级模式的无约束问题提出了两个精确的算 法 2 4 】，他根据g i l m o r e 和g o m o r y 提出的切割级别方式【2 5 1 ，将切割模式与动 态规划相结合，主要是利用三级三种切割方向来解决矩形排样问题。后来， 国外学者利用两分法切割模式，两分法是隶属于三级切割模式，并且是两级 模式的扩展集【2 6 1 。国内学者崔耀东利用动态规划方法较好的解决了单一排样 问题【2 7 1 。 9 0 年代后期，随着智能优化算法的理论研究，如遗传算法f 2 8 】 2 9 j ( g e n e t i c a l g o r i t h m ，g a ) 、禁忌搜索( t u b as e a r c h ，t s ) 模拟退火算法( s i m u l a t e d a n n e a l i n g ，s a ) 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、蚁群 算法( a n ta l g o r i t h m ，a a ) 、粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ， p s o ) 等算法的日益发展【3 0 】。有些学者开始利用智能算法解决排样问题【3 l 】， 也利用智能算法与启发式算法相结合解决排样问题【3 2 】。将遗传算法和近似算 6 哈尔滨丁程大学硕士学位论文 法相结合，提出了一种比较有效的排样方法。利用模拟退火和神经网络相结 合将排样问题进行两步优化【3 3 】，取得了一定的效果。因为遗传算法在解决复 杂问题时具有独特的优越性，成为近几年的研究热点【3 4 1 ，并多次广泛的应用 在组合优化的问题上。国外学者将几种智能算法分别做实验进行比较，主要 有遗传算法、模拟退火、进化算法、爬山算法等，将他们分别与b l 算法相 结合【3 5 1 ，对排样效果图进行比较分析，得出结论，利用这些智能算法得出的 排样效果明显优于传统随机搜索算法，其中，b l 算法与模拟退火相结合得到 的排样效果最优。后来有人用改进的遗传算法，对异形件排样问题给予分析， 利用矩形外包络【3 6 】，对不规则图形进行最小化矩形包络，即最小面积矩形包 含住异形件。结合遗传算法【3 7 1 ，在交叉过程中采用多点交叉，可以尽量的避 免局部最优解，取得了很好的排样效果。 1 5 本文主要工作与组织结构 矩形排样广泛应用于众多行业，因此对其算法进行研究具有重要意义。 本文主要是对矩形排样问题展开研究，为了简化问题的复杂度和符合生产实 践的可行性，本文规定以板宽优先，板材底部的数量级不变，所排放的零件 在板材上占用的最小高度来决定排样效果的优劣。本文采用启发式算法与智 能算法相结合进行对矩形排样问题的求解，在对目前出现的常用启发式算法 进行分析归纳之后，改进了最低水平线搜索算法。对最低水平线的搜索方式 做了调整，引入阈值，搜索时注意2 个矩形边之和与最低水平线的差异。对 遗传算法的遗传算子进行了改进，引入协同进化遗传算法的思想，采用多种 编码方案。基于排样效果的树状关系图，构造出一种全新的染色体方案，染 色体的基因位设置为树状关系图中第一层节点的数量和每个节点所包含的零 件个数。本文对新提出的染色体方案给出了相应的交叉算子、变异算子。用 改进后的遗传算法解决矩形排样问题。接着本文引入搜索优化策略，通过搜 索优化，提高遗传算法的局部寻优能力。 本文的组织结构如下： 7 哈尔滨丁程大学硕十学位论文 第l 章是绪论，简单介绍了课题研究背景与意义、矩形排样问题的复杂 度、国内外研究进展、矩形件排样概述等。 第2 章是遗传算法，本章对遗传算法的概念、历史背景、研究进展等做 了简单的介绍，接着描述了遗传算法的各种参数。本章详细的讲解了遗传算 法在矩形排样问题上的应用，编码设计、初始化种群、选择、交叉、变异操 作和遗传算法的终止条件等。 第3 章是启发式排样算法。本章首先分析了现有的几种经典排样方案， 介绍了b l 算法、下台阶算法、最低水平线算法、最低水平线搜索算法。对 这几种算法的流程和效果进行了分析。其次本章在最低水平线搜索算法的基 础上，对其做了改进，提出了新的搜索方式，引入阈值的概念，在人们能够 接受的废料情况下进行搜索，在对后续待排矩形的搜索过程中，注意两个矩 形的边距之和与最低水平线的差值。 第4 章是改进遗传算法，本章首先分析了切割模式，根据启发式策略得 出排样模式的树状关系图，对树图的层次做了限制，规定只做四级切割，给 出了子矩形、控制节点的概念。本章其次对遗传算法进行了多方面的改进， 引入协同进化的思想，采用多种编码模式，提出了一种新的染色体方案，该 染色体表示树状图中第一层节点的数目和每个节点内包含零件的个数。对新 提出的染色体本章给出了相适应的交叉、变异操作。使用改进后的遗传算法 解决排样问题。最后本章将上述遗传算法加入搜索寻优策略，提高了遗传算 法的局部寻优能力。 第5 章是性能分析，针对第4 章提出的改进遗传算法，本章详细分析了 该方案的可行性、软件系统流程、列取多种参考数据、求出排样效果，比较 令人满意，从而证明了该方案具有较好的排样效果。 最后是结论部分，对全文做了总结和展望。 哈尔滨工稗大学硕士学何论文 第2 章遗传算法简介及其在排样问题上的应用 遗传算法是智能算法的一种，对于复杂度较高的问题，用传统的优化方 法不能成功的解决时，常常需要使用智能算法来解决。或者用智能算法与其 它算法相结合来解决复杂问题。 2 1 简介 遗传算澍3 8 】【3 9 3 是对自然环境中生物遗传进化的一种近似模拟，模拟达尔 文的自然淘汰仿生优化，采用物竞天择，适者生存的策略。进化中不适合的 一代将被淘汰。这种算法是自适应全局的概率搜索算法。美国m i c h i g a n 大学 的j h o l l a n d ( 删教授于1 9 7 5 年提出遗传算法的概念和基本理论。它是一种在 思想上和方法上都具有较新特色的搜索优化方法。遗传算法问世之初，由于 当时计算机技术的限制，内存小、计算速度慢，而遗传算法需要存储的信息 量比较大，所以没有得到广泛的应用。经过多番努力，众多科学家对遗传算 法进行了多方面的改进优化。目前遗传算法在众多科学领域都有广泛的应用， 如计算机科学、物理化学实验、社会科学研究、组合优化、建筑工程、图象 识别处理、商业模式管理、生产调度优化等。遗传算法是对现实生活中物种 的进化过程进行分析模拟，自然界生物的染色体有交叉、变异、选择等几个 过程。遗传算法对这几个过程进行仿真，来寻求所应用问题的最优解，或者 是在可接受时间内的次优解。在搜索过程中，由于对遗传进化各个因素的模 仿，所以遗传算法具有很强的全局搜索能力。同时，它还具有自组织、自适 应、自学习等特征和很强的通用性、鲁棒性、全局搜索性等众多优点。所以 近几年来遗传算法的发展很快，应用范围也很广。当然遗传算法也有很多缺 点，例如，大规模的计算需要的时间较长，适应度函数的选取直接影响着算 法结果，在进化过程中容易出现早熟现象，局部寻优能力不强等。这些缺点 经过科学家的改进，在针对不同的应用环境时进行调整，遗传算法还是非常 有应用价值的。遗传算法有着明确的现实生活应用背景、新潮的方法理念、 9 哈尔滨t 程大学硕七学位论文 特殊的分析方法和以往的成功应用实例，遗传算法也逐步成为近几年各国科 学家争相研究的热点 4 1 儿4 2 】【4 3 1 。遗传算法基本流程如图2 1 所示： 图2 1 遗传算法基本流程图 2 2 基本遗传算法的实现技术 遗传算法的出现主要是学术家们受到自然界的启发。核心思想就是借鉴 自然界的优胜劣汰法则，将所研究的问题与遗传算法的参数进化模拟，再运 用生物淘汰法则，对所应用的问题进行优化。具体过程就是利用遗传算法的 染色体具有遗传进化的功能，对染色体进行交叉、变异、选择等遗传操作， 期间应用法则，那么比较优秀的染色体就能够更多的产生下一代。这样经过 几代的遗传进化，有可能保留下来较优的个体，那么就能够在人们接受的范 围内解决某类问题。需要注意的是，针对某类问题，遗传算法不能够依靠所 研究问题本身的参数，而是将所研究问题与遗传算法的空间相对应，将问题 的参数模拟成遗传算法中的编码，编码有十进制和二进制等。遗传算法的遗 传操作均是通过编码实现的，由于遗传算法进化操作的特殊性，所以遗传算 1 0 哈尔滨丁程大学硕士学位论文 法有优秀的自优化结构、自适应环境能力和自学习模拟性。针对某类问题， 进行编码映射工作，设计科学实用性的编码，然后设计优秀的适应度函数和 相应的染色体的交叉、变异、选择进化操作，确定初始化种群的数量，就可 以利用遗传算法对问题进行遗传进化操作来求解。搜索的范围是在种群的范 围内，也可以利用多种群来进行遗传进化操作。一般将种群分成2 个部分， 可视为2 个并行的种群，对每个种群进行各自的遗传进化操作，在进化过程 中，互相交互信息，这样操作在某种程度上扩大了搜索空间，可以增大寻找 最优解的概率。这里需要注意的是，在选取适应度函数的时候，选取的规则 是简洁、有效、科学性高、能够直接反映解的优劣，能够直接映射到所求解 问题的解空间。适应度函数是对染色体进行评价的唯一标准，对遗传进化操 作的过程有着指导作用，直接影响所得出解的有效性和质量。综上所述，遗 传算法是一种特殊的人工智能算法，与传统的优化搜索过程有着本质的区别。 一般情况下，基本的遗传算法操作( s i m p l eg e n e t i ca l g o r i t h m ，s g a ) 以及参数可以定义为以下公式】： s g a = ( c ，f ，r ，n ，只，己，t ) c 编码：确定一个问题需要利用遗传算法进化优化求解后，第一步就是设 计良好的编码。编码是遗传算法第一个重要的参数，遗传算法是利用遗传进 化和淘汰法则来进行优化，不能依靠问题本身的系数，而是需要设计一个能 够反映所求解问题系数的编码。将所求问题的解用基因编码表示或者能够用 编码间接得出。要求编码的设计简洁明了，与问题的解能够对应。这样才能 对基因编码进行遗传操作从而求解。设计好编码就相当于所求解问题的解范 围空间映射到了遗传算法的遗传搜索空间。与编码相对应的工作就是解码， 解码就是将先前设计好的基因编码还原成所求解问题的解。编码设计的优劣 直接影响遗传操作过程，对算法的性能和所得出解的质量有着直接作用。目 前常用的编码主要有：二进制编码、浮点数编码和符号编码。 厂适应度函数：设计好编码之后，需要构造一个优秀的适应度函数。适应 度函数是用一个函数来评价个体的质量，间接的评价了此次遗传操作得出的 哈尔滨t 程大学硕士学位论文 i i 解的质量。使用适应度函数来计算某个体得出的值称作适应度。一般情况下， 适应度的值越大，则说明此个体较优秀，此次遗传操作得出的解较优。适应 度函数的设计至关重要，它是唯一直接反映个体的优劣情况，这关系到解的 质量。一个较科学的适应度函数可以提高算法的收敛速度和性能，降低时间 复杂度和空间复杂度。一般的遗传操作设计都是适应度的值越大，则此个体 就有更大的概率存活进化到下一代。 只初始化种群：选取适应度函数之后，需要初始化种群，进行解空间的 初始化。初始化种群的概念就是根据某种原则得出的一组解，一般情况下是 随机产生，也可以根据人们先前解决问题时得出的某些经验来人为构造一组 解，一般初始化种群包含最优解的概率越大，接下来的遗传进化工作中得出 最优解的概率就越大。 n 种群的大小：初始化种群的同时，需要确定种群的规模大小，初始化 种群中包含的个体的数量为种群的规模。一般情况下，如果种群规模选取的 过大，接下来的遗传操作过程就较复杂，需要更多的进化操作，进化时间过 长。如果种群的规模选取过小，会导致初始种群中的个体种类不宽泛，过于 单一化，不利于进行遗传操作，增加寻求最优解的难度。 进化选择操作：选择操作又称作复制操作。选择操作是选择一些个体 将其设置为有进行下一代遗传的功能。一般情况下，选择的基本准则就是优 胜劣汰的法则，将具有较优适应度的个体选择出来，选择之后可以让较优秀 的个体以更大的概率进化到下一代当中。目前，应用比较广泛的选择准则就 是比例选择法，也称作轮盘选择法。这种方法的基本思想是根据适应度的大 小比例来决定每个个体的生存概率，一条染色体的生存概率与它的适应度成 正比。由于遗传操作的特殊性，优秀的染色体可能会被相应的交叉、变异操 作所破坏，不利于寻求最优解。所以有人提出了一种最优个体的保留法。在 遗传进化过程中，人们预先设计好一条评价准则，如果某条染色体达到了这 个准则，则这条染色体直接进化到下一代，不进行交叉、变异。这种方法在 某种程度上加大了寻求最优解的概率。 哈尔滨工程大学硕二卜学何论文 i ii 一一一_ ir i i i p 进化交叉操作：交叉算子方案的提出是来自于自然界的染色体相交叉 繁殖出下一代的基本思想。自然界的遗传进化过程中，有两条染色体的d n a 基因部分根据某种原则进行交叉断裂，然后又重新组合产生了新的染色体。 在遗传算法中，两条染色体也是进行同样的操作来产生新个体。目前，人们 比较常用的方法有单点交叉，多点交叉等。交叉算子的设计很重要，好的交 叉准则能够增加解的多样性，扩大遗传空间。两条染色体根据交叉准则相互 交换部分基因位。交叉算子的选取要与编码相适应，主要是要求良好的编码 方案便于交叉操作，产生新染色体的编码依旧合法。交叉概率一般取0 4 o 9 9 。 只进化变异操作：自然界生物在进化过程中，会出现突变现象，科学解 释就是d n a 的某些基因位的变化所导致。这种情况的出现概率相对较小， 但的确存在。在遗传算法中也引入了这种思想，对染色体的某些基因位以极 小的概率给予变化，变化之后产生了新的染色体。变异和交叉操作都是产生 新个体的方法，但变异的发生概率较小。变异算子体现了遗传算法的局部搜 索能力。变异概率的大小设计很重要，太大则会破坏种群的优秀质量，太小 则容易出现早熟现象。变异概率一般取0 0 0 0 1 0 1 。 t 遗传算法终止条件：遗传算法开始求解问题，一代代的进化，这就需 要一个终止条件。对于n p 问题，一般情况下不能够寻求到最优解。首先根 据解的质量来判断是否终止进化。可以预先选取一个评判值，如果适应度的 值达到这个评判值，终止进化。其次也可以设置固定的进化代数，一般为 5 0 0 1 0 0 0 代。另外，在连续几次的进化中，染色体的适应度没有明显的改善。 则终止进化。然后进行解码，求出问题的解。 2 3 基本遗传算法的研究进展 遗传算法诞生至今，针对于遗传算法的特殊性，国内外学者对遗传算法 做了各方面的改进优化f 4 5 】【4 6 1 4 7 】【4 8 3 ，遗传算法对许多典型组合优化问题已进行 过成功的求解。理论上已经证明，改进遗传算法最终能够收敛于全局最优解， 哈尔滨 二程大学硕士学位论文 但收敛到最优解所需要的时间可能较长。目前主要有以下几种改进后的遗传 算法： ( 1 ) 分层遗传算法 随机生成n 个子种群，子种群进行各自的遗传进化操作。运行一定代数 后，将n 个结果保存到数组中，然后对数组进行选择操作，交叉操作中选择 的交叉点也应