基于免疫遗传算法的TSP求解与GA对比系统

资 源 简 介

本项目旨在利用MATLAB平台开发一套高效的免疫遗传算法（IGA）求解器，专门用于解决典型的旅行商问题（TSP），并深入探究其相对于传统遗传算法（GA）的性能优势。系统核心在于模拟生物免疫系统的机理来改进标准遗传算法，具体功能包括：1. 基础遗传算法模块构建，实现选择、交叉、变异等基本算子作为性能对比基准；2. 免疫算子设计与实现，重点包括“抗体浓度计算”以维持种群多样性，防止早熟收敛，以及“疫苗接种与提取机制”，利用TSP问题的局部特征知识（如距离矩阵信息）构建疫苗，对个体进行基因修补，从而提高搜索效率；3. 精确的TSP问题建模，支持30个以上城市的规模求解；4. 算法性能对比分析，系统能够自动统计并输出IGA与标准GA在同样条件下的收敛步数、最优解质量、平均解质量及算法稳定性等指标；5. 动态可视化展示，通过绘图实时显示路径的进化过程以及适应度收敛曲线，直观呈现免疫机制如何加速寻优过程。

详 情 说 明

基于MATLAB的免疫遗传算法TSP优化与对比分析系统

项目简介

本项目是一个基于MATLAB平台开发的高效旅行商问题（TSP）求解系统。该系统不仅实现了标准的遗传算法（GA）作为基准，更核心地构建了一套模拟生物免疫机制的免疫遗传算法（IGA）。通过引入抗体浓度调节、疫苗提取与接种机制，有效解决了传统遗传算法容易早熟收敛和搜索效率低下的问题。系统能够自动运行两种算法，并对同样条件下的收敛速度、最优解质量及稳定性进行全方位的对比分析与可视化展示。

功能特性

• 双算法求解引擎：内置标准遗传算法（GA）与改进型免疫遗传算法（IGA），支持并行对比。
• TSP问题精确建模：系统默认生成30个城市的随机坐标，采用欧氏距离构建30x30的距离矩阵，支持城市规模的灵活扩展。
• 免疫核心机制：

* 多样性维持：通过计算个体间的相似度（浓度），动态调整选择概率，防止种群陷入局部最优。 * 知识型疫苗：利用TSP问题的邻域知识（距离矩阵中的短边）构建疫苗库。 * 免疫修补：将疫苗注入个体基因片段，由于包含“免疫检验”步骤，确保了种群质量的单调非递减。

• 可视化分析：能够记录并绘制算法迭代过程中的收敛曲线，直观展示路径优化效果。
• 可复现性：内置随机种子控制，确保实验结果的可对比性与可复现性。

系统要求

• MATLAB R2016a 及以上版本
• 无需额外工具箱（代码仅使用MATLAB基础矩阵运算与绘图功能）

使用方法

1. 确保MATLAB当前工作目录为项目文件夹。
2. 在MATLAB命令行窗口输入 main 并回车，或直接运行 main.m 脚本。
3. 系统将依次执行以下步骤：

* 初始化地图与距离矩阵。 * 运行标准遗传算法，并在控制台输出进度。 * 运行免疫遗传算法，提取疫苗并进行优化。 * 弹出图形窗口，展示最终的路径规划图及适应度收敛对比曲线。

详细算法实现原理

本项目的核心逻辑全部主要集中在单一脚本中，分为主流程控制、核心算法函数、辅助功能函数及算子实现四个部分。以下是基于实际代码的详细解析：

1. 环境初始化与参数配置

系统首先固定随机数种子以保证实验可复现。随后生成30个城市的（X,Y）坐标，并计算城市间两两的欧氏距离矩阵。 算法参数设置：

• 种群规模：100
• 最大迭代次数：200
• 交叉概率：0.8
• 变异概率：0.1
• IGA特有参数：疫苗接种概率 0.6，浓度阈值系数 0.8。

2. 标准遗传算法 (GA) 实现逻辑

函数 RunGA 实现了经典的遗传算法流程：

• 适应度计算：取路径总距离的倒数作为适应度。
• 轮盘赌选择：根据适应度比例计算累积概率，随机选择父代个体。
• 次序交叉 (Order Crossover)：随机选择父代两个切点，保留中间片段，剩余基因按原顺序填充，有效避免了路径冲突。
• 交换变异：随机交换路径序列中的两个城市位置。

3. 免疫遗传算法 (IGA) 核心机制

函数 RunIGA 在标准GA的基础上引入了生物免疫系统的三个关键特征：

#### A. 疫苗提取 (ExtractVaccines) 利用先验知识（Distance Matrix）进行启发式提取。代码遍历每个城市，找出距离其最近的邻居城市，将“城市-最近邻居”这一对组合定义为一条“疫苗”。这意味着算法认为两个距离最近的城市在最优路径中应当是相邻的。

#### B. 浓度计算与免疫选择 (CalConcentration & SelectImmune) 为了维持种群多样性，代码实现了浓度计算机制：

• 浓度定义：通过随机抽样（20%的种群），计算当前个体与样本个体之间的“共享边”数量。如果两个个体间超过80%的边是相同的，则判定为相似。相似个体越多，该个体的浓度值越高。
• 免疫选择概率：结合适应度与浓度计算最终选择概率。公式设计倾向于选择“高适应度”且“低浓度”的个体，从而抑制高适应度个体的过度繁殖，防止早熟。

#### C. 疫苗接种与免疫检验 (InjectVaccines) 这是IGA加速收敛的关键算子。在每一代进化中，以0.6的概率执行接种操作：

• 接种目标：随机选择种群中30%的个体。
• 接种操作：从疫苗库中随机抽取一个疫苗（即一对紧邻城市[A, B]）。在目标个体的基因序列中找到A和B，保持A的位置不变，将B移动到A的紧邻位置，强制构成短路径片段。
• 免疫检验：这是一种贪婪策略。接种后，计算新路径的总距离。仅当新路径距离小于原路径距离时（适应度提高），才保留该变异；否则由于“排异反应”还原个体。这保证了疫苗接种只会带来正向收益。

4. 辅助算子细节

• 初始化：使用 randperm 生成随机排列作为初始种群。
• 交叉操作：采用了标准的次序交叉法（OX1），确保子代城市不重复、不遗漏。
• 变异操作：采用了通过交换两点位置的简单变异策略。
• 距离计算：严格按照TSP闭环路径（起点-终点-起点）计算总距离。

该系统通过上述机制，在保证代码逻辑严密的同时，清晰地展示了引入免疫机制后对组合优化问题求解能力的提升。