不等圆Packing问题的多策略优化方法

Multi-strategy Optimization Method for Unequal Circle Packing Problem

基于拟物算法思想及性能分析,提出一种求解不等圆Packing问题的高性能启发式算法。该方法以定步长序列梯度下降拟物算法为基础,运用相对势能作为排样布局的约束函数以消除图形尺寸的影响,并采用变邻接系数的邻接矩阵加速方法提升运算效率。在优化策略中,首先提出了改进分支搜索方法,以延长分支长度来扩大搜索范围实现对优胜劣汰策略的拓展;在迭代后期通过领域算子进行多重模拟退火来提升个体多样性和避免局部最优。在不同形状容器算例以及国际公开算例集上的大量实验表明,该算法是一种高效、稳定的不等圆Packing算法。

Based on the idea of quasi-physical algorithm and performance analysis, a high-performance heuristic algorithm for solving the unequal circle packing problem is proposed in this study. The new algorithm is based on a fixed-step sequence gradient descent quasi-physical algorithm, and it uses relative potential energy as the constraint function of the layout to eliminate the influence of graph size, and also uses the adjacency matrix acceleration method with variable adjacency coefficient to improve the computational efficiency. In the optimization strategy, an improved branch search method is proposed to extend the branch length to expand the search range and realize the expansion of the survival of the fittest strategy. In the later stage of the iteration, multiple simulated annealing calculations are performed through the domain operator to increase the diversity of solutions and avoid local optimum. A large number of experiments on containers with different shapes and international open examples show that the new algorithm is more efficient and stable for unequal circle packing problem.