The analysis of evolutionary optimisation on the TSP(1,2) problem
Xiaoyun Xia, Chenfu Yi, Xinsheng Lai · International Journal of Computational Science and Engineering · 2016
TSP(1,2) problem is a special case of the travelling salesperson problem which is NP-hard. Many heuristics including evolutionary algorithms (EAs) are proposed to solve the TSP(1,2) problem. However, we know little about the performance of the EAs for the TSP(1,2) problem. This paper presents an approximation analysis of the (1+1) EA on this problem. It is shown that both the (1+1) EA and (µ + λ) EA can obtain 3/2 approximation ratio for this problem in expected polynomial runtime O(n3) and O ((µ/λ)n3 + n) , respectively. Furthermore, we prove that the (1+1) EA can provide a much tighter upper bound than a simple ACO on the TSP(1,2) problem.