周家智，尹 令，张素敏



基于遗传模拟退火算法的布局优化研究

周家智，尹 令，张素敏

(华南农业大学数学与信息学院，广东 广州 510642)

为提高矩形件排样算法的利用率与时间效率，提出将遗传算法和模拟退火算法融合优化的矩形排样算法。采用带符号的十进制编码,依据矩形件长宽比和面积而生成基因序列用于建立初始种群，以随机产生若干排样顺序与排样尺寸不一的个体，并以利用率为适应度函数，修改后的最低水平线搜索算法作为排样策略，保证较优个体得以保留，减少闲置区域的产生。采用10组随机产生的矩形数据将本算法与现有文献提出的GA算法进行对比实验，实验结果显示：该算法有效地提升了排样结果的利用率与时间效率。

矩形件排样；遗传算法；模拟退火算法；最低水平线改进算法

矩形件排样问题即给定某单一尺寸的库存板材和一组毛坯需求，要求从板材中切割出毛坯，并满足所有毛坯的尺寸及数量需求，使消耗的板材数量或板材价值最小。矩形件排样问题广泛存在于布匹裁剪、金属锻造、木材切割等加工业领域，具有一定的计算复杂性，属于NP问题。对矩形件排样问题的算法优化具有一定的理论价值与现实价值。对矩形件排样问题的研究通常建立在特定的前提条件下：无限原材料或有限原材料。

矩形件排样问题作为经典的NP问题，与生产需求存在密切联系。对于矩形件排样的研究多数分为两个方面：排样策略的研究与排样顺序的研究。……