基于遗传算法的五城市旅行商问题求解器

资 源 简 介

本项目利用遗传算法（Genetic Algorithm, GA）解决经典的旅行商问题（TSP）。以五个城市为算例，旨在寻找一条在访问每个城市一次并返回起点的所有路径中，总行程距离最短的最优路径。程序通过模拟自然选择和遗传进化的过程，初始化包含多条随机路径的种群，并采用启发式搜索策略进行迭代优化。具体实现流程包括：首先建立城市坐标矩阵并预计算城市间的欧几里得距离矩阵；接着生成包含随机城市排列的初始个体；在每一代演化过程中，根据路径总长度的倒数计算每个个体的适应度函数值，适应度较高的个体有更高概率被选中进入下一代。算法运用了轮盘赌选择法来保留优良基因，并通过部分匹配交叉（PMX）操作在保证每个城市仅被访问一次的前提下产生新后代。为了防止算法陷入局部最优，引入了变异操作以维持种群的多样性。程序会实时记录每一代的最优路径和对应的最短距离，并在迭代完成后输出全局最优解。该项目不仅提供了完整的MATLAB源代码，还通过图形化方式展示了求解过程，适用于物流配送、线路规划、电子元件组装等多种实际应用场景，为学习启发式算法在组合优化问题中的应用提供了典型范例。

详 情 说 明

基于遗传算法的五城市旅行商问题求解器

本项目通过模拟自然进化过程，提供了一个解决旅行商问题（TSP）的启发式优化方案。程序以五个具有特定二维坐标的城市为算例，旨在搜索一条总行程距离最短的闭合路径，确保每个城市被访问且仅被访问一次，最后回到起点。

1. 项目介绍

旅行商问题是一个经典的组合优化问题。本项目通过遗传算法中的选择、交叉和变异操作，在广阔的搜索空间中寻找最优解。程序不仅实现了算法的逻辑核心，还集成了结果的可视化功能，能够直观展示算法的收敛过程以及最终搜索到的最优路径图。

2. 功能特性

• 自动化距离计算：根据预设的城市二维坐标，自动计算并生成欧几里得距离矩阵。
• 种群演化机制：支持自定义种群规模和进化代数，通过迭代不断改良路径质量。
• 启发式算子集成：实现了轮盘赌选择法、部分匹配交叉（PMX）和交换变异等标准遗传操作。
• 性能监控：实时记录并追踪每一代的最优解，确保算法能够收敛到全局或局部最优。
• 双重可视化展示：生成的图表涵盖了收敛曲线图和地理路径分布图，便于分析算法性能。

3. 系统逻辑实现说明

程序遵循标准的遗传算法流程，具体逻辑如下：

1. 参数初始化与环境搭建

• 设定种群规模为 40 个个体，最大进化迭代次数为 100 代。
• 设置交叉概率为 0.8，变异概率为 0.1。
• 定义 5 个城市的静态坐标矩阵，并通过双重循环计算两两城市间的几何距离，存储于距离矩阵中。

2. 初始种群生成

• 随机生成 40 条包含 1 到 5 数字的全排列序列，每个序列代表一种可能的城市访问顺序。

3. 适应度评价与选择

• 路径长度计算：计算每个个体从起点出发，按序列访问所有城市并最终返回起点的总路程。
• 适应度函数：采用路径总长度的倒数作为适应度值，路径越短，个体适应度越高。
• 轮盘赌选择：根据个体适应度在总适应度中的占比分配选择概率，通过累计概率分布进行随机抽样，保留优良个体。

4. 遗传算子操作

• 部分匹配交叉 (PMX)：随机选择两个交叉点，交换父代个体间的中间段。针对交换后产生的城市访问冲突，利用中间段的映射关系进行修正，确保每个城市在路径中唯一。
• 交换变异：以指定概率随机选取路径中的两个位置并交换其城市索引，以维持种群多样性，防止算法过早陷入局部最优。

5. 精英保留策略

• 在每一代更新种群后，强制将当前种群中的第一个个体替换为历史最优路径，确保最优基因不会因随机操作而丢失。

6. 输出与可视化

• 控制台输出：打印最终搜索到的最短路径距离及具体的城市访问序列。
• 收敛曲线：绘制进化代数与最短距离的关系图，展示算法的优化轨迹。
• 路径轨迹图：在坐标系中通过散点标记城市位置，并用线条连接成闭合环路，展示最优行程。

4. 关键算法细节分析

• 距离矩阵计算：利用欧几里得公式 $d = sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ 预计算空间成本。
• PMX 交叉逻辑：该算法的核心难点在于处理置换编码的冲突。程序通过 while 循环和映射查找，确保在交换片段后，重复的城市编号被替换为对应映射位置的城市编号。
• 闭合回路处理：在计算路径长度和绘图时，程序显式地将路径的最后一个城市与第一个城市相连，符合 TSP 问题的闭合环路定义。

5. 使用方法

1. 确保计算机已安装 MATLAB 环境。
2. 将程序代码复制或导入 MATLAB 编辑器中。
3. 直接运行程序脚本。
4. 在 MATLAB 控制台查看数值结果，并观察自动弹出的两个图形窗口。

6. 系统要求

• 软件环境：MATLAB R2016b 或更高版本。
• 硬件要求：基础办公配置即可，计算量级较小，运行时间通常在秒级。