（控制理论与控制工程专业论文）零件最优排放布局问题的研究.pdf

零件最优排放布局问题的研究 摘要 二维零件的优化排样技术广泛的应用于制造工业、服装、皮革以及建筑行 业中，同时也是一个具有最高计算复杂度的n p 完全问题。长期以来，一直是众 多学者研究的热点。本文结合国内外的研究现状和排样问题的自身特点，针对 二维零件( 矩形、冲裁件、不规则零件) 排样问题的关键算法进行了深入的研究， 提出了一系列解决优化排样问题的算法，其主要研究内容有以下几点： 1 研究了矩形零件优化排样问题。矩形零件排样是不规则零件排样的基础， 国内外学者在这方面进行了很多探索，提出了多种算法。本人在分析这些算法 的基础上，通过比较分析，将遗传算法与模拟退火算法结合起来运用在矩形零 件排样中，并采用基于板宽优先策略的填充算法不断填充板材。本算法适合应 用于大批量、多种类的矩形零件在定宽无限长板材上的优化排样，获得了较好 的优化排样方案；通常对这类问题的研究通常设定板材种类为定宽无限长，但 在定长定宽板材上的排样优化问题确实存在于实际生产中，为此，本人提出了 一种针对不同排样零件在定长定宽板材上的排样算法。首先采用基于板宽策略 生成有许多组合矩形所组成的条料，转化一维问题，然后采用基于s t e p 策略确 定条料在板材上的排列组合从而确定了矩形零件的排样。 2 研究了冲裁零件的排样问题。本人把碰撞理论应用在冲裁件优化排样中， 通过增加对圆弧分段处理的步骤，采用直接对圆弧计算的方法，求解出零件的 碰撞距离，从而减少了计算复杂度，解决了排样件的非直线轮廓线性化所带来 的离散精度与计算效率的矛盾。 3 研究了不规则零件排样问题本人使用遗传算法，通过全局优化概率搜索 来产生最佳的排样次序和每个排样件的旋转角度，并结合计算机图形学知识， 用改进的平行线分割一步平移法，一次计算出了两个相交的图形不重叠所需移 动的距离，并用类最低水平线算法确定了每个排样件在板材上的定位位嚣。 4 研究开发了实用的矩形件优化排样系统和不规则零件排样系统。在完成 算法设计的基础上，利用v i s u a l b a s i c 作为开发工具，本人开发出了实用的矩 形件优化排样系统，此系统可提供四种优化算法；开发了不规则零件在矩形板 材上和不规则板材上的优化排样系统。 关键字：排样，遗传算法，退火算法，扫描线算法，一步平移法 t h er e s e a r c ho ft h eo p timlz e dl a y o u t o fp a r t s a b s t r a c t t h eo p t i m i z e dl a y o u to ft w o d i m e n s i o n e dp a r t si sb r o a d l yu s e di nt h ef i e l d so f m a n u f a c t u r i n g 、c o s t u m e 、l e a t h e ra n da r c h i t e c t u r e a tt h es a m et i m ei ti sa l s oaq u e s t i o n w i t ht h em o s tc o m p l i c a t e dc o m p u t a t i o n f o ral o n gt i m e 。i ti sa l s ot h er e s e a r c hh o t s p o t o fm a n ys c h o l a r s t h i sp a p e rc o m b i n e st h er e s e a r c ha c t u a l i t yo fb o a r da n da b o a r d w i t ht h e q u e s t i o n o fl a y o u ti t s e l f , a n d i tf o c u so nt h e k e ya l g o r i t h m o f t w o d i m e n s i o n e dp a r t s ( r e c t a n g l e 、p u n c hm o l d 、p o l y g o n ) ，t h ea u t h o rh a v ed o n ed e e p s t u d ya n dp u tf o r w a r das e r i e so f a l g o r i t h mo f o p t i m i z e dl a y o u t , i ti n c l u d e s ： 1 h a v ed o n et h er e s e a r c ho ft h eo p t i m i z e dl a y o u to fr e c t a n g u l a rp a r t s i ti s f o u n d a t i o no fr e c t a n g u l a rp a r t s ，m a n ys c h o l a r si nb r o a da n da b r o a dh a v e s t u d i e di n t h i sf i e l da n dp u tf o r w a r dm a n yk i n d so fa l g o r i t h m o nt h eb a s i so fa n a l y z i n gt h e s e a l g o r i t h m s ，t h ea u t h o rc o m p a r e dt h e s ea l g o r i t h m sa n dc o m b i n e dg e n e t i ca l g o r i t h m w i t hs i m u l a t e da n n e a l i n ga l g o r i t h m , p u ti tu s ei nt h el a y o u to fr e c t a n g u l a rp a r t s ，a n d f i l l e dm a t c f i c a lb yf i l l i n ga l g o r i t h mw h i c hi sb a s e do nt h es t r a t e g yt h a ti st h ew i d t ho f m a t e r i c a lf i r s t t h i sa l g o r i t h mi ss u i t a b l ef o ro p t i m i z e dl a y o u to fr e c t a n g l ep a r t sw i t h l a r g ea m o u n t sa n dm a n yk i n d sa n db e t t e ro p t i m i z e dl a y o u ti sg o t w h e ns t u d y i n gt h e p r o b l e mo fo p t i m i z e dl a y o u to fr e c t a n g l e ，w ea l w a y sa s s u m e dt h a tt h em a t e r i c a l sa r e w i t hf i x e dw i d t ha n di n f i n i t u d el e n g t h ，b u ti np r o c e s so fm a n u f a c t u r i n g ，t h em a t e r i c a l w i t hf i x e dl e n g t ha n df i x e dw i d t h a i m e dt ot h i sc o n d i t i o n ，t h ea u t h o rp u tf o r w a r da k i n do fa l g o r i t h mw h i c hs u i t st ot h em a t e r i c a lw i t hf i x e dl e n g t ha n df i x e d w i d t h f i r s t l y , i tc r e a t e dm a n yb a rm a t e r i c a lw h i c hi sc o m p o s e dw i t hc o m b i n a t i o n r e c t a n g l e i tu s e ss t r a t e g yw h i c hi sb a s e do n w i d t ho fm a t e r i c a l ，a n dt r a n s f o r mi tt o t h el a y o u to fo n ed i m e n s i o n ，a n dt h e np e r m u t a t i o na n dc o m b i n a t i o no fb a rm a t e r i c a l a r ec o n f i r m e db yt h es t r a t e g yw h i c hi sb a s e do ns t e p ，s ot h el a y o u to fr e c t a n g u l a r i i i p a r t sc a l lb er e a l i z e d 2 h a v ed o n et h er e s e a r c ho ft h el a y o u to fp u n c hm o l d f o rt h i sk i n d o f p r o b l e m ，t h e a u t h o rp u tc o l l i s i o nt h e o r yi n t ou s eo fo p t i m i z e dl a y o u to fp u n c h m o l d ，a n db ya d d i n gt h es u b s e c t i o ns t e po fa r c ，a n dd i r e c t l yc o m p u t et h ec o l l i s i o n d i s t a n c eo fa r c s ，s o i td e c r e a s et h e c o m p u t a t i o nc o m p l e x i t y , a n d s o l v et h e c o n t r a d i c t i o no f c o m p u t a t i o ne f i 3 e i e n e ya n dd i s p e r s ep r e c i s i o n 。 3 h a v ed o n et h er e s e a r e ho f t h eo p t i m i z e dl a y o u to f p o l y g o np a r t s f o ro p t i m i z e d l a y o u to fp o l y g o n ，t h ea u t h o ru s e dg e n e t i ca l g o r i t h m ，w h i c hc a np r o d u c et h eb e s t s e q u e n c ea n dr o t a t i o na n g l eo f p a r t sb yg l o b a lo p t i m i z a t i o np r o b a b i l i t y ，a n di n t e g r a t e t h ek n o w l e d g eo fc o m p u t e rg r a p h i c sw i t hu s i n gi m p r o v i n gp a r a l l e lm o v i n g a l g o r i t h m ，a n dc o m p u t e t h ed i s t a n c et h a tt w o o v e r l a p p i n gp o l y g o n s i s n t i n t e r s e c t i n g ，a n du s i n gi m p o v i n g “t h el o w e s th o r i z o n t a la l g o r i t h m i tc a nt h ep o s i t i o n o f e a c hp o l y g o n 4 h a v ec a r r yo u tt h es y s t e mo fr e c t a n g u l a rp a r t sa n dt h es y s t e mo fp o l y g o n p a r t s o nt l l ef o u n d a t i o no fc o m p l e t i n ga l g o r i t h md e s i g n ，t h ea u t h o ru s ev i s u a l b a s i c a sd e v e l o p m e n tt o o l ，a n dc a l t yo u tt h es y s t e mo fr e c t a n g u l a rp a r t s i tc a np r o v i d ef o u r a l g o r i t h m s ；a n dr e a l i z e t h el a y o u to fp o l y g o np a r t si nr e c t a n g u l a ra n dp o l y g o n m a t e r i c a l s k e yw o r d s ：l a y o u t ，g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h r a ，p a r a l l e l a l g o r i t h m 青岛科技大学研究生学位论文 第一章绪论 在激黧豹市场竞争审，陲稳生产瓣成本、褥篱企监瓣生产效率、臻疆金韭 对市场的反映和虚变能力是企业保持长久竞争力的永恒难题。长期以来，在钣 愈、裁凌、玻璃、造纸等译多 予照菇簿遴行台爨黪、最优豹菸撵一壹是掰有释 技工作者孜孜以求的目标。排样过程不仅耗费奄业技术人员大擞的劳动，更严 黧匏是枣子接撵辩阑过长、耪秘懿羁麓察爨，大大酶羝了金韭瓣生产效霉霸受 渡的市场反应能力，增加了生产的成本。同时，由于排样时间太长，从而给材 糕采麴、生产繁采了缀大浆困挽。这些都遍切嚣簧对诗算极优化接撑按零避行 研究。 晷翦的饯化搀撵大郝是根据秘浏与缀验，采媛手工邀行排捞，工作攘丈且 效率和材料利用率都较低，很难适应现代多品种、小批鬣生产的要求。同时， 随着计算机技术以及自动加工技术在各个行业中应用的发展，为伐化萎 样开辟 了新的途径。举个例子：对于镊众件剪裁，如暴没有计簿机，那么纯粹由人工 谶行手工排样，然后按照该排样结果对掇材进行剪裁和加工，这样排样的速度 鞠荮坏完全取决予排祥工入静熬练程度。僵是如莱给该众监配备一台计薄杌鞭 殿相应的优化排样软件，工人可以将零件的形状输入计辣机，让计算机进行排 祥，工夫灵需按照计算税瓣撵稃舔莱爵嫒材进行骛簸郢霹。这样将大大减少企渣 在优化排样工作中的工作量。让我们进行更一步的设想，如果能够将计算机和 器释燕王设冬送行集成，侵得诗簿税豹俊往莽 祥结栗冒激塞按邀经热工浚备， 那么将使得企业的生产效率大大提高，同时减少人为的藏错。因此，对计算机 绫往嚣 榉魏繇究将翼套嚣鬻深远豹意义。 。 优化费 样翘题摄述 由予优亿摊样应用薄豳非常广泛，因此吸弓l 了众多擎者对箕觚各种不嗣酶 具体应用、不同的角度，采用不间的方法进行了研究，以至于排掸问题肖了多 个名称_ 葶【1 分类方法。 零件最优排放布局问题的研究 1 1 1 排样问题的应用领域 工程应用领域中，型材和棒材下料、冲裁件排样、玻璃切割、报刊排版、家 具下料、服装裁剪、皮革下料、造船、车辆和发电设备生产中都存在大量的下 料问题。优化排样问题应用范围非常广泛，如表1 1 所示。 表1 1 排样问题的应用范围 t a b 1 1t h e b r o a ds p e c t r u mo f c u t t i n g a n d p a c k i n g p r o b l e m 应用分类 举例 钣金件n t工业用各种钣金件、厨房用具和家用电器用钣金件、打字机 和电子元件用钣金件、模具及链条链板、电动机用硅钢片、 造船业钣金件等 服装行业 各种布料、皮革排样，衬衫、西服、鞋袜、降落伞等，布料 皮革级中的优化排样等 纸业与玻璃业 办公用纸、财务用纸的裁制等，玻璃的裁制 印刷业排版各种书籍、模板、印刷电路板 集装箱货 将货物优化地装入有限空间的集装箱中 型材、棒材下料棒材、角钢、各种型材下料、建筑业中钢筋、铝合金下料 微电子工业 集成电路的排布 军事国防 图形目标的搜索等优化问题 1 1 2 排样问题的整体描述 下料问题的整体描述：( 1 ) 有两组基本数据，一组是大的原材料的尺寸( 一维 或多维) ，另一组是小的零件的尺寸；( 2 ) 将小的零件在原材料上进行合理几何组 合，切割下料，如何确定下料排样方案，以使得材料利用率最高。图1 1 是一个 管子或铝合金线材下料的例子。有数量不限的长度l = 9 8 的管予被切割成一系列 长度从5 至4 6 的小管予以满足每周生产的需要。 星i 卦萤! ! 定要! 删 = = = 昌詈i ，晕；誉告醛霜。；删 i 胃 ”描 ( a ) 原材料管子 ( b ) 需要的小管子( c ) 小管子的下料组合 图1 1 管材切割下料 f i g1 1c u t t i n go f t u b e s 青岛科技大学研究生学位论文 图1 2 是给定一系列同一规格或不同规格的板材，从中切割出一系列的小零 件，如何排放这些零件才能使所用板材数目最少。 口口嗣争圉团 ( a ) 原材料板材( b ) 待排零件( c ) 排放零件 图1 2 矩形件摊放问题 f i g 1 2c u t t i n go f r e c t a n g l e s 图1 3 是一个集装箱装货问题，这个问题同样也包含两组基本数据，一组是 集装箱，另一组是一些体积大小不一要装入的物品，如何将这些物品装入集装 箱，使所占用的集装箱数目最小。 1 1 3 排样问题的分类 瓣回国回回屺删 ( b ) 待装物品( c ) 密集装入 图1 3 集装箱装货问题 f i g 1 3c o n t a i n e ro f l o a d i n g 对排样问题的科学分类川和标识是全面了解和解决排样问题的基础。按照 是否为空间尺寸划分为狭义下料问题和广义下料问题，如图1 4 所示。 狭义排样问题可按零件的维数划分为：一维下料、二维排样和三维布局。 对二维平面零件排样问题，按被排零件、排样区域、优化标准和工艺要求进行 划分，如图1 5 所示。 p 簪 泛 l ( 零件最忧排放布局问题的研究 图i 4 排样问题的广义分类方法 f i g ，1 4 c r c n c r a i i z e d p h c n o r n o l o g y o f c u t t i n g a n d p a c k i n g p r o b l e m r嘲 i矩彤 r 燕瓣形挠l 三角形 r 形状与种类1 l 奠宙特殊雾边形 | 援则澎姨f - 一秘零孛 擗鞯l 数 淼b 椰则悴觎艇靛 厂下料方式 i 工装要求l 方彝鞋撵襻 i 排样间隙 l 抉刃敬数艇割 4 余辩爨夺标准 余料撼犬标准 后续齄理方便标准，、；、 器 霉 建缝 青岛科技大学研究生学位论文 排样聪域 ， 维数 足寸每教量 l 形靛 辕魅 一维毫疆( 寓窿鞭建，长瘫幂壤) 一维半蠢嫩( 宦窿珂选，长i 壹= 幂限) 斌缝有联 w ) ，约定板材的数量足以排下所有要 排的矩形件，所有要排的矩形件共有k 种，第i 种矩形件的个数为i i ，长度0 k 宽度为( 1 i k ) 。则全部要排的矩形件总数为：r l = 胛，。 i = l 排样基本目标是：使得排样所用的板材数尽可能少，以提高材料的利用率。 排样的基本约束条件为：矩形件之间不能有相互重叠的区域，并且矩形件不能 有排出板材之外的部分。排样规则为：从板材的最左下角开始排至板材的右上 角结束一块板材的排样，设板材左下角的坐标为( 0 ，0 ) 。一块矩形件在板材上的 位鼍可以由该矩形件的左上角和右下角坐标完全确定，设( 一，y 。) ，( x ：；，y 2 i ) 为 第i 块矩形件在板材上的左上角和右下角坐标( 1 i n ) ，则转化的排样过程就 是根据一定的寻优规则，确定每一块矩形件在板材上的左上角和右下角的坐标。 在一般的矩形件排样问题中，矩形件可以有横排或竖排两种方式，因此矩形件的 两个坐标存在两种关系 x 2 i = z l i + ，j ，y 2 f = y l l w f 或x 2 i i + w f ，y z l = y l i - - z ，i = l ，n ，前一种关系为横排， 后一种为竖排。由此可见，对于决定每一块矩形件的排放，实际上只有三个自 由变量，x ，y ，和决定矩形件i 横排或竖排的逻辑变量l ，则应有如下关系： ( 2 一1 ) 设r ，和r 。为任意两个矩形件，它们对应的左上角和右下角的坐标分别为 “ l p 叶 ) ) 一 _ l 卜 ( 一 + i i y 工 = = 屯 圪 ，、l 青岛科技大学研究生学位论文 ( ，y 。) ， j ：，y 2 t ) 移 工，；，y ，；) ，x 。y ：；) 则当下瓤靖况之一出现对，它 们互不蹩叠：恐。 并2 ，y y 。代入( 2 - 1 ) 式得， x ，+ ( 卜) f ；一_ w ， 鼻t f + ( 1 - ) + 1w f ，y n y ( 1 一) u t f s 要使褥任一个矩形秽置没有拱 出扳材之辨，剿它的嫩挺应鄹时满足z ，兰o x 2 l l ，y2 ，0 和y w ，由( 2 一1 ) 式得0s 工l - ( 1 一) ，一o 和 ( 1 一) + - ，y l ，gw ；这样，得到优化排样的目标函数为m a x * t ( 黾厂葺，) ( y 。，一y ：，) ，这里= 0 藏1 ，总结上面分析，得到优化排样的数 ，= l 学穰窒舞 兄) l t + r f 啦) ( ( 1 一) 毪+ 毛) ( 2 - 2 ) 约柬条件为： r u ( z ，一x l ，( 1 一) 一。比) + u ( x 1 。x i t - - ( 1 一r ，) i ，”r f w ，) + u ( y 1 。一( 1 r 。) w ；r 。l ， i | 一y h ) + h ( ，l ，一( 1 一) 珥一5 l , 一y “) l jo x l l ( 1 一) z ，一堆 j l ( 1 - 5 ) w t + 5 l ，y s w | | s t ，。o 或1 ，：，2 0 。r1 b 。t 。i = t ，2 ，k 0 l 0 x o 出( 2 3 ) 式冒戮看出，矩形伟辩样淹禳稽当复杂，蠢蓠在瑾谂土还没肖穰寄 零件最优排放布局问题的研究 效的求最优解的方法，但在生产实际中，要求解决此类问题，因此必须根据具 体加工工艺要求，通过设定一些寻优规则来降低求解的复杂性，获得比较好的 近似最优解。 优化排样问题( 求板材利用率最大) 属于最优化问题，也可描述为下述数学 规划模型： r m a x f ( x ) js tx e r i r g u( 2 - 4 ) 式( 2 - 4 ) 中，x = x ，x ：，x 。 7 为决策变量，坟x ) 为目标函数，x r 和r c u 为约束条件，u 是基本空间，r 是u 的一个子集。满足约束条件的解x 称为可 行解，集合r 表示由所有满足约束条件的解所组成的一个集合，叫做可行解集 合。它们之间的关系如图2 1 所示。 可行解 图2 1 最优化问题的可行解及可行解集合 f i g 2 1t h ef e a s i b l ea l $ w e ro f t h ep r o b l e mo f o p t i m i z a t i o n 2 矩形件排祥的混合遗传算法 2 2 1 混合遗传算法简介 2 2 1 1 遗传算法简述 遗传算法( g a ) 。3 7 1 是一种人工智能的方法。它的机理是基于达尔文的生物 进化论的适者生存的生存原理，它是一种抽象的概率优化方法，仅仅利用个体 受鸢 厶 青岛科技大学研究生学位论文 的适应度避彳亍群体鲍优他，不需袋优化模型中的舅标函数翻约束溺数的母数信 怠，因而具有狠强的鲁棒性，适合各种优化阔鼷。遗传算法利用论文变蹩编码 张论文变量空间进行多点搜索，突变算予能避免交叉繁殖收敛于局部优良个体， 并保持群体搜索蠡每多样穗，这些保证了遴传算法其有更磷盼垒弱寻侥麓力。照 外由于遗传算法搜索过程中保持群体规横不变，因而具商潜在的并行性，所以 它适台解决复杂游、大黧豹优健游逶。这些特蠢馊褥速健算法律为概率援索、 并行算法中的一个关注方向，广泛被使用于各领域，在电力系统生产、运行过 糕静舔究牵，逮祷算法毽墩褥了袋丈豹袋凌，诸麓；毫嬲矮翔，无功馨馁，经 济调度等等。 遮赞蓑法钵经过鳋鼹，霉致绍隽逡熬透錾最饯解。痰手蠡然器饯驻劣汰秘 自然选择的作用，生活夜自然界中的生物体一代代地进化，这些进化发生在作 为生物锩结 鸯编秘嚣染毯体上，遽过对染色体鹣译疆及懋物雾孛瓣遥转终曩过 程而不断生成新的染色体( 生物体) 。自然选择、繁殖过程膏效的实现了生物体既 蠢遗传又有变异秘进化懿特点。它利用鬈弛编礤技术作用于染骰体豹基鞭中， 矮基本指簿思想怒模拟遗些串组成的个体的进化过程，废用于实际过程中把进 他过程与工程方案的优他选择类比，通过把工程坶题的解化为生物进化中豹染 色体表示出来，将以遗传操作为特征代表的生物进化过程作用予工程问磁的各 科l 方案，从而实现对各工程方案性能、代价等各方面的综合评价，最后得到问 藤的一系捌优纯方案一即若干数麓的往黥较好的染色体。由于逢传算法以点静 集台而非个点谯整个空间中作火范围搜索，并以染色体向性能较好的方向转 交彳乍为援索酶方向指导。 遗传簿法中，将1 1 维决策向爨x = 【x ，x ，x 。】1 用n 个记号x ；( i = l ，2 ， n ) 所组成的符号串x 来袭示：x = x ，x ：x f + x 一 x ，x2 ，x 。17 ，把每一个x ； 番作一个遗传基阂，它静所有可能取毽称为等往蕊遴，这样，x 就霹看佟蹩交n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度1 1 是固定的，但 对一望闻惩n 毽褥瑗燕交纯懿。缀攥不鬻懿慵凝，这攀豹等往鏊蠢鼙蔽楚组 熬数，也可以是浆一范围内的实数值，或者是纯粹的一个记号。最简单的等位 蒸透是囱0 窝l 这嚣巾熬数缝或熬，程寝豹染色俸藏蕞袭示秀一个二送剿籍号 串。染色体x 也称为个体x ，对于每一个个体x ，要按照一定的规则确定出其 逶盛褒。令彝酌邋应度与其对应黥令薅袭蠛垄x 鹣嚣栝瓣数毽稷关联，x 越接 零件最优排放布局问题的研究 近于目标函数的最优点，其适应度越大：反之，其适应度越小。 生物的进化是以集团为主体的，与此相对应，遗传算法的运算对象是由m 个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗 传算法的运算过程也是一个反复迭代过程，第t 代群体一记做p ( t ) ，经过一代遗 传和进化后，得到第什1 代群体，它们也是由多个个体组成的集合，一记做 p ( i + 1 ) 。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则 将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个良 好的个体x ，它所对应的表现型x 将达到或接近于问题的最优解x + 。遗传算法 的基本步骤： ( 1 ) 编码：将最优问题的解表示为一个基因串，即染色体，染色体中的各位 一基因对应于问题解向量中的各分量，编码方法可使用二进制、十进制、十六 进制等整数编码，也可按问题需要使用浮点数编码等； ( 2 ) 初始化：确定算法的群规模，杂交、突变概率值及对初始群中的各染色 体初始化，形成以后各步的操作祖先； ( 3 ) 对染色体进行评价，排序按照问题求解目标对解方案进行评价，性能好 的个体以较大概率直接进入下一代，性能较差的将参加下一步的各遗传操作过 程： ( 4 ) 遗传操作：遗传操作过程通过将遗传算子施加予各染色体上，实现生物 体遗传信息的交流和生物体的进化，在解决工程问题时，遗传操作过程的使用 可促进方案间的信息交流，以及多优化方案的出现。遗传算子主要有交叉、突 变、逆变等，具体操作过程这里不再赘述导； ( 5 1 终止规则：遗传算法循环执行计算适应值，选择复制和杂交变异算子，直 至满足某个停止标准。其基本流程如图2 2 ： 计算随 染 珥仉 染 幂 产生 适应 色 r a n d o m 0 ，1 接收新解，r a n d o m 0 ，1 是 0 ，1 区间内的随机数。 3 ) 令t 。+ 1 = 口t 。，k k + 1 ，其中口e ( o ，1 ) ，若满足收敛判据，则退火过程结束 否则，转2 ) 。 其中退火温度t 控制着求解过程向最小值的优化方向进行，同时又以概率 e x p ( 一a f t 。) 来接收劣质解。因此算法可以跳出局部极值点，从理论上只要初始 温度足够高，退火过程足够慢，算法就能收敛到全局优解。 模拟退火算法的构成要素如下： ( 1 ) 搜索空间q 搜索空间也称为状态空间，它由可行解的集合所组成，其中一个状态x 就代 表一个可行解。 ( 2 ) 能量函数e ( x ) 能量函数也就是需要进行优化计算的目标函数，其最小点为所求的最优解。 ( 3 ) 状态转移规则p 状态转移规则是指从一个状态x 。( 一个可行解) 向另一个状态x 。( 另一个 可行解) 的转移概率，它与当前的温度参数t 有关。 ( 4 ) 冷却进度表t ( t ) 零件晟优排放布局问题的研究 冷却进度表是指从某一高温状态t 。向低温状态冷却时的降温管理表。假设 时刻t 的温度用t ( t ) 来表示，则经典模拟退火算法的降温方式为_ t ( t 户i 寿嚣 快速模拟退火算法的降温方式为：快速模拟退火算法的降温方式为：t ( t ) = 二l ， l + t 这两种方式都能够使得模拟退火算法收敛于全局最小点。另外，在实际应用中， 为计算简便起见，也可用下式来进行温度管理：t ( t ) = k t ( t 1 ) 。 假设图2 t 3 某一能量函数的描述图形，如果搜索过程陷入局部最优点a ，若 要使搜索过程脱离这个局部最优点而到达c 点，则必须使系统至少要具有b 点 所对应的能量。亦即，这里必须允许能量函数值可以一时增大。 e b c x 图2 3 能量函数示意图 f i g 2 3t h ec h a i r to f e n e r g yf u n c t i o n 假设在状态x 。时，系统受到某种扰动而可能会使其状态变为x 一，与此 相对应，系统的能量也可能会从e ( x 。) 变成e ( x 。) ，系统由状态xo l d 变为状态 x 。的接受概率可由下面的m e t e o p o l i s 规则来确定： p 2 广1i f e ( x 。) e ( x o l d ) ( 2 5 ) 式f 2 - 5 ) 的含义是：当新状态使系统的能量函数值减少时，系统一定接受这 青岛科技大学研究生学位论文 个新的状态；而当新状态使系统的能量函数值增加时，系统也以某一概率接受 这个新的状态。固定温度参数t ，反复进行状态转移过程，接收概率p ( x ) 将服 从g i b b s 分布： p ( x ) = 圭e x p ( 一半) ( 2 - 6 ) 式( 2 6 ) 中，z 是使概率值正规化的系数。可见，随着温度参数t 的减小， 接收概率也逐渐减小，即能量函数增大的可能性也逐渐减小，最后系统会收敛 于某一能量最小的状态，该状态就可作为目标函数的全局最小值。 2 2 1 3 混合遗传算法p “4 遗传算法由于其运算简单和解决问题的有效能力而被广泛应用到众多的领 域。理论上已经证明，遗传算法能从概率的意义上以随机的方式寻求到问题的 最优解。但另一方面，应用实践表明，在遗传算法的应用中也会出现一些不尽 人意的问题，这些问题中最主要的是它容易产生早熟现象、局部寻优能力较差 等。并且般来说，对很多问题而言，基本遗传算法的求解效果往往不是解决 这个问题的最有效的方法，它比专门针对该问题的知识型启发算法的求解效率 要差。另外，遗传算法也无法避免多次搜索同一个可行解，这也是影响遗传算 法运行效率的一个因素。 另一方面，梯度法、爬山法、模拟退火算法、列表寻优法等一些优化算法 却具有很强的局部搜索能力，而另一些含有问题与相关知识的启发式算法的运 行效率也比较高。可以预计，在遗传算法的搜索过程中融合这些优化方法的思 想、构成种混合遗传算法( h y b r i dg e n e t i ca l g o r i t h m ) 是提高遗传算法运行效率 和求解质量的一个有效手段。 混合遗传算法是在标准遗传算法中融合了局部搜索算法的思想，其特点主 要体现在以下两个方面： ( 1 ) 引入了局部搜索过程。基于群体中各个个体所对应的表现型，进行局部 搜索，从而找出各个个体在目前的环境下所对应的局部最优解，以便达到改善 群体总体性能的目的。 ( 2 ) 增加了编码变换操作过程。对局部搜索过程所得到的局部最优解，再通 过编码过程将它们变换为新的个体，阻便能够以个性能较优的新群体为基础 来进行下一代的遗传进化操作。 零件最优排放布局阿题的研究 2 。2 2 矩形件排榉混合遗传算法 将遗传模拟退火算法遥用在矩形件排样中，利用遗传模拟退火算法的全局 搜索能力，寻找爨搀撑传疑忧的撼榉次序( 撼列最紧密) ，本文提燃基于叛宽恍 先策略的填充算法不断填充板材，获得近似总体麓优的摊样结果。适合_ 酶! 用于 大批量、多种类始矩形馋健纯排榉。 排样件的排样次序和辑自的旒转角度楚影响摊样布局效果的蓬要因索，如 何确定它们以产生最优的刳 样布局是一个n p 完全难题。采用人工智能领域中的 遗传模拟邋火算法，通过全局优纯概率援索来产擞最佳的摊样次序。速传模掇 遢火算法熄将遗传算法与模拟退火算法相结合而构成的一种优化算法，与基本 的遗传算法的总体运行遥稳褶类戳，遗镗模稼邋灾算法也蹙获一缀隧辊产生的 初始解( 初始群体) 开始全局最优解的搜索过程，像先通过选择、交叉、变异等 遗传搡俸采产生一缱薪虢令俸，然后霉独立缝霹掰产生密辩各个个体逶苻横接 遇火过程，以其结果作为下_ _ 代群体中的个体。这个运行过程反复迭代地进行， 煮潮满是萦个终止条俘为正。混会遗传算法基本构成框檠一4 5 1 如黼2 4 。 囤2 4 混合遗传算法基本构成框架图 f i g 2 。4t h eb a s i cf r a m ec h a r to fh y b r i dg e n e t i ca l g o r i t h m 青岛科技大学研究生学位论文 2 2 2 。1 染色体编码、解码方法 采用十进制编码，遗传算法的群体中模式的数目仅与群体大小和染色体长 度有关，它具有短的定义矩、低阶的优点。应用在排样问题中，设所有要排的 矩形件共有k 种，第i 种矩形件的个数为h ，长度，宽度为，面积为a r e a ，( 1 i k ) ，将所有参加排样不同类型的零件按面积大小排列并加以编号，染色体 的长度与排样矩形件的类型数k 相同，染色体中每个基因的编码即它的矩形件 号，染色体为有0 到k 的一个全排列。此编码方式是基于一种排列顺序的基因 编码方式，即所有排样类型的一个排列顺序作为一个染色体。编码设计的关键 是在染色体中如何产生不同编号的遗传算予，例如有6 中不同类型的排样零件， ( 532104 ) 表示一个编码，相应的解码方法则根据所采用的解码方法把具 体的板材定位在不同的板材上及其在板材上的具体位置。 2 2 2 2 遁应度函数的确定 排样的目标函数是板材的有效利用率为最高，但优化的目标函数是求函数 的最小值，因此适应度与目标函数值成反比。设板材为定宽、无限长，所利用 的板材长度为m a t l e n ，宽度为m a t w i d ，设s t r 为遗传算法优化产生的序列，则 排样的适应度函数为 k f i t n e s s ( s t r ) = ( m a t l e n m a t w i d ) ”fl i 嵋。 ( 2 7 ) i = 1 2 2 2 3 设计遗传算子 ( 1 ) 选择算子 采用轮盘赌与精英选择策略相结合的算法，把上种群中适应度函数值较 大的直接进化到下一代，其余的采用轮盘赌策略，具体方法是产生一个【0 ，1 】 f 之间的随机数p i c k ，若p i c k s u m f i 卢f i t n e s s ( j ) ，则第i 个个体被选中。 = o ( 2 ) 交叉算子 采用单点交叉，设有父个体p a r e n t l 和p a r e n t 2 产生子个体c h i l d l 和c h i l d 2 ， 零件最优排放布局问题的研究 先判断是磷发生交叉操作，若发生交叉操作，在 1 ，l e h r o m 区间随机产生交叉位 餮j c r o s s ，葵中i c t w o m 为染色体翡长度，c h i d l 继承p a r e n t l 在j c r o s s 之藩静编弱 和p a r e m 2 在j c r o s s 之后的编码，d l i l d 2 继承p a r e n t 2 在j c r o s s 之前的编码和p a r e n t i 在j c r o s s 之后熬缡璐。交叉摄佟安现靛关键是兹蓠保涯在交叉螽鹃缡璐不董霪复。 ( 3 ) 变界算子 按交：簿概率毪确定令锩c h i l d 懿缓礤链鬟莛秀发生摄终，蓑编褥位数生变 异，则该编码翻转。具体操作是随机产生鼹个界子【1 ，i c h r o m 三l 闯的随机数， 设必n u r n l 和n d i l a 2 将n u m l ，n 瑚缓之闻的弼值交蘸，如有一编码舞0 6 3 2 4 1 5 9 7 8 ， n u m l 为3 ，n u m 2 为6 ，则将3 和6 之间的编码交换，则变鼯后的编码为 0 6 1 4 2 3 5 9 7 8 。 2 。2 。2 。4 确定逮建算法瓣运纷参数 其缝基本运行参数为： ( i ) 群体p 的大小：h i = 2 0 0 ( 2 ) 交义撅率：曩旬。6 2 2 。2 。5 楼拟蘧火撩终 终止代数：t = 1 0 0 0 变异壤攀：芝煳0 0 5 经过交_ 义和变舜运算届，由两个父代个体p a r e n t l 和p a r e n t 2 ，主成两个子代 c h i l d l 和c h i l d 2 ，对由父彳弋个体稻予代个体掰维成的簿个个体组p a r e n t i 和e h i l d l 、 p a r e n t 2 和c h i l d 2 ，以概率p 接受个体为下群体中的个体，以概率( 卜p ) 接受子 代个体舞下彳弋群体孛静个俸，其中： p ：三一 l + e x p ( 华) ( 2 8 ) 丘和工分剐为父代个体和子代个体所对应静瓣酥蘑数德，t 为温度参数一 2 2 3 基予壤充篝法酶解璐方法 毒遗传算法产生一个个俸嚣缀褥嚣，熊否快逮求出其黠应豹瓣榉塑，缮篓 青岛科技大学研究生学位论文 所需板材的尺寸是一个关键，同时只有求出该个体所对应的排样图后，才能计 算其对应的适应度值，并对该个体进行评价。文献 4 6 提出的基于最左最下的 原则，采用b l f 算法，但此种解码策略对于单件、小批量的实现很容易做出解 码，而对于品种较多，具体某种零件的数量又很大的情况不适应。本算法采用 基于板材局部利用率策略的解码方法，为编程方便，设板材为定宽无限长，按 照所得出的最优的排样序列如“3 2 8 7 9 0 4 6 1 5 ”，首先对于编号为3 的零件在板材 宽度上进行横向和竖向试探，设n 1 和n 2 分别为该零件在板材宽度方向上横向 和纵向所能排放的最大数量如图2 5 所示。 在排放零件时，对于w 的情况，采用连续横排，而对于，。w 的情况，则 ( a ) 宽度方向横向排列 ( b ) 宽度方向纵向排列 图2 5 零件在宽度方向的排列 f i g 2 5s t y l eo fp a r t si nw i d t hd