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

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