Title: The analysis of evolutionary optimisation on the TSP(1,2) problem

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(n³) and O ((µ/λ)n³ + 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.

DOI: 10.1504/IJCSE.2019.098535

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: 26 Mar 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article