求解带平衡约束圆形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.%圆形packing问题是一个著名的NP难题，求解该问题具有很高的理论与实用价值。首先将趋势外推原理和微调算子引入人工蜂群算法，对其搜索的随机性进行有效的引导优化，然后将改进后的人工蜂群算法应用于带平衡约束的圆形布局的参数优化，并在文后采用3个典型实例进行了数值实验。结果表明新算法解决带平衡约束的圆形packing问题具有较强的寻优能力和较高的寻优效率，是一种实用的方法。