遗传算法求解TSP的研究

作为一种模拟生物自然遗传与进化过程的优化方法,遗传算法(GA)因其具有隐并行性、不需目标函数可微等特点,常被用于解决一些传统优化方法难以解决的问题。旅行商问题(TSP)是典型的NP难题组合优化问题之一,且被广泛应用于许多领域,所以研究遗传算法求解TSP具有重要的理论意义和应用价值。具有量子计算诸多特点的量子遗传算法(OGA)作为—新的概率进化算法,在解决实际问题时,其高度并行性能极大地提高计算效率,因而研究OGA求解TSP同样有重要的价值;而将具有遍历性和随机性的“混沌”概念引入量子遗传算法求解较复杂的组合优化问题又为求解优化问题开拓了一个新的思路。 首先,本文用一种改进的基本遗传算法求解TSP,由先验知识+随机的方法产生初始群体,采用启发式交叉和边重组交叉相结合的交叉算子及GA的初期和后期采用不同适应度的方法。然后,着重研究了改进的QGA求解TSP,即采用适合TSP的矩阵编码及有效性修复的方法,在基本QGA的基础上运用可控旋转门,引入使算法收敛速度更快的模糊规则控制旋转角,选用量子交叉和量子变异避免陷入局部最优和阻止早熟收敛;最后用混沌量子遗传算法求解TSP,即在量子遗传操作中更新量子门时选用混沌序列函数,以加快收敛速度和防止早熟收敛。计算机模拟实验结果表明本文采用的三种算法较标准遗传算法求解TSP具有种群规模小,迭代次数少,更易跳出局部最优,更易得到最优解等优点。