第十二章 模拟退火算法与人工免疫算法简介 .ppt

1、第十二章第十二章 模拟退火算法与人工与人工免疫算法简介免疫算法简介 本章对目前常用的几种智能优化计算算法作简单介绍，以使读者对它们有个基本认识。内容包括神经网络、遗传算法、模拟退火算法和神经网络混合优化学习策略。12.1 模拟退火算法 模拟退火算法(simulated annealing,简称SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法 模拟退火算法在某一初温下，伴随温度参数的

2、不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。模拟退火算法12.1.1 物理退火过程和Metropolis准则简单而言，物理退火过程由以下三部分组成：加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。模拟退火算法等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状

3、态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。模拟退火算法Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为 ，若 则接受新状态j为当前状态；否则，若概率 大于 区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为Boltzmann常数。jiEE 和ijEE/)(expktEEpijr)1,0 模拟退火算法这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态

4、，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。模拟退火算法12.1.2 模拟退火算法的基本思想和步骤1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全

5、局最优解。模拟退火算法标准模拟退火算法的一般步骤可描述如下：给定初温 ，随机产生初始状态 ，令 ；Repeat:Repeat 产生新状态 ；0tt 0ss 0k)(sGenetesjjjssrandomsCsCif 1,0)()(exp,1min 模拟退火算法 Until 抽样稳定准则满足；退温 ，并令 ；Until 算法终止准则满足；输出算法搜索结果。)(1kktupdatet1 kk模拟退火算法12.1.3 模拟退火算法关键参数和操作的设定从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的

6、优化性能。此外，初温的选择对SA算法性能也有很大影响。模拟退火算法状态产生函数设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。模拟退火算法状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；模拟退火算法随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引入是SA算法实现

7、全局搜索的最关键的因素，SA算法中通常采用min1,exp(-C/t)作为状态接受函数。模拟退火算法初温初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：模拟退火算法均匀抽样一组状态，以各状态目标值的方差为初温。随机产生一组状态，确定两两状态间的最大目标值差 ，然后依据差值，利用一定的函数确定初温。譬如 ,其中 为初始接受概率利用经验公式给出。|maxrptln/0rp模拟退火算法温度更新函数温度更新函数

8、，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。模拟退火算法内循环终止准则内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。模拟退火算法而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样。模拟退火算法外

9、循环终止准则外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：模拟退火算法设置终止温度的阈值；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；检验系统熵是否稳定。12.1.4 神经网络权值的混合优化学习策略 鉴于GA、SA的全局优化特性和通用性，即优化过程无需导数信息，我们可以基于实数编码构造BPSA、BPGA混合优化学习策略，以提高前向网络学习的速度、精度，特别是避免陷入局部极小的能力。12.1.4 神经网络权值的混合优化学习策略4.1 BPSA混合学习策略在BPSA混合学习策

10、略中，采用以BP为主框架，并在学习过程中引入SA策略。这样做，既利用了基于梯度下降的有指导学习来提高局部搜索性能，也利用了SA的概率突跳性来实现最终的全局收敛，从而可提高学习速度和精度。BP-SA混合学习策略的算法步骤如下：神经网络权值的混合优化学习策略 随机产生初始权值 ，确定初温 ，令 利用BP计算 。利用SA进行搜索：利用SA状态产生函数产生新权值 ，其中 为随机扰动。)0(1t1k)(k)(k)()(kk)1,1(神经网络权值的混合优化学习策略 计算 的目标函数值与 的目标函数值之差 。计算接受概率 。若 ，则取 ；否则 保持不变。)(k)(kC)/exp(,1minkrtCP)1,0

11、randomPr)()(kk)(k神经网络权值的混合优化学习策略(4)利用退温函数 进行退温，其中 为退温速率。若 对应的目标函数满足要求精度 ，则终止算法并输出结果；否则，令 ，转步骤。kkvtt1)1,0(v)(k1 kk神经网络权值的混合优化学习策略 4.2 BPGA混合学习策略神经网络的连接权包含着神经网络系统的全部知识。反向传播的BP神经网络(back propagation network)的学习算法是基于梯度下降的，因而具有以下缺点：网络训练速度慢、容易陷入局部极小值、全局搜索能力差等。而遗传算法的搜索遍及整个解空间，因此容易得到全局最优解，而且遗传算法不要求目标函数连续、可微，

12、甚至不要求目标函数有显函数的形式，只要求问题可计算。神经网络权值的混合优化学习策略因此，将擅长全局搜索的遗传算法和局部寻优能力较强的BP算法结合起来，可以避免陷入局部极小值，提高算法收敛速度，很快找到问题的全局最优解。BP算法和遗传算法结合训练神经网络权重的主要步骤为：神经网络权值的混合优化学习策略(1)以神经网络节点之间的连接权重和节点的阈值为参数，采用实数编码。采用三层神经网络，设输入节点数为p，输出节点数为q，隐层节点数为r，则编码长度n为：（10-4-1）qrrpn)1()1(神经网络权值的混合优化学习策略 (2)设定神经网络节点连接权重的取值范围 ,产生相应范围的均匀分布随机数赋给基

13、因值，产生初始群体；(3)对群体中个体进行评价。将个体解码赋值给相应的连接权(包括节点阈值)，引入学习样本计算出学习误差E，个体的适应度定义为：.（10-4-2）Ef11,maxminxx神经网络权值的混合优化学习策略(4)对群体中的个体执行遗传操作：选择操作。采用比例选择算子，若群体规模为M，则适应度为的个体被选中进入下一代的概率为：.（10-4-3）Miiiiffp1神经网络权值的混合优化学习策略 交叉操作。由于采用实数编码，故选择算术交叉算子。父代中的个体 和 以交叉概率 进行交叉操作，可产生的子代个体为：（10-4-4）和 （10-4-5）其中a为参数 。1X2Xcp211)1(Xaa

14、XX212)1(aXXaX)1,0(a神经网络权值的混合优化学习策略 变异操作。采用均匀变异算子。个体 的各个基因位以变异概率 发生变异，即按概率用 区间中的均匀分布随机数代替原有值。引入最优保留策略。iXmp,maxminxx神经网络权值的混合优化学习策略 判断满足遗传算法操作终止条件否？不满足则转步骤。否则转步骤。将遗传算法搜索的最优个体解码，赋值给神经网络权重(包括节点阈值)，继续采用BP算法优化神经网络的权重和阈值。神经网络权值的混合优化学习策略4.3 GASA混合学习策略采用三层前馈网络，GA和SA结合训练神经网络权重的步骤如下：给定模拟退火初温 ，令 ；以神经网络节点之间的连接权重

15、和节点的阈值为参数，采用实数编码。采用三层神经网络，设输入节点数为p，输出节点数为q，隐层节点数为r，则编码长度n为：0t1k神经网络权值的混合优化学习策略 （10-4-6）设 定 神 经 网 络 节 点 连 接 权 重 的 取 值 范围 ，产生相应范围的均匀分布随机数赋给基因值，产生初始群体；对群体中个体进行评价。将个体解码赋值给相应的连接权(包括节点阈值)，引入学习样本计算出学习误差E，个体的适应度定义为：.（10-4-7）qrrpn)1()1(,maxminxxEf11神经网络权值的混合优化学习策略 对群体中的个体执行遗传操作：选择操作。采用比例选择算子，若群体规模为M，则适应度为 的个

16、体 被选中进入下一代的概率为：.（10-4-8）ifiXMiiiiffp1神经网络权值的混合优化学习策略 交叉操作。由于采用实数编码，故选择算术交叉算子。父代中的个体 和 以交叉概率 进行交叉操作，可产生的子代个体为：（10-4-9）和 （10-4-10）其中a为参数 。1X2Xcp211)1(XaaXX212)1(aXXaX)1,0(a神经网络权值的混合优化学习策略 变异操作。采用均匀变异算子。个体 的各个基因位以变异概率 发生变异，即按概率 用区间 中的均匀分布随机数代替原有值。引入最优保留策略。对群体中每一个个体引入模拟退火操作：iXmpmp,maxminxx神经网络权值的混合优化学习策

17、略 利 用 S A 状 态 产 生 函 数 产 生 新 基 因值 ，其中 为随机扰动。计算 的目标函数值与 的目标函数值之差 。计算接受概率 。)(kg)()(kgkg)1,1()(kg)(kgC)/exp(,1minkrtCP神经网络权值的混合优化学习策略 若 ，则取 ；否则 保持不变。引入最优保留策略。利用退温函数 进行退温，其中 为退温速率。)1,0randomPr)()(kgkg)(kgkkvtt1)1,0(v神经网络权值的混合优化学习策略 判断满足遗传算法操作终止条件否？不满足则转步骤。否则转步骤。将遗传算法搜索的最优个体解码，赋值给神经网络权重(包括节点阈值)。二、人工免疫系统二、

18、人工免疫系统引言12免疫算法3典型的人工免疫系统ARTIS4基本免疫方法引言n人工免疫系统作为人工智能领域的重要分支，人工免疫系统作为人工智能领域的重要分支，同神经网络及遗传算法一样也是智能信息处同神经网络及遗传算法一样也是智能信息处理的重要手段，已经受到越来越多的关注。理的重要手段，已经受到越来越多的关注。n它通过类似于生物免疫系统的机能，构造具它通过类似于生物免疫系统的机能，构造具有动态性和自适应性的信息防御体系，以此有动态性和自适应性的信息防御体系，以此来抵制外部无用、有害信息的侵入，从而保来抵制外部无用、有害信息的侵入，从而保证接受信息的有效性与无害性。证接受信息的有效性与无害性。背景

19、O在生物科学领域，人们对进化、遗传和免疫等自然在生物科学领域，人们对进化、遗传和免疫等自然 现象现象已经进行了广泛而深入的研究已经进行了广泛而深入的研究；O进化算法是建立在模仿生物遗传与自然选择基础上的一进化算法是建立在模仿生物遗传与自然选择基础上的一种并行优化算法，其性能优异、应用广泛；种并行优化算法，其性能优异、应用广泛；O进化算子在为每个个体提供了进化机会的同时，也无可进化算子在为每个个体提供了进化机会的同时，也无可避免地产生了退化的可能；避免地产生了退化的可能；O大多数待求问题有可以利用的先验知识或特征信息，故大多数待求问题有可以利用的先验知识或特征信息，故可以利用这些信息来抑制进化过

20、程中的退化现象；可以利用这些信息来抑制进化过程中的退化现象；O生物免疫理论为改进原有算法的性能，建立集进化与免生物免疫理论为改进原有算法的性能，建立集进化与免疫机制于一体的新型全局并行算法奠定了基础疫机制于一体的新型全局并行算法奠定了基础。一门新兴的研究领域一门新兴的研究领域nFarmer等人在等人在1986年首先在工程领域年首先在工程领域提出提出免疫免疫概念概念；nVarela等人受免疫网络学说的启发，提等人受免疫网络学说的启发，提出并进而完善免疫网络模型。出并进而完善免疫网络模型。人工免疫网络模型人工免疫网络模型n独特型免疫网络（独特型免疫网络（Jerne）；）；n互联耦合免疫网络（互联耦

21、合免疫网络（Ishiguro）；）；n免疫反应网络（免疫反应网络（Mitsumoto）；）；n对称网络（对称网络（Hoffmann）；）；n多值免疫网络（多值免疫网络（Tang）.免疫学习算法免疫学习算法n反面选择算法（反面选择算法（Forrest）；）；n免疫学习算法（免疫学习算法（Hunt&Cooke）；）；n免疫遗传算法（免疫遗传算法（Chun）；）；n免疫免疫Agent算法（算法（Ishida）；）；n免疫网络调节算法（免疫网络调节算法（Wang&Cao）；）；n免疫进化算法（免疫进化算法（Jiao&Wang）国际研究n1996年，日本，基于免疫性系统的国际年，日本，基于免疫性系统的国

22、际专题讨论会，提出并确认专题讨论会，提出并确认人工免疫系统人工免疫系统（AIS）的概念的概念；n1997年，年，IEEE的的SMC组织专门成立了组织专门成立了人工免疫系统及应用人工免疫系统及应用的分会组织；的分会组织；n目前，几乎所有有关人工智能领域的学术目前，几乎所有有关人工智能领域的学术会议都收录会议都收录AIS方面的论文。方面的论文。应用 自动控制 故障诊断 模式识别 图象识别 优化设计 机器学习 网络安全AIS在控制领域中的应用nPID型免疫反馈控制器（型免疫反馈控制器（Takahashi）；）；n机器人控制（机器人控制（Mitsumoto,Ishiguro,Lee）；）；n控制系统的

23、设计（控制系统的设计（Ishida）；）；n复杂动态行为建模和自适应控制复杂动态行为建模和自适应控制（Kumak）；）；n倒摆的控制（倒摆的控制（Bersini）。）。AIS在故障诊断中的应用n基于相关识别特性的免疫网络模型用于故基于相关识别特性的免疫网络模型用于故障诊断的方法（障诊断的方法（Ishida）；）；n通过构造大规模独特型免疫网络来建立用通过构造大规模独特型免疫网络来建立用于在线服务的故障诊断系统于在线服务的故障诊断系统（Ishiguru）。）。AIS在模式识别中的应用Hunt等人开发了一种具有学习能力的人工等人开发了一种具有学习能力的人工免疫系统并用于模式识别。免疫系统并用于模式

24、识别。AIS在联想记忆中的应用Gilbert等人采用免疫网络模型设计了一种等人采用免疫网络模型设计了一种内容可访的自动联想记忆系统并用于图像内容可访的自动联想记忆系统并用于图像识别。识别。AIS在优化设计中的应用n永磁同步电动机的参数修正的优化设计；永磁同步电动机的参数修正的优化设计；n电磁设备的外形优化；电磁设备的外形优化；nVLSI印刷线路板的布线优化设计；印刷线路板的布线优化设计；n函数测试；函数测试；n旅行商问题的求解；旅行商问题的求解；n约束搜索优化问题和多判据设计问题约束搜索优化问题和多判据设计问题；AIS在网络安全的应用n数据检测（数据检测（Forrest）；）；n病毒检测（病毒

25、检测（Kephart）；）；nUNIX过程监控过程监控（Forrest）。国际研究新动向之一 以开发新型的智能系统方法为背景，研究基于生物免疫系统机理的智能系统理论和技术，同时将AIS与模糊系统、神经网络和遗传算法等软计算技术进行集成，并给出其应用方法。国际研究新动向之二 基于最新发展的免疫网络学说进一步建立并完善模糊、神经和其它一些专有类型的人工免疫网络模型及其应用方法。国际研究新动向之三 将人工免疫系统与遗传系统的机理相互结合，并归纳出各种免疫学习算法。比如：免疫系统的多样性遗传机理和细胞选择机理可用于改善原遗传算法中对局部搜索问题不是很有效的情况；独特型网络机理可用于免疫系统中的遗传部分

26、以避免系统出现早熟现象；发展用于处理受约束的遗传搜索和多准则问题的免疫学习算法等。国际研究新动向之四 基于免疫反馈和学习机理，设计自调整、自组织和自学习的免疫反馈控制器。展开对基于免疫反馈机理的控制系统的设计方法和应用研究，这有可能成为工程领域中种新型的智能控制系统，具有重要的理论意义与广泛的应用前景。国际研究新动向之五 进一步研究基于免疫系统机理的分布式自治系统。分布式免疫自治系统在智能计算、系统科学和经济领域将会有广阔的应用前景。国际研究新动向之六 发展基于DNA编码的人工免疫系统以及基于DNA计算的免疫算法。尝试将DNA计算模型引入人工免疫系统中，研究一种基于DNA计算与AIS相结合的，

27、有较强抗干扰能力和稳定性能的智能系统国际研究新动向之七 近年来有学者已开始研究B细胞抗体网络的振荡、混浊和稳态等非线性特性，不过其工作才刚刚开始。人们应进一步借助非线性的研究方法来研究免疫系统的非线性行为，拓宽非线性科学的研究范围。国际研究新动向之八 进一步发展AIS在科学和工程上的应用，并研制实际产品，如研制在复杂系统的协调控制、故障检测和诊断、机器监控、签名确认、噪声检测、计算机与网络数据的安全性、图像与模式识别等方面的实际产品。生物免疫的启示n在生物自然界中，免疫现象普遍存在，并对物种在生物自然界中，免疫现象普遍存在，并对物种的的 生存与繁衍生存与繁衍 发挥着重要的作用；发挥着重要的作用

28、；n生物的免疫功能主要是由参与免疫反应的细胞或生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的；由其构成的器官来完成的；n生物免疫主要有两种类型：生物免疫主要有两种类型：特异性免疫特异性免疫（Specific Immunity），），非非特异性免疫反应特异性免疫反应（Nonspecific Immunity）；）；n生物免疫系统是通过自我识别、相互刺激与制约生物免疫系统是通过自我识别、相互刺激与制约而构成了一个而构成了一个 动态平衡的网络结构动态平衡的网络结构。免疫生物学的基本概念抗原是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异

29、性反应的物质。抗体是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。免疫系统的主要功能OO 免疫防御即机体防御病原微生物的感染；OO 免疫（自身）稳定即机体通过免疫功能经常消除那些损伤和衰老的细胞以维持机体的生理平衡；OO 免疫监视即机体通过免疫功能防止或消除体内细胞在新陈代谢过程中发生突变的和异常的细胞大于阈值spam记忆细胞检测器亲和力计算不大于阈值大于阈值不大于阈值亲和力计算正文特征提取用户反馈未成熟细胞检测器hamspam特征库随机特征项检测到spam？删除该未成熟检测器克隆记忆YN用户反馈更新检测器、spam特征库基本免疫方

30、法n1.免疫识别n2.免疫学习n3.免疫记忆n4.克隆选择免疫识别n免疫识别是免疫系统的主要功能，同时也是AIS的核心之一，而识别的本质是区分“自我”和“非我”。n核心机制是根据识别的对象特征进行编码，定义一个自我集合并随机产生一系列检测器，用于检测自我集合的变化。根据阴性选择原理，若检测集合与自我集合匹配，则完成匹配任务，机体发现病变。基本免疫方法n(1)定义自己(self)为一个字符串集合S，每个字符串由n个字母组成，字符串可以是一个网络数据包，电子邮件特征向量电子邮件特征向量或程序的一般行为模式。n(2)产生一个初始监测器集合R。n(3)监测器集合中每个监测器经历阴性选择过程。其中每一个

31、监测器都不能与集合S中的任何一个字符串相匹配，否则就从监测器集合中删去对应的检测器。n(4)通过与R集合的匹配匹配不断监测S的变化，一旦发生任何匹配，则说明S集发生了变化，即有外来抗原侵入。基本免疫方法n在最初的算法描述中，候选的监测器是随机产生的，然后测试以删除与自身字串相匹配的监测器，算法中采用的匹配规则是r-连续位匹配连续位匹配，即当两个字符串至少存在连续r位相同是才发生匹配。n该过程重复进行，直到所需数量的监测器所需数量的监测器被产生出来。通常用概率分析方法概率分析方法来估算为了满足一定的可靠性所应有的监测器的数目。基本免疫方法免疫学习 n免疫识别过程同时也是一个学习的过程，学习的结果

32、是免疫细胞的个体亲和度提高、群体规模扩大，并且最优个体以免疫记忆的形式得到保存。n当机体重复遇到同一抗原时，由于免疫记忆机制的作用，免疫系统对该抗原的应答速度大大提高，并且产生高亲和度的抗体去除病原，这个过程是一个增强式学习过程。而且可以对结构类似的抗原进行识别而且可以对结构类似的抗原进行识别。基本免疫方法n免疫学习一般有以下几种途径:n(a)对同一抗原进行重复学习，属于增强式学习。n(b)亲合度成熟，对应于AIS中的个体经遗传操作后其亲合度逐步提高的过程，属于遗传学习。n(c)低度的重复感染，对应于AIS的重复训练过程。n(d)对内生和外生抗原的交叉应答，属于联想式学习，对应于联想记忆机制。

33、基本免疫方法免疫记忆 n当免疫系统初次遇到一种抗原时，淋巴细胞需要一定的时间进行调整以更好地识别抗原，并在识别结束后以最优抗体的形式以最优抗体的形式保留对该抗原的记忆信息保留对该抗原的记忆信息。而当免疫系统再次遇到相同或者结构相似的抗原时，在联想记忆的作用下，其应答速度将大大提高。n免疫记忆主要体现在再次免疫应答和交叉免疫应答时，可以大大加速优化搜索过程，加快学习进程并提高学习质量。基本免疫方法克隆选择 n克隆选择原理最先由Jerne提出，后由Burnet给予完整阐述。其大致内容为:当淋巴细胞实现对抗原的识别(即抗体和抗原的亲和度超过一定阈值)后，B细胞被激活并增殖复制产生B细胞克隆，随后克隆

34、细胞经历变异过程，产生对抗原具有特异性的抗体。克隆选择理论描述了获得性免疫的基本特性，并且声明只有成功识别抗原的免疫细胞才得以增殖。经历变异后的免变异后的免疫细胞分化为效应细胞疫细胞分化为效应细胞(抗体抗体)和记忆细胞和记忆细胞两种两种。基本免疫方法n克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖，随后通过遗传变异分化为多样性抗体细胞和记忆细胞。n克隆选择对应着一个亲和度成熟的过程，即对抗原亲和度较低的个体对抗原亲和度较低的个体在克隆选择机制的作用下，经历增殖复制和变异操作后，其亲和度逐步提高而亲和度逐步提高而“成熟成熟”的过程。因此亲和度成熟本质上是一个达尔文式的选择和变异的过程，克隆

35、选择原理通过采用交叉、变异等遗传算子和相应的群体控制交叉、变异等遗传算子和相应的群体控制机制机制实现。基本免疫方法免疫算法 n一般的免疫算法可分为三种情况:n模仿免疫系统抗体与抗原识别，结合抗体产生过程而抽象出来的免疫算法;n基于免疫系统中的其他特殊机制抽象出的算法，例如克隆选择算法;n与遗传算法等其他计算智能融合产生的新算法，例如免疫遗传算法。免疫算法的一般步骤 初始抗体生成抗原识别抗体促进和抑制满足终止条件？群体更新结束亲和力计算记忆细胞分化YN免疫算法n(1)识别抗原：免疫系统确认抗原入侵。n(2)产生初始抗体群体：激活记忆细胞产生抗体，清除以前出现过的抗原，从包含最优抗体(最优解)的数

36、据库中选择出来一些抗体。n(3)计算亲和力：计算抗体和抗原之间的亲和力。n(4)记忆细胞分化：与抗原有最大亲和力的抗体加给记忆细胞。由于记忆细胞数目有限，新产生的与抗原具有更高亲和力的抗体替换较低亲和力的抗体。n(5)抗体促进和抑制：高亲和力抗体受到促进，高密度抗体受到抑制。通常通过计算抗体存活的期望值来实施。n(6)抗体产生:对未知抗原的响应，产生新淋巴细胞免疫算法阴性选择算法nProcedurenBeginn随机生成大量的候选检测器(即免疫细胞)/*初始化*/nWhile一个给定大小的检测器集合还没有被产生do/*耐受*/nBeginn计算出每一个自体元素和一个候选检测器之间的亲和力;nI

37、f这个候选的检测器识别出了自体集合中的任何一个元素Then这个检测器就要被消除掉;nElse把这个检测器放入检测器集合里面;/*该检测器成熟*/n利用经过耐受的检测器集合，检测系统以找出变种;nEnd;nEnd.常见免疫算法克隆选择算法nBeginn随机生成一个属性串(免疫细胞)的群体nWhile收敛标准没有满足donBeginnWhile not所有抗原搜索完毕do;*/初始化*/nBeginn选择那些与抗原具有更高亲和力的细胞;*/选择*/n生成免疫细胞的副本:越高亲和力的细胞拥有更多的副本;*/再生*/n根据它们的亲和力进行变异:亲和力越高，变异越小;*/遗传变异*/nEnd.End.E

38、nd.免疫算法免疫遗传算法n随机创建抗体和抗原的群体;n抗体和抗原匹配;n根据抗体的亲和力对抗体做评价;n用标准遗传算法进化抗体。n这个模型使免疫系统能够通过学习，知道哪些抗体对抗原的识别有帮助。常见免疫算法免疫系统与一般免疫算法之间的比较免疫系统免疫算法抗原要解决的问题抗体最佳解向量抗原识别问题识别从记忆细胞产生抗体联想过去的成功淋巴细胞分化优良解(记忆)的保持细胞抑制剩余候选解的消除免疫算法免疫算法中的亲和力计算方法 n免疫算法中最复杂的计算免疫算法中最复杂的计算是亲和力计算。由于产生于确定克隆类型的抗体分子独特型是一样的，抗原与抗体的亲和力也是抗体与抗体的亲和力的测量。n一般计算亲和力的

39、公式:n其中，tk是抗原和抗体k的结合强度。常见免疫算法n一般免疫算法计算结合强度计算结合强度tk的数学工具主要有:n(1)海明空间的海明距离n(2)Euclidena形态空间的 Euclidean距离n(3)Manhattan形态空间的 Manhattan距离免疫算法抗体抗原的编码方式 n目前一般免疫算法种抗体抗原，即解和问题的编码方式主要有二进制编码、实数编码和字符编码三种。n其中，二进制编码因简单而得到广泛使用。编码后亲和力的计算一般是比较抗体抗原字符串之间的异同，根据上述亲和力计算方法计算。免疫算法典型的人工免疫系统模型ARTISnARTIS(ARTificial Immune System)是Hofmeyr提出的一种分布式人工免疫系统模型，它具有多样性、分布性、错误耐受、动态学习、自适应性、自我监测等特性，可应用于各种工程领域。nARTIS的免疫细胞生命周期理论对基于免疫的反垃圾邮件技术具有积极的启迪作用。nARTIS模型是一个分布式系统，它由一系列模拟淋巴结的节点构成，每个节点由多个检测器组成。各个节点都可以独立完成免疫功能。模型涉及的免疫机制包括识别、抗体多样性、调节、自体耐受、协同刺激等。n在ARTIS中，用固定长度的二进制串构成的有限集合U来表示蛋白质链。U可以分为两个子集：N表示非自体，S表示自体，满足U=NS且 NS=。ARTIS