遗传模拟退火算法在服装排料中的研究

程 晖，唐明浩

（东华大学 信息科学与技术学院，上海 201620）

在服装行业制衣过程中，要想降低产品成本，提高原材料的利用率是一个非常重要的手段。服装排样就是按照某种算法合理地在原料上排放要切割的衣服样件，从而达到节约原材料的目的。传统的排样方法是由排样者凭借经验采用模板试切的方式进行的，一方面效率低下，而且排样方案的优劣完全取决于排样者的经验程度，这样就造成了很大的局限性。

在现代工业生产实际中，排样一般为不同形状样件的混合排样，这个属于NP完全问题，随着样件数量的增加，并将样件形状、角度等因素考虑在内，会使问题更加复杂化。本文提出一种启发式算法，同时将遗传模拟退火算法相结合，并应用到服装行业的服装样件的排样，以解决服装样件的混合排样问题。

1 基于BL策略的启发式排样算法

本文采用遗传模拟退火算法，通过全局优化概率搜索来产生最佳的排样次序和每个排样件的旋转角度，然后用启发式排样算法进行定位，实现自动排样。启发式算法采用众所周知的左下角（BL）策略[1]，每一个排样件从板料的右上角开始向板料的左下角平移，重复水平和垂直方向的移动直至无法再向左或者向下移动。启发式思想的本质是模拟人的智能行为，而排样对象的几何表达方式则是算法实现的关键。

1.1 排样对象的几何表达

不规则形状的排样件及样板的几何轮廓由直线段和曲线段组成，因为曲线段可以按一定的精度离散成直线段，所以排样对象最终为可能带有内孔特征或者无效区域的多边形。设G（α）为排样件G旋转α角度后的图形，G（α）最大和最小的 x、y 坐标值分别为 Xmax、Xmin、Ymax、Ymin。以间距为0.25个单位的水平扫描线顺序扫描G（α）的多边形区域，经过 G（α）的扫描线条数 N=int[（Ymax-Ymin）/4]，计算扫描线与多边形的相交区间，对于一条扫描线，可以分为4个步骤实现：

（1）求交。计算扫描线与多边形各边的交点。

（2）交点取舍。交点中，如果是多边形的局部最高点或者局部最低点的顶点（极值点），交点算作零个或者两个交点；如果是顶点但不是极值点，交点只算一个。

（3）排序。把所有交点按递增顺序进行排序。

（4）交点配对。第 1个与第 2个，第 3个与第 4个……每对交点代表扫描线与多边形区域的一个相交区间。这样，排样件可以看作是由一系列水平线段区间组成，如图1所示。

考虑到平面坐标中任何图形都只有x、y两个方向，所以实际操作中可以用2×n形式的矩阵来表示，如表1所示。这样既简洁，使用起来也方便。

表1 排样图形矩阵表示

矩阵中的“×”可以是实际操作中任意一个用不到的数字，例如 100，甚至更大。

本文中就是通过这样的方式来表示原料上已经排好的样件所占的区域用矩阵martx表示，待排的样件用同样的表示方法用矩阵martx1表示。布局过程中通过比较两者相同扫描线的区间来判断要做怎样的操作。

1.2 基于BL策略的启发式算法

启发式算法实现了排样件在原料上的紧密排列。假设排样件的排样次序和各自的旋转角度已经确定，并且也已对各排样件做好预处理，同时令排样件的最左最下处为移动基准点。排样的原料范围这里假设为宽度一定、高度不限的区域，具体可以根据实际需要进行修改。则基于BL策略的启发式算法对排样件队列按以下步骤进行操作：

（1）取第一个排样件 G（1），将它的基准点放在原料的坐标原点处，同时分别取扫描线 0至 G（1）的 y轴方向上的最大值（间隔0.25）进行扫描，并且将各扫描线得到的扫面区间以y轴、x轴升序（y轴优先）为原则进行存储，这样得到已排好的样件所占的区域用矩阵martx表示。

（2）按顺序依次取排样件 G（α）（α=2，3，…，N），将排样件的基准点放在坐标原点。初始化x、y方向上的移动距离，m=0，n=0。取扫描线 0到 G（α）的 y方向上的最大值（间隔0.25）进行扫描，得到各扫面区间进行存储，得到矩阵martx1。

（3）依次取 k=i，i=0 至 martx、martxt1 中 y方向上的最大值。

（4）当 k=i时，按顺序，martx中得到第一个区间（sx1，sx2），martx1 中得到区间（px1，px2）。

（5）判断（sx1，sx2）与（px1，px2）是否有交点：①有交点时，令 x=px2-sx1，将 G（α）整体向右平移 x个单位，判断平移后的 G（α）是否超出 x方向上的限制，即原料的最大宽度。若超出，将x方向上的平移量清零，即m=0；y方向上的平移量增加 0.25个单位，即 n=n+0.25；不超出，m=m+x，从 martx中得到下一个扫描区间（px1，px2），转步骤（5）；若没有下一个扫描区间，转步骤（6）。

②无交点时，martx中若有下一个扫描区间（px1，px2），转步骤（5）；没有，转步骤（6）。

（6）当martx中同一扫描线的所有区间都扫描过后，k=i+1，进行下一条扫描线的扫描，转步骤（4）。

（7）当所有扫描线完成后，可以得到 x、y轴方向上最终的平移量 m、n，将 martx1中的 x值加 m，y值加 n，得到新的 martx1′。对，martx′、martx1′按照同一扫描线的扫面区间从小到大原则进行合并，得到新的martx。

将图形的基准点放在坐标原点，若图形之间的重叠部分较多时，用以上的启发式算法排除出来的结果较为理想。但如果出现类似图2的情况时，结果就会出现排样件之间的重叠。原因在于扫描线k=0～0.55之间两者没有重叠的地方，真正需要移动的扫描线是从k=0.55开始。当k=0.55扫描完后，两个排样件在k=0.55之上的部分都已分开，没有重叠部分；但此时可以看到k=0.55以下的部分却出现了重叠，这是由于扫描线是以y轴正方向顺序扫描的，所以k=0.55以下的部分将不会再予以考虑。

考虑到以上的情况，本文对上述的算法进行了改进，增加了一个回测的环节，也就是从扫描线k=0开始重复扫描。一个简单的方法就是当一条扫面线i完成后，对它之前的0～i-1条扫描线进行重复扫描操作。但这种方法随着实际运用中排样件的数量的增加，重复操作的次数将会呈指数上升，大大延长了排样时间，影响效率。鉴于以上的不足之处，改进的部分将利用扫描线值i及排样件上移量n这两个量来简化这一个过程。

改进的算法为：步骤（5）中有交点的两种处理方法后，排样件或是在x轴方向被移动，或是在y轴方向被移动，此时计算扫描线i值与排样件上移量 n，如果 n＜i，则进行 i-n+1 条扫描线扫描（k=n，n+1，…i），并且重复4×i+1-4×n次操作。通过以上的改进，排样的结果将如图3所示，是理想中的效果。

2 模拟退火算法

2.1 遗传模拟退火混合算法

遗传模拟退火混合算法是将遗传算法和模拟退火算法相结合而构成的一种优化算法[2]。虽然遗传算法有较强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的问题，并且在进化后期搜索效率低。而模拟退火算法却具有摆脱局部最优点的能力，能抑制遗传算法的早熟现象。因此，考虑将模拟退火的思想引入遗传算法，有效解决遗传算法的选择压力。

与基本遗传算法的总体运行过程相类似，遗传模拟退火算法也是从一组随机产生的初始解 （初始群体）开始全局最优解的搜索过程，它先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对所产生出的各个个体进行模拟退火过程，以其结果作为下一代群体中的个体。这个运行过程反复迭代地进行，直到满足某个终止条件为止。具体算法流程可以参考文献[3]，算法能够在起始温度与结束温度之间充分地实现退火过程，且各温度呈线性变化。

2.2 个体适应度评价

在服装行业中，衣片总是放在一整块原料上进行排放，本文已经定义原料为指定宽度，但高度（长度）不限的情况。假设h为个体对应的排样结果的高度，待排任意多边形排样件从原料的最左最下方开始排放（这里采用h作为评价标准），高度越小，原料利用率最高，并且考虑到不同的排样结果有时会有相同的高度h，同时，为了区别两种高度相同的排样结果，这里需要再定义一个宽度d，宽度越小，原料利用率越高。定义遗传算法的目标函数为 f（x）=h（x）+d（x）。

这里将遗传算法的适应度函数定义为 1/f（x），则目标函数值将会转化成[0，1]中的一个数，且目标函数越大，适应度越小，这样有利于后面的选择操作，可以将较为理想的个体保留下来。

2.3 染色体编码

编码是应用遗传算法时首要解决的问题，也是设计遗传算法时的一个关键步骤。编码方法除了决定个体的染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型的解码方法。这里的解空间的表现型即排样件的排样次序和各自的旋转角度。

由于衣片排样件没有任何角度限制，因此不但要考虑 0～360°范围之间 的所有可能角度值，而且还包括排样件关于x轴或者y轴可能的镜像。参考文献[4]把几何形体的角度归纳为 0～89°范围内的基本角度和8个不同镜像之一的联合表示，8个镜像如图4所示。

假设有n个待排样件，第i个排样件带有整数编号i。 I=[i1，i2，…，in]是这 n 个待排样件的一个排列，ij是排列中第j个排样件的编号。在排列I中为每个排样件增加一个角度属性α，那么遗传个体的染色体编码为：

式中，ij是排列中第 j个排样件的编号，1≤ij≤n；αj是第 j个排样件的基本旋转角度，0°≤αj≤89°；flagj是第 j个排样件的角度镜像，1≤flagj≤8。

2.4 交叉操作

有两个个体 Xi、Xj在 [1，n]范围内生成两个不相等的随机数 p和 q，并且 p＜q，从 Xi中的 p位置处开始取（q-p+1）个基因，构成新染色体的前半部分，再从 Xj中取出其余未包含的基因构成后半部分[5]。

2.5 变异操作

以上分析的染色体基因位 （ij，αj，flagj）中包含两部分内容：排样件序号的属性、排样件旋转角度的属性，这里将变异过程也分成次序变异和角度变异两个部分来进行。次序变异改变排样序列，从而形成一个新的个体。在[1，n]范围内生成两个不相等随机数 p和 q，并令 p＜q，然后将两个位置上的基因对调。

角度变异是对基因位中的αj和 flagj分别用各自的等位数值来替换。αj的变异用[0°，89°]范围内的一个随机数去替换原值；同样，flagj的变异用[1，8]范围内的一个随机整数去替换原值。

2.6 遗传参数

为了提高求解效率、改善求解结果，本文对群体大小、交叉概率和变异概率这三个参数的选择使用了浮动数值。群体大小M随着待排样件数的多少而变化，这里取染色体的长度作为M值。若有n个待排样件，染色体的每一个基因位（ij，αj，flagj）长度为 3，则 M=3n。 为了保证“优秀”的个体得以保存而遗传到下一代，而“失败”的个体得以改善，个体的交叉概率和变异概率与个体适应度成反比。在每一代个体中，若最“优秀”的个体的适应度为 Fbest（X），最“失败”的个体的适应度为 Fworst（X），个体 Xi的适应度为 F（Xi），那么个体 Xi的交叉概率 Pc和变异概率Pm为：

2.7 模拟退火

经过交叉和变异运算后，由两个父代个体p1、p2生成两个子代个体c1和c2。对由父代个体和子代个体所组成的两个个体组 p1和c1、p2和 c2，以概率 p接受父代个体为下一代群体中的个体，以概率（1-p）接受子代个体为下一代群体中的个体，其中：

式中，fp和 fc分别为父代个体和子代个体所对应的目标函数值，T为温度参数。

本文的遗传模拟退火算法流程图可简单用图5来描述。

3 排样实例及分析

为了实例说明本文研究的排样算法的排样效果，在Matlab 7.6环境下对算法进行仿真。首先进行单一图形的排样，排样件的形状如图6所示，数量为16个，范围界定为15×8个单位。结果如图6所示，可以看到，单一排样件排样的结果还是令人满意的。

其次，对一件西裤的样板图进行实例排样。样板如图7所示，图中为两条西裤的所有部分，共28个，选择宽度为15个单位，高度为20个单位的区域作为原料范围。

因为待排样部分的数量为28，可以得到种群的大小M=3n=84，经过100次的迭代后，其结果如图 8所示，高度为9.2个单位；经过200次迭代结果如图9所示，高度为8个单位。从结果可以看出，本文的算法对于服装样板具有良好的排样效果，有一定的应用性。

本文将人工智能研究领域中的遗传模拟退火算法运用到服装行业的计算机排样领域中，通过在遗传算法的搜索过程中结合退火算法的思想，将与领域知识相关的局部搜索策略运用于单纯的全局优化概率搜索来提高衍化效率。利用遗传模拟退火算法的全局优化搜索能力，寻找出排样件最优（排列最紧密）的排样次序及各自的旋转角度，再结合启发式排样算法，得到了一种实用高效的排样算法。

[1]BAKER B S， COFFMAN E G， RIVEST R L.Orthogonal packing in two dimensions[J].SIAM Journal on Computing，1980， 9（4）：846-855.

[2]贾志欣，殷国富，罗阳，等.矩形件排样问题的模拟退火算法求解[J].四川大学学报（工程科学版），2001（5）.

[3]康立山，谢云.非数值并行算法-模拟退火算法[M].北京：科学出版社，2008.

[4]BABU A R，BABU N R.A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J].Computer-Aided Design， 2001， 33（12）： 879-891.

[5]刘勇，康立山，陈毓屏.非数值并行算法-遗传算法[M].北京：科学出版社，2007.