（机械电子工程专业论文）基于nga的任意多边形优化排样技术的研究.pdf

摘要 本文采用二步法对任意多边形的优化排样技术进行了研究。首先，将零件 库中的零件根据其面积大小进行分类，把面积比较小的零件存成个填充库， 剩下的零件存成一个排样库。在此基础上，用基于小生境技术的遗传算法对排 样库中的零件进行排样：先建立优化排样的数学模型，根据该数学模型将多边 形在矩形板料上的排列方式转化为特定的编码，并建立编码和和排样方式的映 射模型，然后采用基于小生境的遗传算法对排样过程进行优化。为了减少排样 图中的空隙，提高材料的利用率，在采用n g a 对排样库中的零件进行排样的 基础上，本文通过一定的填充算法，将筛出来的填充库中的零件逐个填充到排 样图的空隙中，完成最后的排样。根据文中提出的思路，设计开发了能够实际 应用的优化排样系统。 关键词：优化排样；遗传算法；填充算法 a b s t r a c t t h i sp a p e rh a db e e nc a r r y i n go u tas t u d yo nt h el a y o u tt e c h n o l o g y o f a r b i t r a r yp o l y g o n s w i t h t w o s t e pt h e o r y f i r s t ，w e s o r t e dt h e a c c e s s o r i e si np a r t s s t o r a g ei n t ot w op o r t i o n sa c c o r d i n gt ot h e i rs i z e s ： af i l i - s t o r a g ew a se s t a b l i s h e dt oa c c o m m o d a t et h es m a l la c c e s s o r i e sa n d a1 a y o u t s t o r a g et ot h eo t h e r s t h e n ，t h et h e m ep r o v i d e de f f i c i e n tl a y o u t s o l u t i o n st ot h o s ea c c e s s o r i e so fl a y o u t s t o r a g ew i t hn i c h e dg e n e t i c a l g o t i t h ma sat 0 0 1 ：t h r o u g he s t a b l i s h i n gt h em a t h e m a t i c a lm o d e l0 f l a y o u t o p t i m i z i n gp r o b l e m a n d a c c o r d i n g t ot h i s m o d e l ，t h e t h e m e t r a n s l a t e dt h el a y o u to fp o l y g o n si nr e c t a n g l ei n t oas p e c i a lc o d i n go f g e n e t i ca l g o r i t h m f o l l o w i n gt h e s es t e p s ，am a p p i n gm o d e lb e t w e e nt h e c o d e sa n dt h e 1 a y o u t o fp o l y g o n sw e r es e t u p w i t h t h a t t h et h e m e o p t i m i z e d t h e l a y o u tp r o c e s su s i n g n i c h e d g e n e t i ca l g o r i t h m f o r d e c r e a s i n g t h ei n t e r s t i c e si nt h e l a y o u tp i c t u r e a n dp r o m o t i n gt h e u t i t i z a t i o nr a t i 0 ，w ef u l f i l l e dt h el a s tl a y o u tp r o c e s sb yf i l i i n ga l l p a r t so ff i l l s t o r a g ei n t ot h i sl a y o u tr e s u l tw h i c hb a s i n go r ln g am e t h o d a c c o r d i n gt o t h i s t h i n k i n g r o u t i n ed i s c u s s e da b o v e ，w ed e s i g n e da n d d e v e l o p e de f f e c t i v el a y o u to p t i m i z a t i o ns y s t e m k e yw o r d s ：o p t i m u ml a y o u t ；g e n e t i ca l g o r i t h m ；f i l la l g o r i t h m s 河海大学硕士学位论文 1 。1引言 第一章绪论 在激烈的市场竞争中，降低生产的成本、提高企业的生产效率、增强企业对市场的 反映和应变能力是企业保持长久竞争力的永恒主题。长期以来，在钣金、制衣、玻璃、 造纸等许多行业，如何进行合理的、最优的排样一直是所有科技工作者孜孜以求的目标。 排样过程不仅耗费了企业技术人员大量的劳动，更严重的是由于排样时间过长、材料的 利用率低，大大降低了企业的生产效率和企业的市场反应能力，增加了生产的成本。同 时，由于排样时间太长，从而给材料采购、生产带来了很大的困扰。这些都迫切需要对 计算机优化排样技术进行研究。 优化排样是指将不同数量和形状的零件摆放到一张或多张板材上，同时使板材利用 率最大。以下是一些常见的优化排样的应用领域： 钣金件加工：工业用各种钣金件、厨房用具、家用电器用钣金件、 件用钣金件、锁、链条链板、电动机用硅钢片、造船业钣金件等。 服装行业：各种布料、皮革排样。衬衫、西服、鞋袜、降落伞等。 的优化排样等。 纸业与玻璃业：办公用纸、财务用纸的裁制等等，玻璃的裁制。 木材制品：各种家具。 打字机、电子元 布料皮革定级中 印刷业排版：各种书刊的排版。 集装货物：将货物优化地装入有限空间的集装箱中。 绳棒的裁剪：建筑业中钢筋的裁用、机械工业中棒料的合理裁用等。 微电子工业：集成电路的排布等。 军事国防：图形目标的搜索等优化问题等。 目前的优化排样大都是根据目测与经验，采用手工进行排样，工作量大且效率和材 料利用率都较低，很难适应现代多品种、小批量生产的要求。利用计算机进行优化排样， 不但可以提高排样的速度，还可以使排样方法更加合理和优化，从而达到节省材料，提 高经济效益的目的。 同时，随着计算机技术以及自动加工技术在各个行业中的应用的发展，为优化排样 ) t 辟了新的途径。举个例子：对于钣金件剪裁，如果没有计算机，那么纯粹由人工进行 手工排样，然后按照该排样结果对板材进行剪裁和加工。这样排样的速度和好坏完全取 决于排样工人的熟练程度。但是如果给该企业配备一台计算机以及相应的优化排样软 件，工人可以将零件的形状输入计算机，让计算机进行排样。工人只需按照计算机的排 样结果对板材进行剪裁即可。这样将大大减少企业在优化排样工作中的工作量。让我们 1 河海夫学颁十：学位论文 进行更一步的设想，如果能够将计算机和各种加工设备进行集成，使得计算机的优化排 样结果可以直接送往加工设备，那么将使得企业的生产效率大大提高，同时减少人为的 差错。因此，对计算机优化排样的研究将具有非常深远的意义。 在人们对优化排样问题的研究中，通常都是将其抽象成二维平面上的多边形布局问 题，从而从数学上对其进行深入研究。在本文中所指的优化排样问题都是数学意义上的 优化排样。 优化排样问题是一个经典的n p ( n o n d e t e r m i n i s t i cp r o b l e m ) 完全问题【卜6 】一一n p 是n o n d e t e r m i n i s t i cp o l y n o m i a l 的缩写意思是非确定型的多项式算法。多项式算法是 指渐近复杂性与规模n 的幂同阶的算法。n p 完全问题是n p 类中最困难的问题。对于 n p 完全问题，至今还没有找到多项式算法。对于这类问题，以目前已成熟的计算理论 和算法，或者根本无法求解，或者求其解的计算量所导致的机时和费用足人们所不能接 受的。因此，求其有效近似满意解是必由之路。 1 2 排样技术发展概况 1 2 1 国内的研究状况： 国内针对矩形容器的情况，提出了许多解决方法。典型的排样算法或排样方案，如： 1 背包算法【7 】：对于板材和零件都是矩形的情况，通过将。个二维排样问题转化为 一个一维f 料问题，构造一个利用背包问题解法的矩形件排样的近似优化算法。 2 拟合算法【8 i ：该算法是受拼图游戏的启发通过将多种异形零件在板材上的优化 排样问题转化为多边形对多边形的填充问题：缚在板材上放入一个零件，就得到一个新 的彤状的板材多边彤，该板材多边彤的面积为放入垓零件以前的面积减去陔零件的面 积。然后再从剩下的零件中选择一个合适的束对这个新的板材多边形进行拟合填充，如 此循环下去，直至全部填充完毕。 首先，多边形都可以表示成每个顶点处的央角 口，和恢顶点到其2 个相邻顶点的距离 f f ，) 的集 合。并目这些参数与各顶点的坐标无关。称 口，i i ，r l ， 为多边彤的形状参数。被用来排样的板 材在丌始是一个矩形，它也是一个多边形。 从第个零件丌始，如果其个数大于1 ，则对 幽1 - 1 多边彤的形j 队参数 其进行中排和对排检测，并从中选 较好的1 个构造排样甲兀，并对酣面产生的排样 单元进行填允，使其凸化，从而构造出凸多边形的排样单元。当所有的零件部被构造成 河海大学硕士学位论文 凸多边形排样单元后，就可以对板材多边形进行拟合排样。 拟合的过程如下：先从板材多边形的第一个顶点开始，在所有的排样凸多边形中寻找 与该顶点能最佳配合的顶点。这里最佳配合是指以下的目标同时达到晟小： m i n i 口j 一口“i 和m i n ( 1 l j 一巩) + ( 一心) 】，其中l t k , 一l o ，k 吩 ( 七ki = 1 ，n k ) 其中，( a ，l l j ，r l ，) 为板材多边形顶点，的形状参数；( 口。l l 。，心) 则为排样多边形 k 的第岛个顶点的形状参数。如果上述条件满足，根据形状参数的定义，则包含顶点k i 的多边形可以放在板材多边形的顶点，处。如果口，口。，顶点k i 将与顶点j 重合，然 后选择m i n ( 1 l ，- l l h ) ，( 一，- r l h ) ，以决定将哪两条边重合起来：当口，吼时，选择 m a x ( f f ，一以，) ，( r l ，一r l 。) 】。选择的两条边重合起来后，将顶点k i 沿着板材上选定的边 内移动，使得顶点k i 能在顶点j 处排下。见图。 c ，既 图1 - 2 多边形在某一点的拟合 如果上述步骤能够成功进行，则包含顶点i 的排样凸多边形被成功地排放到板材地顶点 处。依次往下类推，知道所有的零件排样单元都被排完为止。 3 n f p 问题算法【9 1 ：n f p ( n o f i t - p o l y g o n ) 问题是指在一定的图形区域内，对一个已经定 位好的多边形，求另一个多边形与它正好碰撞 但不互相重叠的位置。如下图所示：多边形0 围绕多边形p 平移，假设顶点a 是参考点。顶 点a 的轨迹组成了这两个多边形的n f p 区域。 优化排样问题实质上就是图形的求交( 即判 断该图形是否与别的图形重叠) 和定位问题。该 算法地思想是：在排样过程中，一旦建立了零件 图1 3n f p 区域的形成过 的图形区域，求交和定位的过程就不再与图形的具体元素( 直线段或圆弧) 有关，而通过判 河海大学硕士学位论文 断图形区域之间的几何关系，就可以快速地求交、有效地定位。算法如下： 创建第一个多边形零件的区域； 求第一个多边形零件的包络矩形，将第二个零件紧贴着第一个多边形零件的包络矩 形，放在该包络矩形的上方，并且第二个零件的左下角和第一个零件的包络矩形的左上 角重合； 将第二个多边形向下移，每移动一个单位都计算两个多边形相交的区域面积，如果 为零，表示还没相交。否则相交，停止移动。并将该多边形放置在此位置。 在实际排样中，多边形还可以在上下左右不同的方向上移动。 4 基于样图的排样及其样图检索方法【l o l ：这种算法是一种基于人工排样结果的方 法。当人工进行零件排样时，在对待排零件做了考察之后，一般要对工厂中已经完成的 大量零件排样施工图进行分析，看是否有与本次待排零件组在特征上相似的样图。如果 有，则以此作为参考，完成排样。这实际上就是人工智能中的基于实例的推理方法。这 样，基于实例的推理方法可以应用于零件排样问题并产生基于样图的布局方法。 该文作者设计了一个基于样图的排样系统，由推理机模块、样图图形数据库模块和 用户界面组成。其中推理机模块是核心模块。其进行推理的主要依据是图形的特征匹配。 关于特征匹配则用的是基于结构特征的方法，这里使用的是中轴变换方法提取图形简化 骨架。然后，将样图中所有多边形的几何特征保存成样图库，以便进行零件间的匹配判 断和样图的相似性检索。 文中把多边形在进行中轴变换时每次产生的一对骨架作为图形简化骨架集的模式 基元，整个骨架表示图形的形状( 拓扑) ，骨架的长度数值表示图形的几何( 尺寸) 。简化 骨架集中所有具有不同长度数值的骨架表达了图形的尺寸等几何特征信息。对骨架线条 长度采用编码字母表方法表示，用英文字母表中前n 个小写字母( 这里取l o ，即a 到j ) ， 形成编码串。选出两个或两组图形的简化骨架，集中骨架长度的最大值l m a x 与最小值 l m i n ，分别对应到数轴上相应的位置。把数轴上从骨架长度最小值l m i n 到最大值l m a x 的区间等分成n 等份( 文中为l o ) ，每一个小区间的长度是( l m a x l m i n ) n 。把骨架长度 数值l i 落在最小值区间，即l i l m i n ，l m i n + ( l m a x l m i n ) n 1 的骨架，以字母表中第1 个 字母( 文中为a ) 表示；把骨架长度数值l i 落在最大值区间，即l i l m i n + ( n 一1 ) ( l m a x l m i n ) n ，l m a x 】的骨架，以字母中最后1 个字母( 文中为j ) 表示。依此类推，根据骨 架长度数值在数轴上的不同区间，分别以字母表中不同的字母表示。为了更精确地描述 每一条骨架，骨架的长度数值将作为属性描述补充到结构符号中。 设待排零件组为a = a l ，a 2 ，a n ) ，a i ( i = l ，n ) 为待排零件，n 为待排样零件个数，所 需板材为a 0 。排样样图上零件组b = b l ，b 2 ，b m ) ，b i ( i = l ，m ) 为样图中已排好的零件， 河海大学硕l 学位论文 m 为样图中零件个数，板材为b o 。设待排样零件组总面积为s a 排样样图上零件组总 面积为s b ，则两个零件组面积需满足条件s a s b ，零件个数n m 。待排零件组a 与 排样样图b 的匹配判断依以下优先序列进行：首先，进行图形组总面积和零件图形个 数的比较，若a 和b 之间相近，则认为两图形组可能匹配，否则不匹配。然后计算骨 架编码串之间的f i n d l e r 距离，作为图形组相似性度量的数值。骨架编码串之问的f i n d l e r 距离的判断方法是，零件组中的零件按面积递减的次序排序。然后把排序后的不同零件 的简化骨架编码串连接起来，组成一个长编码串作为零件组的编码串，进而计算不同零 件组编码串自j 的f i n d l e r 距离，作为零件组间匹配性度量。 5 人工神经网络法1 ：此算法利用 自组织人工神经网络解决二维不 规则零件的排料问题。其模型如图 1 4 所示。其中，输出神经元节点 表示零件的参考点；输出神经元节 输出仃点 点之问的连接表示零件在板材上b 的蘑叠面积；输入节点的数目与排 料的维数相等。在算法中，每个零件 的位置由向量w ，= w 。w ， 表示。 其中w 。w ：，分别表示第f 个零件参 嗍1 4 自组织神经网络对麻排样算法摸刑 考点的x ，y 坐标值。 自组织排样的详细过程如下： ( 1 ) 初始化各个零件随机分自i 在板料的中心附近； ( 2 ) 随机选择一个零件进行旋转，比较旋转前后零件的重叠而积，选择较小的那个 方案。 ( 3 ) 随机选择两个零件进行交换，如果交换后的面积矩小小于原方案，则4 i 交换。 ( 4 ) “生个新的输入向量x ( f ) = x 1 ( f ) ，x 2 ( t ) 】。 ( 5 ) 确定最接近输入向量的零件，并计算学习率目( ，) 及邻域大小月6 ( ，) 。 ( 6 ) 对位丁邻域之内的零件的位置进行更新。 ( 7 ) 增加f ，如果重叠面积 f 日或f = tma x ，则停i 卜。台则，转步骤2 。 最初，通过给所有零件的位置向阜= 改定很小的随机值，使所有零件聚集在扳料的i 一 心| ；付近。然后，存自组织训练过程中输入均匀分柿存整个板料区域内的向量，来修改 这些位置向量。每给出+ 个输入向量，则汁算出这个输入向量与所有位置向量之削的欧 河海大学硕上学位论文 几里得( e “c ，de 日n ) 距离并找出对应于欧氏距离最小的零件p - ，。零件p - ，和在 p ，邻域内的其他零件的位置被修改，以使这些零件更加靠近当| j i 的输入。如果零件 p f 位于零件目的邻域内，零件p f 的位置可根据以下公式来进行更新： fw i f ，= w i f ，一1 + a k r l f ，f ( x i ，f w i j ，p 1 ) 【，2 u = w 2 “一1 + a k r l “( 工2 ，l w 2 一i ) 其中，7 。表示学习率，a t 的选取由零件f 和其他零件的重叠面积最小这个条件 柬决定，其取值范围为：o a k 1 。 1 2 2 国外的研究状况 由于排样问题属于n p 完全问题难以求得最优解，后来有人提出了启发式算法2 。”1 ， 但启发式算法的启发规则难以确定，排样结果时好时坏。后来又提出了一种交瓦式排样 方法，计算结果较稳定，但排样的效果并不好。p m s a d 和s o m a s u n d a r a m 7 1 吸收两种理论的 优缺点，针对3 种不同的问题提出不同的算法效果较好，但没考虑多种不州零件的混合排 样问题。 s e g e n r i e c h 和b r a g a i i 提出遗传算法解决了零件多件多排问题，即在定宽无限蚝的板 材上正交排列给定的矩形件，将排样问题转化为排列问题把问题的解表示成数字串的形 式然后冉进 n 堑择、交义和变异算予对数字串进行操作，从而求得新的解。把零件的编 号按排放顺序进行排列，这类似于一个染色体。既p = p 1 ，p 2 ，p n 其中1 1 足零件个数，p i 为整数，且有f 负之分，l p i n ，表示零件的编号，p i 为负只是表示零件作9 0 度旋转后再 排放。交叉和，变异算子操作就是改变零件的顺序和排放方向从l f l j 生不同的解。冈为 矩形件的正交排样的解空间是无限的，为有效地减少解的数量，该算法引入了b l f 条件 ( b o t t o m l e f f f i l l i n g c o n d i t i o n ) ，即在排样中任何个矩形件在不干涉或不超出边界的情况下 尽可能向f 、向左移动并尽可能放在可被填充的空白区域中。引入条件后矩形件解的 个数为有限个，从而大大减少了解的数量。由于零件形状千差万别，该算法对小规则件的 排样效果仍不是很好。 c i h a n h d a g l i 和p i p a t p o n gp o s h y a n o n d a 提出神绎网络算法i l 。浚系统有3 个模块： 神经州络模块、智能排样模块、优化模块。神经例络模块是用人们排样的艾际经验指导 计算机自动排样，实际卜是提供了选择的枞则。丌始排样时，准备好第一个模块然后：i 哿形 状各芹的长方形零件的图形信息和一些技术要求条件输入智能排样模块根抓：第。个模 块提供的范例和选择的规则对零件进 r 排样囚输出各种可能的排样结果，最后l b 优化 模块对排样结果进行优化，计算出材料利用率最高的选最优解。陔算法较好结合了人 的智能因素，使其排样具有智能性，但零件形状千差万别排样要求的条件随着1 u j 题的f i 河海大学硕士学位论文 同而不同，因此要求神经网络模块具有开放性，知识应不断更新，对各种不同的排样问题 提出更加详细、准确启发规则。 1 3 本文的研究目标 由上所述，对优化排样技术的研究具有广泛的理论和应用价值。而其主要的研究重 点则是排样算法。本文的研究目标就是提出一个具有实用价值的优化排样原型算法。 1 4 本文的研究内容 首先，本文介绍了目前被广泛应用于优化问题的遗传算法理论，然后将排样问题分 解为三大部分：筛选、排样、填充。先通过一定的筛选标准，将所有的多边形零件分类 成零件库和填充库。对零件库中的多边形零件，利用多边形的外部包络矩形，将多边形 的排样转化为矩形排样，再通过将矩形在矩形板料上的排列方式转化为特定编码的方 法，建立编码和和排样方式的映射模型，并采用基于小生境的遗传算法对排样过程进行 优化。然后再把填充库中的多边形，在该排样结果的基础上，采用对矩形容器进行网格 划分的方法对排样结果的空隙进行填充。再在此理论基础上，以v i s u a ic + + 6 0 作为开 发平台，m f c 作为工具库，开发具有实用价值的优化排样系统。 1 5 本章小结 本章介绍了优化排样技术的发展概况；不同类型的优化排样技术和国内外发展现 状；以及在此基础上提出了本课题的研究目标和研究内容。 河海大学硕士学位论文 第二章遗传算法及其在排样中的应用 2 1 遗传算法的原理和特点 遗传算法体经过解码，可以作为问题近似最优解。由于自然界优胜劣汰和自然选择 的作用，生活在自然界中的生物体一代代地进化。这些进化发生在作为生物体结构编码 的染色体上，通过对染色体的译码及生物界中的遗传作用过程而不断生成新的染色体 ( 生物体) 。通常而言，自然界的生物进化的发展、变化具有进化发生于染色体上，而非生 物体上，以及自然选择、繁殖过程有效的实现了生物体既有遗传又有变异和进化的特点。 同时生物进化本身并无记忆，所有有关个体产生的新信息均包含在个体所携带的染色体 的编码组合中。取源于生物进化过程的遗传算法是m i c h i g a n 大学的h o l l a n d 教授在二 十世纪六十年代提出的2 “。 它利用某种编码技术作用于染色体的基因中，其基本指导思想是模拟这些串组成的 个体的进化过程，应用于实际过程中把进化过程与工程方案的优化选择类比，通过把工 程问题的解化为生物进化中的染色体表示出来，将以遗传操作为特征代表的生物进化过 程作用于工程问题的各种方案，从而实现对各工程方案性能、代价等各方面的综合评价， 最后得到问题的一系列优化方案即若干数量的性能较好的染色体。由于遗传算法以 点的集合而非一个点在整个空间中作大范围搜索，并以染色体向性能较好的方向转变作 为搜索的方向指导。仅利用适应性信息，无需导数或其他辅助信息来进行迭代计算，所以 它一方面既不局限于对连续、可微问题的求解，同时又不易陷于局部最优。这些特点使 得遗传算法作为概率搜索、并行算法中的一个关注方向，广泛被使用于各领域，在电力系 统生产、运行过程的研究中，遗传算法也取得了较大的成功，诸如：电网规划，无功补偿， 经济调度等等。 2 2 遗传算法的基本步骤 由于遗传算法并不直接作用于参变量集，而是作用于参变量的某种编码上，所以遗 传算法本身具有很强的适应性，它不依赖于具体的问题模型，具有一般的标准模式，即遗 传算法的基本步骤： 1 编码 将最优问题的解表示为一个基因串，即染色体，染色体中的各位基因对应于问 题解向量中的各分量，编码方法可使用二进制、十进制、十六进制等整数编码，也可按问 题需要使用浮点数编码等： 河海大学顶 。学位沦文 2 初始化 确定算法的群规模，杂交、突变概率值及对初始群中的各染色体初始化，形成以后各 步的操作祖先： 3 对染色体进行评价，排序 按照问题求解目标对解方案进行评价，性能好的个体以较大概率直接进入下一代性 能较差的将参加下一步的各遗传操作过程； 4 遗传操作 遗传操作过程通过将遗传算子施加于各染色体上，实现生物体遗传信息的交流和生 物体的进化，在解决工程问题时，遗传操作过程的使用可促进方案间的信息交流，以及多 优化方案的出现。遗传算子主要有交叉、突变、逆变等。具体操作过程这里不再赘述； 5 终止规则 遗传算法循环执行计算适应值，选择复制和杂交变异算子，直至满足某个停止标准。 廿 产生 1 计算随机i 染淘汰 。 染染 m 个 芝譬卜 色适应色色 斗六 体 + 度低 体 体 随机 l 数值i 排的染交变 染色 体 序色体义异 。叠一 个_曩_墨圈 l 2 4 遗传算法的性能 圈2 1 遗传算法的基奉流样图 一些研究人员对进化算法的运行机理进行过研究，汪明了般的遗传算法不定收 敛，只有每代保存了最优个体时爿收敛。在实际应用中使用了上述结论来保自f 收敛性。 采用优秀个体保护法就是将每代中的最优个体，直接进入子代，柏应i f l | 汰其f 代中适应 度最差的个体，使种群规模不变。 对保存最优个体时遗传算法足收敛的结论的t f 叫足通过对遗传算法构造马尔柯丈 ( m a r k o v ) 链，因为遗传算法的进行过程是 个马尔柯犬过程。 当遗传算法收敛时，求到的解通常只是所要解决问题的最优解的一个近似解，或哲 叫满意解。从数学分析的角度看，收敛过科是一个无限逼近过科，而计算过程是一个白 9 弼海大学硕士学位论文 限自动机，因此通过遗传算法程序求得的解总是一个近似解。近似解与问题真正的最优 解的差是一个统计意义下的量，也就是说每次程序运行得到的解的质量可能是有较大的 差别的。 上面指出遗传算法程序求得的解是一个满意解，哪些因素会影响到解的质量? 这其 实也是遗传算法的性能问题。 首先要注意的是种群的规模要适当，种群规模太小，种群中就没有充分的多样性， 不利于适应度值高的染色体的进化，致使算法得不到满意的解。可以认为种群规模大有 利于种群的进化，种群健壮发展，但染色体多，每进行一轮进化花费的机器时间就多， 致使算法的效率低。 适应度函数的构造对遗传算法的性能影响较大，由于适应度是衡量染色体优劣的准 则，有时优劣染色体的适应度值没有拉开距离，必要提升优良染色体的适应度值，降低 劣弱染色体的适应度值，给优良染色体很多的生存机会，达到提高进化速度的目标。可 以结合所求解问题的实际情况对适应度函数作适当的变换，提高选择过程的效率。如下 有一个线性变换： 彳7 = c l ，+ c 2 式中，为个体的适应度，7 为经标度变换后的适应度值，q 、c ，为常数。 c 1 和c 2 的选取主要依具体问题的情况而定，并应满足一定的约束条件( 例如变换 后的适应度值不能是负值等) 。 适应度函数直接作用到了选择操作，也就是说选择操作的性能主要是由适应度函数 来决定，但是怎样运用适应度函数是需要研究的。 对遗传算法的性能影响最大的也许是交叉和变异操作，有很多文献对此进行了研究 的改进。首先是交叉和变异操作并不是都要进行，对某些问题遗传算法求解时其性能主 要由交叉操作决定，甚至没有变异操作时，算法的性能更好：而对另外的某些问题遗传 算法求解时其性能主要由变异操作决定，甚至不要交叉操作更合适。 交叉和变异操作的更重要的点是不同的问题要构造一些性能更优的交叉和变异操 作，才能保证算法的高效率，构造时往往需要对所要求解的问题进行分析和运用一些经 验。 交叉概率和变异概率选取也是遗传算法的性能影响最大的因素之一，直接影响着收 敛速度。我们着重讨论变异概率，变异概率大会扩大搜索范围，使搜索过程不陷入局部 极小，但也可能使正朝着最优解缓慢前进的个体改变方向，破坏好个体；变异概率大则 对染色体的破坏大，因此常设定一大一小两个变异概率，当整个种群平均适应度增长较 快时，使用小变异概率；反之使用较大变异概率。对整个种群使用相同的变异概率，并 不利于优良个体的成长和劣个体的改良。 让我们来回顾上一小节所指出的遗传算法常使用的收敛准则是每代保留最优个体， 河海大学硕士学位论文 这个要求其实也在降低算法的效率，因为将导致一些个体早熟和降低种群的多样性。 有一个新问题：交叉或变异产生的新个体能否与父个体进行竞争。按简单遗传算法， 交叉或变异产生的新个体不论优劣都取代父个体，并不科学。对新个体要有与父个体进 行竞争的机会，当父个体比新个体优时，按一定的概率保留父个体而舍去新个体。针对 这个问题，本文介绍了基于小生境的遗传算法( n i c h e d g e n e t i c a l g o r i t h m ) 。后面将会有 详细的介绍。 停止条件与解的质量有关系，由于所要解决的问题的最优解预先不知道，就连一个 供参考的近似解也不可能有，停止条件就成了一个值得研究的方面。如果按预设的进化 代数作停止条件，由于不同的问题的复杂度不同，而且对同一问题构造的遗传操作不同 其算法性能不同，因此很难合理地预设一个进化停止代数。另一个常用的停止条件是种 群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时，这 是一个比较合理的方式，但可能由于构造的算法在进化机制上存在不合理因素，出现进 化进程缓慢，或者个别个体早熟，导致过早结束运行，得到一个质量很差的解。 2 5 遗传算法在排样中的应用 目前为止，已经有人研究将遗传算法应用的优化排样中。 华中科技大学的曹炬等人利用遗传算法对大规模矩形件进行优化排样【2 引。排样容器 和排样零件都是矩形件，且矩形件的排放方式只有两种，横排或者是竖排，每一种不同 的零件大都有一个以上的数量。采用的是二进制编码，一条染色体是一组零件加工的排 样结果，一个基因即一个零件的排样结果。其具体数学模型如下： 设板材的宽为w ，长为l 。有k 种零件，其长，宽，数量分别为l i ，w i 和n i ( 1 i k ) ， 一般n i 是一个很大的数，零件在板材上即可以横放，也可以竖放。 然后用r i 表示第i 种零件的放置方式，r i = l 时表示该零件横放，r i = 0 时表示该零件 竖放。同时，规定板材在纵向方向上每行只能排放一种零件，同一行上的零件只能被横 放或者是竖放。用m i 表示第1 种零件横放时所需要的行数，1 1 i 表示该零件竖放时所需 要的行数；v i 表示横放时一行的零件个数；x i 表示竖放时一行的零件个数。 建立数学模型的目标函数为： r 缸w 加1 - r , ) n ，一+ 卅y f 】 - 】 遗传算法模型： 1 基因编码：一个基因包括两部分：怎么排( 即横排还是竖排? ) ，排多少? 如基 因p l = 01 0 0 1 ，表示该零件竖直排放，且同一行排9 个，如下图中的零件2 所示。每个 基因的头一位表示怎么排，是零度还是9 0 度。每个染色体可以表示为c = p l ，p 2 ，p k 。 河海大学硕士学位论文 图2 - 2 矩形零件排样示意图 2 初始化：设群体的规模为n ( 一般取n = 1 0 0 1 0 0 0 ) 。随机产生n 个位数为5 k 的以 二进制编码的染色体串作为产生种群。对每一个染色体计算其函数适应值。其适应度函 数就取数学模型中的目标函数。然后将这些染色体按适应度的大小进行排列，同时淘汰 不满足约束条件的染色体。 3 复制：每代中的每一个个体，按照其适应度值的大小决定它能够被复制到下一代 的概率，通过复制，使得群体中优秀个体不断增加。复制概率的选择“赌轮盘法”。 4 。交叉算子：采用按适应度高低依次配对。即适应值最高的染色体同次于它的染色 体配对，以下类推。只有这样配对能产生优于父代的子代染色体，同时机会较大，配对 后要产生足够多的新染色体，种群的规模不得少于n 。 5 变异算子：交叉概率选3 左右，随机选取染色体中任意两个互不相邻的基因互 换其位置。 6 停止准则：用两种方法来停止遗传算法的进行。一种是设定最大繁殖代数n ，也可 f， 以设定为利用率满足一定条件。取为，w ， 等。 - ，i l 四川大学的贾志欣等人提出一种基于遗传算法求解二维不规则零件排样问题的方 法，通过提取零件的最小包络矩形，将其转化为矩形件的排样问题【2 “。并利用“最低水 平线法”进行解码，转化为实际排样图。 他们研究了矩形件正交排样的遗传算法求解，其主要思想是将个体的编码视作一个 排列，通过一定的解码方法将编码转化为相应的排样图。其主要遗传算法求解过程是： 1 编码方法：文中采用的是带符号的十进制编码方式，将每一个矩形进行编号，依 次从l ，2 ，到1 1 。零件编号构成了一个整数串 p l ，p 2 ，p n ，1 | p i l n ，该整数串就 是一条染色体，按照一定的方式进行解码后，就对应了一种排样方式。而且这种排样方 式是唯一的一种。也就是说，每一条不同的染色体都与一种不同的排样方式相对应，是 一对一的映射关系。在该整数串中，每一个整数都代表一个矩形。并且这些整数还可以 有正负之分。正号表示零件不发生旋转，符号则表示零件旋转( 一般都是逆时针方向旋 转) 9 0 度。 2 解码方法：通过对b l 算法和下台阶法的改进，文中提出了“最低水平线法”。即 河海大学硕士学位论文 首先设置初始最高轮廓线为板材的最下面的边。然后，每当要排入一个零件p i 时，就 在最高轮廓线集中选取最低的一段水平线，如有数段，则选取最左边的一段，测试该段 线的宽度是否大于或等于要排入零件的宽度：如果该段线的宽度大于要排入零件的宽 度，则将该零件在此位置排放，更新零件最高轮廓线；否则，查询与最低水平线段相邻 的左、右两段水平线，将最低水平线提升至与高度较低的一段平齐，更新零件最高轮廓 线。重复上述过程，直至能排入该零件。重复上述过程，直至所有零件排放完毕。 3 适应度函数：适应度函数采用的是最高轮廓线以下的板材利用率： f ( p ) = a r e a a r e a l ， 其中，a r e a 是排入矩形件的总面积，a r e a l 是排样图高度轮廓线以下的板材面积。 4 交叉算子：将父辈的群体中的个体随机两两配对，进行交叉操作，该操作有可分 为两种：单点交叉和双点交叉。 5 变异算子：变异算子也有两种：一种是旋转变异，随机产生一个旋转位b i t ，以概 率p m ，对子辈个体中的b i t 位之后的矩形进行旋转，即将这些位中的整数改变符号。第 二种是位置变异。以较小的变异概率随机产生两个整数b i t l ，b i t 2 。对子辈中的个体中 的位于b i t l ，b i t 2 的两个整数进行对调，也就是将对应的两个矩形进行对调。 6 停止准则，当进化达到最大繁殖代数或者适应度值达到预定要求，则可以停止遗 传求解过程。 然而，文中并没有详细介绍如何提取零件的最小包络矩形以及如何通过它们的包络 矩形排样图来得到零件的实际排样图，同时，该方法受零件大小、形状的影响较大。 日本o s a k a 大学的k i k u of u j i t a 等人利用混合遗传算法对不规则的二维多边形进行 了排样b “。编码方式采用的是字符串编码，由于在每遗传完一次后，都需要对得到的排 样图进行调整，使得排样图上不再有重叠的多边形，因此称为混合遗传算法。进行调整 的办法是采用的是一个多维向量，每遗传完一代后，就求一次该向量的极小值。为了求 解该多维向量的极小值，需要列出多元方程组，用拟牛顿法求出该变元的最小值，然后 再按这个变元对排样图进行调整，从而使得排样图上不再有重叠或者相交的多边形。该 方法的缺点是计算量太大。这是因为上述向量是一个很长的向量，在用拟牛顿法建立方 程组时，方程组的变量太多，解这个方程组过于庞大，需要耗费大量的计算时间。所以。 其数学模型与以上两种所提到的两种排样方案都不一样： 如左图所示，假设板材是一个足够长的矩形，矩形的宽度一定，设为b 。假设多边 形零件在板材上所占据的高度为h 。零件超出板材的宽度为占。各个零件的面积为q ( f - l 一2 ，盯) 排样的目的就是为了使得在满足定的边界条件下，使得板材剩下得空 1 墩s c r a p 为最小： 河海大学硕士学位论文 i 瀑 r 一 b 一五 图2 - 3f u j i t a 的排样模型 整个求解过程如下图所示： r a i n s c r a p = ( b + 8 ) x h - q f - l 边界条件有 1 所有多边形之间的交叉面积必须为0 ； n - 1 月 o v e r l a p = o v e r l a p i = l z ，“ 2 同时，零件必须全部排放在板材之内 占= 0 。 图2 - 4f u j i t a 的遗传算法流程图 在遗传过程中，染色体编码也是采用十进制整数法。对每一个多边形零件依次进行 编号：1 ，2 ，1 3 。n 表示多边形的个数。则字符串p = p l ，p 2 ，p n 则表示一种排样 河海大学硕士学位论文 方式，即一条染色体。 遗传算法开始时，随机生成条染色体。然后再对染色体进行交叉、变异操作， 由于新产生的子代个体不能自动满足边界条件，染色体中各个零件之间会有重叠，以及 零件会排放到矩形容器时边界以外。为了使得子代个体满足这些约束条件，文中使用了 拟牛顿法对新产生的子代个体进行局部优化：设置一个一维矢量 “= ( 丸，妒矿f 叫妒y 矿，f 丸) 。嚣中的各个变量的含义如下图所示： 幽2 - 5f u j i t a 排样模型中的局部优化矢量 2 6 多边形排样中的积木块假设 遗传算法是一种基于串的集合的搜索算法，因此串的各子集的结构和产生对于整个 遗传过程的影响是非常大的。遗传算法的有效性已经通过积木块假设来解释。 模式的概念( s c h e m a t a ) ：模式主要是用来讨论串的各子集的优先级。我们将种群中 的个体即基因串中的相似性称为“模式”，模式表示基因串中某些特征位相同的结构， 因此模式也可解释为相同的结构。它描述的是一个串的子集，在二进制编码的串中，模 式是基于三个字符集( 0 ，l ，+ ) 的字符串，符号t 代表任意字符，即0 或1 。例如模式 河海大学硕士学位论文 + l + 描述了一个四个元的子集 0 1 0 ，0 1 1 ，1 1 0 ，1 1 1 。 在模式定理中所指的具有低阶、短定义距以及平均适应度高于种群平均适应度的模 式被定义为积木块( b u i l d i n gb l o c k ) 。它们在遗传算法中很重要，在子代中呈指数增长， 在遗传操作下相互结合，产生适应度更高的个体，从而找到更优的可行解。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) ：遗传算法通过短定义距、低阶以及高平均 适应度的模式( 积木块) ，在遗传操作下相互结合，最终接近全局最优解。 满足这个假设的条件比较简单，包括两方面： 1 表现型相近的个体，其基因型类似； 2 遗传因子间相关性低。 在多边形排样的遗传优化过程中，父代多边形排列方案里排列整齐的多边形将更容 易被遗传到下一代中，如下图所示的排样图中，染色体 1 , 2 ，3 ，4 ，5 ，6 ，7 ，) ( 父代1 ) 和 1 ，2 45 ，6 ，7 ，3 ) ( 父代2 ) 分别表示两种不同的排样方式。其中，父代l 中的子串 3 , 4 ) 由于排列较为合理，也就是具有较高的适应度，因此在与父代2 的交叉后，被保留到了 子代染色体 5 ，6 ，7 ，1 ，2 ，3 ，4 中。同理，父代2 中的子串 5 , 6 ，7 ) 也被遗传到了予代染色体 5 , 6 ，7 ，1 , 2 ，3 ，4 】中。这就是多边形排样中的积木块假设。 父 代 l 2 7 本章小结 图2 - 6 多边形排样中的积木块假设 本章先简要介绍了和遗传算法有关的几个概念，然后介绍了遗传算法的原理、特点 和基本步骤，讨论了遗传算法的收敛性和影响算法性能的几个因素，以及遗传算法在优 6 河海大学硕士学位论文 化排样中的典型应用。最后还分析了积木块假设在优化排样中的表现。 河海大学硕士学位论文 第三章基于n g a 和填充排样算法的基本原理 3 1 排样的基本原理 由于多边形排样是一个极其复杂的n p 问题，因此为了简化排样前的条件，以得到 适合于本文所提出的排样方法的多边形零件库，有必要先对多边形零件进行事先整理。 尤其是对于一些个别的相对较小的多边形零件，在利用遗传算法进行排样的时候，由于 要采用“最高轮廓线法”进行解码，而小零件占据的空间会受邻近的多边形的面积影响。 如果邻近的多边形面积相对该小零件的面积要大许多，则该小零件就会占用相对自身较 大的排样空间，直接影响了排样结果的好坏，如下图中的斜线阴影部分所示，该空间是 由零件2 造成的：当用最低轮廓线从零件2 最右面的边抬升到零件3 最右面的边时，广： 生了上述空隙。 同时，由于整个n g a 算法都是建立在多边形零件的包络矩形的优化排样上的，当 n g a 算法完成后，各个多边形与自身包络矩形问的空隙又会组成新的空隙。f f i i , l , 零件 正好n j 。以用来对这些空隙进行填充，这就是n g a 填充排样算法的糕奉原理。 凹3 - 1 小零什与犬零e l 放庄一起时产生的空隙图3 2 包络矩形与零仆之间的空隙组成