A comparative performance analysis of evolutionary algorithms on k-median and facility location problems

作者：Peng, Xue; Xia, Xiaoyun^*; Zhu, Rong; Lin, Lei; Gao, Huimin; He, Pei

来源：Soft Computing, 2018, 22(23): 7787-7796.

DOI：10.1007/s00500-018-3462-9

• Evolutionary algorithm
• Facility location
• k-median
• Performance analysis

k-median and facility location problems are classical NP-hard combinatorial optimization problems. Although there are many experimental studies on them, their theoretical results are relatively few. This paper mainly contributes to investigating the approximation performance of two evolutionary algorithms for the k-median and facility location problems from a theoretical perspective. For k-median problem, we show that the evolutionary algorithms with standard bit mutation (SBM) operator can obtain approximation ratios 5 and 3+2/p in expected polynomial time while the evolutionary algorithm with somatic contiguous hypermutation (CHM) operator cannot obtain them. For facility location problem, we show that the evolutionary algorithms with SBM operator can obtain approximation ratio 3 in expected polynomial time while the evolutionary algorithm with CHM operator cannot obtain it. Further, we prove that on a facility location instance the evolutionary algorithm with CHM operator greatly outperforms the evolutionary algorithm with SBM operator.

• 出版日期2018-12
• 单位广东技术师范大学; 嘉兴学院; 广州大学