人工免疫系统及其算法综述

基于异构网络环境的人工免疫系统及其算法研究综述摘要：人工免疫作为一种新型的研究领域，有着广泛的应用范围，人工免疫算法的研究也已成为人工智能研究领域的一个重要内容，它突出地体现了现代科学发展的多层次、多学科和多领域的相互渗透、相互交叉和相互促进的特点。因此，将人工免疫系统的原理应用在计算机领域有着重要的理论意义和实际应用价值。本文详细介绍了几种常见的免疫算法机理，并指出了人工免疫系统的研究方向。关键词：人工免疫系统，人工免疫算法1、人工免疫系统介绍1.1人工免疫系统20世纪70年代，Jerne[1,2]首先提出了人工免疫系统的网络假说，并以此开创了独特型网络理论。独特型网络理论为人工免疫系统以后的应用和研究提供了理论指导，并发展成为人工免疫的基础理论之一。Perelson[3]在独特型网络理论的基础上进一步给出了免疫网络的数学框架，从而加快了人工免疫系统在计算机科学方面的发展。1986年，Farmer【4】基于免疫网络的假说，构造了一个免疫系统的动态模型，并提出了一些学习算法的构造思想。此后Forrest又提出了阴性选择算法，他的工作对于人工免疫系统的发展尤其是在信息安全领域应用的发展具有十分重要意义。随后的研究者不断从生物免疫系统中吸取精髓，使之广泛用于优化、数据分析、机器学习、聚类分析、模式识别、故障诊断、机器人控制、自适应控制领域、计算机及网络安全领域等各个应用领域。人工免疫系统主要关注的是用计算和数学模型对免疫学进行模拟，更好地了解免疫系统。人工免疫包括：免疫系统，遗传系统和神经系统。按照目前人们普遍接受的观点，基于免疫系统仿生机理开发的入工免疫系统[9-12]的理论研究主要在集中在人工免疫网络模型和人工免疫算法两个方面。针对人工免疫网络模型的研究多集中在以Jerne的独特性免疫网络为基础的不同模型仿真实验上。而针对人工免疫算法的研究主要是在已有系统模型的基础上，制定一些目的性较强的计算方法或实施策略，主要包括免疫遗传算法、克隆选择算法、阴性选择算法和免疫学习算法等。1.2人工免疫系统处理特性从信息处理的角度上分析，人工免疫系统具有如下特点：（1）多样性：免疫系统抗体库的多样性特征，能及时对不同类型的入侵抗原进行有效的保证和消除。（2）容错性：免疫系统在分类和响应中突发的一些比较小的信息处理错误不会使整个信息处理结果造成严重影响。（3）分布自律性：免疫系统没有集中控制系统，它是由许多局部的并且相互作用的基本信息单元联合起来达到对全局的保护。（4）动态稳定性：免疫系统要消除各种外来的不断变化的入侵抗原，并保持整个系统的稳定。（5）自适应鲁棒性：免疫系统具有非常强的自我学习能力，并且通过此学习使其成为能够随环境不断变化而不断改变和完善的一个自适应型的鲁棒进化系统。2、免疫算法[6-8]介绍人工免疫系统是借鉴免疫系统机理特点和功能的智能系统，具有广泛的应用和理论基础。在此着重阐述免疫算法的研究和AIS的应用研究。2.1免疫遗传算法为了使遗传算法在个体多样性和群体收敛性之间取得平衡，并克服遗传算法的缺点，在遗传算法中加入免疫的思想，即在遗传算法中加入免疫算子，使遗传算法变成具有免疫功能的新算法，称之为免疫遗传算法(ImmuneGeneticAlgorithm，简称IGA)。增加免疫算子可以提高遗传算法的整体性能，并使其有选择、有目的的利用特征信息来抑制优化过程中的退化现象。免疫算子包括三种操作：提取疫苗、接种疫苗和免疫选择。提取疫苗：对所求解的问题进行具体分析，从中提取出最基本的特征信息。接种疫苗：给个体接种疫苗是指按照先验知识来修改个体的某些基因位上的基因，使所得个体以较大的概率具有更高的适应度。免疫疫苗是从对问题的先验知识中提炼出来的，它所包含的信息量对算法的性能起着重要的作用。免疫选择：对接种了疫苗的个体进行检测，若其适应度不如父代，说明在交叉、变异的过程中出现了严重的退化现象，这时该个体将被父代中所对应的个体所替代；如果子代适应度优于父代，则在目前的子代群体中以一定的概率选择被接种的个体迸入新的父代群体。该算法的实现步骤：（1）抗原识别。输入待求解的目标函数作为抗原。（2）产生初始抗体。将待优化参数的组合作为抗体。根据对象先验知识，将问题的初始解作为初始记忆细胞，与随机产生的抗体共同构成初始种群A1。（3）根据先验知识抽取疫苗。（4）计算亲和力。计算抗原和抗体的亲和力和每个抗体之间的亲和力。（5）更新记忆细胞。将初始种群按抗原和抗体的亲和力的降序排列，将高抗原亲和力的抗体加入到记忆细胞取代记忆细胞中与其亲和力最高的原有抗体。若当前群体中包含最佳个体，则算法停止运行并输出结果；否则继续。（6）对抗体种群中经过选择的抗体进行交叉和变异操作得到新种群B。（7）对种群B进行接种疫苗操作，产生种群C。（8）对种群C进行免疫选择操作，得到新抗体Ak,转到步骤（4）。（9）免疫遗传算法的流程图如图所示。抗原识别产生初始抗体计算亲和力终止条件是否满足更新记忆细胞交叉、变异产生新抗体结束是否提取疫苗接种疫苗免疫选择免疫算子图1免疫遗传算法流程图2.2克隆选择算法Castro【5】基于克隆选择理论提出了克隆选择算法,要依据最优解，根据亲和度的大小选择克隆，进行增值和变异，提高搜索范围，加快收敛速度。这是一种模拟免疫系统的学习过程的进化算法。其基本要点为:（1）随机产生初始群体P,包括记忆群体M和剩余群体Pr。（2）计算亲和度,并根据其大小从P中选择n个最佳个体Tn。（3）克隆这n个最佳个体，产生一个暂时的克隆群体C，克隆的规模随亲和度的大小而改变。（4）克隆后的个体按突变概率产生突变，突变概率与抗体的亲和度成正比/反比。（5）在新产生的群体C*中重新选择一些好的个体构成记忆群体。被克隆的母体中的一些个体被新群体中的其他好于母体的个体取代。记忆单元M保留种群Pr初始种群P亲和力计算最佳个体群Tn克隆群C变异新抗体种群C*重新选择插入新个体图2克隆选择算法2.3人工免疫算法人工免疫算法【13-18】是一种受生物免疫系统启发而设计的新型智能优化算法。它将抗原和抗体分别对应于优化问题的目标函数和可行解。把抗体和抗原的亲和力视为可行解与目标函数的匹配程度。用抗体之间的亲和力保证可行解的多样性，通过计算抗体期望生存率来促进较优抗体的遗传和变异，用记忆细胞单元保存择优后的可行解来抑制相似可行解的继续产生并加速搜索到全局最优解，同时，当相似问题再次出现时，能较快产生适应该问题的较优解甚至最优解。人工免疫算法基本步骤如下：（1）输入问题的目标函数和约束条件，作为人工免疫算法的抗原。（2）确定抗体的编码方式，人工免疫算法的抗体可以用字符串表示。（3）产生初始抗体集，通常可以在解空间中随机产生N个候选解作为初始抗体，N为抗体群中的抗体数目。（4）计算亲和力。构造抗体的亲和力函数f(B),f(B）越大说明抗体B和抗原G之间的匹配越好。（5）计算排斥力。构造抗体与抗体之间的排斥力函数f(B1,B2),此函数越大说明抗体B1和抗体B2之间的差距越大。计算抗体群中所有抗体与当前抗体群中最好抗体之间的排斥力。（6）产生新的抗体。构造人工免疫算子，抗体通过人工免疫算子的作用产生新的抗体。（7）计算新抗体的亲和力。若新抗体中有与抗原匹配的抗体，或已满足预定的停机条件则停机，否则转下一步。（8）抗体选择。按照“优胜劣汰”的自然选择机制，在原有的N个有效抗体和新产生的若干个抗体中选择出N个与抗原匹配得较好的抗体构成新的抗体群，转（6）。在进行选择操作时，应依据抗体之间的排斥力限制进入新抗体群中的相同抗体数目，以保持抗体群中抗体的多样性增强抗体群的免疫力，防止算法收敛于局部优解。产生新的抗体抗原输入抗体编码产生初始抗体集计算亲和力和排斥力计算新的抗体亲和力和排斥力结束抗体选择YN图3人工免疫算法的流程图2.4免疫系统与一般免疫算法比较表1免疫系统与免疫算法比较免疫系统免疫算法抗原要解决的问题抗体最佳解向量抗原识别问题识别从记忆细胞产生抗体联想过去的成功解细胞抑制剩余候选解的消除抗体克隆利用遗传算法产生新抗体3、人工免疫算法在网络性能优化上的应用人工免疫算法来优化网络的吞吐量，将异构网络的吞吐量作为人工免疫算法的目标函数，无线网络的信道容量表达式即香农公式作为抗体是否最优的亲和度评估函数。用人工免疫算法来得到异构网络吞吐量最大往返时延参数rtt和丢包率最优组合，使最大的吞吐量能够逼近无线信道的容量。通过对两个参数进行二进制联合编码；通过克隆选择机制、突变机制及亲和度评估等来获得吞吐量最高时参数的最佳组合，基本步骤如下：（1）异构网络环境：典型的哑铃拓扑；发送端A，B和节点C位于有线链路中，基站AP与接收端之间为一段存在差错的无线链路，拓扑结构如下：图1异构网络拓扑（2）编码机制：对rtt和丢包率进行二进制联合编码；两个参数均有各自的变化范围；将这些范围均分成n个区间；再将这些区间量化成整数；编码的长度是这两个参数编码长度之和；并表示为一种可能的参数组合方案；（3）克隆机制：采用文献[21]中的自适应克隆操作即亲和度高的抗体克隆规模较大。（4）变异机制：对克隆后的临时种群进行突变，采用文献[20]中的自适应变异概率。因为该变异概率自适应于种群的亲和度或进化代数，能够提高算法的收敛速度，具有快速找到最优解的能力。高于种群平均亲和度的候选解（参数抗体），随着亲和度的增加，变异概率减小；低于种群平均亲和度的抗体，变异概率较大。（5）抗体的选择机制：用子代中亲和度高的抗体代替父代中亲和度低的抗体，以保证最终得到的参数（候选解）均最优；计算当前抗体群中适应度值相近的抗体浓度，浓度高的减小该个体的选择概率-抑制；浓度低的增加该个体的选择概率-促进，以此保持种群中个体的多样性。防止种群早熟收敛。（6）亲和度评估：用吞吐量作为亲和度评估函数时，亲和度越高，吞吐量越大。4、人工免疫系统的进一步研究方向本文从免疫系统特性出发，引入了人工免疫工程AIE的概念，讨论了AIE的发展及免疫算法。虽然AIE的研究应用已获得了一定的积极的成果，但AIE研究仍处于起步阶段，理论和应用研究还有许多亟待完善之处，从总体上看，今后的研究应致力于如下几个方面：首先要加深基础理论研究，由于缺乏有力的理论指导，使得目前对AIS的研究仅仅局限于对生态免疫系统某一机理的仿真和应用，对它的稳定性和动力学分析还未涉及。以后的研究在进一步理解生物免疫系统的基础上，将把有关免疫系统的潜在有用的特性整合到一个整体的框架上。其次要加强AIS与其它生物信息处理技术（神经网络、进化计算等）的结合，重点在免疫的分布性、鲁棒性、自适应性及容错性等方面的应用研究，如：分布式故障检测、分布式反馈控制、数据挖掘等。总之，AIS的研究只是刚刚起步，但随着它的进一步深入研究并与其他智能方法的融合，必将为智能优化、智能控制、模式识别、计算机安全等领域的研究提供新的强有力的工具。参考文献[1]JerneNK.Theimmunesystem.ScientificAmerican,1973，229(1)：51-60[2]JerneNK.Towardsanetworktheoryoftheimmunesystem,AnnualImmunology,1974,125C：373389[3]PerelsonA.Immunenetworktheory.ImmunologicalReview，l989，1l0：5-36[4]FarmerJD.PackardNH．PerelsonAS.Theimmunesystem.adaptation,andmachinelearning.PhysicaD,1986,22：187-204[5]DeCastro.L.C，VonZubenF．J．TheClonalSelectionAlgorithmwithEngineeringApplication[J].submitttoCECCO’00,2000.61[6]李金城，张国忠等.免疫算法研究.沈阳航空工业学院学报，Vol.22No.5,2005[7]葛红.免疫算法综述[J].华南师范大