基于格局变换策略的不等圆Packing问题求解算法  

Perturbation-based approach for solving arbitrary sized circle Packing problem

作　　者：黄文奇[1] 付樟华[1] 许如初[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机应用研究》2011年第11期4032-4034,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60773194;61070235)

摘　　要：采用基于格局变换策略的算法ACP-Solver求解不等圆Packing问题。ACP-Solver由连续优化方法、格局变换算子和接收准则组成。连续优化方法可从任一初始格局收敛至对应的局部最优格局。格局变换算子将当前格局变换为新格局。接收准则决定是否接收变换所得格局。基于24个国际公开算例的计算实验表明,ACP-Solver能在可接受的计算时间内改进或持平绝大多数算例的当前最优记录。实验结果表明了ACP-Solver的高效性能。This paper proposed a perturbation-based approach named ACP-Solver which consisted of a continuous optimization method,several perturbation operators and an acceptance criterion for solving ACP.Used the continuous optimization method to obtain a local optimal configuration from any initial configuration.Used the perturbation operators to perturb the incumbent configuration to new configurations.The acceptance criterion determined whether or not to accept a perturbed configuration.Computational experiments based on 24 representative instances show that ACP-Solver succeed in improving or matching most of the best known results within reasonable time.The performance of ACP-Solver in comparison with previous approaches demonstrates that ACP-Solver is a competitive algorithm for solving ACP.

关 键 词：装填问题 启发式算法 连续优化 组合优化 变换算子 接收准则 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构] TP301.6[自动化与计算机技术—计算机科学与技术]