A Gaussian Process Regression Model for the Traveling Salesman Problem | Science Publications

Journal of Computer Science

Wanatchapong Kongkaew¹  Juta Pichitlamken¹ 

关键词: Gaussian process regression;    nearest neighbor;    iterated 2-opt algorithm;    genetic algorithm;    simulated annealing;    traveling salesman problem;   

DOI  :  10.3844/jcssp.2012.1749.1758

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

Problem statement: Traveling Salesman Problem (TSP) is a famous NP hard problem.Many approaches have been proposed up to date for solving TSP.We consider a TSP tour as a dependent variable and its corresponding distance as an independent variable.If a predictive function can be formulated from arbitrary sample tours, the optimal tour may be predicted from this function.Approach: In this study, a combined procedure of the Nearest Neighbor (NN) method, Gaussian Process Regression (GPR) and the iterated local search is proposed to solve a deterministic symmetric TSP with a single salesman. The first tour in the sample is constructed by the nearest neighbor algorithm and it is used to construct other tours by the random 2-exchange swap.These tours and their total distances are training data for a Gaussian process regression model.A GPR solution is further improved with the iterated 2-opt method.In the numerical experiments, our algorithm is tested on many TSP instances and it is compared with the Genetic Algorithm (GA) and the Simulated Annealing (SA) algorithm.Results: The proposed method can find good TSP tours within a reasonable computational time for a wide range of TSP test problems.In some cases, it outperforms GA and SA.Conclusion: Our proposed algorithm is promising for solving the TSP.

【 授权许可】

Unknown