求解带平衡约束圆形packing问题的改进人工蜂群算法  

Exploring Improved Artificial Bee Colony Algorithm for Solving Circle Packing Problem with Equilibrium Constraints

作　　者：王鹏[1] 黄帅[1] 朱舟全 

机构地区：[1]西北工业大学航海学院,陕西西安710072

出　　处：《西北工业大学学报》2014年第2期240-245,共6页Journal of Northwestern Polytechnical University

基　　金：国家自然科学基金(51375389)资助

摘　　要：圆形packing问题是一个著名的NP难题,求解该问题具有很高的理论与实用价值。首先将趋势外推原理和微调算子引入人工蜂群算法,对其搜索的随机性进行有效的引导优化,然后将改进后的人工蜂群算法应用于带平衡约束的圆形布局的参数优化,并在文后采用3个典型实例进行了数值实验。结果表明新算法解决带平衡约束的圆形packing问题具有较强的寻优能力和较高的寻优效率,是一种实用的方法。As is well-known, it is difficult to solve a circle packing problem with equilibrium constraints. Therefore we aim to find a new algorithm that can further enhance search capability, efficiency and success rate. To solve the circle packing problem, we propose an improved artificial bee colony （ IABC） algorithm by introducing the trend extrapolation and a fine-tuning operator into the artificial bee colony so as to reduce its randomness in the search process and improve its search efficiency. The IABC algorithm uses different adaptability degrees of food sources at different places to produce the direction of trend extrapolation and direct the search, thus reducing its randomness. To verify the effectiveness of the IABC algorithm, we apply it to solving the circle packing problem with equilibrium constraints and simulate it with the MATLAB software. The simulation results, given in Figs. 4, 5 and 6 and Tables 3 and 4, and their analysis show preliminarily that our IABC algorithm has better search capability and efficiency than both the genetic algorithm and the particle swarm optimization （ PSO） algorithm. The IABC algorithm can find optimal solutions quickly without taking much computing time, indicating its efficiency in solving a circle packing problem with equilibrium constraints.

关 键 词：约束圆形布局问题 人工蜂群算法 布局优化 启发式算法 

分 类 号：TP3-05[自动化与计算机技术—计算机科学与技术]