智能控制理论和方法(第二版)第章人工免疫算法及其在智能控制中的应用课件.ppt

1、第8章 人工免疫算法及其在智能控制中的应用第8章 人工免疫算法及其在智能控制中的应用8.1 引言8.2 人工免疫系统与基本免疫算法简介8.3 基于生发中心反应的全局优化算法8.4 人工免疫网络算法(aiNet)第8章 人工免疫算法及其在智能控制中的应用 8.1 引引 言言8.1.1 自然免疫系统的组成自然免疫系统的组成自然免疫系统是由分子、细胞、组织和器官组成的一个有机联合体。它是一个多层次的防御系统，主要有物理屏障层(皮肤、粘膜等)、生理屏障层(泪液、唾液、胃酸和汗液等)、先天免疫和适应性免疫系统。通常，免疫系统主要是由参与适应性免疫响应的器官、组织、细胞和免疫活性介质组成的。免疫系统的组成

2、如表8.1所示5。第8章 人工免疫算法及其在智能控制中的应用第8章 人工免疫算法及其在智能控制中的应用8.1.2 自然免疫系统的机理自然免疫系统的机理先天免疫系统为人类提供了第一道能抵抗和消灭入侵病原体的防卫。它主要包括皮肤、粘膜和屏障结构的屏障作用(外部的)以及某些具有杀菌和吞噬作用的免疫细胞(如粒细胞、单核巨噬细胞)等。在人类的生存环境中，某些病原体能突破人的先天免疫系统防线，在人体内生长繁殖，引起感染，此时机体会经历同某一种病原体(抗原)斗争(识别与杀灭)的过程。这一过程称为适应性免疫。参与适应性免疫的细胞有多种，主要有免疫细胞(T细胞、B细胞等)及它们相互作用后产生的特异性免疫效应物质

3、(又称为淋巴免疫球蛋白)。抗体的一种主要形式是依附于B细胞表面的膜结合形态。抗体与细胞膜结合后形成的复合体也称B细胞受体(见图8.1)。抗体是Y形状的一种感受器分子，生在B细胞的表面，其主要作用是通过互补配合，识别抗原，并与抗原粘合。抗原被抗体所识别的部位叫表位，又称抗原决定簇。一个抗原可以与多个抗体相粘合(见图8.2)。抗原和抗体之间的匹配程度称为它们之间的亲和度。第8章 人工免疫算法及其在智能控制中的应用图8.1 B细胞受体或者抗体的结构第8章 人工免疫算法及其在智能控制中的应用图8.2 一个抗原和多个抗体粘合第8章 人工免疫算法及其在智能控制中的应用在适应性免疫系统中，抗原一旦进入机体，

4、抗原分子中的抗原表位就被T和B细胞识别，从而诱导产生免疫细胞活化、适应性地识别特异抗原、分化和响应过程。此一系列过程被称为免疫响应。过程中生产的免疫细胞具有记忆特性，当下一次再遇同一特异抗原时能产生更快的响应。免疫的响应过程如图8.3所示。第8章 人工免疫算法及其在智能控制中的应用图8.3 免疫响应多阶段过程图示第8章 人工免疫算法及其在智能控制中的应用 8.2 人工免疫系统与基本免疫算法简介人工免疫系统与基本免疫算法简介8.2.1 人工免疫系统定义人工免疫系统定义人工免疫系统(AIS)的定义最早由H.Sidburg等人在1990年提出4。人工免疫系统有几种不同的定义。De Castro和Ti

5、mmis概括了几种定义后，将AIS定义4为：“人工免疫系统是受理论免疫学和所观察到的免疫功能、原理和模型启发的自适应系统，被应用于复杂问题领域。”这种人工免疫系统的定义，重点在于将自然免疫系统中所获取的现象作为隐喻，用于计算问题，属于生物学推动的计算。在某些文献中，也有把人工免疫系统叫做免疫学计算、计算免疫学或基于免疫的系统等。第8章 人工免疫算法及其在智能控制中的应用8.2.2 基本的人工免疫算法基本的人工免疫算法基本的人工免疫算法是按照自然免疫系统对病原体的检测、识别、克隆选择、超变异、免疫记忆等原理进行设计的。算法一开始随机地初始化抗体群(相当于随机列出求解问题的候选解)。接着，辨识抗原

6、，计算抗体群中抗体同抗原的亲和度。根据亲和度对抗体进行克隆选择，然后得到新的群体。由于新群体一般是亲和度高的抗体，它们被优先克隆，以继承上一代的优良特性，并记忆、存储。如此反复迭代，直至满足终止条件。基本的人工免疫算法的基本过程如图8.4所示。第8章 人工免疫算法及其在智能控制中的应用图8.4 基本的人工免疫算法的流程第8章 人工免疫算法及其在智能控制中的应用1.计算亲和度计算亲和度基本的人工免疫算法中，亲和度表示抗体和抗原之间的相互作用程度，也反映了抗体适应环境的程度。一般简记为aff。aff表示为属性串之间距离d的函数，即afff(d)，即B细胞或者抗体和抗原之间匹配程度。结合具体的问题，

7、函数关系f可选取不同的形式。也可直接简记为距离dis。距离越小，说明抗体越相似，且它们之间的相互抑制能力越强。对实值属性串，距离d可以表示为欧氏距离(式(8.1)、曼哈顿(Manhattan)距离(式(8.2)或海明距离(式(8.3)。欧氏距离(8.1)第8章 人工免疫算法及其在智能控制中的应用曼哈顿距离海明距离(8.2)(8.3)第8章 人工免疫算法及其在智能控制中的应用和欧氏距离相比较，曼哈顿距离更有效，因为它没有指数和开平方运算。此外，两者对算法有效性的影响也不同。欧氏距离对各属性值之间的差异性更敏感，因此对噪声敏感。而曼哈顿距离对噪声具有鲁棒性。这可以由图8.5进行说明 13。图中抗原

8、Ag(0,0)，抗体B1坐标为(4,4),抗体B2坐标为(6,1)，欧氏距离d(B1,Ag)=5.66，d(B2,Ag)=6.08，而曼哈顿距离d(B1,Ag)=8，d(B2,Ag)=7。距离抗原Ag(0,0)最近的抗体，若按欧氏距离，则为B1；如按曼哈顿距离，则为B2。造成这种问题的原因是欧氏距离和曼哈顿距离的偏好不同。当属性值采用二进制的位表示时，常采用海明距离。整数属性值可视为海明距离的特殊情况。第8章 人工免疫算法及其在智能控制中的应用图8.5 欧氏距离和曼哈顿距离比较第8章 人工免疫算法及其在智能控制中的应用对于混合型属性串，如果属性串中包括整数、实数和符号值，则采用逐一匹配的方法，

9、类似于海明距离的计算，然后求和。如果属性串中的多数属性是数值型，少部分是非数值型，则对数值属性采用欧氏距离或曼哈顿距离，对非数值属性采用海明距离分别计算，然后求和作为总的距离d。例如，设B=b1,b2,bi,bL由混合属性组成，由于空间距离的计算与各属性的次序没有关系，因此我们总可以将抗体表示为：前i个属性为数值型，后Li个为非数值型。则具有混合属性的抗体和抗原之间的距离计算如下：(8.4)式中，第8章 人工免疫算法及其在智能控制中的应用Wj是不同的非数值型属性的权重系数。抗体属性串之间的距离计算和上述计算抗体和抗原之间的距离方法类似。第8章 人工免疫算法及其在智能控制中的应用2.克隆选择和群

10、体更新克隆选择和群体更新克隆选择和群体更新的核心作用是：使抗体种群既能够更快地识别抗原，又能保证抗体群中的多样性。克隆繁衍原则是：使得在与抗原亲和度高的抗体优先繁殖的同时，又能抑制已有抗体群中浓度过高的抗体增长，并淘汰亲和度低的抗体。抗原和抗体对不同的工程问题有不同的定义。在数据分析问题中，抗原为被分析或被训练的数据或训练样本，抗体为分类的网络或类的元素。在函数优化问题中，抗原成为优化问题的辨识对象，抗体成为问题的侯选解。在车间作业调度问题中，抗原为迫使调度发生变化的一组布局，抗体为调度本身。第8章 人工免疫算法及其在智能控制中的应用下面我们用一个多峰值函数寻优问题，具体说明基本人工免疫算法的

11、应用。我们知道，多峰值函数寻优问题是一类典型的复杂优化问题。因为，多峰值函数一般局部极值数量多，全局最优解难以确定。假定被优化的函数为f(x,y)=xsin(4x)ysin(4y)+1参照基本人工免疫算法(克隆选择算法)的基本步骤，解题的程序如下：Step1 随机产生候选解P(抗体)，包括记忆细胞子集C和其他个体Pr。Step2 计算抗原(训练数据)和P的亲和度，并对其递减排序，选择前n个最佳个体Pn。第8章 人工免疫算法及其在智能控制中的应用Step3 (克隆算子)按照式(8.5)克隆繁殖Pn，得到临时克隆细胞集C：(8.5)其中，NC为克隆后的种群规模；为克隆系数，用来控制克隆后的种群规模

12、；round为取整函数；i是最佳抗体Pn的编号，1i0)经一步变异改变到其他任一个体。条件条件2 群体中的最优个体以概率p=1存活在每一代中。第8章 人工免疫算法及其在智能控制中的应用文献15基于以上两个条件，证明了针对优化问题，克隆选择算法的收敛性。文中指出：不管初始值如何，基本免疫算法(克隆选择算法)完全收敛及均值收敛到全局最优的条件是算法必须引入带选择性的衰减算子。基本免疫算法收敛性证明的基本思想是：首先，由于克隆算子和衰减算子都不改变已存在的抗体,也不产生不同的抗体，只有超变异算子和选择算子可能第一次产生群体中的最优解。所以，设长度为L的位串为搜索空间的一个点，并通过向量0,1L来表示

13、。如果群体中的一个抗体与最优解相比时，有c个位不匹配，也就是说有Lc个位匹配,同时若设定一步变异中的c个位变异都是在不同的位上进行,那么，该抗体利用一步超变异算子到达全局最优的概率为第8章 人工免疫算法及其在智能控制中的应用若假设字符集的基数为K，搜索空间的每个点用一个向量 0,1,2,K1L表示,则该概率公式变为其中,1/(K1)为一步变异中的一位变异到最优解相应基因位值的概率(均匀变异)。由于p(L)c总是为正,就说明一般克隆选择算法满足条件1。第8章 人工免疫算法及其在智能控制中的应用其次，要证明条件2也成立，就要证明一旦最优解被找到，对种群执行的任何一个算子都不会再丢失全局最优解。克隆

14、算子只产生个体的拷贝,不会改变任何个体的值,因此它不会丢失最优解。超变异算子只对克隆选择算子所产生的中间种群p(c|0)执行操作,也不改变由其他任何算子(包括它自己)所产生的抗体。衰减算子尽管删除了老的个体,但由于每一代种群的最优候选解的衰减值被设置为0,因而不可能丢失最优解。至于选择算子,因为其删除了最小亲和度的个体,取而代之的是随机新生成的个体,所以最优解不会失去。如果群体中有多个最优解,那么也至少有一个最优解存活下来。由此可见,一般克隆选择算法中的所有算子满足条件2。第8章 人工免疫算法及其在智能控制中的应用鉴于此，可知只要满足条件1和条件2，基本免疫算法是完全收敛及均值收敛到全局最优的

15、。为了改善算法的搜索能力，提高算法的收敛速度和效率，有人12提出基于生发中心反应的人工免疫算法。第8章 人工免疫算法及其在智能控制中的应用8.3 基于生发中心反应的全局优化算法基于生发中心反应的全局优化算法8.3.1 生发中心反应机理生发中心反应机理基本人工免疫算法模拟了免疫系统的免疫响应，而生发中心反应不同于此机理。生发中心反应是脊椎动物免疫系统为抵抗外界抗原的入侵而形成的具有自适应性的自然模型。它构成了免疫机理的另一种诠释，也构造了人工免疫系统的另外一种方法。Kepler和Perelson9 认为超变异过程和B细胞的繁殖发生在外周淋巴组织的生发中心(Germinal Centers)，有一

16、定的生命期限。简单地说来，生发中心反应经历了下述几个阶段。第8章 人工免疫算法及其在智能控制中的应用第一阶段：B细胞单克隆扩张。抗原激活的B细胞(抗体)，在树突状细胞(FDC)环境中克隆(繁殖)。此时的B细胞可以称为中心母细胞，通常由36个种子细胞分裂而成，细胞的分裂速度比其在生物体的其他部分更快。第二阶段：中心母细胞超变异。中心母细胞继续繁殖，繁殖期间经历了很高的体细胞超突变，变异率可达50%以上。于是产生了大量的不同类型的中心母细胞。第三阶段：中心母细胞凋亡。中心母细胞分化为中心细胞。由于超突变的随机性，导致变异了的基因变成无功能的或者自反应性的中心细胞。其中大部分低亲和度的中心细胞和自反

17、应细胞会被消除，少部分通过细胞受体的基因重组(受体编辑)又重新成为有效的免疫细胞。第8章 人工免疫算法及其在智能控制中的应用第四阶段：中心母细胞与抗原粘合(选择)，或者称中心细胞和FDC的相互作用。在这一阶段，与抗原有较高亲和度的中心细胞，因选择作用而被“拯救”出来。被“拯救”出来的中心母细胞，一部分分化为记忆细胞和分泌抗体的浆细胞离开生发中心，另一部分开始再循环。第五阶段：中心细胞的再循环。再循环是中心细胞重新转化为中心母细胞再次进入单克隆扩增、超变异和选择过程。上述生发中心反应过程随新入侵抗原的刺激而启动，先于生发中心的消失而结束，结果产生了大量不同种类的高亲和度的抗体分泌细胞和记忆细胞。

18、这个过程从另外一种角度，解释了免疫系统识别和消除各种抗原的机理。图8.8所示为生发中心反应过程的框图。第8章 人工免疫算法及其在智能控制中的应用图8.8 生发中心反应过程第8章 人工免疫算法及其在智能控制中的应用我们可以从生发中心反应的机理解释中得到一种启示，并用于产生一种新的人工免疫算法。显然，生发中心反应具有进化特性。从计算的观点看，一个进化系统是基于群体的搜索技术，它包含繁殖、遗传变异和选择等过程。生发中心反应中具备这些特点和组成要素。超突变使得后代细胞不同于父代中心母细胞，产生了更好的多样性；FDC递呈的抗原作用于抗体的选择，使变异有积累效应；记忆细胞的作用在于保持已有的阶段性结构；再

19、循环的作用在于继续搜索更好的结构。这样，使免疫系统能够不断地产生新的抗体以适应抗原的不断变化。第8章 人工免疫算法及其在智能控制中的应用另外，生物体中淋巴细胞的总数基本恒定，亲和度相近的抗体之间存在竞争和抑制作用，和抗原之间亲和度较低的一部分抗体会被淘汰，由骨髓新产生的细胞会不断地补充进来，使得生发中心反应中的抗体具有丰富的多样性。生发中心反应也具有学习能力。在生发中心反应中，抗体之间的亲和度，后次比前次的提高，均是在前次与同类抗原频繁遭遇中获得知识而实现的。也就是学习的结果，使记忆细胞的种类随之发生变化。在自然免疫的研究中，我们知道，可以根据特异性免疫产生的机理，运用人工接种的办法，使机体产

20、生或获得特异性免疫的能力，它被称为人工免疫或免疫接种。接种中最常用的一种生物制剂就是疫苗。它是激发机体开始免疫响应、产生免疫记忆、预防感染性疾病的有效手段。第8章 人工免疫算法及其在智能控制中的应用从以上分析可知，在生发中心反应的生命期内，其反应是循环往复、不断重复的，免疫系统能够不断地产生新的抗体以识别不同的抗原，最终消除抗原。这种机理的解释，强调了抗体的多样性和与环境交互的适应性。此外，我们还可以借鉴人工接种的原理，对受体(抗体)进行编辑，来加强免疫的功能。对人工免疫系统而言，抗原相应于系统的外部环境，抗原选择与其高亲和度的抗体，或者说，与抗原有不同亲和度的抗体竞争识别抗原。通过系统与环境

21、之间的相互作用，依靠自身的进化与学习机制，人工免疫系统就有更强的适应环境变化的能力，能更好地解决基本人工免疫算法所存在的不足。第8章 人工免疫算法及其在智能控制中的应用此外，如果我们引入待解决问题的先验知识，可以进一步提高算法的应用效率。例如，我们在求解优化问题时，抗体采用二进制编码，往往会产生等位基因缺失现象，即对应染色体(抗体个体)上的每个基因完全相同，出现病态个体。这时，我们按接种疫苗的思想，用先验知识，选择疫苗，对病态个体进行接种，则产生新抗体，引导优化求解过程。第8章 人工免疫算法及其在智能控制中的应用8.3.2 基于生发中心的全局优化算法基于生发中心的全局优化算法 现在我们利用上述

22、生发中心的机理，阐述基于生发中心的算法 12，简称GOAIA-GCR。假设我们所要求解的问题为 众所周知，式(8.10)是目标函数，式(8.11)是条件约束。利用基于生发中心的全局优化算法，其步骤大致如下：(8.6)(8.7)第8章 人工免疫算法及其在智能控制中的应用Step 1 初始化。设定算法结束条件(如最大迭代次数或期望的近似解精度)；采用二进制编码，在可行域内随机产生N个抗体的初始解，组成初始抗体群体B(n)。设置算法迭代次数计数器n=0，则B(0)=B1,B2,，Bi，BN，其中，Bi=bi1,bi2,，biL(1iN)表示一个B细胞，它是L个属性值组成的一个属性串。Step 2 抗

23、原激活的抗体进入生发中心。计算当前抗体群B(n)中每一个抗体和抗原之间的亲和度aff(B(n)，并按亲和度从高到低排序。从B(n)中选择出25%的高亲和度抗体，作为克隆、超变异和受体编辑的对象，即Bs(n)=So(B(n)。同时，这一部分抗体也存入记忆单元中，即Bs(n)MB(记忆细胞的保存仅在第一次迭代时执行)。第8章 人工免疫算法及其在智能控制中的应用Step 3 参与生发中心反应的抗体完成以下相应的运算操作。Step 3.1 克隆。对Bs(n)实施克隆操作，Bc(n)=C(Bs(n)。采用等量克隆的方法，即每个抗体克隆的数目均相同。Step 3.2 超变异。对Bc(n)施行变异操作，Bm

24、(n)=MH(Bc(n)。将Bc(n)群体按亲和度从高到低排序，然后按1 2 1的比例将其划分为高亲和度、中等亲和度和低亲和度三部分。对应设置三个不同变异率Pm1、Pm2和Pm3，且它们满足关系式：Pm1Pm2Pm3。Step 3.3 受体编辑。判断此时的抗体Bm(n)是否存在基因缺失现象？若存在，则接种疫苗；否则，算法继续。第8章 人工免疫算法及其在智能控制中的应用Step 3.4 抗原对高亲和度抗体进行选择(衰减)。从Bm(n)Bs(n)中选择出部分和抗原有高亲和度的抗体MB1，取代记忆单元MB中与MB1中相似但其亲和度较小的抗体，完成相似性抑制，取抑制阈值为。Step 3.5 再循环。由

25、记忆单元中MB的抗体和新补充的抗体Bnew组成新一代抗体群体，即MBBnewB(n+1)。Step 4 终止条件检测。若B(n+1)满足终止条件，则输出B(n+1)中具有最大亲和度的抗体，以此作为最优解，算法结束；否则，将迭代得到的解作为当前解群，nn+1，转Step2。第8章 人工免疫算法及其在智能控制中的应用我们选用以下四个函数作为算法的测试函数，对GOAIA-GCR算法进行测试。第8章 人工免疫算法及其在智能控制中的应用f1是二维连续的凹函数，也称Rosonbrock马鞍函数，具有一个全局极小点f1(1,1)=0。该函数虽然是单峰值函数，但它却是病态的，许多算法难以求其全局最小值。函数f

26、1的三维空间结构如图8.9所示。f2是一个多峰值函数，具有25个稀疏尖峰，且最优点邻域的变化范围很小，因此要求算法具有较强的搜索能力。其三维空间结构如图8.10所示。第8章 人工免疫算法及其在智能控制中的应用图8.9 函数f1的三维图第8章 人工免疫算法及其在智能控制中的应用图8.10 函数f2的三维图第8章 人工免疫算法及其在智能控制中的应用f3是快速变化的多峰值函数，形状相对原点对称，越接近最优点，函数变化越剧烈。在全局最大值周围有一圈脊使得函数有无数个局部极大值，且极大值与全局最大值非常接近，这样算法在搜索时很容易陷入局部极大值。但函数只有一个全局最大值。函数f3在给定的定义域范围内有f

27、3(x,y)0。其三维空间结构如图8.11所示。f4和f3类似，各局部极值点分布较近，只是接近最优值时，函数变化幅度较小；远离最优值时，函数变化幅度较大。其三维空间结构如图8.12所示。仿真实验的条件见表8.3。第8章 人工免疫算法及其在智能控制中的应用图8.11 函数f3的三维图第8章 人工免疫算法及其在智能控制中的应用图8.12 函数f4的三维图第8章 人工免疫算法及其在智能控制中的应用第8章 人工免疫算法及其在智能控制中的应用仿真计算的结果如表8.4所示。表的左边为未使用接种疫苗操作的结果，右边为使用接种疫苗操作的结果。第8章 人工免疫算法及其在智能控制中的应用从表8.4中我们可以看出，

28、接种疫苗对GOAIA-GCR的性能有所改进，但是作用比较小。原因在于对采用比例选择和以交叉操作为主的算法来说，发生基因缺失的可能性较大；对于以变异操作为主的算法来说发生的可能性较小。而GOAIA-GCR采用确定性选择，以变异操作为主，因此，对GOAIA-GCR来说接种疫苗所起的作用相对较小。图8.13图8.16表示了迭代过程中，函数f2和f4最佳个体适应度和群体平均适应度变化的过程。第8章 人工免疫算法及其在智能控制中的应用图8.13 f2最佳个体适应度的变化第8章 人工免疫算法及其在智能控制中的应用图8.14 f2群体平均适应度的变化第8章 人工免疫算法及其在智能控制中的应用图8.15 f4

29、最佳个体适应度的变化第8章 人工免疫算法及其在智能控制中的应用图8.16 f4群体平均适应度的变化第8章 人工免疫算法及其在智能控制中的应用对GOAIA-GCR、基本免疫算法和SGA(简单遗传算法)的优化性能做对比，其结果如表8.5所示。可见，GOAIA-GCR比基本免疫算法、SGA在收敛速度和克服早期成熟方面，性能有较大的改善。第8章 人工免疫算法及其在智能控制中的应用8.3.3 GOAIA-GCR的收敛性证明的收敛性证明如果把GOAIA-GCR的每一代群体看做一种状态，则可以把算法整个演化过程的所有状态作为一个随机过程来加以考察。这样，就可以利用Markov链来对整个演化过程的性能进行分析

30、12。其中，B细胞属性串采用二进制编码表示。定义定义8.1 长度为L的B细胞属性串，可编码为长度为L的0和1字符串，简称B细胞个体，个体的全体称为个体空间，记为HL0,1L。N个B细胞个体组成的集合，简称B细胞群体，N称为群体规模。称HNL=B=(B1,B2,，BN),BiHL(1iN)为B细胞群体空间。第8章 人工免疫算法及其在智能控制中的应用定义定义8.2 一个满意集B0是一个由B细胞个体组成的子集，它的每一个个体的亲和度均大于它之外的个体的亲和度。显然，待解决问题的全局最优解集B*是满意集。引理引理8.1 由GOAIA-GCR的各代状态B(n)所组成的搜索序列B(n)是齐次的马氏链。证明

31、证明 从GOAIA-GCR的算法演变过程，可把B(n),n0看做一取值离散的随机变量，离散值的全体记为HNL。则对于任意n1，ikHNL(kn+1)，可知，B(n+1)群体的状态仅与B(n)及其相同代的MB和Bnew有关，与过去状态无关，即无后效性，可写为 (8.12)第8章 人工免疫算法及其在智能控制中的应用因此可认为B(n)描述的随机搜索过程是马氏链。进一步，对于马氏链B(n)来说，每一次迭代时的状态转移概率只与超变异率及该次的群体有关，与迭代时的起始时间点无关。由齐次马氏链定义可知，B(n)描述的随机搜索过程是一个齐次的马氏链。证毕。定义定义8.3 超变异的作用方式。它是独立地分别作用于

32、种群B上的每一个个体Bi，以预先指定的概率生成超变异后的个体MH(Bi)，即MH(B)=(MH(B1),MH(B2),MH(Bn)。定义定义8.4 点变异。是指以某一概率独立地改变Bi的一些属性值的进化操作，变异率为Pm。第8章 人工免疫算法及其在智能控制中的应用定理定理8.1 设有任意的两个B细胞个体X(x1,x2,xL)、Y=(y1,y2,，yL)HL，如果对个体X施加点变异操作后，由个体X产生个体Y的概率为PMH(X)=Y=(1Pm)Ld(X,Y)Pmd(X,Y)(8.13)式中，d(X,Y)是X、Y之间的海明距离。证明证明 将Y的分量分为两种情况：一种是yixi；另一种是yixi。显然

33、，yixi的个数为d(X,Y)。这时，每个xi变异为yi的概率为Pm。yixi的个数为Ld(X,Y)，这时，xi不变异，而不变异的概率为1Pm。B细胞个体X的各个属性值的变异是独立的，故式(8.13)成立。证毕。第8章 人工免疫算法及其在智能控制中的应用定理定理8.2 设MH是点变异操作，X、YHL是任意的两个B细胞个体，则PMH(X)=Y 0的充分必要条件是0Pm1。证明证明 X、YHL是任意的两个B细胞个体，且MH是点变异操作。由定理8.1有 PMH(X)=Y=(1Pm)Ld(X,Y)Pmd(X,Y)若0Pm1，则必有PMH(X)=Y0；反之，若Pm0 且XY，则有PMH(X)=Y0；若P

34、m1且Ld(X,Y)，则PMH(X)=Y0。于是，若对任何X、YHL，有PMH(X)=Y0，必有0Pm1。证毕。定理8.2说明变异操作有能力从任何个体出发搜索到HL中的任何其他一个个体，即整个空间HL是变异操作的搜索可达域。第8章 人工免疫算法及其在智能控制中的应用引理引理8.2 B(n)是有限的齐次马氏链。证明证明 由于HL中有2L个个体，种群空间HNL中有2N个个体，HNL是种群序列B(n)的状态空间，从而是有限的。所以B(n)是有限的齐次马氏链。证毕。定理定理8.3 设B(n)是有限的齐次马氏链，p(n)ij为n步转移概率，如果存在某个n01使得 p(n0)ij0，则称状态i可达状态j，

35、记为ij。否则，称i不达状态j。进一步，若有ij和ji同时成立，称i与j互通，记为ij。证明证明 因为，B(n)是有限的齐次马氏链，所以，p(n)ijPn(n1,P一步转移概率)。由定理8.2知，0Pm1时，PMH(X)=Y0，所以p(n)ij0，则有ij。在定理8.2中，X和Y是HL中的任意两个B细胞个体。所以，同样可证得 ji。故我们有结论i与j互通，即i j。证毕。第8章 人工免疫算法及其在智能控制中的应用定义定义8.5 若有ij时，必有ji，则称i是本质状态(Essential States)，记为E；若存在j使ij，但是j不达i，则称i为非本质状态(Inessential State

36、s)，记为I。定义定义8.6 任何有限马氏链的状态集可分解为本质状态和非本质状态，即HLEI。通过重新排列状态，转移概率P的规范形式可写为。p1是本质状态间的转移概率矩阵，R是非本质状态到本质状态的转移概率矩阵，而Q是非本质状态间的转移概率矩阵。引理引理8.3 如果B(n)是一个马氏链，则当n时，P(B(n)I)0，且独立于初始分布。第8章 人工免疫算法及其在智能控制中的应用证明思路证明思路 相似的证明方法见文献14，这里不再重复。为了证明GOAIA-GCR的各代状态B(n)所组成的搜索序列B(n)是全局收敛的，即就是要证明n时，P(B(n)B*)1。定理定理8.4 GOAIA-GCR的各代状

37、态B(n)所组成的搜索序列B(n)是有限的齐次马氏链，它以概率1收敛到全局最优解。证明证明 引理8.3说明，B(n)包含当前最优值的状态，如果该状态不是问题的全局最优解，则该状态是非本质状态。换句话说，包含全局最优解的状态是本质状态。本质状态的类不可能达到别的类，非本质状态可以转到本质状态。这意味着本质状态以概率1存活(符合文献14中的条件2)，同时定理8.2保证了文献14中的条件1的成立。第8章 人工免疫算法及其在智能控制中的应用因此，我们有：(8.14)即GOAIA-GCR的各代状态B(n)所组成的搜索序列B(n)以概率1收敛到全局最优解。证毕。第8章 人工免疫算法及其在智能控制中的应用8

38、.4 人工免疫网络算法人工免疫网络算法(aiNet)8.4.1 人工免疫网络简介人工免疫网络简介1974年，Jerne根据现代免疫学对抗体分子独特性的认识，在克隆选择学说的基础上，提出了著名的独特性网络学说，以阐明免疫系统内部对免疫响应的自我调节11。该学说认为抗原上的表位能够被抗体识别。同样，抗体上也存在能被其他抗体识别的表位。如图8.17 所示，如果抗原Ag能够被抗体Ab1识别，Ab1的独特性又被Ab2的抗体结合部位识别，而Ab2又被其他抗体识别，依此类推就形成了抗体相互作用的网络。第8章 人工免疫算法及其在智能控制中的应用图8.17 生物免疫系统的免疫网络假设示意图第8章 人工免疫算法及

39、其在智能控制中的应用我们知道，免疫系统在抗原刺激发生之前，抗体集处于一种相对的免疫稳定状态。当抗原进入机体后，打破了这种平衡，导致特异抗体分子的产生，在体内形成淋巴细胞与抗体分子所组成的网络结构。由于抗体之间存在相互刺激和抑制关系，制约了抗体总量的无限增大，从而保证了适当的免疫强度，并维持免疫应答的稳定平衡。这也就使它成为一种不同于免疫应答、生发中心反应的另一种免疫学机理。从数据分析和处理的角度看，抗原Ag可以看成是训练数据，抗体是网络节点，经过学习过程，形成映射关系，如图8.18所示。第8章 人工免疫算法及其在智能控制中的应用图8.18 免疫抗体和抗原映射图第8章 人工免疫算法及其在智能控制

40、中的应用图8.19 aiNet抗体网络结构示意图第8章 人工免疫算法及其在智能控制中的应用通过抗体之间的相互刺激和抑制关系，被训练的数据(抗原)可以映射成网络节点。图8.19(a)中表示了一组数据在运行aiNet算法之后，通过抗体的不断克隆和进化，改变抗体网络结构，映射成网络节点之间的连接，再经适当的修正，去除不重要的连接，如图8.19(a)中的虚线，形成了图8.19(b)，使原来的被训练的数据集合分类成三类。从映射结果可以看出，aiNet的节点数目远远地少于原来的数据个数。这些网络节点(记忆细胞)近似地刻画了抗原(训练数据)的特征和结构。三类数据之间的距离有远近，三类内部的数据之间亦有远近之

41、分。因此，我们可把aiNet看做是一个边界加权图，也可称为细胞的节点集合的连接。节点集合的连接也称为边界，每一个连接的边界具有分配的权或连接强度。第8章 人工免疫算法及其在智能控制中的应用8.4.2 人工免疫网络算法在数据分析中的应用人工免疫网络算法在数据分析中的应用如前所述，人工免疫网络算法的基本思想是，不断地进行抗体克隆与抑制过程，使被选的抗体数也即网络节点数不超过一定的范围。具体的算法流程如下：输入：数据集合X；包含所有Nt个细胞的矩阵C；记忆细胞矩阵M。输出：抗体集Ab。初始化：设置抑制门限阈值s和自然死亡门限阈值d的初始值。Step 1 对每一个抗原模式Agj(j=1,2,M),Ag

42、jAg，其中M是数据集的个数。第8章 人工免疫算法及其在智能控制中的应用Step 1.1 确定Agj对所有的Abj的亲和度fi,j，(8.15)(8.16)Step 1.2 选择n个最高亲和度抗体，形成子集合Abn。Step 1.3 对集合Abn中n个抗体进行繁殖(克隆)，产生克隆集合C。其中，每一个细胞的克隆后代的数目Nc正比于它们同抗原的亲和度fi,j。这意味着亲和度越高，被选择的抗体的克隆数量就越多。第8章 人工免疫算法及其在智能控制中的应用Step 1.4 异变。集合C完成一个受控的亲和度成熟过程，即有引导的变异。产生经变异的集合C*。C*集合中每个抗体k经受变异，变异率k反比于父抗体

43、和抗原的亲和度fi,j，即Step 1.5 计算变异后集合C*中所有元素同Agj的亲和度dk,j=1/Dk,j，其中Step 1.6 筛选。从C*中重新选择%具有最高亲和度(dk,j)的抗体，并把它放入克隆记忆矩阵Mj。第8章 人工免疫算法及其在智能控制中的应用Step 1.7 消亡。从Mj消去所有亲和度Dk,jd的记忆克隆。Step 1.8 在记忆克隆中确定亲和度si,k：Step 1.9 克隆抑制。消去si,kd的那些记忆克隆，即消去差异小的克隆。Step 1.10 新旧抗体集成。把总的抗体记忆矩阵与最终对Agj所形成的克隆记忆矩阵M*j链接起来：AbmAbm;M*j Step 2 从Ab

44、m中再确定所有记忆抗体之间的亲和度：第8章 人工免疫算法及其在智能控制中的应用Step 3 再选择。网络抑制：消去si,kd的抗体。Step 4 建立总的抗体集Ab：AbAbm;Ab d，其中d是新加入的抗体数目。Step 5 测试终止判据。判据成立，结束；否则执行Step 1。该算法的终止条件判据有四种(它们之间也可以组合使用)：(1)在预定迭代次数之后，停止迭代过程。(2)当网络达到预定抗体数目之后，停止迭代过程。(3)通过计算各个网络抗体到各个抗原的距离，估计所有抗原和网络记忆抗体Abm之间的平均误差。如果该平均误差大于预定阈值，则停止迭代过程。这个策略对不过于简洁的解有用。第8章 人工

45、免疫算法及其在智能控制中的应用(4)如果在k次连续迭代之后，平均误差上升，则认为网络必须收敛。由aiNet 算法可见，对每一个所出现的抗原模式，引出一个克隆免疫响应。这里存在两个抑制步骤：克隆抑制和网络抑制(Step 1.9 和Step 3)。就对每一个所出现的抗原而言，为了消去克隆内部自相识的抗体，克隆抑制是必需的；网络抑制要求搜索不同克隆集合之间的相似性。学习阶段之后，网络抗体代表了呈现于抗体的抗原(或抗原群)的内部映射。网络的输出可以是记忆抗体坐标(Abm)和它们的亲和度矩阵。而矩阵Abm 是呈现给aiNet的抗原网络内部映射。第8章 人工免疫算法及其在智能控制中的应用下面为两个应用例子

46、。(1)原始数据有5类(见图8.20)，每类10个样本。图8.20 数据和数据分类结果第8章 人工免疫算法及其在智能控制中的应用aiNet的训练参数：最高亲和度的抗体数目为n=4,=0.2，d=1.0,s=0.14,d=10。停止判据为：迭代次数Ngen=10。其中d是每次加入的新抗体数目。最终网络只有10个细胞，问题的复杂度是原来的20%，压缩80%。(2)2D螺旋线数据(见图8.21)聚类的例子。aiNet算法参数设置为s=0.07，d=0.01，(%)=10%，n=4，d=10。经过Ngen=20的迭代，最终得到如图8.22图所示的正确数据划分。如果仅改变s=0.1，则获得不正确数据划分的结果(如图8.23所示)。这说明s对抗体细胞之间的抑制计算很关键。如果抗体之间的抑制阈值设置过大，易导致亲和度较近的抗体抑制增强，数据划分错误。第8章 人工免疫算法及其在智能控制中的应用图8.21 2D螺旋线第8章 人工免疫算法及其在智能控制中的应用图8.22 抑制阈值s=0.07第8章 人工免疫算法及其在智能控制中的应用图8.23 抑制阈值s=0.1第8章 人工免疫算法及其在智能控制中的应用从此可看出，作为数据分析的aiNet算法其参数设置对算法的收敛性影响非常大。如果参数设置不合理，易导致不能搜索到所需的全部数据模式，即搜索到的数据模式不完备。因此，我们认定此算法是不稳定的。