Genetic Quantum Particle Swarm Optimization Algorithm for Solving Traveling Salesman Problems
This paper presents a Genetic Quantum Particle Swarm Optimization (GQPSO) algorithm to solve Traveling Salesman Problems (TSPs). This algorithm is proposed based on the concepts of swap operator and swap sequence by introducing crossover, mutation and inv
- PDF / 161,136 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 14 Downloads / 202 Views
Abstract This paper presents a Genetic Quantum Particle Swarm Optimization (GQPSO) algorithm to solve Traveling Salesman Problems (TSPs). This algorithm is proposed based on the concepts of swap operator and swap sequence by introducing crossover, mutation and inverse operators in Genetic Algorithm (GA). Our algorithm overcomes such drawbacks as low convergence rate and local optimum when using Particle Swarm Optimization (PSO) or Quantum Particle Swarm Optimization (QPSO) algorithm to solve TSP. The experiment result shows that GQPSO algorithm has very powerful global search ability and its convergence rate is sharply accelerated compared to that of QPSO algorithm. GQPSO algorithm will have very good application prospects in solving combinational optimization problems. Keywords TSP · PSO algorithm Combinational optimization.
·
GQPSO algorithm
·
Inverse operator
·
1 Introduction Particle Swarm Optimization (PSO) algorithm was firstly proposed by Kennedy and Eberhart in 1995 [1]. Since PSO is simple and easy to be realized, with just fewer control parameters to tune, it caught attentions from researchers from both domestic and overseas. Theoretically, however, PSO is not an algorithm with global convergence. To overcome disadvantages of PSO, Jun Sun et al. proposed a new version of PSO, Quantum-behaved Particle Swarm Optimization (QPSO) algorithm in 2004, which is global convergent and powerful in locating optimal solutions with fewer control parameters and fast convergence rate. Since it was proposed, this algoW. Yao (B) Mathematical teaching and research section of Guangzhou City Polytechnic, Gungzhou 510405, P.R.China e-mail: [email protected]
B.-Y. Cao and H. Nasseri (eds.), Fuzzy Information & Engineering and Operations Research & Management, Advances in Intelligent Systems and Computing 211, DOI: 10.1007/978-3-642-38667-1_8, © Springer-Verlag Berlin Heidelberg 2014
67
68
W. Yao
rithm has been used in solving many optimization problems [3]. Compared to other intelligent algorithms, such as genetic algorithm (GA), simulated annealing (SA) algorithm, etc., QPSO is more powerful on some function optimization problems. QPSO was successfully applied in dealing with continues optimization problems, but little attention was focused on discrete problems. The travelling salesman problem (TSP) could be described as finding out a shortest path that could visit each city once and only once. TSP is a famous and typical NP problem, belonging to combinatorial optimization problems [4]. In literature [5], a special PSO algorithm for TSP was proposed by introducing the concepts of swap operator and swap sequence. But this PSO is slow in solving TSP, QPSO is employed in [6] to overcome this shortcoming. However, there are few works that combine GA and QPSO for travelling salesman problems. In this paper, we introduced crossover and mutation operators into QPSO and proposed Genetic Quantum-behaved Particle Swarm Optimization (GQPSO) algorithm for TSP. It was shown by the experimental results that GQPSO is faster than
Data Loading...
