基于GA-PSO混合算法的旅行商问题求解源码

资 源 简 介

本项目旨在利用MATLAB开发一套高效的混合进化算法，专门用于解决组合优化领域经典的NP难问题——旅行商问题（TSP）。系统核心在于结合了遗传算法（GA）的交叉变异机制与离散粒子群算法（BPSO）的群体智能搜索特性。鉴于标准PSO算法主要针对连续空间优化，本项目借鉴BPSO思想解决离散路径问题，并将GA中的交叉运算引入到粒子速度和位置的更新过程中。具体实现上，算法将“速度”定义为某种操作集合（如交换子或交叉序列），利用学习因子（c1, c2）来限制这种离散速度的变化范围和方向。为了平衡全局搜索与局部开发能力，算法借用惯性系数w作为概率阈值来实现速度更新的选择机制：在迭代过程中，系统生成一个0到1之间的随机数rand(0,1)，将其与惯性系数w进行比较；根据比较结果，决定粒子是保持当前的运动惯性，还是通过交叉算子分别与个体历史最优解（Pbest）或全局最优解（Gbest）进行信息交换，从而得到新的离散速度变量并更新城市访问序列。该系统能够自动加载城市数据，执行混合优化计算，最终输出收敛后的最短路径方案。

详 情 说 明

基于GA-PSO混合算法的旅行商问题求解系统

项目简介

本项目基于MATLAB平台开发，旨在利用混合进化算法求解经典的组合优化难题——旅行商问题（TSP）。系统创新性地结合了遗传算法（GA）的交叉变异算子与离散粒子群算法（BPSO）的群体智能搜索机制。

传统的PSO算法主要针对连续空间优化，而TSP属于离散路径规划问题。本项目通过重新定义粒子群的“速度”与“位置”更新规则，利用概率阈值机制在“惯性保持（自我变异）”与“社会学习（交叉操作）”之间进行动态切换，有效平衡了算法的全局探索能力与局部开发能力，能够快速收敛并寻找高质量的最短路径解。

功能特性

• 混合优化策略：将GA的交叉和变异操作嵌入到PSO的迭代框架中，解决离散空间的路径更新问题。
• 动态参数调整：采用线性递减权值（Inertia Weight）策略，随着迭代进行，算法重心从全局搜索逐渐转向局部精细搜索。
• 随机场景生成：系统自动在 $[0, 100]$ 的坐标范围内随机生成指定数量的城市节点，并计算欧氏距离矩阵。
• 概率化更新机制：利用随机数与惯性权重的比较结果，智能选择执行变异操作（模拟物理惯性）或交叉操作（模拟向个体最优/全局最优学习）。
• 实时可视化：提供双子图显示界面，左侧实时绘制城市位置及当前最优路径连线，右侧实时绘制适应度（路径长度）收敛曲线。
• 种群历史记忆：每个粒子均记录其历史最优路径（Pbest），整个种群记录全局最优路径（Gbest）。

算法实现逻辑 (main.m)

本项目的核心逻辑位于 main.m 文件中，其具体实现流程如下：

1. 参数设置与数据初始化

• 系统预设了30个城市节点，种群规模为100个粒子，最大迭代次数为500次。
• 定义了PSO的核心参数：惯性权重范围 $[0.9, 0.4]$，个体学习因子 $c1=0.7$，社会学习因子 $c2=0.8$，以及变异概率 $0.1$。
• 随机生成数据：使用固定的随机种子（rng('default')）生成30个城市的二维坐标，并预先计算全连接的距离对称矩阵以加速后续计算。

2. 种群初始化

• 位置编码：粒子的位置被编码为城市的访问序列（Permutation，即1到N的随机排列）。
• 初始化阶段，系统为每个粒子生成随机路径，计算初始适应度，并初始化个体历史最优（Pbest）和全局最优（Gbest）。
• 初始化可视化窗口，准备绘制动态图表。

3. 多策略混合迭代 (核心机制)

在主循环中，算法执行以下操作：

• 线性递减权重：在每次迭代开始时，计算当前的惯性权重 $w$。该权重不仅代表惯性大小，在本项目中还充当了策略选择的概率阈值。
• 策略选择与位置更新：对于每一个粒子，生成一个随机数 rand() 并与 $w$ 进行比较：

* 惯性/自我探索阶段 (当 rand() < w)：模拟粒子保持当前运动惯性。在离散场景下，这被实现为变异操作（Swap Mutation），即在当前路径基础上进行微小扰动。 * 学习/群体智能阶段 (当 rand() >= w)：模拟粒子向更优解靠拢。 * 个体认知：以概率 $c1$ 与该粒子的历史最优解（Pbest）进行交叉操作。 * 社会认知：以概率 $c2$ 与全局最优解（Gbest）进行交叉操作。

• 评估与更新：计算新路径的距离成本。如果发现更优解，则更新粒子的当前位置；同时维护 Pbest 和 Gbest。

4. 结果可视化与输出

• 每隔10代（以及首末代），系统会刷新图形窗口：

* 路径图：显示当前 Gbest 对应的哈密顿回路。 * 收敛图：绘制从第1代到当前代的全局最优适应度变化。

• 迭代结束后，在控制台输出最短路径长度及具体的城市访问序列。

关键函数说明

calculateFitness(path, distMat)

功能：计算路径总长度（适应度）。 逻辑：遍历输入的城市序列，累加相邻城市间的欧氏距离，最后加上终点回到起点的距离，形成闭环总长。

applyCrossover(parent1, parent2)

功能：执行路径交叉操作，模拟PSO中的速度更新和向最优解学习的过程。 逻辑：采用顺序交叉 (Order Crossover, OX1)。

1. 随机选择 parent1的一段基因（子路径）。
2. 保留该段基因在子代中的位置和内容。
3. 遍历 parent2，将其中尚未包含在子代中的城市，按照在 parent2 中的相对顺序依次填充到子代的剩余位置。

此方法保证了生成的路径由有效且不重复的城市序列组成。

applyMutation(path, rate)

功能：执行变异操作，模拟PSO中的惯性运动或随机扰动。 逻辑：

1. 交换变异 (Swap)：根据变异概率，随机选取两个位置交换城市。
2. 逆转变异 (Inversion)：为了增强局部搜索能力，代码中还内嵌了二次变异逻辑（50%概率），随机选择一段路径序列进行逆序排列（Flip）。

plotHamiltonianPath(coords, path, cost, iter)

功能：绘制TSP可视化图。 逻辑：在二维坐标系中绘制红色的城市散点，并按照当前最优路径顺序用蓝色线条连接所有点（包括首尾相连），并在标题中显示当前迭代数和路径长度。

使用方法

1. 确保计算机上已安装 MATLAB 软件。
2. 直接运行 main.m 脚本。
3. 程序将自动开始迭代计算，弹出图形窗口显示优化进度。
4. 运行结束后，查看 Command Window 获取最终的最短路径数值和序列。

系统要求

• 软件：MATLAB R2016a 或更高版本。
• 工具箱：无特殊工具箱需求（代码仅使用了基础绘图和数学函数）。