智能信息处理导论PPT第7章__免疫算法

(7)Ｂ细胞：即Ｂ淋巴细胞，来源于骨髓淋巴样前体细 胞，成熟的Ｂ细胞存在于淋巴结、血液、脾、扁桃体 等组织和器官中，Ｂ细胞是体内产生抗体的细胞，在 清除病原体过程中受到刺激，分泌抗体结合抗原，但 其发挥免疫作用要受Ｔ辅助细胞的帮助。
7.1.1 免疫系统的形态空问
如图所示，在形态空间ｓ 内有一个体积为V的区域， 其中含有抗体（用 来表示） 和抗原（用×表示）的形状 互补区域。假设一个抗体能 识别所有在其周围体积 范围内的互补的抗原。
算法的状态转移情况：
X为搜索空间 n0的群体认为是状态空间S=Xn0中的一个点 |S|表示S中状态的数量
si sj 表示 si，sj 作为 X 的子集时的包含关系
Vki 表示随机变量 V 在第 k 代时处于状态 si
7.2.5 免疫算法的收敛性
设 f 是 X 上的适应度函数，令
S* {x X f (x) max f (xi )}
免疫调节：在免疫反应过程中，大量的抗体的产生降低了 抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同 时产生的抗体之间也存在着相互刺激和抑制的关系，这种 抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫 反应维持一定的强度，保证机体的免疫平衡。
7.2.3 免疫算法中涉及的术语简介
免疫记忆：指免疫系统将能与抗原发生反应的抗体作 为记忆细胞保存记忆下来，当同类抗原再次侵入时， 相应的记忆细胞被激活而产生大量的抗体，缩短免疫 反应时间。
送中心； 结点的供货薰和需求量为一定值； 配送中心使用的车型相同，即所有车辆的装载能力相同，
7.1 免疫算法的生物学基础
7.1.1 免疫系统的形态空问 7.1.2 免疫应答 7.1.3 多样性 7.1.4 克隆选择和扩增
7.1.1 免疫系统的形态空问
基本概念和技术术语： (1)免疫：指机体免疫系统识别自身与异己物质，并通过免
疫应答排除抗原性异物，以维持机体生理平衡的功能。
(2)免疫应答：是指抗原进入机体后，免疫细胞对抗原分子 的识别、激活、分化、增殖和效应的过程。
7.2.1 人工免疫系统的定义
De Castro后来为人工免疫系统给出了第二个定义： “人工免疫系统是受生物免疫系统启发而来的用于求解 问题的适应性系统”。
Timmis后来也为人工免疫系统给出了第二个定义，即： “人工免疫系统是一种由理论生物学启发而来的计算范 式，借鉴了一些免疫系统的功能、原理和模型并用于 复杂问题的解决”。
优势：
改进的疫苗提取算法
疫苗的自我识别 分区域提取疫苗 疫苗提取算法 疫苗的构造
7.3.3 免疫算法的原理及优势
优势：
改进的注射疫苗算法
随机从疫苗库中选取一个疫苗 利用该疫苗所含位置信息，寻找疫苗注射的合理位置 找到个体中与将要注射的疫苗相冲突部分，并将冲突
部分删除 在找到的注射位注射疫苗
7.2 免疫优化算法概述
7.2.1 7.2.2 7.2.3 7.2.4 7.2.5 7.2.6 7.2.7 7.2.8
人工免疫系统的定义 免疫算法的提出 免疫算法中涉及的术语简介 免疫算法的算法思想 免疫算法的收敛性 免疫算法与免疫系统的对应 常见免疫算法 免疫算子说明
7.2.1 人工免疫系统的定义
选择n个具有较高亲和力的个体； 克隆这ｎ个最好的个来自，组成一个临时的克隆群体（C）。
与抗原亲和力越高，个体在克隆时的规模也就越大；
把克隆群体提交到高频变异，根据亲和力的大小决定变异。 产生一个成熟的抗体群体(Ｃ*)；
对Ｃ*进行再选择，组成记忆细胞集合Ｍ。Ｐ中的一些成员可 以被Ｃ*中的其它一些改进的成员替换掉；
生成ｄ个新的抗体取代Ｐ中ｄ个低亲和力的抗体，保持多样性。
7.2.7 常见免疫算法
克隆选择算法
在克隆选择算法表现出的重要特征中，高频变异(hypermutation)、受体编辑 （receptor editing）是其重要的组成部分，它们是实现多样性的基本保障。高频 变异机制的目的是为了使免疫应答能够快速地成熟。整数形态空间可以被看成是 字母表大小缩小了的海明形态空间。
7.4.1 装卸一体化的物流配送VRP描述
数学模型假设：
每一车辆的都有一定的装载能力限制，配送路径上各结 点的供货量和需求量均不超过汽车的核定载重量；
每辆车只有一条行驶路线。期间可以为多个结点服务； 每个结点的集送货服务只能由一辆车提供； 封闭式配送，即每辆车的路线的开始和结束位置都在配
7.1.2 免疫应答
免疫系统的两种免疫应答类型：固有性免疫应答；适 应性免疫应答。
免疫算法主要是利用适应性 免疫应答的应答原理，适应 性免疫应答又分为两种类型， 初次免疫应答和二次免疫应答。
7.1.3 多样性
免疫系统的多样性，本质就是抗体的多样性，即产生 尽可能多的抗体对抗千变万化的抗原。
区别：
免疫算法起源于抗原和抗体之间的内部竞争，其相互作 用的环境既包括外部也包括内部的环境；而遗传算法起 源于个体和自私基因之间的外部竞争；
免疫算法假设免疫元素互相作用，即每一个免疫细胞等 个体可以互相作用，而遗传算法不考虑个体之间的作用；
免疫算法中，基因可以由个体自己选择，而在遗传算法 中基因由环境选择；
7.4.1 装卸一体化的物流配送VRP描述
问题描述：有ｎ个结点需要提供装货或卸货服务，表 示为ｌ，…，ｎ，可使用车辆数为Ｋ（Ｋ条物流配送 路径），每条路径都有自己的装货点和送货点。
已知：要求在结点ｉ的装货量为 ，卸货量为 。这些任 务由车场发出的车辆来完成，假设车辆容量为 ，已知 、 <。
求解：如何确定车辆行驶线路，使得总费用最小或者 总行车路线最短。
定义 1 如果对于任意的初始分布均有
lim
k si
P{Ak} 1，则称算法收敛。
S*
7.2.6 免疫算法与免疫系统的对应
7.2.7 常见免疫算法
否定选择算法
具体步骤:
定义一个自体字符串集合Ｓ，例如，Ｓ可以是一个程 序，数据文件（任何软件）或一般的行为模式.
随机产生一个检测器集合Ｒ，其中每一个字符串都不 能与集合Ｓ中的字符串相匹配。该算法中的匹配不是 完全匹配，而是部分匹配，只要有连续ｒ位相同就称 为匹配，此ｒ为一个可选择的参数。
可用集合的产生：如果Ｐ中某个元素与Ｓ中某个元素 的亲和力大于或等于一个给定的阈值，即这个Ｔ细胞 能识别这个自体，则它肯定被系统选用，放入Ａ；否 则删除它。
7.2.7 常见免疫算法
克隆选择算法
具体步骤：
生成候选方案的一个集合（P）（初始群体），它由记忆细 胞（M）的子集合加上剩余群体（Pr）（P＝Pr＋M）；
免疫系统的多样性的实现： 体细胞高频变异 受体编辑 随机生成新抗体
7.1.4 克隆选择和扩增
基本思想：只有那些能够识别抗原的细胞才进行扩增， 只有这些细胞才能被免疫系统选择并保留下来，而那 些不能识别抗原的细胞则不被选择，也不能进行扩增。
扩增过程：抗体C分化成许多克隆细胞，每一个克隆 细胞受到刺激后又开始克隆，这样，增加了免疫系统 中清除异物的抗体的数量。
7.3.1 两者关系
区别：
免疫算法中，基因组合是为了获得多样性，一般不用交 叉算子，因为免疫算法中基因是在同一代个体进行进化， 这种情况下，设交叉（杂交）概率为０；而遗传算法后 代个体基因通常是父代交叉的结果，交叉用于混合基因。
免疫算法选择和变异阶段明显不同，而遗传算法中他们 是交替进行的。
7.3.2 遗传算法的原理及缺陷
原理：利用遗传算法解决最优化问题，首先应对可行 域中的点进行编码，然后在可行域中随机挑选一些编 码作为进化起点的第一代编码组，并计算每个解的目 标函数值。
缺陷：早熟收敛、随机漫游、控制参数的选择等
7.3.3 免疫算法的原理及优势
核心思想：在合理提取疫苗的基础上，通过接种疫苗 和免疫选择两个操作步骤来提高群体适应度，加速迭 代过程并防止群体的退化。
改进的免疫算法流程
利用浓度概念计算 记忆细胞和抑制细胞 分化
利用期望值计算抗 体产生的促进和抑制
通过随机决定基因 产生新抗体，取代在 前面被消除的抗体
7.4 免疫优化算法在VRP中的应用
7.4.1 7.4.2 7.4.3 7.4.4 7.4.5 7.4.6
装卸一体化的物流配送VRP描述 抗体编码 初始抗体的产生 抗体亲和力计算 产生记忆/抑制细胞 选择、交叉、变异
(3)抗原与抗体：诱导免疫系统产生免疫应答的物质称为抗 原(antigen)；能与抗原进行特异性结合的免疫细胞称为抗 体(antibody)。
(4)亲和力(affinity)：免疫细胞的表面受体和抗原决定基都 是复杂的含有电荷的三维结构，二者的结构和电荷越互补， 就越有可能相互结合，结合的强度即是亲和力。
莫宏伟给出的人工免疫系统的定义为：“人工免疫系统 是基于免疫系统机制和理论免疫学而发展的各种人工 范例的特称。
7.2.3 免疫算法中涉及的术语简介
抗原：在生命科学中，是指能够刺激和诱导机体的免 疫系统使其产生免疫应答，并能与相应的免疫应答产 物在体内或体外发生特异性反应的物质。在我们的算 法中，是指所有可能错误的基因，即非最佳个体的基 因。
抗原识别：通过表达在抗原表面的表位和抗体分子表 面的对位的化学基进行相互匹配选择完成识别，这种 匹配过程也是一个不断对抗原学习的过程，最终能选 择产生最适当的抗体与抗原结合而排除抗原。
7.2.4 免疫算法的算法思想
7.2.4 免疫算法的算法思想
根据流程图具体过程为：
①随机产生初始父代种群A1； ②根据先验知识抽取疫苗；
抗体：在生命科学中，是指免疫系统受抗原刺激后， 免疫细胞转化为浆细胞并产生能与抗原发生特异性结 合的免疫球蛋白，该免疫球蛋白即为抗体。在本文中 是指根据疫苗修正某个个体的基因所得到的新个体。
7.2.3 免疫算法中涉及的术语简介
免疫疫苗：根据进化环境或带球问题，所得到的对最佳个 体基因的估计。