基于双种群协同进化蚁群算法的TSP路径优化

资 源 简 介

本项目致力于解决经典的旅行商问题（Travel Salesman Problem, TSP），采用了一种改进的启发式算法——双种群蚁群算法。该算法克服了传统单种群蚁群算法容易陷入局部最优且收敛速度慢的缺陷。系统通过构建两个具有不同特征或不同进化侧重点的蚁群（例如，一个种群侧重于全局探索以增加解的多样性，另一个种群侧重于局部开发以加速收敛），这两个种群在独立的搜索空间内并行运行，并通过特定的信息交流机制共享最优路径信息，从而协同寻找全局最优解。项目涵盖了从小规模到大规模的测试用例，具体功能包括：1. 算法核心引擎实现了双种群的协同进化逻辑、信息素更新规则及路径选择概率计算；2. 能够读取并解析多种规模的MATLAB格式数据文件，支持坐标数据的导入与距离矩阵的自动计算；3. 集成了“30城市TSP问题数据与最优解.mat”用于算法基准验证，确保基础逻辑正确；4. 使用“75城市TSP问题数据.mat”测试算法在中等规模问题下的稳定性；5. 利用“442TSP问题数据与算法对比.mat”进行大规模复杂场景下的压力测试，并提供与其他算法的数据对比接口；6. 系统具备完善的可视化模块，不仅能绘制最终的最优路径拓扑图，还能实时生成迭代收敛曲线，展示两个种群在迭代过程中的适应度变化趋势。

详 情 说 明

基于双种群蚁群算法的TSP路径优化系统

这是一个基于MATLAB开发的旅行商问题（TSP）路径优化项目。该系统采用了一种改进的双种群蚁群算法（Dual-Population Ant Colony Optimization），通过构建两个具有不同进化策略的种群并行搜索，并结合协同进化机制，有效解决了传统单种群算法易陷入局部最优和收敛速度慢的问题。

项目介绍

本项目针对TSP问题，通过模拟两组蚂蚁的觅食行为来寻找城市间的最短遍历路径。代码不仅实现了核心算法逻辑，还包含了完整的数据处理、协同进化机制以及可视化的结果展示。

系统设计的核心在于差异化的种群配置：

1. 种群A（探索型）：参数设置侧重于全局搜索，保留较多的历史信息素，旨在维持解的多样性，探索潜在的优质解区域。
2. 种群B（开发型）：参数设置侧重于局部开发，具有较高的启发式因子权重和挥发速率，仅允许精英个体更新信息素，旨在快速收敛到最优解。

功能特性

• 双种群协同进化：实现了两个独立种群的并行迭代，分别配置了不同的$alpha$（信息素重要度）、$beta$（启发因子重要度）、$rho$（挥发因子）和$Q$（增强系数）参数。
• 差异化更新策略：

* 种群A采用全员更新策略，保留历史经验。 * 种群B采用精英更新策略，仅对当代前50%的优质个体进行信息素增强。

• 动态信息交互：系统设定每隔10代，提取当前的全局最优路径信息，将其注入到两个种群的信息素矩阵中，实现优势互补。
• 多源数据支持与容错：支持加载30、75、442城市规模的标准MATLAB数据文件（.mat）。若无法找到指定文件，系统会自动生成对应数量的随机坐标数据进行模拟演示，保证程序始终可运行。
• 可视化监控：

* 路径规划图：绘制最终的城市分布及最优连线路径，标注起点。 * 收敛曲线图：同屏展示种群A、种群B以及全局最优解的迭代收敛趋势，便于分析算法性能。

系统要求

• MATLAB R2016a 或更高版本
• 无需额外工具箱，使用基础绘图和计算功能

核心算法逻辑与实现细节

本项目的核心逻辑集中在主脚本中，以下是对代码实际实现功能的详细分析：

1. 参数初始化与差异化配置

代码首先定义了算法的超参数，体现了双种群的设计思想：

• 种群A：$alpha=1.0, beta=2.0, rho=0.1$。较低的挥发率使得信息素保留时间更长，利于广泛探索。
• 种群B：$alpha=2.0, beta=5.0, rho=0.5$。较高的$beta$值和挥发率意味着蚂蚁更倾向于选择短距离路径且快速淘汰劣质路径。

2. 初始化与数据准备

系统根据用户设定的 dataType 变量加载数据。通过 loadData 函数尝试读取 .mat 文件，若文件缺失或格式不符，则调用 generateMockData 使用随机数生成器（固定种子42）创建模拟坐标。随后计算城市间的欧氏距离矩阵，并初始化启发函数矩阵（距离的倒数）和信息素矩阵。

3. 设置迭代主循环

算法进行 maxGen（默认200）次迭代，每次迭代包含以下步骤：

• 路径构建：

利用 constructRoute 函数，两个种群的每只蚂蚁基于当前的信息素浓度和启发函数，通过轮盘赌算法（Roulette Wheel Selection）选择下一个城市，构建完整的访问路径。

• 适应度计算与局部寻优：

计算每个种群中每只蚂蚁的路径长度，找出种群A和种群B各自的当代替代最优解。

• 全局最优更新：

比较两个种群的最优解与历史全局最优解，更新全局最短路径 globalMinCost 和对应的路线 globalBestRoute。

• 信息素更新（关键逻辑）：

* 种群A更新：所有蚂蚁根据其路径长度释放信息素，更新公式包含较低的挥发操作。 * 种群B更新：执行排序操作，仅选择路经长度最短的前50%（精英）蚂蚁进行信息素增强，且挥发操作更剧烈。

• 协同机制（信息交流）：

代码中通过取模运算判断，每逢10倍数的代数（如第10、20...代），将全局最优路径的信息素以 Q_B / globalMinCost 的强度额外叠加到两个种群的信息素矩阵中。这一步强制两个种群向当前发现的全局最优方向靠拢。

4. 结果可视化

算法结束后，创建一个图形窗口显示结果：

• 左子图：显示城市节点的散点图及红色的最优闭环路径，并用绿色圆圈和文字标注起始点。
• 右子图：绘制三条收敛曲线。绿色虚线代表种群A，蓝色虚线代表种群B，红色实线代表全局最优。这直观地展示了种群A的波动探索性和种群B的快速收敛性。

关键函数剖析

• main：主控制流，负责参数定义、循环控制、种群协调和绘图逻辑。
• constructRoute：实现单只蚂蚁的路径搜索。包含状态转移概率计算公式：$P propto tau^alpha cdot eta^beta$。若分母为0或选中概率极低，包含随机选择机制防止程序报错。
• calculateLength：计算给定路径序列的总欧氏距离，包含从终点回到起点的距离。
• plotRoute：用于绘制TSP结果的专用绘图函数，处理坐标点和连线的可视化。
• loadData：负责数据IO。具备异常捕获机制（try-catch），能够智能识别数据文件中的变量名（支持 cityPos, cities, C 等常见命名），并在读取失败时自动切换到模拟数据生成。

使用方法

1. 将代码保存为 MATLAB 脚本文件（例如 main.m）。
2. （可选）将 30城市TSP问题数据与最优解.mat 等数据文件放置在与脚本相同的目录下。
3. 打开脚本，根据需要修改 dataType 变量的值来选择测试规模：

* 1: 30城市案例 * 2: 75城市案例 * 3: 442城市案例

1. 运行脚本。
2. 观察命令行窗口中的实时迭代日志，以及弹出窗口中的最终路径图和收敛曲线。