（服装设计与工程专业论文）模拟退火算法在服装排料中的应用与研究[服装设计与工程专业优秀论文].pdf

东华大学硕士研究生学位论文 模拟退火算法在服装拌料中的应用与研究 能跳出局部最优，而得到全局最优解。 论文在自动排料的问题上，首先解决了以模拟退火算法为基础的 矩形件的自动排料问题，排料算法是基于最低水平线的搜索算法。 在服装排料系统的开发上首先依据服装排料规则将衣片样板进 行矩形化处理，然后调用矩形件的自动排料方法进行自动排料，最 后再运用人机交互式排料方法对排料图进行修改。应用矩形法进行 服装衣片样板的自动排料，虽然大大节约了排料时间，但是面料的 利用率不是很理想，所以在本课题开发的排料系统中，经过自动排 料以后，还需进行人机交互式排料来提高面料的利用率。 本课题开发的服装排料系统是以a u t o c a d 2 0 4 为开发平台，以 a r x 和v c + + 语言为开发工具。 关键词：服装排料，退火算法，最低水平线算法， a u t o c a d 二次开发 壅兰查堂堡主堑窒竺堂垡堡塞 堡垫堡盔竺鲨垄璺蕉堡壁! 塑壁星兰里互 a b s t r a c t w i d e l yu s e d i ni n d u s t r yp r o d u c t i o n ，l a y o u tp r o b l e mi sa no p t i m i z a t i o n p r o b l e m ，w h i c h i sc o n c e r n e dw i t hf i n d i n gag o o da r r a n g e m e mo f m u l t i p l e d i f f e r e n t - s i z e do b j e c t si nal a r g ec o n t a i n i n gr e g i o nw i t h o u t o v e r l a p p i n g ag o o d s o l u t i o no f t h i sp r o b l e mh a saf a r - r e a c h i n gm e a n i n g i ng r e a t l yr e d u c i n gt h ep r o d u c t i o nc o s ti ni n d u s t r y i nt h eg a r m e n tf i e l d , g a r m e n tl a y o u ts y s t e mi sa ni m p o r t a n tp a r to fg a r m e n t c a d s y s t e m ，s oa g o o dg a r m e n tl a y o u ts y s t e mi sag o o dt e c h n i q u et og r e a t l yr e d u c et h e p r o d u c t i o nc o s t c u r r e n t l yt h e r ea r em u c hg a r m e n tc a d s o f t w a r ea p p l i e di ng a r m e n t i n d u s t r yo fo u rc o u n t r y , f o ri n s t a n c e ，i e c t ms y s t e mo ff r a n c e ，g e r b e r s y s t e mo fu s a , a c ss y s t e mo fj a p a n 1 a y o u ts y s t e mo f t h e g a r m e n t c a d s y s t e m si sp e r f e c t ，b u tp a c k i n ga r i t h m e t i co f t h e s el a y o u ts y s t e m s i s n to p e nt os o c i e t y , s oi ti si n n o v a t i v em e a n st o r e s e a r c hl a y o u t p r o b l e mi nu n i v e r s i t y t h e p a p e ra i m sa tl a y o u tp r o b l e m o f t w o d i m e n s i o n a li r r e g u l a rf i g u r e s i nt h em a t e r i a lt h a tw eu s e di sad e f i n e ds i z eo n e t h i sp a p e rs t u d i e st h ep r i n c i p l eo fc o m p u t e ra i d e dg a r m e n tl a y o u t , t h e nt h ep a p e ra n a l y z e st h ed o m i n a n c eo fc o m p u t e r a i d e dg a r m e n tl a y o u t , t h er u l eo f l a y o u tg r a p hd e s i g n e d , t h em e t h o do f c o m p u t e rl a y o u t o nt h eb a s eo fr e s e a r c h i n gg a r m e n tl a y o u ts y s t e m ，t h ep a p e rp r o p o s e s h i 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 s i m u l a t e da n n e a l i n ga r i t h m e t i c ，w h i c hs i m u l a t e sm e t a la n n e a l i n gp r o c e s s t os o l v e o p t i m i z a t i o np r o b l e m t h e s i m u l a t e d a n n e a l i n ga r i t h m e t i c a c c e p t sb a d d i s hv a l u e sa c c o r d i n gt o d e t e r m i n a t ec o n d i t i o n s ，s ot h e s i m u l a t e da n n e a l i n ga r i t h m e t i cc o u l dd a pl o c a lo p t i m i z a t i o nv a l u e sa n d r e a c ho v e r a l lo p t i m i z a t i o nv a l u e a ta u t o m a t i c l a y o u tp r o b l e m , t h ep a p e rs o l v ea u t o m a t i cl a y o u t p r o b l e mo fr e c t a n g l eb ys i m u l a t e da n n e a l i n ga r i t h i n e t i ca tf a s t a tt h e p r o c e s so fl a y o u t ，p a c k i n ga r i t h m e t i ci sb o t t o m m o s tl e v e la r i t h m e t i c a b o u tg a r m e n tl a y o u ts y s t e mo ft h ep a p e r , i ti st of r e de p i o l i cr e c t a n g l e f o re a c ht e m p l e ta c c o r d i n gt ot h ep r i n c i p l eo fc o m p u t e ra i d e dg a r m e n t l a y o u t t h e ni ti st ou s ea u t o m a t i cl a y o u ts y s t e mo fr e c t a n g u l a rm e t h o d ， a tl a s ti ti st om o d i f yl a y o u tg r a p hb ym a n m a c h i n ei n t e r a c t i v em e t h o d s s og a r m e n tl a y o u ts y s t e ms a v e st i m ea n di n c r e a s eu s i n gr a t eo ff a b r i c g a r m e n tl a y o u ts y s t e mb a s e do na u t o c a di sd e v e l o p e db ya r x 髓d v c + + l a n g u a g e y a n gy u h o n g ( f a s h i o nd e s i g n & e n g i n e e r i n g ) s u p e r v i s e db yp r o f e s s o rc h e ny i s o n g & m i a oy u a n j i k e y w o r d ：g a r m e n tl a y o u t , s i m u l a t e da n n e a l i n ga r i t h m e t i c ， a u t o c a d r e d e v e l o p m e n t , b o t t o m m o s t - l e v e la r i t h m e t i c i v 东华大学硕士研究生学位论文 模拟退火算法在服装排料中的惠用与研究 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是 本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和 引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及 成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声 明的法律结果由本人承担。 学位论文作者签名：j 葛州2 日期： 如g 年1 月刀e l 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借 阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密阢 学位论文作者签名：弘z 日期：函旃，月，o e l 一啜骜 日期：移砭暑日 东华大学硕士研究生学位论文模拟退火算法在服装棒科中的应用与研究 1 1 引言 第一章绪论 排料问题，是给定一个布局空间和若干待捧物体，将待排物体合理地摆放 在布局空间中，满足必要的约束条件，并使空间利用率达到最高。排料问题是 随着计算机技术的产生而出现的，大量出现在机械制造、服装加工、汽车、造 船、玻璃、交通运输、航天航空、大规模集成电路板的设计等领域。 根据布局空间和待排物体的形状，二维排料问题可以分为以下两类： 1 ) 二维规则形状排料问题。例如：矩形件排料问题。玻璃下料、一刀切问 题等。 ( 2 ) 二维不规则形状排料问题。例如：服装排料、装入问题等对于二维不 规则形状排料问题。可以把单个或几个不规则零件包络成最小矩形单元，然后 对矩形件进行排料；也可以直接对二维不规则零件进行摊料。 服装排料是指在满足设计、制作等工艺要求的前提下，将服装各个规格的 所有衣片样板在规定的面料幅宽内进行科学地排列、目的是使面料的利用率达 到最高，以降低产品成本，同时给分床、裁剪等工序提供可行的依据。计算机 服装辅助排料是在计算机的显示屏幕上给排料师建立起模拟裁床的工作环境、 操作人员将已完成放码、放缝边工作的各种号型的服装样板，在给定布幅宽度， 布纹方向、花格对齐、尺码搭配等限制条件下，用数学计算方法，合理、优化 地确定衣片在布料上的位置。无漏排、错排现象，将排料信息传递到数控裁床， 实现省时省料的剪裁自动化。 综上所述，数学计算方法是解决排料问题的关键，所以为了能更好地解决 排料问题，求得最优化的排料解，人们不断地寻找新的方法。现在遗传算法、 模拟退火算法、启发式搜索算法都用于求解接科闯题。 东华大学硕士研究生学位论文模拟退火算法在服装排科中的应用与研究 1 2 研究背景与意义 1 2 1 排料问题的研究背景 由于计算机排料问题在应用上可以提高生产效率，节约成本，理论上具有 巨大的挑战性，有重要的研究价值。所以对于计算机排料问题，一直受到广泛 的重视和研究，研究方法涉及了组合优化、人工智能，计算几何学等各种理论。 已经尝试过的方法主要有：遗传算法、模拟退火算法、启发式搜索算法、人工 神经网络法、线性规划法等。 计算机辅助服装摊料作为服装c a d 技术的重要组成部分，是服装c a d 技 术最早发展的技术之一，在2 0 世纪7 0 年代对服装工业化大批量服装制作起了 重要的作用，不仅生产效率得以提高，生产条件和环境也得到很大的改善。2 0 世纪9 0 年代后，c a d 软件的各开发商又相继推出服装结构设计和款式设计等 系统，从而完善了殿装c a d 产品，使款式设计、结构设计、样板制作与推档排 料形成一体，都可通过计算机完成，形成产品的系列化，使服装设计人员基本 上实现设计的计算机操作。 目前我国服装行业中应用的主要国内外服装c a d 系统有：国内有广州银寰 科技的w o o d m a n 系统、北京日升天辰的n a c 系统、航天的a r i s a 系统、北京工 商大学的b i l i 系统、北京六合生的至尊宝坊m o d a s o f t 系统、杭州宏华的a t - d e s i g n 系统、杭州爱科的e c h o 系统等，国外有德国艾斯特系统a s s y s t 、日本东丽系统 a c s 。法国力克系统l e c t r a 、西班牙艾维系统i n v e s t 、美国格柏系统g e r b e r 和匹 基姆系统p g m 、日本d r e s s i n g s i m 系统等2 0 多家【l i 1 2 2 排料问题研究的意义 捧料厨题在工业生产中应用十分广泛。如造船工业、汽车工业、钣金加工 工业、服装生产、皮革加工、纸张及木材加工工业等都需要处理排料问题。 二维排料问题按照其应用范围的不同，可分为五类： 1 ) 应用于造船或汽车制造等行业，零件的外形复杂、不规则，采用火焰切 割、激光切割、等离子切割或数控线切割分离零件的优化捧料问题。 2 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 2 ) 应用于冲裁冷加工作业，加工各种冲裁件的优化排料问题。 3 ) 应用于以加工矩形零件为主的板料柔性加工系统的优化排料问题。这类 零件的加工设备主要是数控冲床、数控裁床，重点应用于机箱、机柜类钣金产 品的生产上。 4 ) 应用于建筑领域，膜结构的优化捧料问题。 5 1 应用于服装工业生产中。 其次，排料问题在工业生产中占有重要的地位并与经济效益有直接关系。 众所周知，材科费在产品的成本中占有较大的比例，因而如何提高材料利 用率，减少材料损失便成为降低产品成本，提高产品竞争力的主要手段之一。 而排料的主要任务正是；在满足一定的约束条件下合理、有效地布置零件以求 最大限度地利用材料。所谓在满足一定的约束条件下合理且有效地布置零件就 是要符合将零件从材料上分离下来所采用的设备和工具的加工工艺特点与要 求。 综上所述，解决排料问题具有理论和现实应用意义 在服装的工业生产中，对于服装排料问题的研究所具有理论意义和现实应 用意义具体表现为以下四个方面 1 ) 服装生产的整个过程基本上可概括为；款式设计、制作样板、摊料、裁 剪及缝纫整理等几个生产环节，排料结果的好坏会影响后面的服装剪裁这个工 艺环节1 2 】。 2 ) 缩短服装产品的加工周期，在服装产品的加工制作过程中，应用计算机 辅助排料使采用人工排料要花几个小时甚至几天的服装衣片样板排料在几分钟 内就可完成，从而缩短了服装产品的加工周期。 3 ) 降低劳动成本，合理的排料系统除了可以节省面料的利用率，节省面料 费外，计算机辅助服装摊料可以将大量款式和纸样存储在计算机内，因此可大 量减少甚至取消纸样的存放，取代纸样库房，提高了查询、检索效率，便于样 板管理，本来由多人完成的工作，可以由少数人员操作电脑来完成、节约人员 和场地。 4 ) 在排料系统生成的排料图中可以计算出每种款式每套衣服的用料率，从 而成为服装核定成本的依据之一 东华大学硕士研究生学位论文模拟退火算法在服装捧科中的应用与研究 当前计算机技术飞速发展，无论是软件还是硬件，都在快速地更新换代。 对于用原来的软硬件环境所开发出的排料系统，提供了更大的发展方向，以前 受制于计算机速度和存储空间的限制，以往的一些排料系统在算法上常过多地 使用近似法，以至于影响了利用率的提高，还有的一些排料系统，采用了穷举 法进行排料，由于运行速度慢而极大地影响了效率和实用性。 所以有效的排料算法，能充分利用计算机的潜力，使捧料软件系统不断升 级，向更新更高的方向发展。例如：计算机服装辅助排料系统同服装c a m 系 统相结合：计算机辅助服装排料系统和面料订货系统相结合。 1 3 国内外研究历史及现状 自从本世纪六十年代起，由于计算机技术、优化技术、计算机图形学、数 据存储与提取技术的发展，人们对排料问题的研究逐渐深入。下面分别介绍国 内外对排料问题研究的历史及现状。 1 3 1 国外研究概况 对于任意形状零件的排料问题，目前所采用的解决方法归纳起来主要有以 下三种【3 j ： 1 ) 近似矩形法，即把单个或几个不规则零件组合成矩形单元，然后对矩形 单元进行排料 2 ) 启发式推理方法，此方法模拟人工排料，定义大量的规则，使用启发式 推理方法，由计算机决定排料方案，不需要人的参与。但组建这样的系统需要 丰富的经验。 3 ) 智能优化法，即以最小浪费率为目标函数，采用诸如人工神经网络、模 拟退火法、遗传算法等智能优化方法，在整个解空间中进行搜索 下面分别针对这三种方法，对排料研究的历史以及现状加以简要介绍。应 该指出实际应用时常常用“加加”创造思维技法可以同时使用两种或两种以上 的方法进行排料优化处理 ( 1 ) 近似矩形法 1 9 7 6 年纽约大学的m a d a m o w i c a 在所发表的博士论文中利用矩形模块分 4 东华大学硕士研究生学位论文模拟退火算法在服装捧料中的应用与研究 两阶段对二维不规则零件进行排料。然后，他和意大利p i s a 大学的a 舢b 卸。合 作，作了迸一步的研究与完善工作。1 9 7 7 年a a i b 黝发表论文【4 】，论文的基本 腰了耐两步法”和“人机交互法”。在这篇文章中，首先通过启发式方法和动 一态规划方法的组合，由计算机产生一个初始排料方案，然后再通过人机交互的 方法对其进一步加以改进。 1 9 9 1 年，c h e o k 和n e e 5 提出了用于造船业的三步自动排料方法。第一阶段， 称为形状处理，通过去除诸如倒角、圆角等小的特征简化零件轮廓。然后，将 这些简化的轮廓进行分类。第二阶段，根据先前的经验，匹配以分类的零件， 产生好的或紧密排列的矩形单元。第三阶段，采用矩形排料方法排列这些单元。 c y u z u l 6 j 也曾与1 9 8 7 年提出了基于这种方法的用于服装裁剪的专家系统。在这 种方法中对于每一种服装类型，如男士衬衫，均给出一大套特定的规则。可是 对于这些规则的细节和应用并没有进行详细的讨论。 ( 2 ) 启发式推理方法 f r e e m a n 于1 9 6 4 t 7 年和后来的r a d a c k 与b a d l e r 于1 9 8 2 i s ! 年提出一个与排料 问题十分类似且很有趣的问题拼板玩具问题。r a d a c k 与b a d l c f 提出了用边 昴中心极坐标编码代表零件轮廓的新颖方法来决定边界的匹配情况。但应用 f r e e m a n 或r a d a c k 与b a d l e r 所提出的方法是困难的，因为在排料中完全类似于 其提出规则的轮廓匹配情况很少存在。 1 9 8 0 年，a a l b 锄。和s a p up _ p o 【9 】提出了一种自动排料方法，在论文中他们 使用了人工智能的典型启发式搜索策略，将排科问题转换为寻找一条最有路径 的问题。 1 9 8 3 年，d a g l i 和t o t o g l u ( 1 0 1 通过决定零件的优先权，如根据零件的面积、 轮廓周长、复杂性等等，依次定位零件。从两个具有最高优先权的零件开始， 由它们的边界匹配情况。决定它们之间的相对位置，然后选择具有最小包络矩 形( m i n i m u me p i b o l i cr e 咖n g l e ) 的位置。按优先权顺序不断重复以上过程，直 到所有的零件均已定位或将板料捧满，这种不加选择地判断边界匹配的各种可 能性的方法，耗费了大量的计算时间。 1 9 8 9 年，c h u n g 及其合作者 1 解决了复杂轮廓的钣金排料问题。他们使用 一系列技术定位零件，运用启发式搜索方法匹配零件的凹凸特征，分别对四个 5 东华大学硬士研究生学位论文模拟退火算法在服装捧料中的应用与研究 基本位置( 9 0 度、1 8 0 度、2 7 0 度、3 6 0 度) 寻找最好的毗邻零件。一旦一个零件 定位。它的下一个最好毗邻零件被测定。但是，他并没有给出“最好的毗邻零 件”的定义。而且，对于四个基本方位的约束，虽然对轮廓近似于矩形的零件 是合理的，但对于形状复杂的零件，则需要具有更多的自由性。 1 9 9 4 年，p r a s a d t l 2 7 在文章中讨论了边界的基本原理。他提出将一个零件先 固定，而将另一零件沿着它的n f p ( n o t - f i t p o l y g o n ) 多边形的轮廓移动通过 对正轮廓的最长边界，决定零件的相对位置，在沿n f p 多边形移动的每一步过 程中均构造一个最小包络矩形，然后选择其中最好的最小包络矩形，可是这种 算法仅限于钣金加工，解决的问题也仅限于两、三个零件。 ( 3 ) 智能优化方法 近年来，国际上掀起了一股人工神经网络的研究热潮。神经网络的应用研 究取得了很大的成绩，涉及面非常广泛。就应用的技术领域而言有计算机视觉， 语言的识别、理解与合成，优化计算，智能控制及复杂系统分析，模式识别， 神经计算机的研制，知识处理，专家系统与人工智能。涉及的学科有神经生理 学，认识科学，数理科学，心理学，信息科学，计算机科学，微电子学，光学， 生物电子学等【”l 。人工神经网络独特的结构和处理信息的方法，使其在许多应 用领域中取得了显著的成效，能够解决一些传统计算难以解决的问题。 一些学者已经将人工神经网络技术应用到捧料领域中，但在这方面所进行 的研究还处于探索阶段下面作一些简要介绍t m s r i r a m 和s m k a n g ( 1 9 9 0 ) 1 4 喇用改进的h o p f i e l d 人工神经网络解决3 - - - 维模块的线路排料问题。文章以总线长最小为目标函数来构造排料模型。通过 使网络的互联权矩阵依赖于网络的状态，并且在能量函数中包含四次项来改造 h o p f i e m 神经网络。经过这种改造后原来的二维排料问题被分解成两个一维 问题。同时文章中采用了最小排料布局的分层方法，使得网络的大小与模块的 数目呈线性关系。计算结果表明，这种方法与一般的启发式方法相比有较多优 点。 c x z l 瑚喀和d a m l y n s l d ( 1 9 9 0 ) 0 5 l 运用k o h o n e n ( 1 9 8 2 ) 和r i t e r ( 1 9 8 6 ) 提出了 人工神经网络模型的拓扑映射特征解决大规模集成电路的捧料问题文章将集 成电路中捧料问题所具有的特征与神经网络模型的映射特征结合在一起。通过 6 东华大学硕士研究生学位论文模拟退火算法在服装捧料中的应用与研究 输入空间与输出空问的拓扑映射关系来建立可移动模块与芯片上槽之间的关 系。并且用c 语言编程，在v a x l l 7 5 0 计算机上实现了所提出的算法。所得的 排料结果与传统的排料算法的结果相比，在效率和时间上均有所提高。 s s k i m 和c m k y u n g ( 1 9 9 2 ) t 1 6 l 针对印刷电路板的排料问题，提出一种自组 织辅助排科算法( s o a p ) 。这篇文章所解决的问题不是将任意形状的零件在规则 的区域上进行排料，而是在任意形状的区域上进行排料。文章中的任意区域包 括由直线边界组成的二维区域、非平面的表面区域以及三维体域。所采用的算 法根据k o h o m c n 提出的自组织特征映射( s o m ) 的神经网络，利用了s o m 的自 组织学习特性以及s o m 对于类似的输入较敏感的特性。文章还改进了以往的算 法，以往的在直线边界组成的区域内进行捧料的算法都是将整个区域分割成若 干矩形区域，因此所产生的最终结果依赖于划分的方式。而这篇文章所提出的 自组织辅助排料算法( s o a p ) 是对任意形状区域的电路布局问题均适用的算法， 没有以下缺点。 目前，人们已经将模拟退火算法运用到二维择料问题中模拟退火算法是 一种著名的全局优化算法f 1 7 】，是采用概率搜索方法的组合优化技术。模拟退火 算法是基于m o n t ec a r l o 迭代求解的一种启发式随机搜索法，它非常适合解决具 有大范围搜索空间的问题。 例如，s h a h o o k a r 和m a z u m b e l ( 1 9 9 1 ) i s l 运用这种算法解决了大规模集成电 路中的布局问题。h c r g t l 和a l g a ( 1 9 9 2 ) i 1 9 】利用模拟退火算法解决印刷中的排料问 题。j a i n 和f e n y e s 以及硒c m c f ( 1 9 9 2 ) 【捌用此算法解决了= 维冲裁零件排料问题。 c h o ( 1 9 9 3 ) 1 2 1 】也对钣金冲裁零件摊料问题加以解决。 为了验证模拟退火算法的搜索能力，i c a d o w n s l a n d ( 1 9 9 3 ) 2 2 ) 苇j 模拟退火算 法对许多的组合优化问题进行了试验验证。结果表明，模拟退火算法是种有 效的全局搜索方法，并说明了该算法的基本要求是定义适当的邻域结构。邻域 结构是决定在搜索过程中所产生的新解是被接受还是被放弃的主要参数，所产 生的解的好坏对此参数的选取很敏感同时，作者把模拟退火算法应用到包装 领域的捧料问题中，进行了一系列试验，用来证明模拟退火算法解决此问题的 有效性。并提出了最合理的邻域结构和最有参数的选取问题 另外，h i s m a i l 和k k b h o n ( 1 9 9 2 ) 1 2 3 】提出了用于解决二维冲裁件排料的 7 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 自动成组匹配算法。文章将整个排料过程分为两个阶段。首先，提取边界信息 以便形成边界数组，进而获得最佳边界匹配。然后运用遗传算法的非确定性理 论，产生排料结果。 从排料问题的实际应用方面来看，国外在七十年代已进入实用阶段由于 国外在这方面研究开发得比较早，目前许多公司如：a p p l i c o n 公司、e d s 公 司都提供有关排料的软件产品。但国外的排料系统价格昂贵，还附有一些限制。 如：t r i m f 公司得排料软件必须用a p t 语言编程输入，速度慢，要求有专门 的使用技术人员，因此不便推广应用。 1 3 2 国内研究概况 国内对优化摊料的研究尽管起步较晚，但也做了大量工作。常用的方法主 要源于苏联学者a k h u p b a p a h j i o b 的板料冲压最佳排料图编制过程的 自动化针对排料问题的不同方面，最早提出的有加密点法、人机对话法，随 后出现点阵判交法。平行线分割一步平移法等 2 a - 2 6 。浙江大学、上海交大、西 安交大、清华大学及华中理工大学等院校均做了一定的研究。 1 9 9 2 年，李新军、熊火轮等发表 点阵判交种计算机自动排样系统 设计的新方法【2 飘文章介绍了一种新的非几何判交方法。指出判断两个几何 元素是否存在交点，即求交，是捧料的基础性工作之一。其方法的优劣直接影 晌着排料程序的可靠性和效率判断两个集合元素是否相交，从图形上看是十 分容易的，但运用解析法在计算机上用程序实现却很费周折文章论述了屏幕 光栅点阵判交的中心思想是判断某一直线所要经过的点是否已经被打亮。 对于冲裁件排料，国内所做的研究工作，在算法上也比较成熟，其排料方 式可分为：普通单排、普通双排、对头单排、对头双排。所需解决的主要问题 是冲裁步距和冲裁角度的计算问题。 例如，上海交通大学的夏萼辉、卞铭甲、李绍成发表了单双排冲裁件的 最佳捧样法【2 7 1 微机所确定的方案较人工方案材料利用率提高了5 以上。 文章中将排料零件的几何图形信息化，采用坐标点法( 即加密点法) 近似代表 真实图形。为使问题简化，只考虑了同一种零件在“无限长”条料上排料的情 况。 矗 东华大学硕士研究生学位论文模拟退火算法在服装排料中的应用与研究 华中理工大学c a d 中心的曹炬、周济于1 9 9 3 年发表了冲裁件排样最优 化的数学模型及算法闭。文章通过对数学模型的分析，解决了冲裁件排料问 题。排料后所得的最佳冲裁角度于冲裁步距的计算精度分别可达l 度和 0 0 0 1 m m ，在3 8 6 型微机上平均计算时间为四分钟。但是此优化模型没有对板 材的大小加以限制，即不能在有限长、宽的板材上排料，需进一步给出整体优 化模型以及相应的算法。 1 9 9 8 年，华中理工大学的董长双、杨楚民、宾鸿赞发表了 冲裁零件二维 排样优化 2 9 j 。文章提出了在以往的冲裁件优化排料的计算机求解方案中，人 们一般将卷板当作无限长的条料或将有限长、宽的板材裁成若干条等宽度的条 料，所采用的优化模型也是建立在此基础上的。当将有限长宽的整体板料在冲 压设备上进行x ，y 轴双向送料冲裁时，上述建立的模型将不再适用。这篇文 章给出了以在有限长、宽的整体板料上能冲裁出的最大样件个数为目标的整体 优化模型及算法。 北京工业大学的杨洪旗，西安交通大学的储家佑发表了冲裁件的排样优 化与动画排样寻优法例。可输出材料利用率特征曲线及最佳排样图并设计了 动画排料子程序该方法形象直观，操作方便，但过多的依赖于人的参与。所 得的排料结果与操作者的经验直接相关 浙江大学的周泓一、金廷赞的二维不规贝l j 形状的最优布局问题计算 机辅助服装裁片自动排料系统( 3 ，将计算机图形学和人工智能相结合，运用 人工智能的启发式方法把裁片的二维最优布局问题转化为在一个状态空间中寻 找一条最优路径的问题。将从初始状态出发的所有可能达到的状态集合视为一 个有向图，其中节点对应状态，边对应算子，将问题视为一个寻找从初始节点 到目标节点路径的搜索过程。 上海交大的杨世胜、吕荣发表了服装自动排料初探1 3 】，提出了用服装样 板几何图形的数学模型来实现图形的输入，以及对图形进行各种判断、处理。 其最优排料方案的材料利用率达9 2 判断板样是否相交，贯穿于整个捧料过 程。 另外，东北大学的聂瑞华阎，在其硕士论文中，对任意形状的零件进行捧 料。对以往算法中将任意形状的轮廓用直线或圆弧代替的方法进行了改进。将 9 东华大学硕士研究生学位论文模拟退火算法在服装捧科中的应用与研究 任意形状的曲线用参数样条逼近，也把二维最优排料问题转化为在一个状态空 问寻找一条最优路径的问题。 1 4 基于模拟退火算法的排料算法的可行性 由于布局问题属于n p ( 非多项式时间问题) 完全问题，随着待排物体数量 的增加，解空间里指数倍地扩大，会出现组合爆炸现象，即运算时间的无限延 长。用动态规划、分支定界等基于穷举思想的算法都无法解决。本文所介绍的 模拟退火算法在最优解的求解过程中缩小解空间的搜索范围，从而提高求解效 率，节约计算时间。如前文提及人们已经将模拟退火算法运用到二维排料问题 中。模拟退火算法是一种著名的全局优化算法【j 7 1 ，是采用概率搜索方法的组合 优化技术。模拟退火算法是基于m o n t ec a r l o 迭代求解的一种启发式随机搜索 法，它非常适合解决具有大范围搜索空间的问题。 1 5 本章小结 本章从排料问题的概念出发，将排料问题分为；二维规则形状排料问题和 二维不规则形状的排料闯题。指出了在排料问题中排料的数学计算方法是捧料 问题的关键。还介绍排料问题的研究背景及研究意义，从四个方面说明了服装 排料的理论和现实应用意义并且分别介绍了捧料问题的国内、外研究现状， 并对模拟退火算法在排料闻题中的应用做了可行性分析。 东华大学硕士研究生学位论文模拟退火算法在服装捧科中的应用与研究 第二章计算机辅助服装排料软件的研究 服装排料是指在满足设计、制作等工艺要求的前提下，将服装各个规格的 所有衣片样板在规定的面料幅宽内进行科学地排列，目的是使面料的利用率达 到最高，以降低产品成本，同时给分床方案的制定提供可行的依据。计算机服 装辅助排料是在计算机的显示屏幕上给排料师建立起模拟裁床的工作环境，操 作人员将已完成放码、放缝边工作的各种号型的服装样板，在给定布幅宽度、 布纹方向、花格对齐、尺码搭配等限制条件下，用数学计算方法，合理、优化 地确定衣片在布料上的位置，无漏排、错排现象，将排料信息传递到数控裁床， 实现省时省料的剪裁自动化。 2 1 服装排料的原则 不管是手工排料还是计算机排料，对于服装排料都要遵循以下三个原则： 1 ) 符合服装制作工艺要求，对于这个要求，首先考虑的是衣片的对称性， 组成服装的衣片基本上是对称的，如上衣左、右袖片，裤子左、右裤片等。然 后考虑的是面料的方向性。面料的方向性其一是指面料的经向和纬向，其二是 指面料的表面状态，所谓面料的表面状态是指一些种类的面料沿经向和纬向， 其表面状态具有不同的特征和规律。这些面料种类包括毛绒面料、条格面料、 图案面料。 2 ) 保证设计要求，保证设计要求这一原则主要用于条格面料的排料中。当 设计的服装款式对面料条格有一定要求，排料的样板便不能随意放置，必须保 证排出的衣片符合设计要求。 3 ) 节约用料，排料的重要目的是节约面料，降低产品成本。服装排料经验 可以用以下四句话概括“齐边平靠，斜边颠倒；弯曲相交，凹凸互套；大片定 局，空挡塞小；经短则省，纬满为巧”。 2 2 计算机辅助服装排料的优势 传统的排料是由人手工按照经验进行的，虽然面料的利用率较计算机排料 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 略高，但是人工排料效率低、速度慢、劳动强度大、差错率高。而计算机排料 是根据数学优化原理，利用图形学技术设计而成的。把传统的排料作业计算机 化，把排料师傅丰富的经验和计算机具有的快捷、方便、灵活等特征结合起来， 从而快速获得较高的面料利用率。 计算机辅助排料与传统手工排料相比，其优势在于以下四个方面： 1 ) 计算机排料可多次试排，并精确的计算各种排料图的面料利用率，以寻 找最佳衣片组合方式，从而获得较高的面料利用率。同时，由于计算机高度的 精确性，不会漏排或重排，降低了差错率。 2 ) 排料操作人员在计算机屏幕上进行排料，一方面可减轻手工排料时来回 走动的劳累；另一方面可通过换屏等操作纵观全局，以进行较好的衣片布局。 3 ) 计算机排料可大大减小手工排料时占用较大的厂房面积、同时排料的信 息有助于用来进行各方面的管理，如估料，成本核算等。 4 ) 计算机排料信息可传输给自动裁床直接用机器代替人工裁剪。 2 3 计算机排料图设计的规则n 3 不管是手工排料还是计算机排料， 合理的样板排放形式。要达到此目的， 料： 其目的都是要找出一种用料最省、排列 从大的方面来讲，一般要按下述规则排 1 1 先大后小，先排面积较大的衣片，后排面积较小的衣片。 2 ) 交叉排列，形状凹凸或大小头的衣片交叉排列。 3 ) 防止倒顺，在对衣片进行翻转或旋转时特别注意防止“顺片”或“倒顺 毛”现象。 4 ) 大小搭配，几件套排，特别是当大小不同规格的纸样套排时，相互搭配， 统一排放，不同规格之间的纸样取长补短，实现合理用料。 2 4 计算机排料方法n 1 计算机排料方法一般有人机交互式排料和半自动、全自动及智能自动排料。 目前大多数的服装排料系统采用人机交互排料。 1 2 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 2 4 1 人机交互排料 人机交互式排料是指按照人机交互的方式由操作者利用鼠标或键盘根据排 料的规则和排料时的经验将各种不同款式及不同号型的衣片样板通过平移、分 割、翻转等几何变换来形成排料图。其中，每排放确定一个衣片，系统会随时 报告己排放的衣片数、待排衣片数、用料幅宽、用料长度、利用率等信息。这 种方式多用于服装生产企业正式的裁剪过程。 2 4 2 全自动排料 全自动排料是计算机完成所有衣片样板的自动排放。计算机按用户事先设 定的方式来自动配置衣片，让衣片自动寻找合适位置靠拢已捧衣片或面料边缘。 在排料的同时自动报告用料长度、面料利用率。待排衣片数目等信息，并自动 检查衣片的排料条件，如限制某一衣片可否翻转，限定旋转角度等。自动排料 在排料过程中无需操作者干预，因而速度快，但大多数软件系统的排料结果的 面料利用率与交互式排料比较均不十分理想，所以这种方式作为估料、计算每 款每套衣服的用料率使用，或用于比较规范的款式排料。 按用户事先设定的方式，自动排料又可分为设定排料时间、设定排料方案 数、设定面料利用率或前台自动排料( 排料过程显示在计算机屏幕上) ，后台自 动排料( 计算机屏幕不显示排料过程) 等。 2 4 3 半自动排料 是介于人机交互式排料和全自动排料之间的一种排料方式。只须指示待排 衣片，系统首先进行自动排放，然后由操作者人机对话地排其余衣片，最后产 生完整、合理的排料图或在计算机自动排料过程中操作者可随时干预，将排料 过程暂时中断，人工调整衣片排放位置，之后再恢复。 2 4 4 智能自动排料 采用最新的模糊智能技术，结合专家排料经验，能实现全自动排料。高效 1 3 东华大学硕士研究生学位论文 模拟退火算法在服装捧科中的应用与研究 自动调节，择优选择最好的排料结果，大大改进用料率。智能自动排料软件能 够模仿曾经做过的优化方案进行排料，还可进行无入在线操作，系统深夜持续 运转可处理大量排版任务，大大解决了排版人员的繁重劳动。此种系统可提供 两种排料方式：一种是一次完成( d r a f t ) ，速度快；另一种是设定一定的排料时 间，要求在一定的时间内完成( f u l l ) 。 另外，随着网络的迅速发展，目前还出现了一种网上自动排料方式，就是 通过网络把需要进行排料的衣片发送到相应的网站上，进行自动排料，排好后 再把结果发回，l o 分钟可排4 0 个。这种方式的优点在于企业不用购买排料软件 系统，节省了场地、资金，而且不需要配置人员。 2 5 计算机服装排料系统的实现功能 2 5 1 排料文件编辑 在进行交互式排料或自动排料之前，首先要编辑排料文件，包括农片排料 属性设置和排料单设置。衣片排料设置是指设置待排衣片的名称，衣片的号型 规格，正反片的数量，衣片是否允许进行翻转、切割、对格对条；排料单设置 就是要告诉计算机需要排料的服装款式、面料门幅、服装尺码、服装件数等信 息。 2 5 2 排料操作 根据用户所选择的排料方法进行排料。人机交互式排料可用光标选择衣片， 这是衣片随光标移动根据农片限制进行操作，如平移、翻转等。可移动光标确 定衣片移动方向以引导衣片捧放，计算机可自动将衣片移动到合适位置并靠至 已排衣片或布边。排料时还可以应用成组技术，即根据衣片的尺寸形状，把衣 片分成若干组，按照从大到小分组，经验证明，这样面料的利用率较高。自动 排料就是计算机自动完成所有衣片的自动排放。 1 4 东华大学硕士研究生学位论文 模拟退火算法在服装捧料中的应用与研究 2 5 3 排料图的输出 排料结果的输出主要是排料文件格式的转换和排料软件与绘图设备的连接 驱动。排料图的输出通常是通过绘图机打印在纸上，绘图机可以绘出并得到各 种任意比例的排料图，l ：1 的排料图作为裁剪的样板。每一块农片上都标有名 称和号型，以便在裁剪完成后，顺利、快速地完成衣片的打包工作。此外，绘 图机还可绘出小样以供向加工单位下任务单；或可存成迷你排料图用于存档或 用打印机输出作为硬拷贝存档。 2 6 服装排料的用料计算 2 6 1 按排料长度计算用料 当排料结束后，对每一排料图，即可得出其用料长度( 在这里排料长度是 指在排料图中所有衣片样板排放好后，所用面料的长度) ，再除以排料图中的服 装件数，即可得到平均每件服装的用料长度( 米件) 但是，在统计用料，只 能与相同幅宽的排料方案得出的用料量相比 2 6 2 按排料面积计算用料 对于每一排料图，在得出其用料长度后，将用料长度的长度乘以面料幅宽， 得到用料面积的平方米数，再除以捧料图中的服装件数，即得到平均每件衣服 用料的平方米数( 平方米，件) 。 2 6 3 计算面料利用率 面料的利用率有两种计算方法，一种是面积法，另一种是重量法。面积法 计算面料的利用率首先需计算用料长度后，面料的利用率等于排料图中所有衣 片样板的面积之和与使用的面料面积( 用料长度乘以面料幅宽) 之比。重量法 计算面料的利用率是指是所有衣片的总重量与捧料用掉的面料重量的比例。 东华大学硕士研究生学位论文模拟退火算法在服装捧料中的应用与研究 2 7 本章小结 计算机辅助排料作为服装c a d 的重要组成部分，在工业化大生产中起到了 快速、准确、高效的作