本文所涉及所有资源均在传知代码平台可获取

一、背景介绍

旅行商问题（Traveling Salesman Problem，TSP）作为组合优化领域中的经典NP - Hard问题，在物流配送、电路布线、旅游规划等众多实际场景中具有广泛应用。其核心目标是为旅行商规划一条遍历所有城市且不重复、最终回到起点的最短路径，然而随着城市数量的增加，问题的复杂程度呈指数级增长，传统遗传算法在求解TSP时存在收敛速度慢且不稳定等问题。

遗传算法（Genetic Algorithm，GA）是一种基于自然选择和遗传学原理的优化算法，通过模拟生物进化过程来寻找最优解。然而，传统遗传算法在处理TSP问题时，由于其种群初始化的随机性、固定的交叉和变异概率等因素，容易导致算法陷入局部最优解，且收敛速度较慢，无法满足实际应用中对高效求解的需求。本复现旨在深入理解和验证基于改进遗传算法在解决TSP问题上的有效性，该算法通过引入邻域搜索算法优化种群初始化、设计自适应调节的交叉和变异概率、加入Metropolis准则以及逆转操作等改进策略，提高算法的收敛速度和求解精度，为TSP问题的求解提供更高效、更稳定的解决方案。
原文链接

二、算法原理

（一）旅行商问题描述

1. 数学模型
   • TSP问题可抽象描述为在一个带权重的完全无向图中，找到一个权值总和最小的哈密顿回路。设城市集合为(V = {v_1,v_2,\cdots,v_n})，城市(v_i)到(v_{i + 1})的距离为(d(v_i,v_{i + 1}))，目标是找到一条遍历所有城市且不重复、最终回到起点的路径(V)，使得路径总长度(L(V)=\min\sum_{i = 1}^{n - 1}d(v_i,v_{i + 1})+d(v_n,v_1))最小。

（二）传统遗传算法概述

1. 基本流程
   • 传统遗传算法主要包括以下步骤：
     • 确定合适的编码方式，如直接采用城市序号编码，对种群进行初始化，生成初始的可行解集合。
     • 建立合适的适应度函数，通常采用路径长度的倒数或相反数，计算种群中每个个体（路径）的适应度值，适应度值越大表示路径越优。
     • 根据个体适应度值进行选择操作，常用的选择方式有轮盘赌选择法和锦标赛选择法等，选择适应度较高的个体进入下一代种群，保留优秀基因。
     • 根据设定的交叉概率进行交叉操作，如部分映射交叉、顺序交叉等，通过交换父代个体的部分基因生成新的子代个体，增加种群的多样性。
     • 根据变异概率进行变异操作，如交换变异、逆序变异等，对个体的基因进行随机改变，引入新的基因，防止算法陷入局部最优解。
     • 判断是否满足停止条件，如达到最大迭代次数或种群中最优个体的适应度在一定迭代次数内未发生变化等，若满足则输出结果，否则返回选择操作继续迭代。

（三）改进遗传算法策略

1. 种群初始化优化
   • 传统遗传算法的种群初始化通常随机生成，导致初始种群个体适应度与最优适应度偏差较大。改进算法采用邻域搜索算法与随机生成相结合的方式，一半种群由邻域搜索生成，另一半由随机生成。邻域搜索算法从随机选择的起始城市开始，依次选择与上一个被选城市距离最近的城市，直到构成完整路径。这种方式在提高初始种群质量的同时保证了多样性，有助于算法在初期快速收敛。
2. 自适应交叉和变异概率
   • 传统遗传算法使用固定的交叉和变异概率，可能破坏优良个体或保留劣质个体。改进算法设计了自适应交叉和变异概率，根据当前个体的适应度值以及当前种群个体最大适应度与平均适应度的差值自动调整。当种群中个体适应度值最大值接近平均值时，算法可能收敛到全局最优解或陷入局部最优解，此时交叉概率和变异概率增大，增加种群多样性；当两者差值较大时，降低适应度较大个体的交叉和变异概率，保留优质个体，淘汰劣质个体。公式中加入三角函数使概率呈非线性变化，利于算法跳出局部最优解。
3. Metropolis准则的引入
   • 传统遗传算法在进化后期容易陷入局部最优解。改进算法引入Metropolis准则，在变异操作后生成新种群时，对每个解进行操作。随机选取解中的两个城市，将这两个城市之间（包含这两个城市）的城市顺序随机打乱，计算原路径长度(dist_{old})和新路径长度(dist_{new})。若(dist_{new}<dist_{old})，则接受新路径；若(dist_{new}>dist_{old})，则以概率(p_1 = e^{-\left(\frac{dist_{new}-dist_{old}}{maxgen - 0.9\times gen}\right)})接受新路径，其中(maxgen)为算法最大迭代次数，(gen)为当前迭代次数。随着迭代进行，(maxgen - 0.9\times gen)不断减小，(p_1)值也减小，算法接受劣解概率减小，有助于整体收敛。且当(dist_{new}-dist_{old})较大时，(p_1)概率变小，接受劣解概率减小；当(dist_{new}-dist_{old})较小时，接受劣解概率增大，在不影响收敛能力的同时保留了跳出局部最优的能力。
4. 逆转操作
   • 为加快种群收敛，改进算法加入逆转操作。在生成的种群中随机选取两个城市，将这两个城市之间的顺序倒换，然后保留路径距离更小的解。通过局部寻优思想，不断改进路径，提高算法的收敛速度。

三、代码实现

（一）数据准备

1. 距离矩阵生成
   • generate_distance_matrix函数用于生成城市间的距离矩阵，在示例中，距离矩阵元素随机取值在(1)到(100)之间（实际应用中可根据城市坐标计算真实距离），该矩阵用于计算路径总距离，是评估路径优劣的关键数据结构。

（二）关键函数实现

1. 路径总距离计算函数
   • total_distance函数计算给定路径的总距离，通过累加路径中相邻城市间的距离（考虑循环路径，最后一个城市与第一个城市相连），准确量化路径的长度，为后续的适应度计算、选择、交叉、变异等操作提供评估依据。
2. 种群初始化函数
   • init_population函数生成初始种群，每个个体是城市编号的随机排列，代表一种可能的旅行商路径，保证了初始种群的多样性。
3. 选择操作函数
   • selection函数实现选择操作，结合精英保留策略，先根据适应度对种群排序，保留一定比例的精英个体，然后通过轮盘赌选择法选择父代个体进行交叉操作，确保优秀基因得以保留并传递到下一代种群。
4. 交叉操作函数（改进的OX交叉）
   • crossover函数执行改进的顺序交叉（OX）操作，随机选择交叉点，将父代1在交叉点之间的基因片段复制到子代，然后从父代2中选择未在子代中出现的基因填充子代剩余位置，保证生成的子代个体具有一定的随机性和多样性，同时保留了父代的优良基因。
5. 变异操作函数
   • mutation函数实现变异操作，以给定的变异概率对个体进行变异，若随机数小于变异概率，则随机选择两个城市位置并反转它们之间的路径片段，引入新的基因，增加种群的多样性，有助于算法跳出局部最优解。
6. Metropolis准则接受函数
   • metropolis_acceptance函数根据Metropolis准则决定是否接受新路径，通过比较新路径和旧路径的适应度以及计算接受概率，在一定程度上接受劣解，增加算法跳出局部最优解的机会，提高算法的全局搜索能力。
7. 逆转操作函数
   • reversal函数执行逆转操作，随机选择两个城市并反转它们之间的路径顺序，然后比较原路径和逆转后的路径长度，保留较短路径，通过局部优化改进路径，加速算法收敛。
8. 遗传算法主函数
   • genetic_algorithm函数是算法的核心，执行以下操作：
     • 初始化种群，计算初始种群中每个个体的适应度，记录最优适应度和路径。
     • 进行迭代，在每次迭代中：
       • 选择操作生成新种群。
       • 对新种群进行交叉和变异操作。
       • 根据Metropolis准则对变异后的种群进行调整。
     • 迭代结束后，返回最优路径和最终的最优适应度。

（三）结果可视化

1. 最优路径绘制函数
   • plot_path函数用于绘制最优路径，将城市用蓝色线段连接表示城市间的可达性，用红色线段连接最优路径中的城市，直观展示旅行商的最优遍历路径，帮助用户更好地理解算法结果。
2. 适应度曲线绘制
   • 在主程序中，绘制最优适应度随迭代次数的变化曲线，展示算法的收敛过程，通过观察曲线的变化趋势，可以分析算法的收敛速度和稳定性。

四、实验结果

（一）实验设置

1. 参数调整
   • 在genetic_algorithm函数中，可调整参数包括种群规模pop_size、最大迭代次数max_gen、精英比例elite_ratio和变异概率mutation_rate等。增加种群规模和迭代次数可能提高解的质量，但会增加计算时间；调整精英比例会影响优秀基因的保留程度，进而影响算法的收敛速度；变异概率的大小决定了引入新基因的频率，对算法跳出局部最优解的能力有重要影响。

（二）结果展示

1. 最优路径和适应度
   • 运行代码后，输出最优路径（Best path）和最佳适应度（Best fitness），展示算法在给定距离矩阵下找到的最优旅行商路径及其对应的路径长度（适应度值）。通过多次运行代码或调整参数，可以进一步分析算法在不同条件下的性能表现，如最优解的稳定性、收敛速度等。
2. 对比实验结果

   • 文中将改进遗传算法（IGA）与传统遗传算法（GA）、粒子群算法（PSO）、蚁群算法（ACO）、模拟退火算法（SA）以及结合2 - opt局部寻优操作的混合遗传算法（HGA）在TSPLIB数据集不同城市规模的实例上进行测试。实验结果表明，IGA在中小型TSP问题的求解精度上更高，收敛速度更快。例如，在Oliver30、eil51等实例中，IGA的偏差率明显低于其他算法，且从迭代曲线可以看出，IGA的初始解具有优势，收敛速度较快，这得益于其种群初始化优化、自适应交叉和变异概率、Metropolis准则和逆转操作等改进策略。通过与其他算法的对比，验证了改进遗传算法在求解TSP问题上的有效性和优势。

   • 

   • 

部署方式

• python 3.8以上

资源获取

详细复现过程的项目源码、数据和预训练好的模型可从该文章下方附件地址获取。

附件地址：改进遗传算法复现