1、第第7章章 免疫算法免疫算法目录目录免疫算法简介免疫算法简介1 1基本流程基本流程2 2常用免疫算法常用免疫算法 3 3相关应用相关应用4 47.1 免疫算法简介免疫算法简介免疫算法是什么?免疫算法是什么?免疫算法(免疫算法(Immune Algorithm,IA):是指以):是指以人工免疫系统的理论为基础,借鉴免疫系统的人工免疫系统的理论为基础,借鉴免疫系统的记忆、学习、自我识别等性质,建立相应数学记忆、学习、自我识别等性质,建立相应数学模型,从而设计出解决实际问题的算法。该算模型,从而设计出解决实际问题的算法。该算法实现了类似于生物免疫系统的抗原识别、细法实现了类似于生物免疫系统的抗原识别
2、、细胞分化、记忆和自我调节的功能。胞分化、记忆和自我调节的功能。7.1.1 思想来源思想来源免疫系统能抵御日常生活中的绝大多数病原体,免疫系统能抵御日常生活中的绝大多数病原体,使我们保持健康。使我们保持健康。免疫系统还具有记忆功能,当我们得过某种疾病免疫系统还具有记忆功能,当我们得过某种疾病后,系统会生成专门的记忆细胞记住那些触发疾后,系统会生成专门的记忆细胞记住那些触发疾病的病原体,细菌再次入侵的时候身体就有了免病的病原体,细菌再次入侵的时候身体就有了免疫力。疫力。疾病的记忆细胞也可通过注射疫苗获得,记忆细疾病的记忆细胞也可通过注射疫苗获得,记忆细胞不仅能记住曾经入侵的病原体,对类似的其他胞
3、不仅能记住曾经入侵的病原体,对类似的其他疾病也能起到一定的免疫效果。疾病也能起到一定的免疫效果。可见免疫系统具有学习性、记忆性和模式识别性。可见免疫系统具有学习性、记忆性和模式识别性。7.1.1 思想来源思想来源抗原抗原抗体抗体抗原和抗体之抗原和抗体之间的亲和性间的亲和性目标函数目标函数优化解优化解解与目标函数的解与目标函数的匹配程度匹配程度免疫算法免疫算法优化问题的一般搜索算法优化问题的一般搜索算法类比关系类比关系7.1.1 思想来源思想来源免疫算法最先起源于免疫算法最先起源于1973-1976年间年间Jernel的三的三篇关于免疫网络的文章,篇关于免疫网络的文章,Jernel在文中提出了一
4、在文中提出了一组组基于免疫独特型的微分方程基于免疫独特型的微分方程,这就是最早的免,这就是最早的免疫系统。疫系统。免疫算法的主要会议免疫算法的主要会议:International Conference on Artificial Immune Systems,ICARIS 7.1.2 免疫系统的生物学原理免疫系统的生物学原理从人的角度:免疫的主要作用是帮助人体自身的从人的角度:免疫的主要作用是帮助人体自身的免疫系统抵制由病毒和细菌引起的疾病。免疫系统抵制由病毒和细菌引起的疾病。从生物学角度:免疫或免疫接种是强化个体抵御从生物学角度:免疫或免疫接种是强化个体抵御外部个体的能力的过程。外部个体的能
5、力的过程。7.1.2 免疫系统的生物学原理免疫系统的生物学原理抗原抗原:被免疫系统看作异体,引起免疫反应的分:被免疫系统看作异体,引起免疫反应的分子。即能刺激人体免疫的细胞,使人体产生免疫子。即能刺激人体免疫的细胞,使人体产生免疫反应的物质。可以是人体本身固有的,如血液,反应的物质。可以是人体本身固有的,如血液,也可以是人体内根本不存在的,如某些细菌,病也可以是人体内根本不存在的,如某些细菌,病毒,药物等。毒,药物等。抗体抗体:免疫系统用来鉴别和移植外援物质的一种:免疫系统用来鉴别和移植外援物质的一种蛋白质复合体。每种抗体只识别特定的目标抗原。蛋白质复合体。每种抗体只识别特定的目标抗原。当某种
6、抗原刺激人体后,人体对这种抗原会产生当某种抗原刺激人体后,人体对这种抗原会产生一种能识别它,并抵抗或消灭它的物质。当这种一种能识别它,并抵抗或消灭它的物质。当这种抗原再次入侵时,人体会产生抵抗(免疫)能力,抗原再次入侵时,人体会产生抵抗(免疫)能力,从而避免疾病的发生。从而避免疾病的发生。相关名词相关名词7.1.2 免疫系统的生物学原理免疫系统的生物学原理淋巴细胞淋巴细胞:免疫系统中起主要作用的微小白细胞,:免疫系统中起主要作用的微小白细胞,包括包括细胞和抗体细胞和抗体,细胞和细胞因子细胞和细胞因子以及以及自然自然杀伤细胞杀伤细胞。细胞细胞:全称为淋巴细胞,在骨髓分化成熟,:全称为淋巴细胞,在
7、骨髓分化成熟,免疫系统的本质部分。免疫系统的本质部分。细胞细胞:全称为淋巴细胞,在胸腺分化成熟,:全称为淋巴细胞,在胸腺分化成熟,按功能可分为按功能可分为细胞毒细胞细胞毒细胞(用来分解、消灭已(用来分解、消灭已感染病毒的细胞),感染病毒的细胞),辅助辅助T细胞细胞(用来识别病(用来识别病菌),菌),调节调节/抑制抑制T细胞细胞和和记忆记忆T细胞细胞。亲和力亲和力:抗体和抗原,抗体和抗体之间的相似程:抗体和抗原,抗体和抗体之间的相似程度。度。相关名词相关名词7.1.2 免疫算法的生物模型免疫算法的生物模型图图 免疫系统层次示意图免疫系统层次示意图7.1.3 二进制模型二进制模型每个抗体都有抗体决
8、定簇和抗原决定基。抗体和抗原的亲每个抗体都有抗体决定簇和抗原决定基。抗体和抗原的亲和程度由它的抗体决定簇和抗原决定基的匹配程度决定。和程度由它的抗体决定簇和抗原决定基的匹配程度决定。抗原决定基对其他的抗体来说也是一个特殊的抗原决定基对其他的抗体来说也是一个特殊的“抗原抗原”,它们之间的亲和度由它的抗原决定基和其他抗体的抗体决它们之间的亲和度由它的抗原决定基和其他抗体的抗体决定簇的匹配程度决定。定簇的匹配程度决定。图图 B细胞抗体结构图细胞抗体结构图7.1.3 二进制模型二进制模型二进制模型模仿了免疫系统的工作原理,涉及二进制模型模仿了免疫系统的工作原理,涉及识别识别和和刺刺激激两方面。两方面。
9、识别识别:每个抗体可以用:每个抗体可以用(e,p)的二进制串表示,匹配通过的二进制串表示,匹配通过计算两个串之间的互补字符个数计算两个串之间的互补字符个数t决定,决定,e表示抗原决定基表示抗原决定基,p表示抗体决定簇,它们的长度分别是表示抗体决定簇,它们的长度分别是le、lp(所有抗体所有抗体或抗原的这两个长度均相同或抗原的这两个长度均相同),s表示一个匹配阈值,当表示一个匹配阈值,当s minle,lp时免疫反应发生,也称两串相互识别,否则不时免疫反应发生,也称两串相互识别,否则不发生反应。设发生反应。设ei(n)表示第表示第i个抗原决定基的第个抗原决定基的第n位,位,pi(n)表表示第示第
10、i个抗体决定簇的第个抗体决定簇的第n位。串匹配运算用异或运算符位。串匹配运算用异或运算符“”。7.1.3 二进制模型二进制模型匹配特异矩阵为:匹配特异矩阵为:).()()(171 knjiijsnpkneGms匹配的阈值匹配的阈值 k串之间的错位长度串之间的错位长度 n串的具体某位串的具体某位 i和和j具体哪个抗体或抗原的某种决定基(簇)具体哪个抗体或抗原的某种决定基(簇)).(,)(27000 xxxxG由由(7.1)计算计算mij需求出需求出k的所有情况之和。但实际不必这样的所有情况之和。但实际不必这样计算。如书计算。如书P135图图7.3。模型还指出当一个模型还指出当一个B淋巴细胞识别一
11、个抗原决定基时,它淋巴细胞识别一个抗原决定基时,它受到刺激并分裂,产生更多表面附着相同抗体类型的受到刺激并分裂,产生更多表面附着相同抗体类型的B淋淋巴细胞。巴细胞。7.1.3 二进制模型二进制模型刺激刺激:二进制串之间匹配,会刺激新抗体的生成。以两:二进制串之间匹配,会刺激新抗体的生成。以两个抗体的相互识别为例,抗体个抗体的相互识别为例,抗体A的抗体决定簇能识别(即的抗体决定簇能识别(即匹配个数匹配个数t大于阈值大于阈值s)抗体)抗体B的抗原决定基,首先导致抗的抗原决定基,首先导致抗体体A以固有概率大量繁殖,同时逐渐清除抗体以固有概率大量繁殖,同时逐渐清除抗体B。这样通。这样通过抗体决定簇和抗
12、原决定基之间的作用控制了一类抗体过抗体决定簇和抗原决定基之间的作用控制了一类抗体的复制和另一类抗体的消亡。的复制和另一类抗体的消亡。建立微分方程模型,设建立微分方程模型,设N种类型的抗体,浓度为种类型的抗体,浓度为x1,x2,xN,n种类型的抗原,浓度为种类型的抗原,浓度为y1,y2,yn,此处的此处的浓度就是某种抗原或抗体的具体数量,则浓度就是某种抗原或抗体的具体数量,则抗体浓度变化抗体浓度变化方程方程为:为:).(3721111injjijiNjNjjiijjijiixkyxmxxmkxxmcx i1,N mij抗体抗体i和抗体和抗体j(或抗原(或抗原j)在匹配特异矩阵特定位置的值。)在匹
13、配特异矩阵特定位置的值。7.1.3 二进制模型二进制模型injjijiNjNjjiijjijiixkyxmxxmkxxmcx21111 抗体刺激抗体刺激i型抗体的抗体决定型抗体的抗体决定簇受到簇受到j型抗体的抗型抗体的抗原决定基的刺激原决定基的刺激抗体抑制抗体抑制i型抗体的抗原决定基被型抗体的抗原决定基被j型抗体的抗体决定簇识型抗体的抗体决定簇识别后,对别后,对i抗体的抑制抗体的抑制抗原刺激抗原刺激i型抗体的抗体决定簇受到型抗体的抗体决定簇受到j型抗原的抗原决定基的刺激,型抗原的抗原决定基的刺激,即抗原驱动即抗原驱动自然衰减自然衰减随着时间的推移,含有随着时间的推移,含有抗体细胞以抗体细胞以k
14、2决定的速决定的速率减少率减少模型中,当前抗原和抗体类型是动态变化的,模型中,当前抗原和抗体类型是动态变化的,N和和n是随是随时间变化的,且它们的变化速度分别远小于浓度时间变化的,且它们的变化速度分别远小于浓度xi和和yi的的变化速度。变化速度。7.1.3 二进制模型二进制模型抗体和抗原的动态调整规则为:抗体和抗原的动态调整规则为:图图7.6 抗原调整流程图抗原调整流程图7.2 免疫算法的基本流程免疫算法的基本流程免疫系统和免疫算法的比较免疫系统和免疫算法的比较免疫系统免疫系统 免疫算法免疫算法 抗原抗原要求解的问题要求解的问题抗体抗体最佳解向量最佳解向量抗原识别抗原识别问题识别问题识别从记忆
15、细胞产生抗体从记忆细胞产生抗体联想过去的成功解联想过去的成功解淋巴细胞分化(记忆细胞分化)淋巴细胞分化(记忆细胞分化)维持最优解维持最优解T细胞抑制抗体细胞抑制抗体消除多余的候选解消除多余的候选解生命增加(细胞克隆)生命增加(细胞克隆)用遗传算子生成新的抗体用遗传算子生成新的抗体7.2.1 基本流程基本流程图图7.8 免疫算法流程图免疫算法流程图7.2.1 基本流程基本流程免疫算法的七个要素免疫算法的七个要素 识别抗原,生成初始化的抗体,识别抗原,生成初始化的抗体,计算亲和度计算亲和度,记忆细胞分化,抗体促进和抑制,产生新的抗体,记忆细胞分化,抗体促进和抑制,产生新的抗体,结束条件。结束条件。
16、(1)识别抗原识别抗原把目标函数和约束作为抗原。把目标函数和约束作为抗原。(2)生成初始化的抗体生成初始化的抗体随机生成独特型串维数为随机生成独特型串维数为M的的N个抗体。个抗体。7.2.1 基本流程基本流程(3)计算亲和度计算亲和度 抗体抗体v和抗原的亲和度为和抗原的亲和度为axv 其中其中optv表示抗体表示抗体v和抗原的结合强度,对最优化问题,和抗原的结合强度,对最优化问题,可以用抗体可以用抗体v的独特型的解和已知的最优解的相似程度的独特型的解和已知的最优解的相似程度表示。表示。抗体抗体v和抗体和抗体w的亲和度为的亲和度为 其中其中E(2)表示表示v和和w的平均信息熵。的平均信息熵。11
17、vvaxopt).()(,57211Eaywv 7.2.1 基本流程基本流程下面介绍信息熵:下面介绍信息熵:免疫系统由免疫系统由N个抗体,有个抗体,有M个基因,第个基因,第j个基因的信个基因的信息上为息上为Ej(N):K若为二进制数就是若为二进制数就是2pij选择第选择第i个抗体的第个抗体的第j位等位基因的概率位等位基因的概率平均信息熵平均信息熵E(N):).(log)(671 NiijKijjppNE).()()(7711 MjjNEMNE7.2.1 基本流程基本流程(4)记忆细胞分化记忆细胞分化与抗原有最大亲和度的抗体加入了记忆细胞。因为记忆与抗原有最大亲和度的抗体加入了记忆细胞。因为记忆
18、细胞数量有限,因此新生成的抗体将会代替记忆细胞中细胞数量有限,因此新生成的抗体将会代替记忆细胞中和它有最大亲和力者。和它有最大亲和力者。(5)抗体促进和抑制抗体促进和抑制通过计算抗体通过计算抗体v的期望值,消除那些低期望值的抗体。的期望值,消除那些低期望值的抗体。即促进高亲和度、低密度个体。即促进高亲和度、低密度个体。抗体抗体v的期望值的期望值ev的计算公式:的计算公式:).().(9787Nqcvcaxekvvvv 的的密密度度:抗抗体体qk表示和抗体表示和抗体k有较大亲和力的抗体有较大亲和力的抗体7.2.1 基本流程基本流程(6)产生新的抗体产生新的抗体根据不同抗体和抗原亲和力的高低,使用
19、轮盘赌方法,根据不同抗体和抗原亲和力的高低,使用轮盘赌方法,选择两个抗体。然后把这两个抗体按一定变异概率做变选择两个抗体。然后把这两个抗体按一定变异概率做变异,之后交叉,得到新的抗体。重复该步骤直到产生所异,之后交叉,得到新的抗体。重复该步骤直到产生所有有N个新抗体。个新抗体。(7)结束条件结束条件若求出的最优解满足一定结束条件则结束。若求出的最优解满足一定结束条件则结束。7.2.2 更一般化的基本免疫算法更一般化的基本免疫算法1.求解多目标优化问题的免疫算法求解多目标优化问题的免疫算法 多目标优化问题,可把抗原扩展到多目标优化问题,可把抗原扩展到L个,把抗体个,把抗体v和抗原和抗原w的亲和度
20、的亲和度axv,w重新定义为重新定义为 其中其中optv,w表示抗体表示抗体v和抗原和抗原w的结合强度,即抗体的结合强度,即抗体v在目在目标函数标函数w中的解和此函数最优解的接近程度。中的解和此函数最优解的接近程度。,11v wv waxopt7.2.2 更一般化的基本免疫算法更一般化的基本免疫算法2.求解更一般问题的免疫算法求解更一般问题的免疫算法表示抗体表示抗体表示抗原表示抗原V是抗体可识别的空间是抗体可识别的空间是识别空间的半径是识别空间的半径V是包含所有抗原的空间是包含所有抗原的空间图图7.10 免疫系统形态空间免疫系统形态空间一个抗体可以识别在其识一个抗体可以识别在其识别空间内的所有
21、抗原,同别空间内的所有抗原,同时抗原也能被不同类型的时抗原也能被不同类型的抗体所识别。抗体所识别。7.2.2 更一般化的基本免疫算法更一般化的基本免疫算法2.求解更一般问题的免疫算法求解更一般问题的免疫算法假设在形态空间内,抗体假设在形态空间内,抗体v和抗原的坐标分别为和抗原的坐标分别为 和,和,v=1,.,N,那么它们之间的距离为那么它们之间的距离为 Manhattan距离距离 Euclidean距离距离 Hamming距离距离21()MiiviDabag1MiiviDabag11,if,0,otherwiseiiMviiiabagD ,.,Mvvvababab21,.,Magagag217
22、.2.2 更一般化的基本免疫算法更一般化的基本免疫算法2.求解更一般问题的免疫算法求解更一般问题的免疫算法同理可求抗体与抗体之间的距离。同理可求抗体与抗体之间的距离。此外亲和度公式也需修改如下:此外亲和度公式也需修改如下:tv抗体抗体v和抗原的距离和抗原的距离Hv,w抗体抗体v和抗体和抗体w的距离的距离).(14711vvtax ).(,15711wvwvHay 7.3 常用免疫算法常用免疫算法 7.3.1 负选择算法负选择算法 7.3.2 克隆选择算法克隆选择算法7.3.3 免疫算法与智能计算免疫算法与智能计算7.3.1 负选择算法负选择算法算法基本思想:需要两个字符串组成的集合算法基本思想
23、:需要两个字符串组成的集合R和和R,通过先求一个和,通过先求一个和S不匹配的不匹配的R集合,然后用集合,然后用R集合判断集合判断S集合是否发生了变化。集合是否发生了变化。算法分成两部分,第一步是初始化算法分成两部分,第一步是初始化R,第二步监,第二步监视保护数据视保护数据S。7.3.1 负选择算法负选择算法初始化监测器初始化监测器R生成随机串R0把R0中不和S所有的串匹配的串放入R集合,作为检测器自体串集合S匹配拒绝7.3.1 负选择算法负选择算法监视保护数据监视保护数据S初始串集合S随机变异若干部分检测器R探测到非自体两集合的串存在匹配没有探测到是否7.3.2 克隆选择算法克隆选择算法克隆选
24、择原理图克隆选择原理图212471282221281282抗原抗原决定基骨髓抗体决定簇011001101001100111101001死亡部分抗体克隆选择成熟7.3.2 克隆选择算法克隆选择算法克隆选择流程图克隆选择流程图MnPrP选择克隆成熟CC*dN重新选择(1)(2)(3)(4)(5)(6)7.3.3 免疫算法与进化计算免疫算法与进化计算免疫遗传算法免疫遗传算法创 建 初 始 种 群交 叉变 异注 射 疫 苗免 疫 选 择重 新 复 制 出 新 的 种 群是 否 满 足结 束 条 件计 算 个 体 的 适 应 度否是G eneration=0G eneration+1开 始结 束7.4 免疫算法的应用免疫算法的应用识别与分类问题识别与分类问题优化问题优化问题机器人学习与控制机器人学习与控制数据挖掘数据挖掘