Abstract: In the rectangle packing, the effect of packing sorted by area is better than that of packing at random. Therefore, adding individuals sorted by area into the random initial population of genetic algorithm can accelerate the convergence. However, in the same population, the fitness of this part of individuals is higher than the random one. In earlier iteration, its fast diffusion reduces the population diversity and brings premature convergence of the genetic algorithm. For this problem, the random individuals are arranged as one population and the individuals sorted by area are regarded as another population. The specific crossover method is used to ensure that the offspring individual of this population is sorted by size overall and out-of-order partially. Besides, regarding the low search frequency of the lowest horizontal search algorithm, the operation timing of search is increased, which realizes the more frequent adjustment sort and improves the local search capability of genetic algorithm. The experimental results show the effectiveness of the improved algorithm.

Key words: rectangle packing, optimization algorithm, genetic algorithm, lowest horizontal line, dual population

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

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