关键词: 计算几何, 启发式算法, 人工蜂群算法, p-center问题, M-ABC算法

Abstract:

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.

Key words: computational geometry, heuristic algorithm, artificial bee colony algorithm, p-center problem, M-ABC algorithm