Abstract: Based on the analysis of the basic concepts of quantum evolution, a new Mixed Quantum-Inspired Evolutionary Algorithm for solving Traveling Salesman Problem（TSP） has been proposed, in which 3-Optimize local search heuristic was incorporated with quantum evolutionary mechanism, the nearest neighbor heuristic rule was used to initiate parameters, and the ordered crossover operator was introduced to extend the exploratory range of quantum population. Experiments were carried out on some cases from the well-known TSP library (TSPLIB). The results show that the new algorithm is effective and robust, which is able to find the satisfactory resolution with small size population and tiny relative error, even for medium or large scale problems (city number > 500). Key Words Quantum Computing; Evolutionary Algorithm; Traveling Salesman Problem.

Key words: quantum computing, evolutionary algorithm, Traveling Salesman Problem（TSP）

摘要： 在分析量子进化基本概念的基础上，提出了一种新的求解TSP的混合量子进化算法（MQEA）。该算法将三段优化局部搜索算法融入量子进化机制，采用一种基于边的编码方法，应用最近邻规则设置初始参数，并设计了排序交叉算子以扩展种群的搜索范围。通过选取国际通用旅行商问题（TSP）实例库(TSPLIB)中的多个实例进行测试，表明新算法具有高的精确度和鲁棒性，即使对于中大规模问题（城市数大于500），也能以很小的种群和微小的相对误差求得满意解。

关键词: 量子计算, 进化算法, 旅行商问题