1、免疫进化理论的研究,主要内容, 研究背景与现状 免疫进化算法 免疫神经网络 计算机免疫安全系统探索,研究背景,在生物科学领域，人们对进化、遗传和免疫等自然 现象已经进行了广泛而深入的研究 ；进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广泛；进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；大多数待求问题有可以利用的先验知识或特征信息，故可以利用这些信息来抑制进化过程中的退化现象；生物免疫理论为改进原有算法的性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础。,Artificial Immune SystemAIS,人工智能信息
2、处理系统的研究,脑神经系统（神经网络）遗传系统（进化计算）免疫系统（人工免疫系统）,一门新兴的研究领域,AIS的研究历史,Farmer等人在1986年首先在工程领域提出免疫概念Varela等人受免疫网络学说的启发，提出并进而完善免疫网络模型。,人工免疫网络模型,AIS的研究现状之一,独特型免疫网络（Jerne）互联耦合免疫网络（Ishiguro）免疫反应网络（Mitsumoto）对称网络（Hoffmann）多值免疫网络（Tang）, 免疫学习算法,AIS的研究现状之二,反面选择算法（Forrest）免疫学习算法（Hunt&Cooke）免疫遗传算法（Chun）免疫Agent算法（Ishida）免
3、疫网络调节算法（Wang&Cao）免疫进化算法（Jiao&Wang）, 国际研究,AIS的研究现状之三,1996年，日本，基于免疫性系统的国际专题讨论会，提出并确认人工免疫系统（AIS）的概念；1997年，IEEE的SMC组织专门成立了人工免疫系统及应用的分会组织；目前，几乎所有有关人工智能领域的学术会议都收录AIS方面的论文。,AIS 的应用,自动控制故障诊断模式识别图象识别优化设计机器学习网络安全,AIS在控制领域中的应用,PID型免疫反馈控制器（ Takahashi ）机器人控制（ Mitsumoto, Ishiguro, Lee）控制系统的设计（ Ishida ）复杂动态行为建模和自适
4、应控制（Kumak）倒摆的控制（ Bersini ）,AIS在故障诊断中的应用,基于相关识别特性的免疫网络模型用于故障诊断的方法（Ishida）；通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统（Ishiguru）。,AIS在模式识别中的应用,Hunt等人开发了一种具有学习能力的人工免疫系统并用于模式识别。,AIS在联想记忆中的应用,Gilbert等人采用免疫网络模型设计了一种内容可访的自动联想记忆系统并用于图像识别。,AIS在优化设计中的应用,永磁同步电动机的参数修正的优化设计电磁设备的外形优化VLSI印刷线路板的布线优化设计函数测试旅行商问题的求解约束搜索优化问题和多判据设计问
5、题,AIS在网络安全的应用,数据检测（Forrest ）病毒检测（ Kephart）UNIX过程监控（ Forrest）,国际研究新动向之一,以开发新型的智能系统方法为背景，研究基于生物免疫系统机理的智能系统理论和技术，同时将AIS与模糊系统、神经网络和遗传算法等软计算技术进行集成，并给出其应用方法。,国际研究新动向之二,基于最新发展的免疫网络学说进一步建立并完善模糊、神经和其它一些专有类型的人工免疫网络模型及其应用方法。,国际研究新动向之三,将人工免疫系统与遗传系统的机理相互结合，并归纳出各种免疫学习算法。比如：免疫系统的多样性遗传机理和细胞选择机理可用于改善原遗传算法中对局部搜索问题不是很
6、有效的情况；独特型网络机理可用于免疫系统中的遗传部分以避免系统出现早熟现象；发展用于处理受约束的遗传搜索和多准则问题的免疫学习算法等。,国际研究新动向之四,基于免疫反馈和学习机理，设计自调整、自组织和自学习的免疫反馈控制器。展开对基于免疫反馈机理的控制系统的设计方法和应用研究，这有可能成为工程领域中种新型的智能控制系统，具有重要的理论意义与广泛的应用前景。,国际研究新动向之五,进一步研究基于免疫系统机理的分布式自治系统。分布式免疫自治系统在智能计算、系统科学和经济领域将会有广阔的应用前景。,国际研究新动向之六,发展基于DNA编码的人工免疫系统以及基于DNA计算的免疫算法。尝试将DNA计算模型引
7、入人工免疫系统中，研究一种基于DNA计算与AIS相结合的，有较强抗干扰能力和稳定性能的智能系统。,国际研究新动向之七,近年来有学者已开始研究B细胞抗体网络的振荡、混浊和稳态等非线性特性61，不过其工作才刚刚开始。人们应进一步借助非线性的研究方法来研究免疫系统的非线性行为，拓宽非线性科学的研究范围。,国际研究新动向之八,进一步发展AIS在科学和工程上的应用，并研制实际产品，如研制在复杂系统的协调控制、故障检测和诊断、机器监控、签名确认、噪声检测、计算机与网络数据的安全性、图像与模式识别等方面的实际产品。,免疫进化算法的研究,第一部分,生物免疫的启示,在生物自然界中，免疫现象普遍存在，并对物种的
8、生存与繁衍 发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；生物免疫主要有两种类型： 特异性免疫（Specific Immunity）， 非特异性免疫反应（Nonspecific Immunity）；生物免疫系统是通过自我识别、相互刺激与制约而构成了一个 动态平衡的网络结构 。,免疫生物学的基本概念, 抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。 抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。,免疫系统的主要功能, 免疫防御
9、即机体防御病原微生物的感染； 免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡； 免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞。,免疫系统的主要特点,免疫识别免疫应答免疫耐受免疫记忆免疫调节,算法研究,生物学概念与理论,方法：,工程计算方法,进化免疫,传统进化算法是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中的个体提供了进化机会的同时，也无可避免地产生了退化的可能。每一个待求的实际问题都会有自身一些基本的、显而易见的特征信息或知识。然而进化算法中的交叉和变异算子在求解问题时，操作的可变程度较小。,
10、基本概念,染色体表示待求问题的解的形式的一种数据结构。基因构成染色体的最基本的数据单位。个体具有某类染色体结构的一种特例。,基本概念,抗原所有可能错误的基因，即非最佳个体的基因。疫苗根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。抗体 根据疫苗修正某个个体的基因所得到的新个体。,免疫算子有两种类型：全免疫 非特异性免疫目标免疫 特异性免疫,免疫思想的实现, 免疫算子,即：群体中的每个个体在进化算子作用后，对其每一环节都进行一次免疫操作的免疫类型；,即：在进行了进化操作后，经过一定的判断，个体仅在作用点处发生免疫反应的一种类型。,http:/,免疫操作的基本过程,首先，对待求求问
11、题进行具体分析，从中提取出 最基本的特征信息； 其次，对此特征信息进行处理，以将其转化为求解问题的一种方案；最后，将此方案以适当的形式转化成 免疫算子 以实施具体的操作。,免疫算子,算法中的免疫思想主要是在合理提取疫苗的基础上，通过免疫算子来实现的；免疫算子由 接种疫苗 和 免疫选择 两个操作完成的。,The Immune operator,为了防止群体的退化。,为了提高个体的适应度。,设个体x，给其接种疫苗是指按照先验知识来修改x的某些基因位上的基因或其分量，使所得个体以较大的概率具有更高的适应度。疫苗 是从先验知识中提炼出来的，它所含的信息量及其准确性对算法性能的发挥起着重要的作用。,免疫
12、算子,接种疫苗,之,这一操作一般分两步完成：第一步是 免疫检测 ，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，则该个体将被父代中所对应的个体所取代；第二步是 退火选择 ，即在目前的子代群体中以右边所示概率,免疫算子,免疫检测,之,选择个体进入新的父代群体。在免疫策略中，仅有免疫检测而没有退火选择。,体系结构,免疫算法免疫规划免疫策略,免疫算法,随机产生初始父代种群A1 ，根据先验知识抽取疫苗；若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续；对当前第k代父本种群Ak进行交叉操作，得到种群Bk；对Bk进行变异操作，得到种群Ck；对Ck进行接种疫苗操作，得到种群Dk；对Dk进
13、行免疫选择操作，得到新一代父本Ak+1，转至第二步。,Immune Algorithm-IA,免疫算法的收敛性,状态转移过程示意图：,定 理：免疫算法是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,初始化：首先，根据要求确定解的精度；其次，随机产生N个个体，并由此构成初始的父代种群A0；根据先验知识抽取疫苗H；计算当前种群Ak的个体适应度，并进行停机条件的判断。若条件满足，则停止运行并输出结果；否则继续；对当前的父代群体Ak进行变异操作，生成子代群体Bk；对群体Bk进行接种疫苗操作，得到种群Ck；对群体Ck进行免疫选择操作，得到新一代父本Ak+1，并转至第三步。,免疫规划,Im
14、mune Programming-IP,免疫规划的收敛性,状态转移过程示意图：,定 理：免疫规划是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,免疫策略,根据要求确定解的精度，再根据先验知识抽取疫苗H；随机产生个个体作为初始的父本群体；交叉：产生由父代和子代构成的规模为2的中间群体；变异：对每一个个体进行变异将得到一个新的个体；免疫：首先按照对问题的先验知识修改个体(x,)的某些分量；然后对群体中注射了疫苗的个体进行检测；选择：从规模为2的群体中按适应度的大小取出前个个体作为新一代父本的群体；停机条件检测。,Immune Strategy-IS,免疫策略的收敛性,状态转移过程示
15、意图：,定 理：免疫策略是收敛的。,定 义：如果对于任意的初始分布均有,则称算法收敛。,免疫算子的机理,在免疫选择作用下，若疫苗使抗体适应度得到提高，且高于当前群体的平均适应度，则疫苗所对应的模式将在群体中呈指数级扩散；否则，它将被遏制或呈指数级衰减。,定 理：,Begin:抽取疫苗： 分析待求问题，搜集特征信息； 依据特征信息估计特定基因位上的模式: ；k = 0 and j = 0；while (Conditions = True) if PV=True, then j = j +1； i = 0； for (in) 接种疫苗： ； 免疫检验：if , then ; else ； i =
16、i +1； 退火选择： ； k = k+1；End,免疫算子的执行算法,具体分析待求问题，搜集特征信息。,免疫疫苗的选取方法,通用方法,之一,以TSP问题为例，通过具体分析可以得出相邻两两城市之间的最短路径即为求解该问题时可以利用的一种疫苗。,TSP问题的描述,TSP问题是旅行商问题的简称。即一个商人从某一城市出发，要遍历所有目标城市，其中每个城市必须而且只须访问一次。所要研究的问题是在所有可能的路径,中寻找一条路程最短的路线。该问题是一个典型的NP问题，即随着规模的增加，可行解的数目将做指数级增长。,TSP问题的分析,设所有与城市Ai距离最近的城市为Aj,进行一次如虚线所示的调整后,多数情况
17、下， l3较aj-1 + aj的减少量要大于l1 + l2较ai的增加量。,故：,Begin:while (Conditions = True) 统计父代群体，确定最佳个体：; 分解最佳个体，抽取免疫基因：; 执行遗传和免疫算子操作;end,免疫疫苗的选取方法,自适应方法,之二,Begin:邻近城市序列初始化：Neighbor(i) = random(1, n) , i =1, , n;最短子路径的初始化：Sub_path(i) i =1, n;while (Conditions = True) for i = 1 to n 变异： Neighbor(i) = Floor(Gauss(Neig
18、hbor(i), 1 ) ) ; 选择：if Distance(City_ i, Neighbor(i) Min_distance(i) then Sub_path(i) = Neighbor(i); Min_distance(i) = Distance(City_ i, Neighbor(i); end endend,免疫疫苗的选取方法,进化规划方法,之三,仿真实验,基于IA的TSP求解,之一,a. 免疫抗体b. 最优化路径75城市的TSP问题免疫优化仿真示意图,子代适应度值随进化过程的变化曲线,a 通用遗传算法计算曲线b 免疫算法计算曲线,仿真实验,基于IS的TSP求解,之二,a. 免疫疫
19、苗示意图 b. 最优路径示意图442城市的TSP问题免疫优化仿真示意图,子代适应度值随进化过程的变化曲线,a (,2 )-ES计算曲线 b ( ,2 )-IS 计算曲线,仿真实验,基于IE的函数优化,之三,问题: 在(0,1)内寻找 xmax使下式成立:,接受正常免疫疫苗时的计算曲线,(a) 基于EP的进化过程中个体分布图;(b) 基于IP的进化过程中个体分布图(c) EP和IP所求得的最佳适应度对比图(d) EP和IP所求得的平均适应度对比图,免疫疫苗为 时的计算曲线,(a) 基于EP的进化过程中个体分布图;(b) 基于IP的进化过程中个体分布图(c) EP和IP所求得的最佳适应度对比图(d
20、) EP和IP所求得的平均适应度对比图,免疫神经网络的研究,第二部分,自然免疫网络, 生物学免疫网络原型： Jerne: 免疫系统是通过自我识别和相互刺激与约束而构成的一个动态平衡的网络结构。 免疫应答 ( 免疫耐受与记忆 ); Varela 的免疫网络模型：,系统的动力学部分；系统的元动力学部分；系统的免疫恢复机制(IRM).,免疫神经网络的生物学特征,一个完整的神经元由细胞体、树突、轴突、突触和神经末梢等几大部分构成，其中细胞体是神经元的主体。人的脑系统大约由1011个神经元组成。这些神经元虽然在物理结构上是基本一致的，但其功能和在系统中所发挥的作用是有明显差别的。 生物免疫系统具有记忆功
21、能以及自学习、自组织和自适应的能力。,人工免疫神经网络的研究,已有人工神经网络的特点。利用先验知识改进人工神经网络结构的尝试： Stork，1992年，奇偶校验问题。 Kryghyak，1993年，奇偶校验问题。 吴佑寿，1996年，奇偶校验和对称性校验的 问题。,一种免疫神经网络模型,免疫神经网络中激励函数的选取方法,分析待求问题的过程，搜集特征信息，再根据先验知识找出输入变量之间的相互约束关系；设计激励单元的基本类型。即根据上述约束关系，选取一种适当的含有待定参数的函数族；根据第步所提取的疫苗填充疫苗接种单元；选取一种网络学习算法，如LMS和改进的BP算法等，利用训练样本来修正网络中的权值
22、矩阵和阀值等相关参数。,免疫神经网络的自学习算法,将激励函数中的参数V当作网络训练的目标之一；采用成批训练和添加动量项的方法来训练网络权值和激励函数中的参数。,免疫神经网络的设计实例,双螺旋线问题的求解,设螺旋线的参数方程形式为：,由此可得：,双螺旋线问题的求解,设计激励单元的基本类型：,双螺旋线问题的求解,解决双螺旋线的免疫神经网络的形式为：,双螺旋线问题的仿真结果,带有随机干扰的两类螺旋线：,免疫进化子波网络模型,网络方程：,免疫进化子波网络模型,目标函数：,子波函数的参数初始化,确定一个母波函数以及对特定目标信号的伸缩、平移参数的取值范围；利用免疫进化算法进行优化搜索； 获得一组有利于分
23、类识别的信号子波特征。,子波网络的学习算法,初始化。将任意选取n组权值以及初始化后的子波基参数做为初始群体；根据先验知识抽取疫苗H。根据对问题的先验知识或其应用背景方面的特征信息，来确定个体在某些基因上的取值特征或基因之间的相互制约关系，并以此做为待求问题的免疫疫苗，经编码处理后即可视为H；另一方面，若以上条件尚不具备，我们即可采用算法2来动态寻找H，并将该过程置于第4与第5步骤之间进行；,学习算法（续）,计算当前群体中所有个体的适应度，并从中确定最佳个体，然后判断停机条件是否满足；对当前群体实施变异操作； 对当前群体实施接种疫苗操作； 对接种了疫苗的个体进行检验，并对所注射的疫苗做出评价；计
24、算当前群体中所有个体的适应度，并以此为根据在一定的选择机制下，挑选出n个个体组成下一代进化的群体，然后转至第3步。,双螺旋线问题的仿真结果,带有随机干扰的两类螺旋线：,免疫理论的应用研究,第三部分,计算机免疫系统的研究,计算机网络模型示意图, 随着现代计算机网络技术和信息技术的高速发展，特别是Internet在全球领域的推广，计算机信息系统的安全日渐突出； 从功能上分析，计算机（网络）系统一般包括信息的传输与变换两个方面。由于这两方面对信息处理的目的不同，所以它们对安全性的要求也不一样。就传输过程而言，系统要求防止外界自然因素对信息的影响和人为因素的监听、截获和施扰；在对信息的转换和处理过程中
25、，主要预防黑客的入侵和病毒的破坏。,计算机免疫系统的研究, 先天免疫性 自适应免疫性 信息发布的快速性 可测量性 安全与可靠性 用户可控性,免疫系统的设计原则,信息传输免疫系统,信息传输免疫系统示意图,信息传输免疫系统,信息序列的基带信号：,伪随机信号：,调制后发送信号：,信息传输免疫系统,接收段信号：,经伪随机解调信号：,经过解调输出的干扰信号总能量：,信息处理免疫系统,计算机人工免疫系统结构示意图,终端层各单元的功能, 病毒检测 指在终端机或单独的计算机上进行针对病毒代码和信息异常变化的检测，所采取的主要技术包括病毒特征码的扫描技术和系统信息跟踪技术； 获取样本病毒 在单机系统内部散布一些
26、“诱饵”程序并监测其变化情况，将被改变程序中的相关代码与已知病毒代码进行比对处理，从中获取相应的、新的病毒样本。这一过程即为后面即将介绍的诱饵算法的基本思路； 病毒清除 清除由病毒检测过程和“诱饵”算法所查获的新旧病毒，然后记录操作情况并发出警告； 信息修复 根据上一级免疫系统提供的修复程序对病毒破坏的信息进行自主式修复。,局域层各单元的功能, 系统监控 系统随时监测本系统内信息的变化情况，遇有异常迹象则释放“诱饵”并跟踪和记录该信息的变化过程，以判断其操作的合法性。 系统报警 当判断信息的变化过程确属异常或非法时，锁定信息并向上一层或管理人员报警；另外，系统根据本层病毒特征提取的情况确定是否
27、向下层发出新型病毒入侵的警报。 病毒特征提取 系统响应下层上报的病毒报警信息，从病毒样本中提取病毒代码。然后将其与广域层的病毒数据库进行对比，属于新代码则上传给广域层进行病毒数据库的更新。,广域层各单元的功能, 系统信息发布 根据局域层上报的信息异常变化警报，决定是否将其跟踪和记录变化过程的数据向下层发布；定期和不定期向下层发布新型病毒特征代码和一些修复程序。 修复程序生成 根据信息遭受破坏的过程记录及其特点，人为或自动地生成相应的信息修复程序。 病毒数据库更新 根据下层上报的病毒特征代码更新当前的全局病毒数据库（添补新型病毒代码和删除一些长期不用的代码）。,病毒监测算法,异常变化监测算法,广
28、域层各单元的功能, 系统信息发布 根据局域层上报的信息异常变化警报，决定是否将其跟踪和记录变化过程的数据向下层发布；定期和不定期向下层发布新型病毒特征代码和一些修复程序。 修复程序生成 根据信息遭受破坏的过程记录及其特点，人为或自动地生成相应的信息修复程序。 病毒数据库更新 根据下层上报的病毒特征代码更新当前的全局病毒数据库（添补新型病毒代码和删除一些长期不用的代码）。,基于免疫策略RBF的多用户监测, CDMA系统相对于以前的TDMA和FDMA系统来说具有很多突出的优点。 仅有时域处理能力的CDMA系统存在诸如远近效应、多址干扰等缺陷。 自适应天线可以在空域方面进一步改善传统CDMA系统的通
29、信能力。,空时信号模型,用户k 的基带信号：,用户k 的特征波形：,用户k 的发送信号：,空时信号模型,多径信号的基 带冲激响应：,用户k 经第l条路径到达天线阵列的方向向量：,天线阵列所接收到的信号：,空时二维接收机, 一个空时二维处理器即为空时接收调制解调器，它同时对所有的天线工作，并在时间和空间两个域处理所接收的信号。一个典型的空时匹配滤波器一般为两极结构。其中，前一级结构主要用作对接收信号的时域匹配滤波；后级结构则对时域处理过的信号再进行空域匹配滤波处理。,空时信号模型,信号经时域匹配滤波处理后的中间结果为：,经空域匹配滤波处理：,空时匹配滤波器的输出：,空时多用户检测器,利用Came
30、ron-Martin公式，我们可以将基于所有用户数据b的对接收信号r(t)的似然函数写成如下形式：,其中：,空时多用户检测器,使似然函数最大化的过程即可转化为使最大化：,问题实质上是一个多目标参数的组合优化问题，若用Viterbi算法来对其进行对数最大似然估计，则计算复杂度一般为 ，故是一个完备的NP问题。,基于免疫策略的RBF网络,RBF网络的一般结构,1. 根据经验随机地选择固定的中心；2. 根据聚类方法自组织地选取中心；3.有监督地选择中心（广义径向基函数网络）。 以上三种算法中，采用第三类算法训练的RBF网络性能最好，但是由于它采用的是梯度下降算法，其训练过程较长，很容易陷入局部极小。
31、,RBF网络的学习策略,基于免疫策略的RBF网络,疫苗提取算法： 如果隐层节点的个数为M，则随机地从训练数据集中选取M个中心。 根据的不同取值计算隐层节点相应于训练数据集的输出矩阵G根据矩阵方程(Gw = d)， 采用最小二乘法估计RBF网络的输出线性权值矩阵w。 比较取不同的值时，采用上述方法构造的不同RBF网络相应于训练数据集的均方误差。以使得均方误差最小的的取值为中心，在一定范围内重复步骤1和步骤2。,基于免疫策略的RBF网络,基于RBF网络的多用户检测器示意图,http:/,RBF网络的免疫策略学习算法, 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，从而构造
32、出一个个码链（每个码链代表网络的一种权值分布）。 根据经验或针对具体问题的先验知识来大致地确定方差的大致取值范围，以此作为当前问题的免疫疫苗。 对当前群体进行交叉和变异算子操作，产生下一代的准个体。 从当前的群体中随机地选取一定数量的个体进行疫苗注射。 对所产生的网络计算它的误差函数，从而确定其适应度函数值。 根据网络的适应度选择若干个个体作为下一代群体。判断终止条件是否满足：是，则停止运行并将当前最优个体所代表的网络参数作为最终的训练结果；否，则转至第步继续运行。,a. 8用户b. 16用户用户1的信噪比与误码率的关系曲线,基于RBF网络的多用户检测器仿真结果,a. 8用户b. 16用户两用户的能量比与误码率的关系曲线,基于RBF网络的多用户检测器仿真结果,对RBF网络进行训练时的三种算法对比曲线,基于RBF网络的多用户检测器仿真结果,Bye ！,
