一种求解TSP问题的动态杂交算子

TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。论文在文犤5犦提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率,此外,在杂交母体范围内执行贪婪策略也导致了算法的效率较低。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效地保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明了该算子的有效性。