改进遗传算法求解TSP问题：性能提升与实验验证

本文主要探讨了一种针对旅行商问题（Traveling Salesman Problem, TSP）的改进遗传算法。TSP是一个经典的组合优化问题，旨在找到访问一系列城市并返回起点的最短路径。作者庞文颖在中山大学攻读计算机软件与理论硕士学位期间，针对遗传算法在解决这类问题上的潜力进行了深入研究。 遗传算法是一种模拟自然选择和遗传机制的搜索优化方法，它在求解TSP问题时展现出良好的性能。然而，算法的效果受到多个关键参数的影响，如初始种群的质量、群体规模、交叉概率和变异概率。为了提升算法效率和精确度，本文提出了一种创新策略。 首先，作者通过最短路径算法优化初始种群，确保其包含更优质的解，从而提高算法的起点。这减少了随机性，有助于快速收敛到较好的解决方案。接着，引入了基于聚类的自适应方法，根据当前种群的特性动态调整交叉概率和变异概率，这样能够更好地探索搜索空间，避免陷入局部最优。 本文的改进遗传算法采用了单亲演化与群体演化相结合的方式，增强了算法的全局搜索能力。同时，作者对适应值函数和交叉算子进行了适当的设计，进一步提升了算法的收敛速度和精度。通过实验证明，这种改进的遗传算法在求解TSP问题上取得了显著的性能提升，有效地解决了问题，并证明了其在实际问题中的可行性。 这篇硕士学位论文不仅展示了遗传算法在TSP问题中的应用，而且提出了实用的优化策略，为同类问题的求解提供了新的思路和技术支持。关键词包括遗传算法、旅行商问题、基因片段、交叉概率和变异概率，这些都是理解和评价这一研究的重要线索。