求解TSP的量子遗传算法

A Novel Quantum Genetic Algorithm for TSP

量子遗传算法(QGA)在求解数值和组合优化问题时效率明显优于传统进化算法,但目前较多被用于求解组合优化的背包问题,为了充分发挥QGA的优点,文中用其求解TSP这一经典的NP难问题.首先,文中设计了一种利用几率幅值编码的新的编码方式,即利用几率幅值编码的量子个体与一组向量对应,而此向量又与一条可行路径一一对应.这样的编码方式不仅缩小了种群规模,占用较少内存,所得的解均可行,而且有效地增强了种群的多样性;其次,在量子个体上实施量子杂交,这一操作有利于保留相对较好的基因段;最后,为了加快算法的收敛速度,引入两阶段局部搜索,第一阶段主要针对实例中排列稀疏处的城市进行优化,第二阶段在第一阶段的基础上着重对排列密集处的城市优化.据此,设计了解TSP的一个新的高效的QGA,并证明了其以概率1收敛到全局最优解;测定算法性能的数值实验数据表明,该算法在种群规模较小,迭代次数较少的情况下就可以收敛到已知最优解.

Quantum genetic algorithm （QGA） was proved to be better than the conventional genetic algorithms on numerical and combinational optimization problems, but it is usually used to solve the knapsack problems of the combinational optimization. It is also possible to use its strong ability of exploitation and exploration to other difficult problems, for example, the TSP, a class of NP-hard combinatorial optimization problems. First, a new encoding scheme with pairs of amplitudes is designed. A quantum individual is corresponding to a vector, and the vector is corresponding to the unique valid tour, and vice versa. The advantages of the encoding scheme are that it always generates feasible solution, uses less population size and storage, and can effectively enhance the diversity of the population. Second, the quantum crossover can maintain the relatively good gene blocks. Third, the two-phase local search for edge evolving is integrated into QGA to accelerate its convergent speed. The first phase is used to optimize the sparsely located cities, and the second phase is used to optimize densely located cities. Based on these, a novel and efficient QGA for TSP is proposed, and its convergence to global optimal solution with probability one is proved. The numerical experiments show that the proposed algorithm can find the global optimal solution with less computation and evolving time.