第7章-免疫算法

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