基于孵化算法的多变形排样

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于孵化算法的多变形排样范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 基于现有的优化排样算法，模拟鸡蛋孵化过程，设计一种孵化算法来解决排样问题。算法是对实际生活中存在现象的抽象和改进。将寻找最优解整个过程划分为占位，孵化，挤兑，抢占，复活，五个阶段，探索状态下排布决策的适应性，从而得到排样件在排样时的最优次序和最大可容纳的样本数目。

关键词： 排样；孵化算法；适应度

0 引言

孵化算法是模拟鸡蛋动态孵化的过程，对样本的排布方案进行创新性探索。针对实际中具体的排样问题的特点，寻求近似最优的策略。

计算机辅助计算的应用是当前科研的一个新趋势，在服装、材料等工业、制造业中有广泛的应用，通过探索优化排样问题给出尽可能的最优方案，以提高材料利用率，降低生产成本。在过去的五十年里，国内外的大量学者对优化排样问题进行了大量研究，早期的研究工作中使用了数学规划技术，例如整数规划[1]、整数线性规划[2]等。本文在现有成果和理论的基础上，受到自然现象的启发，创造性的提出新的算法，模拟有限空间中鸡蛋孵化工程，抽象出占位，孵化，挤兑，抢占，复活，五个步骤，启发性选择样本排布策略。

1 优化排样

1.1 问题描述

在板材上排布样本属于二维排布，有两个方向，长和高，需要判断样本的边界是否超出了板材的边界。需要考虑样本的布局，用以最大限度的利用板材，提高板材的利用率。假如给定一个矩形零件，长度为L，宽度为W，这个零件在长度为L0，宽度为W0的矩形板材上，有两种排布方式：一种是横排，L与L0方向一致，如图1；另一种是竖排，W与W0方向一致，如图2。

图1 横排 图2 竖排

在给定的矩形板材上排布样本有三种排布方式：

1）沿着板材宽度方向连续横排

2）沿板材材宽度方向连续竖排

3）横排竖排交错排列

1.2 孵化算法

受到鸡蛋孵化的动态过程的启发，对应不同阶段，抽象出占位，孵化，挤兑，抢占，复活的步骤，将这种思想应用于优化排样问题，对最优情况进行预估计，经过有限步的调整变化，找出相对最优的排布策略。

分为五个步骤：

步骤一：占位，首先计算出孵化鸡蛋时，每个鸡蛋占用的格子大小，计算最多能孵化出多少只小鸡，将可能孵化成小鸡的鸡蛋标记出来。

步骤二：孵化，进行鸡蛋孵化操作，鸡蛋孵化，其占用的格子会变大，会挤兑到其他鸡蛋，当其他格子通过平移就能满足该鸡蛋孵化时，通过平移来为该鸡蛋提供空间，否则进行步骤三挤兑操作。

步骤三：挤兑，当通过平移以无法满足鸡蛋孵化所需的空间时，则进行挤兑操作，这时需要占用其他鸡蛋所用的格子空间，其他鸡蛋因为格子变小，因此无法孵化，此时把变小后的格子标记成无法孵化，并在后面没有标记成可孵化的第一个格子，标记成可孵化。

步骤四：抢占，鸡蛋在孵化的过程中，可以抢占被标记成不可孵化的格子空间，如果被抢占的格子在右侧或者下侧，则鸡蛋可进行右移或下移。

步骤五：当最后孵化的小鸡数量小于最大可孵化的小鸡数量时，调整小鸡的位置，当调整后，能容纳下一只小鸡孵化时，则孵化该小鸡，如果仍未达到最大数量，如此反复，直至所有排列均被实验过。

1.2.1 最优估计

理论上最多能孵化的鸡的数量为：

maxCount = （int） （（tWidth * tHeight） / （rWidth * rHeight））；

1.2.2 状态定义

将鸡蛋在孵化过程中的不同状态定义为：Free，Busy，Broken，Dead，Chicken。初始状态为Free ，选出将要孵化的鸡蛋，修改其状态为Broken。当前被标记的右侧或下侧的鸡蛋状态为Free，则把将要孵化的右侧和下侧鸡蛋状态修改成为Busy。满足孵化条件则将状态改为Chicken。对扩展的方向进行适应性的分析，分析两个方向的适应度，选择最优的方向扩展样本所占空间，被挤兑的鸡蛋标记为Dead，分析鸡蛋所处状态以及空间利用情况，如果尚有空间可被利用，则开始复活操作，将标记为Dead的鸡蛋变为可孵化状态，如果已孵化数量小于最大估计值则重复以上步骤。

1.2.3 适应度分析

在鸡蛋孵化进行挤兑时，需要选择扩展的方向，对横向和纵向两种选择，比较其适应度，选择适应度高的方向进行扩展。

竖排适应度：

horizentalFit=1/（hRemindWidth%rWidth*1.0/rWidth + hRemindHeight%rHeight * 1.0/rHeight）；

横排适应度：

verticalFit=1/（vRemindWidth%rHeight*1.0/rHeight + vRemindHeight%rWidth * 1.0/rWidth）；

2 实例分析

在eclipse环境中实现了上述算法，程序测试了不同实例下算法的效果，以矩形板材为例，分别测试了五种典型情况，板材长大于宽，样本长大于宽（L0>W0，L>W）；板材长大于宽，样本长小于等于宽（L0>W0，L≤W）；板材长小于等于宽，样本长小于等于宽（L0≤W0，L≤W）；板材长小于等于宽，样本长大于宽（L0≤W0，L>M）；异常情况样本边界超过板材边界。

以一个实例进行分析，L0=800，W0=700，L=160，W=87。所能排布的最大样本数目估计值是40。使用孵化算法进行优化排样的过程后，实际所能排布的样本最大数是40，和估计值相吻合。

3 结论

本文针对优化排样问题，提出了一种基于孵化算法的启发式排样算法。通过对其他算法的研究比较，对孵化算法进行探索和改进，联系实际生活，多方面思考，解决问题。利用孵化算法自动排样，寻找出排样件的最优排样次序，得到一种实际有效的优化排样算法。

参考文献：

[1]A Farley·Mathematical programming models for cutting stock problems in the clothing industry[J].Journal of the Operational Research Society，1988，39（1）：41～53.

[2]M S Reda，E A Abd·An interactive technique for the cutting stock problem with multiple objects[J].European Journal of Operational Research，1994，78（3）：304～317.

[3]M Shpitalni，V Manevich·Optimal orthogonal subdivision of rectangular sheets[J].Transactions of ASME Journal of Manufacturing Science and Engineering，1996，118（3）：281～288.

作者简介：

王彬彬（1991-），女，河南省周口市人，本科学历，软件学院软件工程专业，单位：吉林大学。