免疫遗传算法求解TSP及其性能对比分析系统

资 源 简 介

本系统利用MATLAB开发环境，实现了结合免疫机制与遗传算法的混合优化算法（IGA），专门用于解决经典的旅行商问题（TSP）。系统核心功能包括： 数据初始化：支持自定义城市坐标输入，自动生成城市间的欧氏距离矩阵，作为算法的基础计算依据。 算法实现：在传统遗传算法（GA）的选择、交叉、变异算子基础上，深层引入了生物免疫学的抗体浓度调节机制、免疫促进入选机制以及免疫记忆库。通过对抗体（即路径编码）浓度的实时计算，系统能够抑制相似度过高的个体繁盛，从而在保证全局搜索能力的同时，有效维持种群的基因多样性，从根本上

详 情 说 明

基于免疫遗传算法的TSP问题求解与性能对比分析系统

项目介绍

本系统是一个基于 MATLAB 开发的情境化仿真平台，旨在通过对旅行商问题（TSP）的求解，深入探讨和对比标准遗传算法（GA）与免疫遗传算法（IGA）的性能差异。TSP 问题要求寻找一条遍历所有城市并返回起点的最短路径，是一个典型的组合优化难题。本系统通过引入生物免疫学中的抗体浓度调节和免疫记忆机制，改进了传统遗传算法在搜索后期易陷于局部最优、种群多样性缺失的弊端，实现了更高效的全局路径寻优。

功能特性

1. 自动化城市建模：系统能够随机生成指定数量（默认30个）的城市坐标，并自动计算完整的欧氏距离矩阵，为算法提供基础评估依据。
2. 双算法同步仿真：共用同一套初始种群与环境参数，同步运行标准遗传算法与带有免疫机制的改进算法，确保对比实验的公平性与客观性。
3. 免疫调节机制：通过计算抗体间的相似度来评估种群浓度，利用适应度与浓度的综合权重来决定选择概率，有效抑制高浓度个体，维持基因多样性。
4. 记忆库进化策略：系统内置免疫记忆库，自动保留每一代中最优秀的基因片段，并在迭代中将其随机回馈至种群，保障了算法的收敛速度和精度。
5. 动态可视化呈现：实时绘制算法进化过程中的收敛曲线，并以图形化方式直观展示两种算法最终寻找到的最优路径结构。

使用方法

1. 确保您的计算机已安装 MATLAB 环境。
2. 将系统相关的所有代码文件放置在同一个工作目录下。
3. 在 MATLAB 命令行窗口中输入主函数名称并回车运行。
4. 系统将依次执行 GA 和 IGA 算法，并在命令行实时显示运行耗时。
5. 运行结束后，系统会自动弹出可视化窗口，展示最短距离对比图及两条最优路径的形状。

系统要求

• 操作系统：Windows, macOS 或 Linux
• 开发平台：MATLAB R2016b 及以上版本
• 硬件要求：基础运算能力即可，推荐 4GB 以上内存

核心功能与逻辑实现详解

数据初始化与生成逻辑

系统首先设定 30 个城市节点，利用固定随机种子的方式生成位于 100x100 区域内的随机坐标，以保证实验的可复现性。通过双重循环计算每两个城市间的几何距离，生成城市间距离矩阵，作为后续计算路径总长度的查找表。

标准遗传算法（GA）实现逻辑

算法按照经典的进化流程执行：

• 适应度计算：将个体路径总距离的倒数作为适应度值，距离越短，适应度越高。
• 选择算子：采用轮盘赌选择法（Roulette Wheel Selection），根据适应度占比决定个体进入下一代的概率。
• 交叉算子：执行部分映射交叉（PMX），在保留亲本部分优良路段的同时，通过映射关系解决基因冲突，生成合法子代。
• 变异算子：采用交换变异（Swap Mutation），随机交换路径中的两个城市位置，引入随机扰动。
• 最优保留：每一代都会识别当前最优个体并尝试更新历史最佳记录。

免疫遗传算法（IGA）实现逻辑

在 GA 的基础上，IGA 引入了复杂的免疫平衡机制：

• 免疫记忆库：专门开辟 10% 规模的存储空间，用于保留历代搜索到的最优抗体。
• 浓度计算：通过比对个体间的基因序列一致性，计算每个抗体在当前种群中的浓度。若两个体在相同位置拥有相同城市的比例超过 0.7，则判定为相似。
• 免疫选择概率：个体的最终被选概率由适应度和浓度共同决定。系统赋予适应度 70% 的权重，浓度（取指数负相关）30% 的权重。这一机制使得适应度虽高但重复性过强的个体受到抑制，通过提高“稀有”优良个体的保留率来防止早熟收敛。
• 记忆提取：在每一代进化后，将记忆库中的精英抗体随机替换回种群，确保优秀的基因能够被稳定遗传。

关键算法与细节分析

个体编码与评价

系统采用自然数排列编码，抗体长度等于城市数量。评价函数不仅考虑了城市间的顺序连接，还严格计入了从最后一个城市回到出发点的闭合距离。

部分映射交叉 (PMX) 细节

在执行交叉时，系统随机选取两个交叉点，交换中间段基因。对于剩余位置出现的重复城市，利用交叉段建立的映射关系进行迭代替换。这种逻辑保证了每一个城市在路径序列中出现且仅出现一次，满足 TSP 的合法解约束。

性能对比维度

系统从两个维度评估免疫机制带来的提升：

• 收敛精度：通过收敛曲线展示 IGA 是否能跳出 GA 可能陷入的局部极小值，获得更短的路径总长。
• 进化效率：对比完成相同迭代次数后的最短距离和计算耗时。尽管 IGA 增加了浓度计算的复杂度，但通常能以更少的迭代次数达到更优的解。

可视化逻辑

绘图模块将界面划分为四个区域：上方长图显示收敛曲线的交错与下行趋势；下方两个正方形区域分别通过坐标连线图展示 GA 与 IGA 的最终路径布局，标注出最终的最短距离数值。