Current Issue Cover
求解带平衡约束圆形Packing问题的快速局部搜索算法

刘建1, 黄文奇1(华中科技大学计算机科学与技术学院,武汉 430074)

摘 要
带平衡性约束的圆集在圆容器内的布局优化问题,属于NP困难问题。针对此问题,提出了一种快速的局部搜索算法。该算法首先构造出等价的物理模型,定义系统的能量函数,再利用最速下降法对能量函数进行优化,从而间接得到问题的近似解。在局部搜索算法中引入加速策略,提高了计算效率。最后通过两个算例的数值计算,验证了该方法的可行性和有效性。
关键词
A Fast Local Search Algorithm for Solving Circles Packing Problem with Constraints of Equilibrium

()

Abstract
The optimal layout problem of circle group in a circular container with performance constraints of equilibrium belong to NP hard problem. A fast local serach algorithm (LS) is presented for solving this problem. Firstly, the method constructs an equivalent physical model and defines the energy function of the system. Then the energy function is optimized by the steepest descent method and the approximation solution is obtained indirectly. In order to improve the computational efficiency, the accelerating strategy is added to the LS algorithm. Two examples are computed numerically, and the results of the experiment show the feasibility and efficiency of the approach.
Keywords

订阅号|日报