第7章_免疫算法.ppt

1、第7章 免疫算法,目录,免疫算法简介,1,7.1 免疫算法简介,免疫算法是什么？,免疫算法（Immune Algorithm，IA）：是指以人工免疫系统的理论为基础，借鉴免疫系统的记忆、学习、自我识别等性质，建立相应数学模型，从而设计出解决实际问题的算法。该算法实现了类似于生物免疫系统的抗原识别、细胞分化、记忆和自我调节的功能。,7.1.1 思想来源,免疫系统能抵御日常生活中的绝大多数病原体，使我们保持健康。 免疫系统还具有记忆功能，当我们得过某种疾病后，系统会生成专门的记忆细胞记住那些触发疾病的病原体，细菌再次入侵的时候身体就有了免疫力。 疾病的记忆细胞也可通过注射疫苗获得，记忆细胞不仅能记

2、住曾经入侵的病原体，对类似的其他疾病也能起到一定的免疫效果。 可见免疫系统具有学习性、记忆性和模式识别性。,7.1.1 思想来源,7.1.1 思想来源,免疫算法最先起源于1973-1976年间Jernel的三篇关于免疫网络的文章，Jernel在文中提出了一组基于免疫独特型的微分方程，这就是最早的免疫系统。 免疫算法的主要会议: International Conference on Artificial Immune Systems，ICARIS,7.1.2 免疫系统的生物学原理,从人的角度：免疫的主要作用是帮助人体自身的免疫系统抵制由病毒和细菌引起的疾病。 从生物学角度：免疫或免疫接种是强化

3、个体抵御外部个体的能力的过程。,7.1.2 免疫系统的生物学原理,抗原：被免疫系统看作异体，引起免疫反应的分子。即能刺激人体免疫的细胞，使人体产生免疫反应的物质。可以是人体本身固有的，如血液，也可以是人体内根本不存在的，如某些细菌，病毒，药物等。 抗体：免疫系统用来鉴别和移植外援物质的一种蛋白质复合体。每种抗体只识别特定的目标抗原。当某种抗原刺激人体后，人体对这种抗原会产生一种能识别它，并抵抗或消灭它的物质。当这种抗原再次入侵时，人体会产生抵抗（免疫）能力，从而避免疾病的发生。,相关名词,7.1.2 免疫系统的生物学原理,淋巴细胞：免疫系统中起主要作用的微小白细胞，包括细胞和抗体，细胞和细胞因

4、子以及自然杀伤细胞。 细胞：全称为淋巴细胞，在骨髓分化成熟，免疫系统的本质部分。 细胞：全称为淋巴细胞，在胸腺分化成熟，按功能可分为细胞毒细胞（用来分解、消灭已感染病毒的细胞），辅助T细胞（用来识别病菌），调节/抑制T细胞和记忆T细胞。 亲和力：抗体和抗原，抗体和抗体之间的相似程度。,相关名词,7.1.2 免疫算法的生物模型,图 免疫系统层次示意图,7.1.3 二进制模型,每个抗体都有抗体决定簇和抗原决定基。抗体和抗原的亲和程度由它的抗体决定簇和抗原决定基的匹配程度决定。,抗原决定基对其他的抗体来说也是一个特殊的“抗原”，它们之间的亲和度由它的抗原决定基和其他抗体的抗体决定簇的匹配程度决定。,

5、图 B细胞抗体结构图,7.1.3 二进制模型,二进制模型模仿了免疫系统的工作原理，涉及识别和刺激两方面。 识别：每个抗体可以用(e,p)的二进制串表示，匹配通过计算两个串之间的互补字符个数t决定，e表示抗原决定基，p表示抗体决定簇，它们的长度分别是le、lp(所有抗体或抗原的这两个长度均相同)，s表示一个匹配阈值，当s minle,lp时免疫反应发生，也称两串相互识别，否则不发生反应。设ei(n)表示第i个抗原决定基的第n位，pi(n)表示第i个抗体决定簇的第n位。串匹配运算用异或运算符“”。,7.1.3 二进制模型,匹配特异矩阵为：,s匹配的阈值 k串之间的错位长度 n串的具体某位 i和j具

6、体哪个抗体或抗原的某种决定基（簇）,由(7.1)计算mij需求出k的所有情况之和。但实际不必这样计算。如书P135图7.3。,模型还指出当一个B淋巴细胞识别一个抗原决定基时，它受到刺激并分裂，产生更多表面附着相同抗体类型的B淋巴细胞。,7.1.3 二进制模型,刺激：二进制串之间匹配，会刺激新抗体的生成。以两个抗体的相互识别为例，抗体A的抗体决定簇能识别（即匹配个数t大于阈值s）抗体B的抗原决定基，首先导致抗体A以固有概率大量繁殖，同时逐渐清除抗体B。这样通过抗体决定簇和抗原决定基之间的作用控制了一类抗体的复制和另一类抗体的消亡。 建立微分方程模型，设N种类型的抗体，浓度为x1,x2,xN,n种

7、类型的抗原，浓度为y1,y2,yn,此处的浓度就是某种抗原或抗体的具体数量，则抗体浓度变化方程为：,i1,N mij抗体i和抗体j（或抗原j）在匹配特异矩阵特定位置的值。,7.1.3 二进制模型,抗体刺激,i型抗体的抗体决定簇受到j型抗体的抗原决定基的刺激,抗体抑制,i型抗体的抗原决定基被j型抗体的抗体决定簇识别后，对i抗体的抑制,抗原刺激,i型抗体的抗体决定簇受到j型抗原的抗原决定基的刺激，即抗原驱动,自然衰减,随着时间的推移，含有抗体细胞以k2决定的速率减少,模型中，当前抗原和抗体类型是动态变化的，N和n是随时间变化的，且它们的变化速度分别远小于浓度xi和yi的变化速度。,7.1.3 二进

8、制模型,抗体和抗原的动态调整规则为：,图7.6 抗原调整流程图,7.2 免疫算法的基本流程,免疫系统和免疫算法的比较,7.2.1 基本流程,图7.8 免疫算法流程图,7.2.1 基本流程,免疫算法的七个要素 识别抗原，生成初始化的抗体，计算亲和度，记忆细胞分化，抗体促进和抑制，产生新的抗体，结束条件。 (1)识别抗原 把目标函数和约束作为抗原。 (2)生成初始化的抗体 随机生成独特型串维数为M的N个抗体。,7.2.1 基本流程,(3)计算亲和度 抗体v和抗原的亲和度为axv 其中optv表示抗体v和抗原的结合强度，对最优化问题，可以用抗体v的独特型的解和已知的最优解的相似程度表示。 抗体v和抗

9、体w的亲和度为 其中E(2)表示v和w的平均信息熵。,7.2.1 基本流程,下面介绍信息熵： 免疫系统由N个抗体，有M个基因，第j个基因的信息上为Ej(N): K若为二进制数就是2 pij选择第i个抗体的第j位等位基因的概率 平均信息熵E(N)：,7.2.1 基本流程,(4)记忆细胞分化 与抗原有最大亲和度的抗体加入了记忆细胞。因为记忆细胞数量有限，因此新生成的抗体将会代替记忆细胞中和它有最大亲和力者。 (5)抗体促进和抑制 通过计算抗体v的期望值，消除那些低期望值的抗体。 即促进高亲和度、低密度个体。 抗体v的期望值ev的计算公式：,qk表示和抗体k 有较大亲和力的抗体,7.2.1 基本流程

10、,(6)产生新的抗体 根据不同抗体和抗原亲和力的高低，使用轮盘赌方法，选择两个抗体。然后把这两个抗体按一定变异概率做变异，之后交叉，得到新的抗体。重复该步骤直到产生所有N个新抗体。 (7)结束条件 若求出的最优解满足一定结束条件则结束。,7.2.2 更一般化的基本免疫算法,1.求解多目标优化问题的免疫算法 多目标优化问题，可把抗原扩展到L个，把抗体v和抗原w的亲和度axv,w重新定义为 其中optv,w表示抗体v和抗原w的结合强度，即抗体v在目标函数w中的解和此函数最优解的接近程度。,7.2.2 更一般化的基本免疫算法,2.求解更一般问题的免疫算法,表示抗体 表示抗原 V是抗体可识别的空间 是

11、识别空间的半径 V是包含所有抗原的空间,图7.10 免疫系统形态空间,一个抗体可以识别在其识别空间内的所有抗原，同时抗原也能被不同类型的抗体所识别。,7.2.2 更一般化的基本免疫算法,2.求解更一般问题的免疫算法 假设在形态空间内，抗体v和抗原的坐标分别为 和， ，v=1,.,N，那么它们之间的距离为 Manhattan距离 Euclidean距离 Hamming距离,7.2.2 更一般化的基本免疫算法,2.求解更一般问题的免疫算法 同理可求抗体与抗体之间的距离。 此外亲和度公式也需修改如下： tv抗体v和抗原的距离 Hv,w抗体v和抗体w的距离,7.3 常用免疫算法,7.3.1 负选择算法 7.3.2 克隆选择算法 7.3.3 免疫算法与智能计算,7.3.1 负选择算法,算法基本思想：需要两个字符串组成的集合R和R，通过先求一个和S不匹配的R集合，然后用R集合判断S集合是否发生了变化。 算法分成两部