改进的双种群遗传算法在矩形件排样中的应用

来源：计算机工程与应用杂志2018年第15期北京时间：

作者：孙佳正，郭 骏

单位：华东师范大学 计算机科学与软件工程学院，上海 200062

摘要：在矩形件排样问题中，按照面积大小的顺序排放通常比随机排放效果要好，因此在遗传算法的随机初始的种群中加入部分按照面积大小排序的个体以达到加速收敛的目的。然而在同一个种群中，这部分个体适应度高，迭代前期快速扩散，使得种群多样性降低，导致遗传算法过早熟。针对此缺陷把随机个体作为一个种群，按照面积大小排序的个体作为另一个种群并采用特定的交叉方式保证此种群子代个体大体上按面积大小排序局部乱序。此外，针对最低水平线搜索算法搜索频率低的缺陷，增多了搜索的发生时机，实现更频繁的调整排序提高遗传算法局部搜索能力。实验结果表明了改进后算法的有效性。

关键词：矩形件排样,优化算法,遗传算法,最低水平线,双种群