分布式人工免疫系统的鲁棒性归约模型

龚  涛^{1, 2}，蔡自兴¹，夏  洁¹，江中央¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083;

2. 东华大学 信息科学与技术学院，上海，201620)

摘  要：利用分布式多真体 (Agent) 系统的鲁棒性归约模型，将分布式人工免疫系统看作理想的分布式多真体系统，从而把分布式人工免疫系统的鲁棒性分析问题归约为其各个相对独立的模块的鲁棒性分析问题。人工免疫系统包括正常模型建模模块、自体/异体检测模块、已知异体识别模块、未知异体学习模块、异体消除模块和受损系统修复模块。用问题归约法分析人工免疫系统的鲁棒性后，建立人工免疫系统的鲁棒性归约模型，用各个模块的鲁棒性判据和模块之间免疫控制过程的鲁棒性判据表示分布式人工免疫系统的鲁棒性判据。经定理证明，鲁棒性归约模型能分解和简化分布式人工免疫系统的鲁棒性分析问题，通过各个模块的鲁棒性分析问题求解实现该问题的最终求解。因此，分布式人工免疫系统的鲁棒性归约模型是有用的鲁棒性分析工具，为复杂人工免疫系统的鲁棒性分析提供了有效的方法。

关键词：分布式人工免疫系统；问题归约法；鲁棒性；模块

中图分类号：TP311         文献标识码：A         文章编号：1672-7207(2007)05-0956-06

Reduction model of robustness for distributed artificial immune system

GONG Tao^{1, 2}, CAI Zi-xing¹, XIA Jie¹, JIANG Zhong-yang¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. College of Information Science and Technology, Donghua University, Shanghai 201620, China)

Abstract: With the model of reducing robustness of distributed multi-agent system, the distributed artificial immune system was regarded as an ideal distributed multi-agent system, so the robustness analysis problem of the distributed artificial immune system was reduced into the robustness analysis problems of all the independent modules of the system. The artificial immune system includes the module of modelling the normal model, the module of detecting selfs and non-selfs, the module of recognizing known non-selfs, the module of learning unknown non-selfs, the module of eliminating non-selfs and the module of repairing the damaged system. After analyzing the robustness of the artificial immune system with the problem reduction method, the model of reducing robustness of the distributed artificial immune system was built. Proved by some theorems, the model of reducing robustness can reduce and simplify the robustness analysis problem of the distributed artificial immune system, and the problem can be solved after the robustness analysis problems of all the modules were solved. The results show that the model of reducing robustness of the distributed artificial immune system is a useful tool to analyze robustness, and it can provide an effective approach to analyzing robustness of complex artificial immune system.

Key words: distributed artificial immune system; problem reduction method; robustness; module

人类免疫系统能抵御疾病、外来伤害等异体的干扰或侵害，在未知的、不确定的生存环境中能保持人体的一些重要健康指标不变^[1-3]，保证一定的动态品质的能力，因此，人类免疫系统具有很强的鲁棒性。人工免疫系统是模拟人类免疫系统的人造系统，免疫性和鲁棒性是这种模拟的重要方面，因此，人工免疫系统应该具备一定的鲁棒性，鲁棒性也是免疫计算的一个重要高级特性。

自然免疫系统是天然的并行、分布式生物信息处理系统，人工免疫系统也具有分布式信息处理的特  征^[4-5]。因此，根据已提出的多真体鲁棒性归约模型，可以用分布式系统的鲁棒性分析方法分析人工免疫系统的鲁棒性^[6]。分布式系统的性能分析很复杂，其中分布式系统的鲁棒性分析尤为困难。目前，关于这方面的研究增多，主要有：智能控制鲁棒性判据研究方法^[7-8]；非线性系统控制理论与李雅普诺夫稳定性理论、小增益理论以及耗散性或无源性等理论相结合的鲁棒系统分析和设计方法^[9]；多真体鲁棒性的尝试性分析方法^[10]；多真体鲁棒性的应用研究问题^[11]。但由于多真体鲁棒性问题很复杂和单真体的鲁棒性理论未能很好利用，因此，必须寻找分布式系统鲁棒性研究的新方法。问题归约法是一种把问题由繁化简、由多元转化为一元的有效分析方法^[12]，用问题归约法分析人工免疫系统的鲁棒性，能建立人工免疫系统的鲁棒性归约模型，并分析实际人工免疫系统的鲁棒相关性^[13]。

1  人工免疫系统鲁棒性的定义

目前，对人工免疫系统的鲁棒性还没有统一的定义。为了便于分析基于正常模型的人工免疫系统的鲁棒性，下面对人工免疫系统的鲁棒性进行定义。

一般来说，系统在某种扰动下，出现一定范围的参数不确定性或存在一定限度的未建模动态时，仍能保持系统某些性质不变，保证一定的动态品质的能力，称为系统的鲁棒性。

定义1  在免疫系统受到外界病菌的感染后，能够通过自身的免疫机制恢复健康以保持正常工作的一种特性或属性称为免疫系统的鲁棒性。在异体等抗原的扰动下，基于正常模型的人工免疫系统能通过自体/异体检测、识别和异体消除恢复系统的正常状态，能保持系统的自体百分比、异体百分比和某些功能不变，保证一定的动态免疫品质的能力，称为人工免疫系统的鲁棒性。

人工免疫系统的免疫计算具有鲁棒性，实际上是通过持续的自体含量最大化和异体含量最小化过程来实现的。因为正常的人工免疫系统只含有自体，而不含有异体，免疫计算的目标就在于检测、识别并消除异体，恢复受异体感染的自体。

定义2  从数学上说，人工免疫系统的自体含量最大化可表示为

反过来，人工免疫系统的异体含量最小化可以表示为

定义3  人工免疫系统的鲁棒性判据集是指其自体含量最大化、异体含量最小化的条件集合，即式(1)和(2)中极限收敛的条件集合。

根据上述定义，可以提出人工免疫系统的鲁棒性判据定理，以分析所述系统的鲁棒性。

定理1  从数学上说，人工免疫系统S具有鲁棒性的判据R_S是该系统中自体百分比恢复100%、异体含量降为0的条件，即

，且 。                   (3)

证明  根据统计特性，当不同时刻的人工免疫系统中自体和异体的组成相同时，该系统的自体百分比、异体百分比和一些功能是相同的。因此，尽管异体对人工免疫系统S的自体百分比、异体百分比和一些功能参数造成了一些扰动，但是在t₀时刻，人工免疫系统S的自体百分比、异体百分比和一些功能与正常的人工免疫系统相同。此时，该系统保持了一定的动态免疫品质，例如抗病毒、故障诊断与修复的动态品质。所以，根据定义1，从初始时间到t₀时刻的免疫计算过程中，所述人工免疫系统具备鲁棒性。

这样，人工免疫系统的鲁棒性分析问题可以进一步扩展为人工免疫系统的鲁棒性设计与维护问题，可以通过免疫算法保持所述人工免疫系统中的自体最大化和异体最小化来实现人工免疫系统的鲁棒性。

2  分布式人工免疫系统的鲁棒性分析

2.1    人工免疫系统的分布式结构

根据人工免疫系统的3层结构^[14]，人工免疫系统主要包括几个相对独立的计算模块：正常模型生成模块、自体/异体检测模块、已知异体识别模块、未知异体学习模块、异体消除模块和系统修复模块。这些计算模块是平等、独立的，相互管理和通信，不存在共同的高层管理模块。因此，在理想情况下，各个计算模块完全独立。该人工免疫系统是一种对等型的分布式系统，如图1所示，其中，箭头表示人工免疫系统中各个模块之间的免疫控制过程。

图1  人工免疫系统的分布式结构

Fig.1  Distributed structure of artificial immune system

运用问题归约方法，可以把对等型分布式人工免疫系统的鲁棒性问题分解为2个子问题：

a. 各个模块的鲁棒性分析问题；

b. 各个模块之间免疫控制过程的鲁棒性分析问题。

2.2    分布式人工免疫系统的鲁棒性归约定理

对等型分布式人工免疫系统是一种理想的分布式人工免疫系统，下面提出该系统的鲁棒性归约模型及其定理。

设分布式人工免疫系统S由6个计算模块M_i (i=1, …, 6)和各个模块之间的免疫控制过程C_jk (j=1, …, 6; k=1, …, 6)构成，记为{M_i, C_jk|i=1, …, 6; j=1, …, 6; k=1, …, 6}；其中任意模块M_i (i=1, …, 6)的鲁棒性判据集为( i=1, …, 6)，各个模块之间的离散控制过程C_jk (j=1, …, 6; k=1, …, 6)的鲁棒性判据集为(j=1, …, 6; k=1, …, 6)。则整个分布式人工免疫系统S的鲁棒性归约模型可用下面的鲁棒性判据集表示：

。                (4)

根据分布式人工免疫系统的鲁棒性归约模型、多真体的鲁棒性归约定理和问题归约方法，显然，可得理想分布式人工免疫系统的鲁棒性判据定理，称为人工免疫系统的鲁棒性归约定理。

定理2  对于理想分布式人工免疫系统，系统处于对等型分布式环境，人工免疫系统运行过程{M_i, C_jk}的鲁棒性判据集为

。   (5)

其中：表示对集合列取并运算，各个模块M_i (i=1, …, 6)的鲁棒性判据集分别记为，计算模块M_j与M_k之间的免疫控制过程C_jk的鲁棒性判据集为

     (6)

这样，基于分布式人工免疫系统的鲁棒性归约模型及其定理，就可以利用其单个计算模块的鲁棒性理论和免疫控制过程的鲁棒性理论，对实际的人工免疫系统的鲁棒性问题进行深入研究。

3  实际人工免疫系统的鲁棒相关性

研究实际人工免疫系统的鲁棒性问题，需要建立一系列新的理论框架，搭好从多元模块的鲁棒性问题向一元模块的鲁棒性问题转化的“桥梁”。

定义4  设人工免疫系统的计算模块M_i (i=1, …, 6)的鲁棒性判据集分别记为( i=1, …, 6)，整个人工免疫系统的鲁棒性判据集表示为R。对于任意的，对的隶属度称为的鲁棒隶属度，记为

。            (7)

鲁棒隶属度用来描述单个计算模块的鲁棒性判据集对人工免疫系统的鲁棒性判据集的任意子集的贡献程度。

定义5  实际人工免疫系统的环境往往达不到理想分布式要求，人工免疫系统中某些计算模块的鲁棒性对另一些计算模块的鲁棒性相互影响和相互制约，它们的鲁棒性判据集的某些部分是密切相关的，称这种性质为鲁棒相关性。

定义6  设R_i和R_j为2个非空的鲁棒性判据模糊集，则其直积R_i×R_j中的1个模糊子集R_k是从R_i到R_j的模糊关系，称为鲁棒相关关系，记为

。 (8)

鲁棒相关关系反映各个计算模块的鲁棒性判据集之间的鲁棒相关性。

定义7  用来表示各个真体的鲁棒性之间相互关联程度的系数，称为鲁棒相关系数。

例  模块M₁与M₂的鲁棒性之间80%相关，则它们的鲁棒相关系数为0.8。

定义8  设R_i和R_j为鲁棒性判据论域R中2个非空的鲁棒性判据模糊集，其鲁棒隶属度分别为和，则对于所有，存在下列运算：

a. R_i和R_j的并(逻辑或)记为，其隶属函数定义为

。(9)

b. R_i和R_j的交(逻辑与)记为，其隶属函数定义为

。 (10)

c. R_i的补(逻辑非)记为，其隶属函数定义为

。                    (11)

鲁棒性判据模糊集并、交和补运算满足幂等律、交换律、结合律、分配律、吸收律、同一律、迪摩根(DeMorgan)律、复原律和对偶律(逆否律)，互补律不成立^[15]。

基于以上定义，可推导出有关人工免疫系统的鲁棒相关性的性质定理。

定理3  假设计算模块M_i和M_j的鲁棒性判据集分别为和，人工免疫系统鲁棒性判据集为R，R对的隶属度为，计算模块M_i与M_j的鲁棒相关系数为λ，则

。  (12)

证明  因为真体M_i与M_j的鲁棒相关系数为，根据定义7，与可以看成相互独立的，所以，

；            (13)

。                 (14)

由于与密切相关，所以，与对R的贡献程度是相同的。

； (15)

故

。 (16)

证毕。

利用问题归约思想，建立了人工免疫系统在理想分布式环境中的鲁棒性归约模型及其定理，并且创建了实际人工免疫系统的鲁棒相关性的理论框架之后，对于实际人工免疫系统，根据各个计算拉模块之间的鲁棒相关性，能把鲁棒性归约模型推广到鲁棒相关性模型，用以深入分析实际人工免疫系统的鲁棒性特点。

对于人工免疫系统{M_i, C_jk |i=1, …, 6; j=1, …, 6}，其中模块M_j和模块M_k之间的鲁棒相关系数记为λ_jk (j=1, …, 6; k=1, …, 6)，各个计算模块M_i (i=1, …, 6)的鲁棒性判据集分别表示为(i=1, …, 6)，计算模块之间的免疫控制过程C_jk (j=1, …, 6; k=1, …, 6)的鲁棒性判据集记为(j=1, …, 6; k=1, …, 6)，该人工免疫系统的鲁棒性判据集记为R，则人工免疫系统的鲁棒性判据集R的求解问题可分解和转化为以下子问题：

a. 各计算模块M_i (i=1, …, 6)的鲁棒性判据集(i=1, …, 6)的求解问题；

b. 计算模块之间的免疫控制过程C_jk (j=1, …, 6; k=1, …, 6)的鲁棒性判据集(j=1, …, 6; k=1, …, 6)的求解问题。

在各子问题求解的基础上，利用定理1~3和鲁棒相关性系数，对各种子问题的鲁棒性判据解集进行运算，从而求解出整个复杂的人工免疫系统的鲁棒性判据集问题。对于具体的应用背景，鲁棒相关性系数的取法与具体应用系统有关，具有一定的经验性。

整个人工免疫系统的鲁棒相关性模型是自顶向下逐步分解和变换鲁棒性问题，不断降低问题难度和元数，直到可以消解为比较容易解决或者已经能够解决的鲁棒性问题，如某些模块的鲁棒性问题和某些免疫控制过程的鲁棒性问题，然后，对这些本原问题求解；接着，反过来自底向上，利用人工免疫系统的鲁棒性相关模型以及性质定理，对本原问题的各种鲁棒性判据解集进行运算，从而求解出整个人工免疫系统的鲁棒性判据集。

4  实际应用

在抗蠕虫病毒的静态Web免疫系统中，正常模型构建、自体/蠕虫病毒检测、蠕虫病毒识别、蠕虫病毒消除和受损Web系统自修复是该系统的几个相对独立功能模块，呈现分布式的结构。其中，自体/蠕虫病毒检测模块和受损Web系统自修复是对系统鲁棒性最重要的2个模块。

自体/蠕虫病毒检测的仿真结果如图2所示。曲线1表示基于正常模型的自体/蠕虫病毒检测结果，蠕虫病毒就是异体；曲线2表示基于神经网络的蠕虫病毒检测结果。从图2中曲线1可以看出，正常模型有利于实现对蠕虫病毒的完全检测。

图2  蠕虫病毒检测的实验比较

Fig.2  Comparison between two experiments for detecting worms

对于不同的蠕虫病毒样本，静态Web免疫系统会产生不同的病毒识别率，但是，利用正常模型能始终实现对蠕虫病毒的完全检测，并在此基础上对这些病毒进行消除，对受损的自体进行修复，对丢失的自体进行补充。蠕虫病毒的多样性对静态Web免疫系统的计算过程造成了一些干扰，但是正常模型、自体/异体检测模块和受损系统自修复模块保证了该系统的自体最大化和异体最小化，结果如图3所示，从而维护了系统的鲁棒性。因此，正常模型构建模块、自体/异体检测模块和受损系统自修复模块的鲁棒性保证了静态Web免疫系统的鲁棒性。

图3  静态Web免疫系统的自体百分数最大化

Fig.3  Maximization of self percent for static Web immune system

在图3中，5条曲线对应静态Web免疫系统的5次抗蠕虫病毒实验结果，这些结果显示系统的自体百分比都逐渐上升到100%。其中，曲线1表示该系统中没有丢失文件，最初自体数目与正常系统中自体总数目的百分数为99%，在用人工免疫系统检测并消除病毒的同时，这些蠕虫病毒处于非激活状态，消除病毒后对受损的自体进行了修复；曲线2表示该系统中没有丢失文件，最初自体数目与正常系统中自体总数目的百分数为99%，在用人工免疫系统检测并消除病毒的同时，这些蠕虫病毒处于激活状态，复制自身，产生新的蠕虫病毒文件，直到这些病毒的进程被关闭，这些病毒逐渐被消除，然后对受损的自体进行了修复；曲线3表示该系统中没有丢失文件，最初自体数目与正常系统中自体总数目的百分数为99%，在用人工免疫系统检测并消除病毒的同时，这些蠕虫病毒处于激活状态，感染系统的正常文件，自体百分数逐渐降低，直到这些病毒的进程被关闭，这些病毒逐渐被消除，然后对受损的自体进行了修复；曲线4表示该系统中本身存在丢失的文件，最初自体数目与正常系统中自体总数目的百分数为89%，在用人工免疫系统检测并消除病毒的同时，这些蠕虫病毒处于非激活状态，消除病毒后对受损的自体进行了修复；曲线5表示该系统中本身存在丢失的文件，最初自体数目与正常系统中自体总数目的百分数为89%，在用人工免疫系统检测并消除病毒的同时，这些蠕虫病毒处于激活状态，复制自身，产生新的蠕虫病毒文件，直到这些病毒的进程被关闭，这些病毒逐渐被消除，然后，对受损的自体进行了修复。

5  结  论

a. 鲁棒性归约模型是对理想分布式环境中人工免疫系统的鲁棒性进行分析，鲁棒相关性模型是对实际人工免疫系统的鲁棒性和各个计算模块的鲁棒性之间的相关性进行分析。鲁棒性归约模型是鲁棒相关性模型的简化模型，鲁棒相关性模型是对鲁棒性归约模型的深化和推广。因此，鲁棒性归约模型和鲁棒相关性模型是一脉相承、相互关联的，鲁棒性归约模型是研究鲁棒相关性模型的基础，鲁棒相关性模型是鲁棒性归约模型在实际应用中深化的结果。

b. 在理想分布式环境下，由于各个计算模块鲁棒性之间没有相关性，也就是说相互独立，各个计算模块的鲁棒相关系数都为0，因而，鲁棒相关系数在鲁棒相关性模型的作用为0，此时，鲁棒相关性模型就可简化为鲁棒性归约模型。反过来，利用各个计算模块的鲁棒相关性分析，就可以搭建由鲁棒性归约模型向鲁棒相关性模型转化的“桥梁”，通过鲁棒相关性理论新框架的创建和完善，把鲁棒性归约定理和计算模块的鲁棒性分析方法转化为实际人工免疫系统的鲁棒性分析工具。

参考文献：

[1] Kim M, Spelta V, Sim J, et al. Differential assembly of rat purinergic P2X7 receptor in immune cells of the brain and periphery[J]. Journal of Biological Chemistry, 2001, 276(26): 23262-23267.

[2] Medzhitov R, Janeway C A J. Decoding the patterns of self and nonself by the innate immune system[J]. Science, 2002, 296(5566): 298-300.

[3] Chao D L, Davenport M P, Forrest S, et al. Modelling the impact of antigen kinetics on T-cell activation and response[J]. Immunology and Cell Biology, 2004, 82(1): 55-61.

[4] Sarafijanovic S, Le Boudec J Y. An artificial immune system approach with secondary response for misbehavior detection in mo-bile ad hoc networks[J]. IEEE Trans Neural Networks, 2005, 16(5): 1076-1087.

[5] de Castro L N, Timmis J. Artificial immune systems: A new computational intelligence approach[M]. London: Springer- Verlag, 2002.

[6] 龚 涛, 蔡自兴. 多艾真体的鲁棒性归约模型[J]. 控制理论与应用, 2003, 20(4): 514-520.
GONG Tao, CAI Zi-xing. Model of reducing robustness of multi-agent system[J]. Control Theory & Application, 2003, 20(4): 514-520.

[7] Laure E O. A Java framework for distributed high performance computing[J]. Future Generation Computer Systems, 2001, 18(2): 235-251.

[8] Kranakis E, Santoro N. Distributed computing on oriented anonymous hypercubes with faulty components[J]. Distributed Computing, 2001, 14(3): 185-189.

[9] Shaw N G, Mian A. A comprehensive agent-based architecture for intelligent information retrieval in a distributed heterogeneous environment[J]. Decision Support Systems, 2002, 32(4): 401-415.

[10] 蔡自兴, 刘健勤. 非确定性TS模糊神经模型鲁棒性的统计判据[J]. 中南工业大学学报: 自然科学版, 1997, 28(6): 586-588.
CAI Zi-xing, LIU Jian-qin. A statistical criterion of robustness for uncertainty TS fuzzy neural network model[J]. Journal of Central South University of Technology: Natural Science, 1997, 28(6): 586-588.

[11] CAI Zi-xing, LIU Jian-qin, LIU Juan. A criterion of robustness based on fuzzy neural structure[J]. High Tech Letters, 1999, 9(1): 38-42.

[12] 蔡自兴, 徐光祐. 人工智能原理及其应用[M]. 3版. 北京: 清华大学出版社, 2004.

CAI Zi-xing, XU Guang-you. Artificial intelligence: Principles and applications[M]. 3rd ed. Beijing: Tsinghua University Press, 2004.

[13] 龚 涛. 多维教育免疫艾真体的研究[D]. 长沙: 中南大学信息科学与工程学院, 2003.

GONG Tao. Research on multi-dimension education immune agent[D]. Changsha: School of Information Science and Engineering, Central South University, 2003.

[14] 龚　涛, 蔡自兴. 移动机器人的并行免疫计算模型[J]. 中南大学学报: 自然科学版, 2006, 37(1): 124-129.

GONG Tao, CAI Zi-xing. Parallel immune computation model of mobile robot[J]. Journal of Central South University: Science and Technology, 2006, 37(1): 124-129.

[15] CAI Zi-xing. Intelligent control: Principles, techniques and applications[M]. Singapore: World Scientific Press, 1997.

收稿日期：2007-01-26；修回日期：2007-03-18

基金项目：国家自然科学基金资助项目(60234030, 60404021)

作者简介：龚  涛(1978-)，男，湖南常德人，博士，讲师，从事人工免疫系统等研究

通信作者：龚  涛，男，博士，讲师；电话：021-67792312(O)；E-mail: taogong@sigmaxi.net