摘要： 为求解矩形区域内的圆形Packing问题，提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局，使这些圆两两互不嵌入地放置。算法从任一初始构形出发，采用模拟退火(SA)算法进行全局寻优，在SA执行过程中，应用基于自适应步长的梯度法进行局部搜索，同时介绍一些启发式策略。对2组共20个算例进行实算测试，计算结果证明了该算法的有效性。
关键词:
圆形Packing问题,
模拟退火算法,
启发式策略,
梯度法,
布局,
形区域
Abstract: To solve the circular Packing problem, a Heuristic Simulated Annealing(HSA) algorithm is put forward. The objective of the problem is to find a good layout by Packing circles without overlapping within a larger rectangular container. The algorithm begins from a random initial configuration and applies the Simulated Annealing(SA) algorithm to optimize layout. In the process of the SA iteration, the gradient method with an adaptive step length is used to execute local search. To construct a special neighborhood and jump out of the local minima, some heuristic strategies are proposed. The two sets of benchmarks consisting of 20 instances are tested. The results show HSA is effective.
Key words:
circular Packing problem,
Simulated Annealing(SA) algorithm,
heuristic strategy,
gradient method,
placement,
rectangular region
中图分类号:
刘朝霞, 刘景发. 一种求解圆形Packing问题的模拟退火算法?[J]. 计算机工程, 2011, 37(19): 141-144.
LIU Chao-Xia, LIU Jing-Fa. Simulated Annealing Algorithm for Solving Circular Packing Problem[J]. Computer Engineering, 2011, 37(19): 141-144.