A Novel Particle Swarm Optimization With Genetic Operator and Its Application to TSP

Introduction

The travel salesman problem (TSP) firstly formulated as a mathematical problem in 1930 is a typical NP-complete problem. In recent years, it attracts much attention in mathematics and computation sciences communities and has been one of the most intensively studied problems in optimization(Bello, Gomez, Nowe, et al, 2007). The purpose of the TSP is to find the shortest journey, which each city can be visited only once and returns to the starting city. Concretely, it means to search for an arrangement of natural subsets (the elements of C are the serial number of cities). The TSP can be described as following:

Since meta-heuristic methods are able to find solutions rapidly by the strong ability of exploring and exploiting the full search space, those algorithms have attracted a lot of attention in solving global optimization problems (Li, Wang, 2019; Li, Chen, et al, 2018). Considering the advantage of it, many heuristics algorithms are applied to deal with TSP in recent years, such as simulated annealing (SA)(Li, Zhou, Zhang, 2011), tabu search (TB)(Lin, Bian, Liu, 2016), neural networks (NN)(Li, Qiao, Li, 2016), and genetic algorithm (GA)(Pang, Wang, Zhou, et al, 2004; Li, Liang, et al, 2019).

Particle swarm optimization (PSO) proposed by Kennedy and Eberhart(Kennedy, Eberhart, 1995) in 1995 is an effective approach to address continuous problems. In recent years, PSO has been successfully applied in many optimization problems, such as function optimization(Yin, Li, Gao, et al, 2016, Wang, Zhang, Li, et al, 2018), wavelet mutation(Ling, Iu, Chan, et al, 2008), image processing (Chandramouli, Izquierdo, 2006), and automatic control(Chatterjee, Pulasinghe, Watanabe, et al, 2005; Chen, Ren, Fan, 2006). However, the conventional PSO cannot directly be applied in TSP which is a type of discrete problem rather than a continuous problem. So the PSO method is proposed to solve TSP firstly by Clerc(Clerc, 2004) in 2004. Then Hendtlass(Hendtlass, 2003) uses PSO to solve small-size TSP by adding a memory capacity for each particle. Pang(Pang, Wang, Zhou, et al, 2004) combined the characteristics of PSO with the concept of fuzzy theory.

Based on the previous research, an improved hybrid PSO (IHPSO) is proposed in this work, in which some new features are introduced to improve its comprehensive performance. Firstly, a probability initialization is used to reduce the complexity as well as to achieve better performance on a large scale in TSP. Relying on the strategy, the initial population can obtain the guidance of prior knowledge. Secondly, two different matrices are introduced to enhance two crossover operators. Through two crossover operators the algorithm can take full advantage of the global best solution Gbest and the personal best solution Pbest. Thirdly, a directional mutation operator is proposed to avoid the excellent genes broken, thus to improve its solution accuracy.