免疫计算的主要模型

9.3.1　免疫计算的特性

从计算的角度来看,生物免疫系统是一个高度并、分布、自适应和自组织的系统,具有很强的学习、识别、记忆和特征提取能力[14]。免疫计算具有很强的计算能力,能够对识别匹配、优化、学习、控制、决策和协同等诸多复杂问题进行求解,这都源于免疫计算具有的分布式和并行性、自组织和自适应、全局优化、涌现性和稳健性等优良特性[15]。

(1)分布式和并行性。由于免疫应答机制是通过局部细胞的交互起作用而没有集中控制,所以免疫系统是一个高度分布式系统,不存在单点失效的问题。分布式结构要求诸多个体单元协同完成工作,因而免疫系统的分布式特性同时也蕴涵了免疫系统是一个高度并行的系统。分布式和并行性在提升系统的计算工作效率方面具有良好的借鉴作用。免疫计算采用群体搜索策略,计算任务分布在不同的多个单元上,系统执行并行计算搜索。

(2)自组织和自适应。免疫系统具有自组织的性质,它不需要外部的控制,本身具有自我调节和自组织学习抗原的能力。免疫系统能通过“学习”对新的抗原做出识别和反应,通过免疫细胞的增殖和分化作用,不断地产生新的抗体,最终生成适合的抗体来消灭抗原,从而动态地适应外界环境的变化,并保留对这些抗原特征的记忆。

(3)全局优化性。免疫系统具有多样性特性,包含群体多样性和多样性个体,免疫系统通过多种免疫行为产生多样性抗体以及维持和增加抗体的多样性,例如浓度控制与代谢机制。多样性特性使得免疫计算具备优良的全局优化性,从而能够有效防止过早收敛和避免陷入局部最优。

(4)涌现性。免疫系统的各种行为和特征,包括抗体生成、免疫耐受、自我与非我识别、免疫记忆、免疫系统的进化过程和种群规模的控制及其多样性等都是免疫网络涌现作用的结果[16]。

基于以上特点,免疫系统具备高度稳健性,分布式和并行性,使得免疫系统不会因为局部组织损伤而对其整体功能造成很大影响,而自组织特性使之不需要外部的控制,可以通过自我调节完成免疫功能,实现机体的稳定。全局优化性则使得免疫系统能够应答多种类型的抗原。发源于免疫系统的免疫计算也具有很强的稳健性和涌现性[17]。

9.3.2　免疫计算的主要模型

免疫计算研究在人工免疫入侵检测研究中较为系统,国外有3个代表性的研究团队:美国新墨西哥大学的Forrest、Hofmeyr、Perelson团队,美国孟菲斯大学的Dasgupta团队,英国伦敦大学学院的Kim团队。Perelson,Highttower和Forrest建立了一个简单模型来研究基因库的进化,其中个体的适应度根据其表达的抗体指令系统识别随机选择的抗原的好坏程度来评估[18]。Varela和Stewart发现体细胞变异能加速基因库进化,从而促进抗体多样性,呈现Baldwin效应(学习对进化的间接影响效应)[19]。For-rest、Perelson和Cherukuri提出了常用的检测器生成算法是随机生成算法及其改进算法[20]。基因库一般是通过对被删除的记忆检测器进行高频变异[21]。Dasgupta出版了首部人工免疫系统研究专著,有力地推动了人工免疫系统在计算机科学领域的研究和应用[22]。Kim和Bentley提出了用以描述阴性选择、克隆选择和检测子基因库进化三种免疫机制的应用模型[23]。人工免疫系统和免疫计算的研究主要包含以下几类经典模型。

(1)免疫网络。1974年,N.K.Jerne根据现代免疫学对抗体分子独特型的认识,在克隆选择学说的基础上提出了著名的独特型网络学说(idiotypic networks theory),即免疫网络模型(immune network model)以阐明免疫系统内部对免疫应答的自我调节。从数学的角度,N.K.Jerne为免疫系统模型建立了严格的框架,使用微分方程模拟淋巴细胞的动力学特性。

(2)阴性(或称之为反向、否定)选择算法。S.Forrest等人在1994年提出了阴性选择算法(negative-selection algorithm),原理是免疫系统可以区分自身/非自身细胞。在阴性选择算法中,常见的检测器生成方案有穷举、线性、贪婪、二元模板等算法,而常用的匹配算法有r位连续、r块、海明距离等。

(3)aiNET算法。aiNET的前身是克隆选择算法,克隆选择是用来解释non-self的抗原模式是如何被一个B细胞识别及免疫系统如何反应的理论。在aiNET中,对输入部分(抗原)的识别,将会引起细胞按照克隆选择理论进行增值、变异、选择。

(4)混合结构模型。Grilo提出了混合结构,该模型包含的三个主要部分是:细胞自动执行,人工生命和人工免疫。

(5)人工免疫系统模型。Hart提出了一个用于解决可测量性问题和动态数据的人工免疫系统模型。该模型结合了免疫学记忆和稀疏分布式记忆,类似于自组织体。

(6)多级免疫学习算法。多级免疫学习算法(MILA,Multilevel Immune Learning Algorithm)被作为一种新的算法提出,引入和利用了更多免疫系统的机制,算法以多级、多解的方式进行检测,使得大空间的异常检测应用有较高效率。

免疫复杂系统涉及系统科学、复杂科学、免疫学和计算机技术等多学科,其理论的创新演进是交替演进的,很多研究成果存在交叠,而学者之间也有许多互动,具体见表9.2。

9.3.3　免疫遗传算法

免疫算法是一类新型的遗传算法,可以认为是遗传算法的拓展,是借鉴生物免疫机制所设计的算法,其主要是通过浓度自适应调节过程,使得抗体群落具有适当的多样性,动态抑制浓度高的抗体群,激发浓度低的抗体群转变[11]。免疫算法比较适用于解决非线性和全局最优等问题。为解决种群多样性和收敛性之间的矛盾,学者们将免疫算法和遗传算法融合,提出免疫遗传算法,以弥补单独使用的不足。

免疫遗传算法(IGA,Immune Genetic Algorithm)中的参数设置影响寻优效果,其中交叉概率和变异概率自适应调整是提高算法搜索与收敛的有效途径,但已有的免疫遗传算法缺乏面向多样性和周期的自适应机制,此处根据生物进化的种群多样性分布特点

和周期渐变性,采用基于相似度的自适应交叉和基于多样性的变异函数,在免疫遗传过程中同时引入全局与局部信息,从而避免收敛早熟等问题,使得免疫遗传算法能快速收敛于全局峰值,提高算法的搜索效率。

表9.2　免疫复杂系统重要研究成果演进

1)多样性及浓度

此处以信息熵作为度量抗体之间相似度的指标,设定免疫系统中有N个抗体,单个抗体有M位基因,每位基因存在S个可供选择的符号(如果是二进制0－1式,则S＝2),则N个抗体信息熵(H(N))为:

式中,H i(N)为N个抗体第i位的信息熵,p ij为N个抗体的第i位出现S中某一特定符号的概率。抗体亲和度用于表明两抗体之间的相似度,第v号抗体和第w号抗体之间的相似度为:

H(2)是两个抗体之间的信息熵,H(2)等于0时,表明两抗体所有基因都相同。a v,w取值范围为[0,1]。采用信息熵作为评价抗体群的相似度指标,比采用海明距离更能反映其相似性,并且考虑整体多样性。

抗体浓度用于表示相似的抗体的数量规模,即:

式中,α,β为调节系数,α＜1＜β。由于α＜1＜β,浓度计算取一个范围,使得抗体之间具有Baldwin效应,可以适当地鼓励较优抗体。

2)记忆选择

免疫系统是在抗体空间中通过免疫操作选择具有最优的抗体,免疫选择操作是算法收敛性的保证。抗体v的选择概率(p v)是由亲和度和浓度进行双重控制的,与亲和度呈正向关系,与浓度呈反向关系,即:

一般情况下,选择概率与抗体亲和度呈正关系,而与抗体浓度呈反关系。如此,在保留高亲和度抗体的同时,也确保了抗体群的多样性。将经过选择的抗体存入记忆单元。在进化过程中,当出现亲和度更高的抗体时,则替代记忆单元中亲和度较低的抗体,以更新记忆单元。

3)交叉变异

交叉变异操作对免疫算法的整体性能有着关键作用。当交叉概率和变异概率较大时,新抗体的产生越快,抗体群的多样性越明显,但容易破坏原有的优良基因,概率过大时,则转变成随机搜索。交叉变异概率过小时,不利于产生新抗体,搜索速度缓慢。当抗体群多样性较好时,应减少交叉和变异操作,当多样性较差时,应增加交叉和变异操作。在交叉操作时,为避免多峰之间的交互,破坏收敛方向,通常的操作是设置一个阈值,计算该抗体与最近的峰值的距离,当距离小于该阈值时,则在该抗体群内完成交叉操作[38]。此处以一种更为平滑的方式避免多峰优值之间的交叉,以免破坏寻优效果,而不用设置交叉的距离阈值,是一种自适应的过程。在选择排序之后,两个相邻抗体的交叉概率()为:

其中,t为进化代数,T为总进化代数。当抗体相似度a v,w较大,抗体亲和度a v,a w较大时,增加两个个体的交叉概率,而随着进化代数t增加,减小交叉概率。本算法是对相似度和亲和度的综合考量,能更快地改良与挖掘优势抗体。

此处采用一致变异策略,便于控制整体多样性,变异概率(q m)为:

式中,λ为调节系数。当种群中个体亲和度趋于一致时,即H(N)较小时,适当提高变异概率,有利于跳出局部最优困境。

本算法采用二进制编码方式,其中每个参数是长度为L的二进制位串,表示为m＝(m 1,m 2,…m L)2。m＝0 or 1。所对应的实数值如下。

式中,x为参数,[x max,x min]为取值范围。

免疫遗传算法步骤如下。

Step 1.抗原识别。将目标函数作为抗原识别对象。

Step 2.参数配置和产生初始抗体种群。

Step 3.计算抗体亲和度。将高亲和度的抗体加入到记忆单元,替换低亲和度的抗体。

Step 4.抗体浓度与多样性控制。主要通过计算抗体相似度和信息熵得到抗体浓度,对抗体浓度进行免疫调节。

Step 5.遗传操作。通过选择、交叉、变异对抗体群进行自适应调整,增进抗体的多样性。在交叉和变异算法中融入相似度和种群信息熵。

Step 6.判别终止条件。若达到进化迭代次数或者抗体浓度趋于稳定,则停止计算,输出解;否则,转向step 3。

免疫遗传算法流程如图9.1所示。

图9.1　基于相似性交叉与多样性变异的免疫遗传算法流程图

在免疫遗传算法中,交叉概率的设置可以融入权变因子的考虑,例如决策偏好。两个相邻抗体的交叉概率()可重设为:

对于决策者的偏好是难以量化和描述的,但决策者的心理演变趋势可以归纳为几类基本形式。将偏好趋势理解为针对目标的适应度调整是一种新的思路,对于适应度函数的选择,至少存在五类可能性[39],基本形式如图9.2所示。

图9.2　基于偏好的适应度调整函数

以上包含五类:①边际递减模式,前陡后平g 1;②边际递增模式,前平后陡g 2;③边际增减模式,前平中陡后平g 3;④边际减增模式,前陡中平后陡g 4;⑤边际水平模式,直线正向g 5。在计算测试中,通常采用标准化模式。

此处假设在应用免疫遗传算法求解多目标问题时,决策者意见是对多目标问题解的子向量,而在免疫遗传算法中表示为抗体的亲和度,而在决策者意见综合中有四种交互模式:相互借鉴、兼容并蓄、分散探索、集中突破(如表9.3所示)。

模式一的特点在于当决策组意见接近时,能快速形成一致意见,而当决策组意见不集中时,能分散探索,增加决策群组的多样性。模式二的特点在于当决策组意见集中时,相互借鉴的意义较弱,则交叉概率较低,而当决策组意见分散时,扩大交叉概率,达到相互借鉴的目的。模式一更趋向于“分而治之”中的“治”策略,能对较好的决策快速形成一致性意见;模式二更趋向于“分而治之”中的“分”策略,能集中多样性决策。

表9.3　免疫遗传算法中决策者意见交叉模式