人工免疫算法（AIS算法）求解实例---旅行商问题 (TSP)
目录
一、采用AIS求解 TSP
完整代码关注博客底部微信公众号获得！
求解代码在文中，后续会出其他算法求解TSP问题，你们参加数学建模竞赛只需要会改代码即可。
用来对比此专栏的
遗传算法（GA算法）求解实例—旅行商问题 (TSP)
粒子群算法（PSO算法）求解实例—旅行商问题 (TSP)
模拟退火算法（SA算法）求解实例—旅行商问题 (TSP)
蚁群算法（ACO算法）求解实例—旅行商问题 (TSP)
禁忌搜索算法（TS算法）求解实例—旅行商问题 (TSP)
差分进化算法（DE算法）求解实例—旅行商问题 (TSP)
注意每次运行算法得到的结果可能不太一样。
我知道大家对原理性的东西不感兴趣，我把原理性的东西放在后面，大家如果需要写数模论文可以拿去，但是记得需要改一改，要不然查重过不去。
二、 旅行商问题
2.1 实际例子：求解 6 个城市的 TSP
假设有 6 个城市，其坐标如下：
| 城市 | X 坐标 | Y 坐标 |
|---|---|---|
| 0 | 10 | 20 |
| 1 | 30 | 40 |
| 2 | 20 | 10 |
| 3 | 40 | 30 |
| 4 | 10 | 10 |
| 5 | 50 | 20 |
目标是找到一个经过所有城市且总距离最短的路径。
2.2 求解该问题的代码，代码（完整代码关注底部微信公众号获取）
import numpy as np
import random
# 定义城市坐标
cities = np.array([
[10, 20],
[30, 40],
[20, 10],
[40, 30],
[10, 10],
[50, 20]
])
# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):
return np.sqrt(np.sum((city1 - city2) ** 2))
# 运行人工免疫算法
best_path, best_distance = ais_tsp(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)
2.3 代码运行过程截屏
2.4 代码运行结果截屏（后续和其他算法进行对比）
三、 如何修改代码？
这一部分是重中之重，大家参加数学建模肯定是想跑出自己的结果，所以大家只需要把自己遇到的数学问题，抽象成TSP问题，然后修改代码的城市坐标，然后运行即可。
# 定义城市坐标
cities = np.array([
[10, 20],
[30, 40],
[20, 10],
[40, 30],
[10, 10],
[50, 20]
])
3.1 减少城市坐标，如下：
# 定义城市坐标
cities = np.array([
[10, 20],
[30, 40],
[20, 10],
[40, 30]
])
3.2 增加城市坐标，如下：
# 定义城市坐标
cities = np.array([
[10, 20],
[30, 40],
[20, 10],
[40, 30],
[30, 40],
[20, 10],
[10, 10],
[50, 20]
])
四、人工免疫算法（Artificial Immune System, AIS）原理
人工免疫算法（AIS）是一种受到生物免疫系统启发而发展的智能优化算法。生物免疫系统具有识别和消灭外部病原体（如病毒、细菌等）的能力，通过学习和记忆机制，能够快速识别并应对新入侵的病原体。AIS 模拟了这种免疫系统的特性和机制，用于解决复杂的优化和分类问题。
4.1 AIS算法的核心概念
-
抗体（Antibody）：在 AIS 中，抗体通常表示一个候选解。例如，在旅行商问题（TSP）中，一个抗体可以表示城市访问顺序（路径）。
-
抗原（Antigen）：抗原是需要被识别和优化的问题或目标。在优化问题中，抗原表示需要求解的目标（例如，TSP 中的最短路径）。
-
亲和力（Affinity）：亲和力表示抗体与抗原之间的匹配程度。在优化问题中，亲和力通常由目标函数值表示，亲和力越高（或越低，取决于优化目标），表示解的质量越好。
-
克隆选择（Clonal Selection）：克隆选择是 AIS 的核心机制之一，表示根据亲和力对抗体进行选择、克隆和变异。质量越高的抗体会被选择生成更多的克隆体，并通过变异产生新的候选解。
-
亲和力成熟（Affinity Maturation）：在克隆选择之后，通过对克隆体进行变异和选择，使抗体的亲和力进一步提高，从而产生更好的解。这类似于遗传算法中的“变异”操作。
-
记忆集（Memory Set）：记忆集存储当前找到的最优解，以防止算法丢失已找到的优秀解。
4.2 AIS算法的工作流程
-
初始化：随机生成一组抗体（候选解），形成初始种群。
-
计算亲和力：对每个抗体计算其亲和力（即适应度函数），用以衡量抗体的质量。
-
克隆选择：根据亲和力对抗体进行选择，选择质量较高的抗体进行克隆。克隆率通常与亲和力成正比，即亲和力越高的抗体被克隆的数量越多。
-
变异操作：对克隆体进行变异操作，产生新的候选解。变异的目的是引入多样性，以探索解空间中的更多区域。
-
亲和力成熟：对变异后的克隆体重新计算亲和力，选择质量更高的解更新种群。
-
记忆更新：将当前找到的最优解存入记忆集中，以防止丢失优秀解。
-
终止条件：重复步骤 2-6，直到满足终止条件（如达到最大迭代次数或找到满意的解）。
4.3 AIS算法的优缺点
4.3.1 优点
-
全局优化能力强
通过克隆选择和亲和力成熟机制，AIS 能有效地进行全局搜索，避免陷入局部最优解。 -
自适应性好
AIS 能自动调整种群结构，通过亲和力评价和选择机制，提高算法的搜索效率。 -
具有记忆能力
AIS 可以记住并保存最优解，通过记忆集的机制防止解的退化，保持解的质量。 -
解决多样性问题
通过变异操作引入多样性，保持种群多样性，避免早熟收敛，提高算法的搜索空间覆盖率。 -
适用于多种优化问题
AIS 广泛应用于优化问题（如 TSP、背包问题）、模式识别与分类、数据挖掘与特征选择、网络安全等领域。
4.3.2 缺点
-
收敛速度较慢
在大规模或复杂问题中，由于需要进行大量的克隆、变异和亲和力计算，收敛速度可能较慢。 -
参数设置敏感
算法性能对参数的选择（如克隆率、变异率、种群大小等）敏感，参数不恰当可能导致局部最优或过早收敛，需要大量调参。 -
容易陷入局部最优解
尽管变异操作引入了多样性，但在解空间复杂或具有大量局部最优解的情况下，算法仍有可能陷入局部最优。 -
计算复杂度高
克隆、变异和亲和力计算的操作对计算资源要求较高，对于大规模问题或多维问题，计算复杂度显著增加。 -
对问题特征依赖较强
AIS 的有效性在很大程度上取决于问题的特征，在某些问题上可能无法比其他优化算法取得更好效果。 -
缺乏理论分析
相较于其他经典优化算法，AIS 算法的理论基础和收敛性分析较少，理论研究不够完善。 -
实现复杂度较高
AIS 涉及多个复杂的过程（如克隆选择、亲和力成熟等），实现和调试较为复杂，需要更多的时间和精力。
4.4 AIS算法的应用
- 优化问题（如 TSP、背包问题）
- 模式识别与分类
- 数据挖掘与特征选择
- 网络安全（如入侵检测）
原文地址：https://blog.csdn.net/qq_63913621/article/details/142299217
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！