改进Inver-over算子的二阶段演化算法求解旅行商问题

"这篇论文研究了旅行商问题(Traveling Salesman Problem, TSP)的求解策略，提出了一种二阶段演化算法(Two-stage Inver-over EA)，该算法通过改进Inver-over算子来平衡算法的收敛速度和种群多样性。在第一阶段，算法仅使用1st-Inver-over算子加速收敛；第二阶段，算法根据种群多样性自适应地选择1st-Inver-over算子和2nd-Inver-over算子，以避免早熟收敛并保持搜索效率。实验结果显示，二阶段Inver-over EA在TSPLIB标准数据集上表现优于传统的郭涛算法(GT算法)，显示出更好的收敛特性和搜索效率。该研究得到了国家自然科学基金的支持，由在软件工程、智能计算、计算机网络和人工智能等领域有研究背景的学者共同完成。" 旅行商问题(TSP)是组合优化领域的一个经典问题，目标是在给定城市间距离的情况下，找到一条访问每个城市一次并返回起点的最短路径。它在数学上被定义为寻找有n个节点的完全图中最短的Hamilton回路，使总距离最小化。由于TSP被证明为NP-hard问题，无法在多项式时间内找到最优解，因此研究主要分为完全算法和近似算法。前者保证最优解但计算复杂度高，后者则在多项式时间内找到接近最优解的路径。 郭涛算法是一种基于Inver-over算子的演化算法，对于小规模问题可能有效，但在处理大规模TSP实例时，解的质量会下降。论文中提出的问题在于，虽然增大种群规模可以改善解的质量，但会导致算法的时间复杂度显著增加，不适用于实际应用。 为了解决这个问题，研究者对Inver-over算子进行了改进，提出了1st-Inver-over和2nd-Inver-over算子。在二阶段Inver-over EA中，初期阶段侧重于快速收敛，使用1st-Inver-over算子；后期阶段通过自适应选择两种算子来保持种群多样性，从而在保证算法收敛性的同时，提高搜索效率。这种方法在TSPLIB数据集上的实验验证表明，改进后的算法相比传统方法有更优的表现。 这篇论文贡献了一种针对TSP的新型演化算法，通过优化算子和引入二阶段策略，提高了算法在解决大规模问题时的性能，为TSP的近似求解提供了新的思路。