·50· 智能系统学报 第2卷 后排放， 取乃交叉点开始的基因顺序为1、6、7、5、2、3、 上述染色体的排样方案可能是第5、24号矩形 4,消除中已有的1、3、5，得到6、7、2、4，按此顺序决 件排入第2块板材，第1、3号矩形件排入第1块板 定x,O变为 材，第6号矩形件排入第3块板材.对于每个染色体 01:123,13516724) 所表示的排样方案由矩形匹配分割算法具体确定 同理可得： 也就是说，在遗传算法中通过调用矩形匹配分割算 02:132,234|6715) 法实现每个染色体所表示的排样方案.比如，对于上 2)方向交叉 述染色体，先选2号板材将矩形件排样，2号板材排 如果板材先旋转90°，根据矩形匹配分割算法 满后再将剩余的矩形件在1号板材上排样，1号板 中始终采用沿矩形件的竖边切割的规定，实际上是 材排满后再选3号板材对其余的矩形件排样 对板材实现了沿矩形件的横向切割.同样，矩形件放 如果只在一块板材上排样，可将板材部分的字 入板材时旋转90°可以调整矩形件的横排和竖排」 符全部设置为0.对于卷材，可将染色体中第2层板 因此，方向交叉只对染色体第2层的字符进行操作 材部分的字符全设为0，并将矩形匹配分割算法中 交叉方法如下： 的分割方向设为竖切，就可以实现矩形件在卷材上 设父代染色体为 的排样.这样，上述2层形式的染色体编码就可以具 123,1352467 P: 有比较广泛的适用性，为算法既可以应用于套排，也 010,0110100 可应用于单排提供了方便 132,2341675 1.3.2适应度函数 110,1001001 己有文献中用一个排样方案的板材利用率即板 交叉后的子代染色体O的第1层为P的第1 材上排放的矩形件的面积与板材面积之比的大小衡 层，第2层为P的第1层字符在B中所对应的第 量一个染色体的优劣，然而，余料面积相同而形状不 2层的0.1值.染色体O2的第1层为B的第1层 同，其可利用性是不同的，利用率应当包含余料面积 第2层为B的第1层字符在A中所对应的第2层 的大小和形状2个要素.因此，在适应度函数中采用 的0,1值.这样，得到子染色体如下： 了一个余料的长宽比例系数(0<B),当长和宽 123,1352467 相等时B最大 101,1011000 13.3交叉 132,2341675 由于矩形件的排放顺序和排放方向均产生不同 O2 001,011000 的排样结果，因此，设计了包括顺序交叉和方向交叉 1.3.4变异 的交叉算子在执行每次交叉操作时，随机确定是顺 由于板材横切或竖切的改变都将改变剩余矩形 序交叉还是方向交叉 的形状，从而使以后的排放方式发生变化.因此，变 1)顺序交叉 异操作只对染色体的第2层实施变异操作.根据变 顺序交叉只在染色体的第1层进行.在染色体 异概率在种群中随机选择出染色体和染色体的基因 长度范围内随机产生一个交叉点，这个点可能在板 位，对该位的基因值反转变异，即若为0，则变为1， 材部分也可能在矩形件部分.如果在板材部分就只 若为1，则变为0.由于变异操作，板材或矩形件的方 对板材顺序实施交叉，而矩形件部分保持不变.如果 向发生了变化，这样就需要对于变异点以后的剩余 在矩形件部分就只对矩形件部分实施交叉，而板材 矩形和矩形件重新调用矩形匹配分割算法， 部分保持不变.进行交叉操作时是保留交叉点前部 1.4矩形匹配分割算法 还是后部，每次也随机确定.交叉方法如下：设2个 为了实现“一刀切”，在剩余矩形匹配算法1的 父代染色体的第1层为 基础上提出了矩形匹配分割算法，按照先进行矩形 P:123,135|2467), 匹配后进行板材分割的原则进行.即首先在矩形件 P:132,234|1675) 中搜索与板材的一个边匹配程度最近的一个矩形件 “”为交叉位置，即对矩形件部分进行交叉.若保留 放入板材的左下角，然后再把板材分成2部分.由于 交叉点前部分，得到： 板材和矩形件都可旋转，因此，这里规定板材的切割 0:123,1351×××, 方向为竖切.算法主要步骤如下： 0:132,234|×××为 1)读入板材的长L和宽W,所有矩形件的长1 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net后排放. 上述染色体的排样方案可能是第 5、2、4 号矩形 件排入第 2 块板材 ,第 1、3 号矩形件排入第 1 块板 材 ,第 6 号矩形件排入第 3 块板材. 对于每个染色体 所表示的排样方案由矩形匹配分割算法具体确定. 也就是说 ,在遗传算法中通过调用矩形匹配分割算 法实现每个染色体所表示的排样方案. 比如 ,对于上 述染色体 ,先选 2 号板材将矩形件排样 ,2 号板材排 满后再将剩余的矩形件在 1 号板材上排样 ,1 号板 材排满后再选 3 号板材对其余的矩形件排样. 如果只在一块板材上排样 ,可将板材部分的字 符全部设置为 0. 对于卷材 ,可将染色体中第 2 层板 材部分的字符全设为 0 ,并将矩形匹配分割算法中 的分割方向设为竖切 ,就可以实现矩形件在卷材上 的排样. 这样 ,上述 2 层形式的染色体编码就可以具 有比较广泛的适用性 ,为算法既可以应用于套排 ,也 可应用于单排提供了方便. 1. 3. 2 适应度函数 已有文献中用一个排样方案的板材利用率即板 材上排放的矩形件的面积与板材面积之比的大小衡 量一个染色体的优劣 ,然而 ,余料面积相同而形状不 同 ,其可利用性是不同的 ,利用率应当包含余料面积 的大小和形状 2 个要素. 因此 ,在适应度函数中采用 了一个余料的长宽比例系数β(0 <β≤1) ,当长和宽 相等时 ,β最大. 1. 3. 3 交 叉 由于矩形件的排放顺序和排放方向均产生不同 的排样结果 ,因此 ,设计了包括顺序交叉和方向交叉 的交叉算子. 在执行每次交叉操作时 ,随机确定是顺 序交叉还是方向交叉. 1) 顺序交叉 顺序交叉只在染色体的第 1 层进行. 在染色体 长度范围内随机产生一个交叉点 ,这个点可能在板 材部分也可能在矩形件部分. 如果在板材部分就只 对板材顺序实施交叉 ,而矩形件部分保持不变. 如果 在矩形件部分就只对矩形件部分实施交叉 ,而板材 部分保持不变. 进行交叉操作时是保留交叉点前部 还是后部 ,每次也随机确定. 交叉方法如下 :设 2 个 父代染色体的第 1 层为 P1 : (1 2 3 , 1 3 5 | 2 4 6 7) , P2 : (1 3 2 , 2 3 4 | 1 6 7 5) . “| ”为交叉位置 ,即对矩形件部分进行交叉. 若保留 交叉点前部分 ,得到 : O1 : (1 2 3 , 1 3 5 | × × × ×) , O2 : (1 3 2 , 2 3 4 | × × × ×) . 取 P2 交叉点开始的基因顺序为 1、6、7、5、2、3、 4 ,消除中已有的 1、3、5 ,得到 6、7、2、4 ,按此顺序决 定 x , O1 变为 O1 : (1 2 3 , 1 3 5 | 6 7 2 4) . 同理可得 : O2 : (1 3 2 , 2 3 4 | 6 7 1 5) . 2) 方向交叉 如果板材先旋转 90°,根据矩形匹配分割算法 中始终采用沿矩形件的竖边切割的规定 ,实际上是 对板材实现了沿矩形件的横向切割. 同样 ,矩形件放 入板材时旋转 90°可以调整矩形件的横排和竖排. 因此 ,方向交叉只对染色体第 2 层的字符进行操作. 交叉方法如下 : 设父代染色体为 P1 : 1 2 3 , 1 3 5 2 4 6 7 0 1 0 , 0 1 1 0 1 0 0 , P2 : 1 3 2 , 2 3 4 1 6 7 5 1 1 0 , 1 0 0 1 0 0 1 . 交叉后的子代染色体 O1 的第 1 层为 P1 的第 1 层 ,第 2 层为 P1 的第 1 层字符在 P2 中所对应的第 2 层的 0 ,1 值. 染色体 O2 的第 1 层为 P2 的第 1 层 , 第 2 层为 P2 的第 1 层字符在 P1 中所对应的第 2 层 的 0 ,1 值. 这样 ,得到子染色体如下 : O1 : 1 2 3 , 1 3 5 2 4 6 7 1 0 1 ,1 0 1 1 0 0 0 , O2 : 1 3 2 , 2 3 4 1 6 7 5 0 0 1 , 0 1 1 0 0 0 1 . 1. 3. 4 变 异 由于板材横切或竖切的改变都将改变剩余矩形 的形状 ,从而使以后的排放方式发生变化. 因此 ,变 异操作只对染色体的第 2 层实施变异操作. 根据变 异概率在种群中随机选择出染色体和染色体的基因 位 ,对该位的基因值反转变异 ,即若为 0 ,则变为 1 , 若为 1 ,则变为 0. 由于变异操作 ,板材或矩形件的方 向发生了变化 ,这样就需要对于变异点以后的剩余 矩形和矩形件重新调用矩形匹配分割算法. 1. 4 矩形匹配分割算法 为了实现“一刀切”,在剩余矩形匹配算法[7 ] 的 基础上提出了矩形匹配分割算法 ,按照先进行矩形 匹配后进行板材分割的原则进行. 即首先在矩形件 中搜索与板材的一个边匹配程度最近的一个矩形件 放入板材的左下角 ,然后再把板材分成 2 部分. 由于 板材和矩形件都可旋转 ,因此 ,这里规定板材的切割 方向为竖切. 算法主要步骤如下 : 1) 读入板材的长 L 和宽 W ,所有矩形件的长 l ·50 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net