An Improved Noise Quantum Annealing Method for TSP
- PDF / 2,688,118 Bytes
- 19 Pages / 439.642 x 666.49 pts Page_size
- 29 Downloads / 205 Views
An Improved Noise Quantum Annealing Method for TSP Yumin Dong1
· Zhijie Huang1
Received: 14 June 2020 / Accepted: 5 October 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Traveling Salesman Problem (TSP) is a combinatorial optimization problem, which has NP-Complete (NPC) complexity. At present, there is no exact algorithm to solve similar problems, only an approximate algorithm to simplify the problem can be found. For example, quantum annealing algorithm (QA) can play such a role. QA transforms the distance matrix sum of TSP into Pauli matrix, adds a transverse magnetic field to realize the quantum tunneling effect, reduces the energy needed to cross the barrier, and reduces the number of iterations to find the optimal solution. However, although the QA has fewer iteration steps, it usually produces errors. In this context, this paper’s INQA improves the QA. In this paper, the theoretical basis of quantum annealing algorithm is introduced, aiming at the shortcomings of quantum annealing algorithm in solving TSP problem, a new algorithm INQA is proposed, and it is verified by experiments. In the case of high initial temperature, the INQA has larger search range and more active search. Meanwhile, with the decrease of temperature, the search range is reduced, and the accuracy of the algorithm is improved. In fact, QA in this paper is a quantum annealing method for simulation. Keywords TSP · Quantum annealing · Optimization algorithm
1 Introduction TSP, also known as freight forwarding problem, is one of the famous problems in the field of mathematics and has been proved to be a Non-deterministic Polynomial-Hard (NP-Hard) problem [1]. Since TSP represents a kind of combinatorial optimization problem, the study of its approximate solution has always been an important problem in algorithm design. There are two kinds of algorithms to solve this problem. One is the heuristic search algorithm related to the characteristics of the problem, including dynamic programming method,
Yumin Dong
[email protected] 1
College of Computer and Information Science, Chongqing Normal University, Chongqing, China
International Journal of Theoretical Physics
branch ninition method, etc. The other is the intelligent optimization algorithm independent of the problem, such as simulated annealing (SA) and QA, to seek the optimal solution or approximate optimal solution in the tolerable resource space [2]. In 1982, Kirkpatrick and others [3] introduced the idea of annealing into the field of optimization, and proposed the SA. The basic idea is to simulate the solid annealing process, improve the calculation efficiency of Monte Carlo (MC) sampling by using the important sampling criterion of metropolis, and control the algorithm process by a group of cooling scheduling [4]. The algorithm not only has high search efficiency, but also has the ability of global optimization [5]. Unlike SA, which is based on the principle of thermal fluctuation, QA uses quantum fluctuation to build optimization algorith
Data Loading...
