Quantum Ant Algorithm And Its Application Research

Many combinatorial optimization problems such as knapsack problem, travelingsalesman problem (TSP) and quadratic assignment problem are still unsolved so far.They are NP-hard problems with a wide practical application prospects. Lots ofapplications are developed aiming to solve these problems, however, it’s of a greatchallenge. To find out effective algorithms is critical. In recent years, intelligentoptimization algorithms have been providing methodology for solving these problems,which include simulated annealing algorithm, genetic algorithm, ant colony algorithm,particle swarm optimization, quantum computing and algorithm, etc.Ant colony algorithm, known as a good solution strategy for TSP, has a strongsearch capability compared with other common heuristic algorithms, and it has showngreat advantages in solving a number of difficult combinatorial optimization problems.While the quantum computing and algorithm, as a kind of evolutionary algorithm, usesthe modern quantum coding, the whole cross-interference and the quantum spinvariation to search the solution space, proves to have better search performance than thegenetic algorithms.This thesis proposes a novel algorithm-quantum inspired ant colony algorithm(QACO), which is based on the ant colony algorithm and the quantum computing andalgorithms. It is inspired by the basic principles of quantum computing, such asquantum spin variation and quantum field potential. Its effectiveness and efficiency areverified in the general discrete optimization and function optimization problem by largequantity of experiments. It is used to solve the classical knapsack problem. The resultsof numerical tests show the effectiveness and generality of QACO compared with ACOand GQA (genetic quantum algorithm). Then it is used to solve the classical TSPthrough series of typical instances. The computational results show the effectiveness ofthe algorithm in numerical simulations. A lot of results achive the best results in the TSPlibrary. It proves that QACO is one of effective algorithms for the general discreteoptimization.During QACO which is based on the Delta potential well for local search worksout the function optimization, it shows the convergence performance and validitycomparing with other algorithms.Multi-objective optimization is also studied in the thesis. QACO provides a newmethod for the system science, artificial intelligence, optimization theory, complexity science and other interdisciplinary. QACO is also an effective solution method forengineering and socio-economic areas.