We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A comparative performance analysis of evolutionary algorithms on k-median and facility location problems.
- Authors
Peng, Xue; Xia, Xiaoyun; Zhu, Rong; Lin, Lei; Gao, Huimin; He, Pei
- Abstract
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.
- Subjects
EVOLUTIONARY algorithms; PERFORMANCE evaluation; FACILITY location problems; PROBABILITY theory; APPROXIMATION theory; CLUSTER analysis (Statistics)
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2018, Vol 22, Issue 23, p7787
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-018-3462-9