第四章免疫算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工免疫系统,整理发布,Contents,引言,1,2,免疫算法,3,典型的人工免疫系统,ARTIS,4,基本免疫方法,引言,人工免疫系统作为人工智能领域的重要分支，同神经网络及遗传算法一样也是智能信息处理的重要手段，已经受到越来越多的关注。,它通过类似于生物免疫系统的机能，构造具有动态性和自适应性的信息防御体系，以此来抵制外部无用、有害信息的侵入，从而保证接受信息的有效性与无害性。,背景,在生物科学领域，人们对进化、遗传和免疫等自然 现象已经进行了广泛而深入的研究；,进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广泛；,进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；,大多数待求问题有可以利用的先验知识或特征信息，故可以利用这些信息来抑制进化过程中的退化现象；,生物免疫理论为改进原有算法的性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础,。,一门新兴的研究领域,Farmer等人在1986年首先在工程领域提出,免疫,概念；,Varela等人受免疫网络学说的启发，提出并进而完善免疫网络模型。,人工免疫网络模型,独特型免疫网络（Jerne）；,互联耦合免疫网络（Ishiguro）；,免疫反应网络（Mitsumoto）；,对称网络（Hoffmann）；,多值免疫网络（Tang）.,应用,自动控制,故障诊断,模式识别,图象识别,优化设计,机器学习,网络安全,AIS,在控制领域中的应用,PID型免疫反馈控制器（Takahashi）；,机器人控制（Mitsumoto,Ishiguro,Lee）；,控制系统的设计（Ishida）；,复杂动态行为建模和自适应控制（Kumak）；,倒摆的控制（Bersini）。,AIS,在故障诊断中的应用,基于相关识别特性的免疫网络模型用于故障诊断的方法（Ishida）；,通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统（Ishiguru）。,AIS,在模式识别中的应用,Hunt等人开发了一种具有学习能力的人工免疫系统并用于模式识别。,AIS,在联想记忆中的应用,Gilbert等人采用免疫网络模型设计了一种内容可访的自动联想记忆系统并用于图像识别。,AIS,在优化设计中的应用,永磁同步电动机的参数修正的优化设计；,电磁设备的外形优化；,VLSI印刷线路板的布线优化设计；,函数测试；,旅行商问题的求解；,约束搜索优化问题和多判据设计问题,；,AIS,在网络安全的应用,数据检测（Forrest）；,病毒检测（Kephart）；,UNIX过程监控（Forrest）。,国际研究新动向之一,以开发新型的智能系统方法为背景，研究基于生物免疫系统机理的智能系统理论和技术，同时将AIS与模糊系统、神经网络和遗传算法等软计算技术进行集成，并给出其应用方法。,国际研究新动向之二,基于最新发展的免疫网络学说进一步建立并完善模糊、神经和其它一些专有类型的人工免疫网络模型及其应用方法。,国际研究新动向之三,将人工免疫系统与遗传系统的机理相互结合，并归纳出各种免疫学习算法。比如：免疫系统的多样性遗传机理和细胞选择机理可用于改善原遗传算法中对局部搜索问题不是很有效的情况；独特型网络机理可用于免疫系统中的遗传部分以避免系统出现早熟现象；发展用于处理受约束的遗传搜索和多准则问题的免疫学习算法等。,国际研究新动向之四,基于免疫反馈和学习机理，设计自调整、自组织和自学习的免疫反馈控制器。展开对基于免疫反馈机理的控制系统的设计方法和应用研究，这有可能成为工程领域中种新型的智能控制系统，具有重要的理论意义与广泛的应用前景。,国际研究新动向之五,进一步研究基于免疫系统机理的分布式自治系统。分布式免疫自治系统在智能计算、系统科学和经济领域将会有广阔的应用前景。,国际研究新动向之六,发展基于DNA编码的人工免疫系统以及基于DNA计算的免疫算法。尝试将DNA计算模型引入人工免疫系统中，研究一种基于DNA计算与AIS相结合的，有较强抗干扰能力和稳定性能的智能系统,国际研究新动向之七,近年来有学者已开始研究B细胞抗体网络的振荡、混浊和稳态等非线性特性，不过其工作才刚刚开始。人们应进一步借助非线性的研究方法来研究免疫系统的非线性行为，拓宽非线性科学的研究范围。,国际研究新动向之八,进一步发展AIS在科学和工程上的应用，并研制实际产品，如研制在复杂系统的协调控制、故障检测和诊断、机器监控、签名确认、噪声检测、计算机与网络数据的安全性、图像与模式识别等方面的实际产品。,生物免疫的启示,在生物自然界中，免疫现象普遍存在，并对物种的,生存与繁衍,发挥着重要的作用；,生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；,生物免疫主要有两种类型：,特异性免疫,（Specific Immunity），,非特异性免疫反应,（Nonspecific Immunity）；,生物免疫系统是通过自我识别、相互刺激与制约而构成了一个,动态平衡的网络结构,。,免疫生物学的基本概念,抗原,是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。,抗体,是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。,免疫系统的主要功能,免疫防御,即机体防御病原微生物的感染；,免疫（自身）稳定,即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；,免疫监视,即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞,大于阈值,spam,记忆细胞检测器,亲和力计算,不大于阈值,大于阈值,不大于阈值,亲和力计算,正文特征提取,用户反馈,未成熟细胞检测器,ham,spam,特征库,随机特征项,检测到,spam,？,删除该未成熟检测器,克隆记忆,Y,N,用户反馈,更新检测器、,spam,特征库,基本免疫方法,1.免疫识别,2.免疫学习,3.免疫记忆,4.克隆选择,免疫识别,免疫识别是免疫系统的主要功能，同时也是AIS的核心之一，而识别的本质是区分“自我”和“非我”。,核心机制是根据识别的对象特征进行编码，定义一个自我集合并随机产生一系列检测器，用于检测自我集合的变化。根据阴性选择原理，若检测集合与自我集合匹配，则完成匹配任务，机体发现病变。,基本免疫方法,(1)定义自己(self)为一个字符串集合S，每个字符串由n个字母组成，字符串可以是一个网络数据包，,电子邮件特征向量,或程序的一般行为模式。,(2)产生一个初始监测器集合R。,(3)监测器集合中每个监测器经历阴性选择过程。其中每一个监测器都不能与集合S中的任何一个字符串相匹配，否则就从监测器集合中删去对应的检测器。,(4)通过与R集合的,匹配,不断监测S的变化，一旦发生任何匹配，则说明S集发生了变化，即有外来抗原侵入。,基本免疫方法,在最初的算法描述中，候选的监测器是随机产生的，然后测试以删除与自身字串相匹配的监测器，算法中采用的匹配规则是,r-连续位匹配,，即当两个字符串至少存在连续r位相同是才发生匹配。,该过程重复进行，直到,所需数量的监测器,被产生出来。通常用,概率分析方法,来估算为了满足一定的可靠性所应有的监测器的数目。,基本免疫方法,免疫学习,免疫识别过程同时也是一个学习的过程，学习的结果是免疫细胞的个体亲和度提高、群体规模扩大，并且最优个体以免疫记忆的形式得到保存。,当机体重复遇到同一抗原时，由于免疫记忆机制的作用，免疫系统对该抗原的应答速度大大提高，并且产生高亲和度的抗体去除病原，这个过程是一个增强式学习过程。,而且可以对结构类似的抗原进行识别,。,基本免疫方法,免疫学习一般有以下几种途径:,(a)对同一抗原进行重复学习，属于增强式学习。,(b)亲合度成熟，对应于AIS中的个体经遗传操作后其亲合度逐步提高的过程，属于遗传学习。,(c)低度的重复感染，对应于AIS的重复训练过程。,(d)对内生和外生抗原的交叉应答，属于联想式学习，对应于联想记忆机制。,基本免疫方法,免疫记忆,当免疫系统初次遇到一种抗原时，淋巴细胞需要一定的时间进行调整以更好地识别抗原，并在识别结束后,以最优抗体的形式保留对该抗原的记忆信息,。而当免疫系统再次遇到相同或者结构相似的抗原时，在联想记忆的作用下，其应答速度将大大提高。,免疫记忆主要体现在再次免疫应答和交叉免疫应答时，可以大大加速优化搜索过程，加快学习进程并提高学习质量。,基本免疫方法,克隆选择,克隆选择原理最先由Jerne提出，后由Burnet给予完整阐述。其大致内容为:当淋巴细胞实现对抗原的识别(即抗体和抗原的亲和度超过一定阈值)后，B细胞被激活并增殖复制产生B细胞克隆，随后克隆细胞经历变异过程，产生对抗原具有特异性的抗体。克隆选择理论描述了获得性免疫的基本特性，并且声明只有成功识别抗原的免疫细胞才得以增殖。经历,变异后的免疫细胞分化为效应细胞(抗体)和记忆细胞两种,。,基本免疫方法,克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗传变异分化为多样性抗体细胞和记忆细胞。,克隆选择对应着一个亲和度成熟的过程，即,对抗原亲和度较低的个体,在克隆选择机制的作用下，经历增殖复制和变异操作后，其,亲和度逐步提高而“成熟”,的过程。因此亲和度成熟本质上是一个达尔文式的选择和变异的过程，克隆选择原理通过采用,交叉、变异等遗传算子和相应的群体控制机制,实现。,基本免疫方法,免疫算法,一般的免疫算法可分为三种情况:,模仿免疫系统抗体与抗原识别，结合抗体产生过程而抽象出来的免疫算法;,基于免疫系统中的其他特殊机制抽象出的算法，例如克隆选择算法;,与遗传算法等其他计算智能融合产生的新算法，例如免疫遗传算法。,免疫算法的一般步骤,初始抗体生成,抗原识别,抗体促进和抑制,满足终止条件？,群体更新,结束,亲和力计算,记忆细胞分化,Y,N,免疫算法,(1)识别抗原：免疫系统确认抗原入侵。,(2)产生初始抗体群体：激活记忆细胞产生抗体，清除以前出现过的抗原，从包含最优抗体(最优解)的数据库中选择出来一些抗体。,(3)计算亲和力：计算抗体和抗原之间的亲和力。,(4)记忆细胞分化：与抗原有最大亲和力的抗体加给记忆细胞。由于记忆细胞数目有限，新产生的与抗原具有更高亲和力的抗体替换较低亲和力的抗体。,(5)抗体促进和抑制：高亲和力抗体受到促进，高密度抗体受到抑制。通常通过计算抗体存活的期望值来实施。,(6)抗体产生:对未知抗原的响应，产生新淋巴细胞,免疫算法,阴性选择算法,Procedure,Begin,随机生成大量的候选检测器(即免疫细胞)/*初始化*/,While一个给定大小的检测器集合还没有被产生do/*耐受*/,Begin,计算出每一个自体元素和一个候选检测器之间的亲和力;,If这个候选的检测器识别出了自体集合中的任何一个元素Then这个检测器就要被消除掉;,Else把这个检测器放入检测器集合里面;/*该检测器成熟*/,利用经过耐受的检测器集合，检测系统以找出变种;,End;,End.,常见免疫算法,克隆选择算法,Begin,随机生成一个属性串(免疫细胞)的群体,While收敛标准没有满足do,Begin,While not所有抗原搜索完毕do;*/初始化*/,Begin,选择那些与抗原具有更高亲和力的细胞;*/选择*/,生成免疫细胞的副本:越高亲和力的细胞拥有更多的副本;*/再生*/,根据它们的亲和力进行变异:亲和力越高，变异越小;*/遗传变异*/,End.End.End.,免疫算法,免疫遗传算法,随机创建抗体和抗原的群体;,抗体和抗原匹配;,根据抗体的亲和力对抗体做评价;,用标准遗传算法进化抗体。,这个模型使免疫系统能够通过学习，知道哪些抗体对抗原的识别有帮助。,常见免疫算法,免疫系统与一般免疫算法之间的比较,免疫算法,免疫算法中的亲和力计算方法,免疫算法中最复杂的计算,是亲和力计算。由于产生于确定克隆类型的抗体分子独特型是一样的，抗原与抗体的亲和力也是抗体与抗体的亲和力的测量。,一般计算亲和力的公式:,其中，t,k,是抗原和抗体k的结合强度。,常见免疫算法,一般免疫算法,计算结合强度,t,k,的数学工具主要有:,(1)海明空间的海明距离,(2)Euclidena形态空间的,Euclidean距离,(3)Manhattan形态空间的,Manhattan距离,免疫算法,抗体抗原的编码方式,目前一般免疫算法种抗体抗原，即解和问题的编码方式主要有二进制编码、实数编码和字符编码三种。,其中，二进制编码因简单而得到广泛使用。编码后亲和力的计算一般是比较抗体抗原字符串之间的异同，根据上述亲和力计算方法计算。,免疫算法,典型的人工免疫系统模型ARTIS,ARTIS(ARTificial Immune System)是Hofmeyr提出的一种分布式人工免疫系统模型，它具有多样性、分布性、错误耐受、动态学习、自适应性、自我监测等特性，可应用于各种工程领域。,ARTIS的免疫细胞生命周期理论对基于免疫的反垃圾邮件技术具有积极的启迪作用。,ARTIS模型是一个分布式系统，它由一系列模拟淋巴结的节点构成，每个节点由多个检测器组成。各个节点都可以独立完成免疫功能。模型涉及的免疫机制包括识别、抗体多样性、调节、自体耐受、协同刺激等。,在ARTIS中，用固定长度的二进制串构成的有限集合U来表示蛋白质链。U可以分为两个子集：N表示非自体，S表示自体，满足U=NS且 NS=。,ARTIS,