一种求解旅行商问题的演化算法研究

摘要

旅行商(TSP)问题是一个被证明具有NP计算复杂性的组合优化问题.郭涛算法在求解TSP问题的高效率是得到广泛认可的,其算法的核心在于Inver-over算子的设计.当节点数量较多时,该算法在寻找近似最优解仍然有很好的表现,但其寻找全局最优解的能力却会下降.提出的基于基因片段插入的演化算法,它能以较高的概率找到TSP问题的最优解.文中提出一种新的演化算法,将基于基因片段插入与Inver-over算子进行融合.实验证明:新算法可有效防止解的早熟,增强了算法的全局搜索能力,使算法获得全局最优解的概率大大提高,同时仍然具备高效率的特性.