一种求解不等圆Packing问题的改进遗传模拟退火算法

An Improved Genetic Simulated Annealing Algorithm to Solve the Unequal Circle Packing Problem

不等圆Packing问题是求解半径不等的小圆在一个圆形容器内的优良布局,使得圆形容器的半径值最小。该问题属于NP hard的组合优化问题,使用传统的数学方法很难求解,提出了一种解决该问题的改进遗传模拟退火算法,该算法通过计算生成一个合适大小的初始圆形容器来指导初始种群的生成,以减少搜索范围,采用最优保存策略来保证历代的最优解不被破坏,结合了遗传算法全局搜索能力强的优势和模拟退火算法局部搜索能力强的优势,改进了算法的搜索能力。最后通过算例验证,该算法有效地提高了圆形容器的面积利用率,证明了改进遗传模拟退火算法的有效性。

The unequal circle packing problem is putting several unequal circles into a circular container without overlapping, meanwhile minimize the size of the circular container. This problem belongs to NP hard combinatorial optimization, which is difficult to solve by traditional mathematical method. This paper presents an genetic simulated annealing algorithm to solve the unequal circle packing problem. By calculation to generate an appropriate circular container, which is used to produce an initial population, the search range can be reduced. Using elitist strategy to guarantee the optimal solution of the past dynasties can be preserved.Combining the advantage of global search ability of genetic algorithm and the advantage of local search ability of simulated annealing algorithm can improve the search ability of this algorithm. Finally, some calculation examples are presented, the area utilization ration of the circular container is improved effectively, hence the effectiveness of this algorithm is proved.