Authors: Xiaoyun Xia; Xinsheng Lai; Chenfu Yi
Addresses: College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314001, China; School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China ' School of Mathematics and Computer Science, Shangrao Normal University, Shangrao 334001, China ' School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China
Abstract: 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.
Keywords: evolutionary algorithms; TSP(1,2); approximation performance; analysis of algorithm; computational complexity.
International Journal of Computational Science and Engineering, 2019 Vol.18 No.3, pp.261 - 268
Received: 09 May 2016
Accepted: 30 Aug 2016
Published online: 13 Mar 2019 *