（计算数学专业论文）基于遗传模拟退火算法的二维不规则多边形排样问题.pdf

西北工业大学硕士毕业论文 摘要 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上， 找出零件的最优排布，使得给定材料的利用率最高，以达到节约材料，提高效益的 目的。从数学计算复杂性理论看，二维不规则样件的排样问题在理论上属于n p 完全 问题，因为存在实际形状的复杂性和计算上的复杂性，求解十分困难。传统的排样 工作都是人工依靠经验进行的，时间长并且效果不理想。由于生产实际的需要，人 们迫切需要利用现代科技来解决这一问题。目前研究较多的是规则零件( 如矩形) 的 排样问题，对不规则件的研究较少。 本文系统介绍了一种在基于遗传模拟退火算法的前提下，对不规则零件进行直 接处理的方法，该方法在通过遗传算法模拟退火算法在空间上搜索优化的排布样件 序列。对于每一个待排序列应用启发式定位算法确定其布局，并根据个体适应度评 价函数对其布局进行评价，保证在进化过程中良好的排布序列可以保存下来。 在分析现有的不规则多边形启发式定位算法的基础之上，本文提出了一种基于 平行梯形分割的启发式定位算法，该方法能直接实现不规则多边形的精确定位，并 且具有很好的运算效率，这些优越的性能是现有方法所不具有的；对于遗传模拟退 火算法，本文根据实际的问题需要确定了染色体的编码方式及相关参数，给出了具 体的个体适应度评价函数。 本文提出的理论和方法应用到了为x x 公司开发的仓库时空优化系统上，项目应 用表明该方法满足了实际工程的需要，具有良好的排样效果和实用价值。 关键词；不规则样件，排样，启发式算法，遗传模拟退火算法 a b s t r a c t a b s t r a c t t h ea i mo ft h ec o m p u t e ra i d e do p t i m a ll a y o u to ft h ep a r t sw i t hd i f f e r e n ts h a p e si st o f i n dt h ea r r a n g e m e n to fp a r t sa n dp r o d u c i n gt h el e a s tw a s t e t h ep r o b l e mo fo p t i m a l l a y o u tb e l o n g st ot h en l - c o m p l e t ep r o b l e mw i t ht i p t o pc a l c u l a t ec o m p l e x i t y i ti sv e r y d i f f i c u l tt of i n dt h eo p t i m a ls o l u t i o nf o rs u c hap r o b l e mb e c a u s eo f t h eh i g hc o m p l e x i t yo f s h a p e sa n dc o m p u t a t i o n c o n v e n t i o n a ll a y o u tw o r k sa l la d o p tm a n u a lo p e r a t i o nt h a th a v e m a n ys h o r t c o m i n g ss u c ha sl o wy i e l d ，i n e f f i c i e n ta n dl o n gt i m ec o n s u m i n g p e o p l ec r y f o ras o l u t i o nb yt h em o d e ms c i e n c ea n dt e c h n o l o g yb e c a u s eo ft h en e e do fp r o d u c t i o n m o s to ft h ep a p e r sp u b l i s h e di n t h i s f i e l da r ec o n c e r n e dw i t ht h ep a c k i n gp r o b l e mo f r e g u l a rs h a p e s ( s u c ha sr e c t a n g l e ) ，o n l yaf e wa r ea b o u tt h ei r r e g u l a rs h a p e s am e t h o df o rd i s p o s i n gt h ei r r e g u l a rs h a p e sd i r e c t l yi sd e v e l o p e db a s e do ng e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h m ，w h i c hs e a r c ho p t i m a ls h a p es e q u e n c ei nt h es p a c e 。t h e l a y o u to f e a c hs e q u e n c ei sf i x e db yh e u r i s t i cl o c a t i o na l g o r i t h m ，a n dt h e ne v a l u a t e si tb y f i t n e s se v a l u a t i o nf u n c t i o n , t oe n s u r et h eg o o ds e q u e n c ec a n b ep r e s e r v e di nt h e e v o l u t i o n a r yp r o c e s s i na n a l y z i n gt h ee x i a i n gl o c a t i o na l g o r i t h m sf o ri r r e g u l a rp o l y g o n , t h i sp a p e rp r e s e n t s an e wh e u r i s t i ca l g o r i t h mb a s e do np a r a l l e lt r a p e z i u md e c o m p o s i t i o n t h i sm e t h o dc a n d i r e c t l yd e t e r m i n et h ep r e c i s e l o c a t i o no ft h ei r r e g u l a rp o l y g o n ，a n dh a v eg o o d o p e r a t i o n a le f f i c i e n c y t h e s ee x c e l l e n tp e r f o r m a n c e sa r et h a tt h ee x i s t i n gm e t h o d sd on o t h a v e f o rg e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h m ，t h i sp a p e rc o n f i r m st h ec h r o m o s o m e c o d i n ga n dt h ep a r a m e t e r sa c c o r d i n gt ot h ea c t u a lp r o b l e m s t h es p e c i f i ci n d i v i d u a l f i t n e s se v a l u a t i o nf u n c t i o na l s oi sg i v e n t h i st h e o r ya n dm e t h o dw e r ea p p l i e dt ot h ed e v e l o p m e n to f as y s t e mf o rx xc o m p a n y t h ea c t u a la p p l i c a t i o ns h o w st h a tt h i sm e t h o dm e e t st h en e e d so ft h ep r o j e c t ，a n dh a s g o o dl a y o u tr e s u l t sa n dp r a c t i c a lv a l u e k e y w o r d s ：i r r e g u l a rs h a p e s ，o p t i m a ll a y o u t ，h e u r i s t i ca l g o r i t h m ，g e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h m i i 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的知 识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构遴交论文的复印件和电 子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时本人保证毕 业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学。 保密论文待解密后适用本声明。 指导教师签名： 御年； 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的学位论文，是本人 在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容和致 谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果，不包 含本人或其他已申请学位或其他用途使用过的成果。对本文的研究做出重要贡献的个人和 集体均己在文中以明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的 学位论文作者签名： 卅年弓聃日 西北工业大学硕士毕业论文 1 1 引言 第一章绪论 随着全球对资源消耗问题的日益重视及降低消耗也是环境问题治本措施等新观 念的出现，制造系统资源优化利用的研究己愈来愈重要。随着社会生产力的不断提 高，生产规模越来越大，先进的机器生产代替了人工操作，排样问题在很多行业产 生了迫切的需要，如服装、木材、玻璃、金属板、纸业等行业。 计算机辅助优化排样就是寻求某种优化的布局方式，使平面区域的材料面积利 用率较高。许多工业问题如卷材、玻璃、印刷业等的切割，服装、皮革等的剪裁， 货物装箱等均属此类排样问题，是典型的组合优化问题，具有很高的计算复杂性。 因此对规模较大的排样问题，不但手工排样不可能做到真正的优化，即使采用计算 机辅助排样也必须开发高效的算法才能实现利用率相对较高的优化排样和切割。 在国民经济许多行业中，都会遇到材料分割问题。计算机辅助优化排样的作用， 就是生成高利用率的材料分割排样方案，因此，凡是需要进行材料分割的行业，都 可以应用计算机辅助优化排样，达到提高生产率、节约材料、降低成本的目的。 此外，一些仓库货物的摆放问题也可以简化为优化排样问题，在仓库的货物自 动排放系统方面优化排样问题也有着广泛的应用前景。 1 2 排样问题的研究背景和意义 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上， 找出零件的最优排布，使得给定材料的利用率最高，以达到节约材料，提高效益的 目的。排样问题广泛应用在机械制造、轻工、服装和印刷业排版等行业中。由于材 料费用在产品成本中占很大比例，还有一些行业，材料非常昂贵，如汽车制造业， 所采用的是比较昂贵的薄钢板。因此材料的节约对于降低整个行业的制造成本有重 要的影响，特别是在大批量生产中材料利用率的提高可以带来显著的经济效益 但是，在很多企业，仍然是在没有排样图的情况下进行人工排样，排样技术人 员仅仅凭借自己的经验自由地在材料上排样，一般排出来的并不是最优的方案，并 且材料浪费很多；有些企业，即使有排样图，但是一方面排样图是人工绘制，费时 费力，效率低下，另一方面也不能做到最优化排样，材料利用率仍然不高。 第一章绪论 计算机和计算机辅助技术的应用和发展，大大提高了工作效率和质量，使得许 多人工难以完成的工作成为可能。上世纪四十年代以来，人们便尝试着提出各种理 论，设计不同的计算方法来解决计算机辅助优化排样问题。优化排样问题实际上是 一个十分困难的问题，从数学计算复杂性理论看，它属于n p 完全问题，也就是说在 一般情况下，即使是使用很快的计算机，在人们可以接受的时间内也不太可能求出 这类问题的最优解。另一方面，由于实际生产的需要，人们又迫切需要利用现代科 技对这一问题给出一个能满足生产需要的求解方法。这些方法应该是能以较高的计 算速度求出一个近似的解。所谓近似的解是指虽然不是最优解，但接近最优解，并 且要比人工排样的效果好，能达到或超过人们所期望的材料利用率。 开发、应用计算机辅助优化排样系统的意义【l 】，可以归纳为：通过节约材 料、减少排样工作量和化简切割工艺，最终达到降低产品成本的目的。 1 节约材料，提高经济效益 人工排样受人的工作态度、能力等主观因素所限制，很难给出材料利用率最高 或者接近最高的排样方案。应用计算机辅助优化排样，可以充分发挥计算机强大的 计算能力，经过大量排样方案的比较，选出材料利用率最高或者接近最高的排样方 案，以达到节约材料的目的。 2 减少排样工作量，加快排样速度 人工排样时，为了得到一个较好的排样方案，往往需要长时间的反复工作。而 计算机辅助排样，则可以在非常短的时间内完成排样，并且得到高质量的排样方案。 3 化简切割工艺，减少切割工作量 排样时经常遇到这样的情况，存在许多材料利用率接近的排样方案，称其中材料利 用率最高的排样方案为最优排样方案。应用计算机辅助排样，可以在大量的达到最 优，或接近最优的排样方案中，选择切割工艺尽可能简单的排样方案，减少切割工 作量。 i 3 优化排样问题的研究现状 国外有关下料排样问题的研究起步比较早。最早关于排样的文章是前苏联人 k a n t o v o r i c h 在1 9 3 9 年发表的【2 】，讨论一维下料问题。五十年代中期，p a u l l p ! ， e i s e m a n n s ，h e r r m a n n 年f l v a j d a 5 率先提出用线性规划方法解决印刷和造纸工业的矩 形件排样问题，但材料利用率不高。g a r e y 和j o h n s o n 【6 1 证明用数学规划的方法解决 2 西北工业大学硕士毕业论文 二维切割问题属于n p 完全问题。6 0 年代初，g i l m o r e 和g o m o r y l 7 1 0 l 发表了四篇著名的 文章，提出了一维下料方案和二维排样问题。7 0 年代至今，许多学者对排样问题进 行了大量的研究，取得了一定的成果。但排样问题为n p 完全问题，复杂难解；同时 由于排样时存在各种限制条件，因此至今也没用通用的标准方法来进行求解。 由于研究矩形件排样既可以直接解决矩形件排样问题，也可以作为解决二维不 规则零件排样问题的基础( 以包络矩形法将不规则零件排样问题转换为矩形件排样 问题) ，所以一直是众多学者研究的热点。 启发式算法在排样问题求解中占据了重要的地位。y a n a s s e 】提出依次序的启 发式排样算法，算法的主要思想是根据排样零件的物理属性( 长、宽、面积) 等给出 一定的优先级规则，零件按照这种优先级规则排序，从板材的左下角开始按次序排 放每一个零件。d a g l i 和t a t o g l u 1 2 】提出使用启发式算法，但该启发式算法的启发规 则难以确定，排样结果不稳定。a m a r a ”】提出一种交互式排样方法，计算结果比较 稳定，但排样效果一般化。p r a s a d 和s o m a s u n d a r a m i l 吸收两种理论的优缺点，针对 三种不同的问题提出了不同的算法。文献 1 5 提出了一种混合启发式优化算法，在 建立新的数学模型的基础上，采用一个三步算法进行求解。文献 1 6 利用启发式算 法和最小下晃条件来解决装箱问题。 d y c k h o f f h 】对排样问题进行了综述，依据空间维数、排样任务种类、排样材料 分类和排样零件分类等四个特点，建立了排样问题的拓扑模型。 7 0 8 0 年代，随着智能优化算法如神经网络、遗传算法、禁忌搜索、模拟退火等 的不断出现，给解决排样问题提供了新的思路。9 0 年代后，智能优化算法不断发展， 日益成熟，它们在t s p 、装箱问题、任务调度等组合优化问题得到了成功的应用，体 现了智能优化算法的优越性。这些算法与排样算法相结合解决排样问题正日益成为 热门。 e h o p p e r 和b t u r t o n l l 8 搬照空间维数和排样图形的几何形状对排样问题进行 了分类，对遗传算法中的排样问题编码方法、遗传算子和解码算法进行了讨论； s e g e n r i e c h 和b r a g a t l 9 i 提出用遗传算法解决零件多件多排问题；文献 2 0 提出一种 新型的结合遗传算法和模糊控制的排样算法，以获得较好的排样效果；文献 2 1 3 提 出神经网络算法，较好地结合了算法和人的智能因素，排样结果较好；文献 2 2 应 用模拟退火算法解决圆形排样问题；文献 2 3 应用蚁群算法来求解具有动态条件约 束的排样问题；文献 2 4 综合利用启发式算法和遗传算法求解排样问题；文献 2 5 提出一种“树形搜索”算法来解决切割下料问题；文献 2 6 3 对不同问题实例的综合 第一章绪论 性能评价的结果，有两点主要结论：复合算法的结果优于单纯排放算法的结果， 并且排放算法效果越好，则复合算法在同等条件下的效果也越好。任何算法都有 效果不佳的算法实例，即使对矩形件排样目前都没有完全有效的排样算法 在对矩形件进行研究的同时，人们也对二维不规则零件的排样问题进行着研究。 相对来说，不规则零件的排样问题难度要大很多。对不规则零件排样的方法可以分 为三大类：第一类是以矩形件排样为基础的排样算法。对不规则零件，首先利用包 络矩形技术转化为矩形零件，然后利用矩形件排样算法进行求解；第二类是以图形 运算和计算几何为基础的方法。把排样的材料和零件都作为图形来处理，利用图形 学和计算几何的知识来进行排样零件的定位和判交处理；第三类是采用智能优化算 法。这类方法一般都是和第一、二类方法相结合使用的。 文献 2 7 提出了两步法的排样思路；文献 2 8 用两步法进行排样，首先利用包 络矩形法，然后利用模拟退火算法进行求解：文献 2 9 利用遗传算法进行求解；文 献 3 0 提出将遗传算法和启发式算法相结合来求解二维不规则零件排样问题，对遗 传算法的编码方法进行了改进，从图形学的角度出发，使算法尽可能忽略材料和零 件几何形状的复杂性的影响；文献 3 1 讨论了不规则材料上的圆盘排样问题；文献 3 2 应用临界多边形求解不规则零件排样问题。 我国的计算机辅助排样研究工作开展的比较晚，始于8 0 年代，开始时，一般都 集中在矩形件排样的研究上。至今已经获得了很大的发展，但是总体上，国内就排 样问题研究和国外相比，无论是深度和广度方面，仍然有很大的差距。 进入9 0 年代之后，矩形件排样技术有了进一步的发展。曹炬【3 3 】提出了一个利用 背包问题解法的矩形件排样的近似优化算法；崔耀东【3 4 】提出了组块策略，将制造同 一种产品所需各种不规则形状零件套排成大小各异的矩形组块，每一组块包括多个 零件：下料时在整张板上按矩形组块切割，同一张板上可以排列多个矩形组块；文 献 3 5 构造了一个近似算法，该算法的主要思想是在排样过程中根据一种局部最优 原则不断地动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一 些己排过的矩形区域，直至所有的矩形件被排完；文献 3 6 提出用遗传算法求解矩 形件排样问题；文献 3 7 提出一种带预选搜索步深的二维一刀切矩形优化排料算法； 李建勇提出分别用混沌人工神经元网络【3 8 】和c i i n n 人工神经元网络【3 9 】进行排料优化 计算。 9 0 年代以后，开始逐步涉及不规则零件排样研究。岳为【4 0 1 提出将不规则零件转 换为规则零件，并进行自动组合填充，然后根据局部寻优的原则进行排样的算法， 4 西北工业大学硕士毕业论文 提高了材料利用率；文献 4 1 提出一种针对不规则形状冲压零件排样的智能化算法， 该算法利用了种新的自动碰撞技术以寻求尽可能多的可行排样，并自动计算碰撞 零件和固定( 被撞) 零件之间的动态距离；文献 4 2 提出基于改进免疫遗传算法的不 规则图形排样算法；刘心雄【4 3 】提出一种基于人工智能的自动排料算法，该算法运用 问题归约理论，将自动排料的过程简化为基本块的生成与搜索，运用规则判断与启 发式搜索的方法，生成基本块，对系统中大片、小片( 衣片) 进行自动判断分组，从 而加快了运算速度；文献 4 4 提出一种基于四树结构的排样算法，它也采用了两步 法，预先利用组合规则和邻接规则生成矩形块。 应用图形学和计算几何理沦，能使计算机在排样时自动控制整个图形作整体平 移、旋转而不局限于某一线段，排样具有一定的智能性。文献 4 5 给出了解决自动 排料的求解思路，并对自动排料的主要算法一移动算法，进行了研究和改进；文献 4 6 给出了一种对象的几何表达方式，可以忽略高度不规则形状带来的复杂性影响， 然后利用遗传模拟退火算法进行优化排样：文献 4 7 提出一个任意简单多边形的旋 转靠接算法，该算法通过快速提取多边形的关于点的单调线族的方法，将多边形的 旋转靠接问题转换为多边形的部分线族的选择靠接问题：文献 4 8 中讨论了计算机 自动优化排样过程中图形求交和定位的关键技术，n f p 问题的算法实现。 1 4 本文的主要内容及安排 本文的主要内容按章节安排如下； 第一章：绪论。介绍了优化排样问题的研究背景和研究意义，总结了排样问题 的国内外研究现状。 第二章；优化排样问题简介。介绍优化排样问题的分类和相关的优化算法，包 括一些经典算法和最近研究较为广泛的智能算法，总结了排样问题现在所存在的技 术难点和今后的发展趋势。 第三章：遗传算法和模拟退火算法。介绍了遗传算法和模拟退火算法，分析了 两种算法的特点和不足，最后介绍了对两种算法进行结合的遗传模拟退火算法及算 法并行实现的可行性。 第四章：二维不规则多边形的启发式定位算法。介绍了现有的一些启发式定位 算法，对其性能和特点做了分析，在此基础之上提出了一种基于基于平行梯形分割 的启发式定位算法，该方法具有可以实现精确定位和运算效率高的特点，最后通过 一些计算实例实际验证了该算法的优越性能。 第一章绪论 第五章：遗传模拟退火算法在二维不规则排样中的应用。介绍了遗传模拟退火 算法在排样中的应用，根据实际的需要选择遗传算法的编码方式及相关参数，确定 具体的个体评价函数，最后通过应用实例给出了该方法在实际工程中的应用效果。 实例表明该方法可以满足实际工程的需要，具有良好系统的运行效率和精度。 第六章：总结和展望。对全文所作的工作进行了总结和提出下一步值得研究的 内容。 6 西北工业大学硕士毕业论文 2 1 排样问题分类 第二章优化排样问题简介 对排样问题的科学分类和标识是全面了解和解决排样问题的基础。根据不同的 分类标准，排样问题可以分为很多类：按形状分为矩形、凸多边形、规则多边形、 任意多边形等：按单元排列方式分固定方向、可旋转等：按照排样要求分为在定宽 无限长板材上求最小排样高度、在无限多定宽定高板材上求最少板材个数以及在不 规则材料上求最大材料利用率等；还有其他多种分类方式，形成各式各样的排样问 题。可以说，排样问题在生活中随处可见，应用广泛。 按照空间尺度分为狭义切割排样问题和抽象切割排样问题，其中狭义切割排样 问题可按零件和材料的形状分为以下几种类型： 1 一维排样问题 一维排样问题，又称为线材排样问题，是指在排样时只需要考虑一个方向的尺 寸。例如，将较长的型材、管材等，分割成各种较短的毛坯。典型的应用领域包括 门窗、金属制品、机械设备、专用设备、交通运输设各、电气机械等制造行业，这 些行业所属企业在制造过程中，需要将线材切割成较短的毛坯，用于生产产品 2 = 维排样问题 二维排样问题，又称为板材排样问题，是指将板材分割成各种形状的毛坯。这 些毛坯可以是矩形、梯形、三角形等规则形状，也可以是不规则形状。典型的应用 领域包括木材制品业、家具假造业、金属制品业、普通机械制造业、交通运输设备 制造业、电气机械制造业等行业 另外一种比较特殊的二维排样问题，卷材排样问题，又称为一维半排样问题， 是指被分割的材料宽度较小，长度很大，排样时可以将长度看作无限长。布匹、纸 张、塑料、金属薄板等，都可以用卷材的形式供应。典型的应用领域包括服装、纸 制品、塑料制品、电机等制造行业。当金属薄板的厚度在0 5 m m 以下时，经常以卷材 的形式供应。在分割过程中，通常先沿着卷材的长度方向、将其分割成很长的条带， 然后再将条带分割成较小的毛坯 3 三维排样问题 在三维排样问题中，材料和毛坯都必须按照立体形状处理。典型的应用领域包 7 第二章优化排样问题简介 括木材加工业，在那里需要将圆木分割成尺寸较小的方木。圆木的长度、弯度等都 可能不同，但方木的尺寸要求是规则的。因此需要确定分割方案，使圆木分割后所 产生的方木价值尽可能大。 2 2 优化排样问题相关算法 2 0 世纪5 0 ，6 0 年代以来，经典的优化算法，包括线性规划、动态规划、整数规 划和分枝定界法等，逐步发展成熟，在优化领域得到了成功的应用。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌理论、遗传 算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或揭示某些 自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智 能等方面，为解决复杂优化问题提供了新的思路和手段。这些算法独特的优点和机 制，引起了国内外学者的广泛重视并掀起了该领域的研究热湖，目前己在诸多领域 得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，因而通常 被称作智能优化算法、或称现代启发式算法、现代优化算法。现代优化算法的主要 应用对象是优化问题中的难解问题，也就是优化理论中的n p - h a r d 问题。 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通 过一定的途径或规则来得到满足用户要求的问题的解。优化算法有很多的角度可以 进行分类。就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典 算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等【4 9 】。 下面分别介绍在优化排样领域中常用的一些优化算法。 1 线性规划法 针对一维排样问题，可以建立如下的线性规划模型f 删： 设有m 种零件，考虑玎个排样方式，只有一种线材可供使用，其长度为工，并且 对线材的可用根数没有约束，排样问题的整数规划模型为： r a i nz - - - q _ 1 - 1 l 口l l 毛+ a z 2 屯+ + q 毛6 i j a 2 l x l4 - 而j + 呸一矗6 2 l ： 【l + 2 屯+ + 口删毛k 西北工业大学硕士毕业论文 膏，为非负整数，j = 1 ，2 ，栉 式中= 为目标函数值，表示所用线材的总价值； c j 为第，种排样方式所使用线材的单位价值，如果只有一种线材，可令c ，= l ， j = 1 ，2 ，刀； j ，为按照第，种排样方式切割的线材根数，j = 1 ，2 ，疗； 吼表示第_ ，种排样方式中，含第f 种零件的数量，f = l ，2 ，研，j = l ，2 ，押； 磊为第f 种零件的需求数量，f = 1 ，2 , - - , 埘。 2 、分枝定界法 分枝定界法是f l j l a n dd o i g 等人于本世纪六十年代提出的1 5 l 】其算法思想不仅 适用于解决整数线性规划( 或者混合整数线性规划) 的问题，也适用于几乎任何组合 优化问题。它采用了类似分而治之的算法策略，在分析一个组合优化问题的所有可 行解的过程中，采取了必要的限制条件，设法排除解空间中大量非最优解区域，从 而能够有效地求解一些规模较大的问题。 算法过程中，将所有待分解或探查的活点( 子问题) 存储于集合a c t i v e s e t 中，集 合u 中存放目前发现的最优解值。算法步骤如下： ( 1 ) 初始化u = 0 0 ，尽可能去掉一些明显的非最优点，将其余的可行解集合作 为一个子集合。转到( 2 ) 。 ( 2 ) 分枝采用某种分枝规则，从日前的若干可行解子集中选择一个子集，将其 分解为若干子集合。 ( 3 ) 定界对每个新子集y ，计算三( n 。 ( 4 ) 探测根据工( 功的估计值进行判断，决定是否进一步分解子集y ，情况如 下：( a ) 三( 即2 u ；( b ) y 中不含可行解，从可行域中排除y ；( c ) 对问题m i n 厂( ， 求到最优解| ，那么三( y ) = ( 力。如果( a ) 成立，那么从可行域中去掉集合l ，；如果 ( a ) 不成立，则令u = 工( y ) ，将，作为当前最好解。然后，对其它活点( 子问题) 再根 据( a ) 进行如上判断。 ( 5 ) 停止规则如果没有活点( 子问题) 待处理，即a c t i v e s e t 中不含点集，算法终 止。当前所获得的最好解为最优解。否则，返回到( 1 ) 。 9 第二章优化排样问题简介 3 、人工神经网络算法 人工神经网络( a r t i f i c i a ln e u r a ln e t ，简写为a n n ) 是人工智能的一种研究方 法，与人工智能几乎同时起步。1 9 4 3 年，美国神经生理学家w a r r e nm c c u l l o c h 和数 学家w a l t e rp i t t s 合写了关于神经元如何工作的开拓性文章1 5 2 ，并用电路构成了简 单的神经网络模型。近年来随着各种数学理论在神经网络中的应用，出现了很多变 形的神经网络模型，如模糊神经网络、遗传神经网络、混沌神经网络、小波神经网 络等。 目前，人工神经网络在信号处理、模式识别、图像处理、自动控制、组合优化 等领域都取得了相当大的进展。人工神经网络通过模仿人类大脑的生理结构来研究 人的智能行为。人的大脑中用于记忆与思维的最基本单元是神经元，人工神经网络 中相对应的处理单元称为节点；大脑中神经元通过突触互连形成网络，人工神经网 络则用加权有向连接形成网络，权值表示两个处理单元之间相互影响的强弱。神经 网络的处理单元可以分为三种类型：输入单元、输出单元和隐含单元，输入单元从 外界环境接收信息，输出单元给出神经网络系统对外界环境的作用，隐含单元则处 于神经网络中间，它从网络内部接收输入信息，所产生的输出只作用于神经网络系 统中的其它处理单元，隐含单元在神经网络中起着极为重要的作用。 4 、蚊群算法 蚁群算法是一种新型的模拟进化算法，该算法应用求解t s p 问题、分配问题、 j o b s h o p 等组合优化问题取得了较好的结果。把优化问题变成寻找一棵面积比率最 大的二又树，用蚁群算法实现这种树搜索，就是把一定数量的蚂蚁分布在与或树的 根节点，蚂蚁间通过使用信息素相互交流，完成从与或树到二叉树的选择，从而得 到矩形件优化排样问题的优化解。 与其它的启发式算法相比，蚁群算法的主要特点是：正反馈和分布式计算，正 反馈过程使得该方法能较快找到解；分布式计算使得该方法并行操作以找到较优解。 该算法具有较强的全局搜索能力和寻优能力，解的质量稳定并具有更高的搜索效率。 自然界中的蚂蚁是以外激素( p h e r o m o n e ) 为媒介进行信息传递的，从而蚂蚁个体 能相互协作，完成复杂的任务。蚂蚁在运动中，会在它们经过的地方留下外激素。 同一蚁群中的蚂蚁能够感知到这些外激素的存在及其浓度，并以此来指引自己的行 动方向，表现为选择外激素浓度大的路径的概率要高些。这样，后到的蚂蚁同样留 下外激素，对原有的外激素进行加强，如此循环下去。蚁群的行为便表现出一种信 1 0 西北工业大学硕士毕业论文 息正反馈现象：某一路径上经过的蚂蚁越多，则后到者选样该路径的概率就越大。 由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而该路径所积累的外激 素就越多，在下一时间段内，后到的蚂蚁选中该路径的概率就越大，这个过程会一 直持续到大多数蚂蚁都走最短的那条路径，蚂蚁个体之间就是通过这种信息的交流 来达到搜索食物源的日的。 蚁群算法的原理就是人工模拟蚂蚁的上述食物搜索过程，蚁群算法具有如下优 点：( 1 ) 较强的鲁棒性：对基本蚁群算法稍加修改，便可以应用于其它问题：( 2 ) 分 布式计算：蚁群算法是一种基于种群的进化算法，具有真正的并行性，易于实现并 行；( 3 ) 易于与其它算法相结合：蚁群算法很容易与其他优化算法相结合构成混合优 化算法，以改善算法的性能。众多研究己经证明蚁群算法具有很强的发现优化解的 能力，这是因为该算法利用了正反馈原理，在一定程度上可以加快进化过程：而且 是一种本质并行的算法，不同个体之间不断进行信息交流和传递，从而能够相互协 作，有利于发现较好解。 5 、遗传算法 遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的 人工智能计术，己广泛应用于计算机科学、图像处理、人工智能、信息技术及工程 实践。遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则 与群体内部染色体的随机信息交换机制相结合的搜索算法。它在搜索之前，先将变 量以某种形式进行编码( 编码后的变量称为染色体) ，然后以某种方法评估出其适应 值，不同的染色体构成一个群体 遗传算法的基本执行过程如下： ( 1 ) 随机选择n 个个体组成初始种群； ( 2 ) 计算每个个体的适应度函数值； ( 3 ) 选择运算对n 个个体构成的初始种群，根据个体适应度函数值大小，进行比 例选择运算； ( 4 ) 交叉运算对进行了选择运算的群体中的个体以一定的交叉概率两两配对， 产生两个新个体，构成子辈群体； ( 5 ) 变异运算以一定的变异概率选择种群中的个体，对选择出的个体迸行变异 操作，形成新的子辈群体； 第二章优化排样问题简介 ( 6 ) 若不满足终止准则，则将第( 5 ) 步得到的n 个个体作为新的下一代种群，转向 第( 2 ) 步继续运算。若满足终止准则，则停止计算，输出最优结果。 6 、模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n g ) ，简称s a ，是局部搜索算法的扩展，它不 同于局部搜索之处是以一定的概率选择领域中费用值大的状态。理论上说，它是一 个全局算法。模拟退火的核心思想与热力学的原理颇为相似，而且尤其类似于液体 流动和结晶以及金属冷却和退火的方式。模拟退火算法是一种基于热力学的退火原 理建立的随机搜索算法口为了克服搜索过程极易陷入局部解的缺点，模拟退火算法 使用基于概率的双方向随机搜索技术。当基于邻域的一次操作使当前解的质量提高 时，s a 接收这个被改进的解作为新的当前解；在相反的情况下，s a 以一定的概率接 收相对当前解来说质量较差的解作为新的当前解。 模拟退火算法的特点： ( 1 ) 搜索策略有利于避免搜索过程因陷入局部最优解而无法自拔的弊端，有利于 提高求得全局最优解的可靠性。不仅在理论上能突破传统算法难以解决的难题，而 且具有很强的科学和实际的工程应用价值，因而被誉为解决许多高难度优化问题的 救星。 ( 2 ) 有十分顽强的鲁棒性，因为比起普通的优化搜索方法，它采用许多独特的方 法和技术。 模拟退火算法可以跳离局部最优，模拟退火算法是一种随机算法，它随时做上 升运动。 2 3 排样问题的技术难点 日前优化排样技术存在以下一些难点： l 、现在应用的启发式算法和智能优化算法，都只能够获得近似解，而最优解的 获取仍然是个难点。这是由排样问题的n p 性质决定的。当然，寻求更好更优的算法， 取得更好的排样结果，是我们努力的目标。 2 、无论是启发式算法还是智能优化算法，都存在一个算法的稳定性问题。任何 算法都有效果不佳的算法实例，在同一问题的不同实例计算中也会有不同的效果， 有些解很好，而有些解则很差。这主要是由算法本身的特性所决定的。但如何获得 西北工业大学硕士毕业论文 稳定、有效的解，始终是我们努力研究的方向。 3 、排样问题很复杂，再加上工艺条件的限制，难以建立一个精确的数学模型。 另外，各类排样问题的要求不同，生产情况也差别很大，排样的材料和零件情况差 别更大，因此难以建立一个统一的数学模型。现在一般情况下建立的数学模型，都 是进行了很多简化处理的。有效、精确的数学模型对优化排样是至关重要的。 2 4 排样问题的发展趋势 2 1 世纪的制造业要求企业以批量生产的时间和成本生产出具有个性化( 客户化) 的产品，使得制造企业的生产方式由面向产品的生产逐步转向面对顾客的生产【5 3 】。 1 、考虑面向制造的问题 面向制造是面向并行工程的一种设计方法，即产品设计与工艺设计并行进行的 一种设计方法。面向制造全面评价产品设计与工艺设计，并提供改进的反馈信息， 及时改进设计，以保证产品设计，工艺设计和制造一次成功，以达到降低产品成本， 提高产品质量，缩短产品开发周期的目的。具体到排样问题，要考虑的包括： ( l ) 把产品零件设计和排样联系起来。板类零件分为两类：二维平面零件和具有 立体形状的零件。立体板类零件一般通过平面展开，切割下料，然后成型。因此， 在设计时就应该把零件的立体信息和后续加工信息存入特定的数据库供零件排样时 使用，以提高零件的生产效率和质量。 ( 2 ) 把排样和具体的工艺制造联系起来。要考虑不同的工艺制造问题，如对于火 焰切割问题，要考虑切割变形问题，切割路径优化问题；对于冲压问题，要考虑压 力中心问题、零件的排列间隙问题。因此在排样时要完成相关工艺咨询，进行多工 艺方案的经济性分析。要综合考虑设备情况，加工成本和交货期等因素，以达到整 体上的最优。其中加工成本和交货期是最重要的。 2 、解决计算的智能化问题 2 1 世纪是以知识经济和信息社会为特征的新时代，智能制造的研究应运而生。 智能制造技术和智能制造系统是在传统制造技术的基础上，利用计算机技术，自动 控制技术、传感器技术、信息处理技术、光机电一体化技术与人工智能技术等发展 起来的新型制造技术。其具体表现为：智能设计、智能加工、智能控制、智能工艺 决策、智能调度和管理等。 上世纪9 0 年代以来，各种智能优化算法如神经网络、遗传算法、禁忌搜索、模 第二章优化排样问题简介 拟退火算法等得到了很大的发展，日益走向成熟。由于排样问题的特殊性，计算量 非常大，在有限的时间内难以遍历整个问题的解空间，因此非常适合利用智能优化 算法进行求解。但如何综合多种算法以及哪些算法在哪一阶段综合，是排样问题研 究的一个重要方向。事实上自从9 0 年代以来。许多学者已经开始应用智能优化算法 解决排样问题，并且获得了很好的效果。这类算法的基本思想是首先将排样问题转 换为排列问题，求出个次优或者较好的结果，然后利用智能优化算法的自适应搜索 能力，在问题的解空间中进行充分的搜索，最后得到一个最优或者次优的解。 1 4 西北工业大学硕士毕业论文 3 1 遗传算法 第三章遗传算法和模拟退火算法 人们受生物在自然界中生存繁衍显示出对自然环境优异的自适应能力，进行了 大量的研究，遗传算法( g e n e t i ca l g o r i t h m s ，g a ) 就是令人瞩目的重要成果。遗传 算法是由美国密歇根大学j o h nh o l l a n d 根据生物进化模型提出的一种优化算法，它 是一种基于生物自然选择和基因遗传学原理的优化搜索方法。作为强有力且应用广 泛的随机搜索和优化算法，遗传算法可能是当今影响最为广泛的进化计算方法之一。 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局 优化概率搜索算法。其核心思想源于“适者生存，不适者被淘汰”这一自然规律。 生物进化过程本身是一个自然的、并行发生的、稳健的优化过程，这一优化过程的 目标是提高对环境的适应能力，生物物种通过遗传、变异等方式达到这个目的。 遗传算法己广泛应用于控制、规划、设计、组合优化、图像处理、信号处理、 机器人、人工生命等多个领域，并且已取得丰硕成果。 3 1 1 遗传算法基本操作 遗传算法把问题的解表示成“染色体”，在算法中也就是一系列的编码串。并且， 在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把这些假设解置 于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体” 进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。这样， 经过若干代的进化，最后就会收敛到最适应环境的一个“染色体”上。它就是问题 的最优解。 l 、选择( s e l e c t i o n ) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代，故 有时也称这一操作为再生或复制。由于在选择用于繁殖下一代的个体时，是根据个 体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀再生。 2 、交叉( c r o s s o v e r ) 选择操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉操作模 拟了生物进化中的繁殖现象，通过两个染色体的交换组合来产生新的优良品种。它 第三章遗传算法和模拟退火算法 的过程为：在匹配池中任选两个染色体，随机选择一个交换点：交换双亲染色体交 换点右边的部分，即可得到两个新染色体数字串。交换体现了自然界中信息交换的 思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交 叉是最基本的方法，应用较广。 3 、变异( m u t a ti o n ) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突 变，它以很小的概率随机地改变遗传基因( 表示染色体编码串的某一位) 的值。在染 色体的编码系统中，它随机地将改变染色体的某一个基因，若只有选择和交叉，而 没有变异，则无法在初始基因组合以外的空间进行