Font Size: a A A

Research On Shortest Path Problem Based On Quantum Ant Colony Algorithm

Posted on:2020-09-27Degree:MasterType:Thesis
Country:ChinaCandidate:L Y ZhaoFull Text:PDF
GTID:2428330602486840Subject:Computer technology
Abstract/Summary:PDF Full Text Request
The concept of quantum computing was first proposed by Benioff and Feynman in the 1880 s.They have conducted long-term research and exploration on quantum computing and achieved good results.At the same time,due to the greater computing power of quantum computing,quantum computing has been widely used in many problems.The fusion of quantum computing and intelligent algorithms has opened up a new direction of exploration.Under certain conditions,the new algorithm can improve the computational efficiency of the original algorithm and improve the probability of the algorithm searching for the optimal value.Therefore,the introduction of some principles related to quantum computing in the traditional classical calculation algorithm can improve the performance of algorithm calculation,and has important practical application value and theoretical research value.The Quantum Ant Colony Optimization Algorithm(QACO)combines the traditional ant colony algorithm with quantum information technology to integrate the advantages of quantum computing into the ant colony algorithm to improve the ant's global search ability and avoid ants.The problem of falling into the local optimal solution,while improving the search efficiency of ant colony algorithm and the slow convergence rate.This paper mainly improves the characteristics of the quantum ant colony algorithm and applies it to the solution of the shortest path problem.For the shortest path problem,the improved Quantum Ant Colony Algorithm(IQACO)is used in this paper.The improved quantum ant colony algorithm is mainly improved from the following three aspects:1.The improved algorithm uses quantum fidelity as a heuristic factor to improve the search speed to overcome the heuristic factor of the quantum ant colony algorithm being too small due to the increase of the distance to search the optimal value.2.The pheromone is encoded by quantum bits,and the quantum pheromone is updated by quantum Hadamard gate.3.The improved algorithm takes the node pheromone to consideration,and uses the local update method to increase the search probability for other nodes and increase the convergence speed.After the initial iteration of the volatilization mechanism,the pheromone will return to the normal level,but the improved quantum ant colony algorithm will obtain a better result at the beginning,which lays a good foundation for the later iteration of the algorithm.Finally,the effectiveness of the algorithm is verified by MATLAB simulation experiment.The experimental results show that the improved quantum ant colony algorithm has stronger optimization ability than the traditional quantum ant colony algorithm.
Keywords/Search Tags:Quantum information, Ant Colony Algorithm, Quantum Ant Colony Algorithm, quantum fidelity, Quantum Hadamard Door
PDF Full Text Request
Related items