基于人工蜂群算法的p-center问题求解算法

平面p-center问题是经典的NP难题,所以寻找高效的近似求解算法是解决实际应用问题时的基本需求。在人工蜂群算法的基础上,通过引入遗传算法的交叉和变异算子,改进局部解的搜索策略与搜索能力,即根据给定概率对当前解做交叉或变异运算,以获得更好的局部解,进而提出BeeGenP启发式求解算法,用于求解平面离散型p-center问题。通过构造测试数据,对所设计的算法进行了有效性验证,实验结果表明,BeeGenP算法与现有的M-ABC算法相比,算法的局部解搜索能力得到了提升,增加了搜索空间的多样性,在相同迭代次数约束下所得到的解的质量更高,而趋近收敛于最优解时的迭代次数则有较大幅度的降低。

A p-center problem solving algorithm based on artificial bee colony algorithm

The planar p-center problem is a classic NP hard problem, so finding an efficient algorithm with approximate solutions is the basic requirement for solving practical problems. To solve the discrete p-center problem on the plane, a heuristic algorithm, namely BeeGenP, is proposed. Based on the artificial bee colony algorithm, BeeGenP improves the search strategy and ability of local solutions by introducing the crossover and variation operators from the genetic algorithm. Namely, the current solution is crossed or varied to obtain a better local solution according to an appropriate probability. Some test data are employed to verify the algorithm. The experimental results indicate that, compared with the existing M-ABC algorithm, the proposed BeeGenP algorithm has an enhanced search ability of local solutions, and increases the diversity of the search space. BeeGenP has a higher quality of the obtained solution under the constraint of the same iterations, while the number of iterations is greatly reduced when the solution converges to the optimal solution.