3.3　免疫计算

1958年澳大利亚学者Burnet率先提出了克隆选择原理，并于1960年因此获得诺贝尔奖。Farmer于1986年基于免疫网络学说理论构造出了免疫系统的动态模型，展示了免疫系统与其他人工智能方法相结合的可能性，开创了免疫系统研究的先河。1996年，在日本举行的国际专题研讨会上，免疫系统的概念被提出。1997年，IEEE的SMC组织专门成立了人工免疫系统及应用的分会组织[1]。

免疫算法是受生物免疫系统的启发而推出的一种新型的智能搜索算法。对外界入侵的抗原，受抗原的刺激，生物上淋巴细胞会分泌出相应的抗体，其目标是尽可能保证整个生物系统的基本生理功能得到正常运转，并产生记忆细胞，以便下次相同的抗原入侵时，能够快速地做出反应。研究者借鉴其相关内容和知识，并将其应用于工程科学的某些领域，收到了良好的效果。

3.3.1　概要

免疫算法是模仿生物免疫机制，结合基因的进化原理，人工地构造出的一种新型智能搜索算法。免疫算法具有一般免疫系统的特征，免疫算法采用群体搜索策略，一般遵循的步骤是：“产生初始化种群→适应度的计算评价→种群间个体的选择、交叉、变异→产生新种群”。通过这样的迭代计算，最终以较大的概率得到问题的最优解。相比于其他算法，免疫算法利用自身产生多样性和维持机制，保证了种群的多样性，克服了一般寻优过程中特别是多峰值的寻优过程中不可避免的“早熟”问题，从而求得全局最优解。大量研究表明，免疫算法能在较少的迭代次数下快速收敛到全局最优。

虽然起步较晚，但免疫算法已在函数优化、人工神经网络设计、智能控制等领域获得了成功的应用。由于免疫算法在增强系统的鲁棒性、维持机体动态平衡方面有明显的成效，因此也充分与其他算法融合，例如，免疫遗传算法、免疫粒子群算法，这些算法的灵活性很高。免疫算法目前主要的应用领域包括机器学习、故障诊断、网络安全、优化设计。

国内虽然对免疫算法的研究起步较晚，但在免疫算法的研究及其应用上取得了较好的成果。经研究归纳，免疫算法可分为以下3种。

（1）基本免疫算法，模拟免疫系统中抗原与抗体的结合原理。

（2）基于免疫系统中其他特殊机制抽象出来的免疫算法，如克隆选择算法。

（3）免疫算法与其他智能算法的结合形成的新的算法，如免疫遗传算法。

3.3.2　基本免疫算法

基本免疫算法基于生物免疫系统基本机制，模仿了人体的免疫系统。基本免疫算法从体细胞理论和网络理论得到启发，实现了类似于生物免疫系统的抗原识别、细胞分化、记忆和自我调节的功能，如图3-12所示。

一般来说，免疫反应就是当病原体入侵到人体时，受病原体刺激，人体免疫系统以排除抗原为目的而发生的一系列生理反应。其中，B细胞和T细胞起着重要的作用。B细胞的主要功能是产生抗体，且每种B细胞只产生一种抗体。免疫系统主要依靠抗体来对入侵抗原进行攻击以保护有机体。T细胞不产生抗体，它直接与抗原结合并实施攻击，同时还兼顾调节B细胞的活动。成熟的B细胞产生于骨髓中，成熟的T细胞产生于胸腺中。B细胞和T 细胞成熟之后进行克隆增殖、分化并表达功能。正是由于这两种淋巴细胞之间相互影响，相互控制，才使得机体得以维持机体反馈的免疫网络。

1.免疫算法的相关概念

免疫算法保留着生物免疫系统中一些主要的元素，免疫算法各元素与生物免疫系统一一对应，如表3-4所示。

抗原：在生命科学中，指能够诱发机体的免疫系统产生免疫应答和抗体进行免疫作用的物质，在算法中特指非最优个体的基因或错误基因。

抗体：在生命科学中，指免疫系统受抗原刺激后，免疫细胞转化为T细胞并产生的与抗原发生特异性结合的免疫球蛋白。

疫苗：在生命科学中，指保留了能刺激生物免疫系统的特性，使免疫应答做出反应的预防性生物制品；在免疫算法中，疫苗指根据已求问题的先知经验得到的对最优个体基因的估计。免疫算子：与生命科学中的免疫理论相对应，免疫算子可分为全免疫和目标免疫，前者对应生命科学中的非特异性免疫；后者则对应特异性免疫。

免疫调节：在免疫反应过程中，抗原对免疫细胞的刺激会增强抗体的分化和繁殖，但大量抗体的产生会降低这一刺激，从而控制抗体的浓度；同时，产生的抗体之间也存在相互刺激和抑制作用，这种抗原与抗体亲和力、抗体与抗体之间的排斥力使抗体免疫反应维持在一定的强度，保证机体的动态平衡。

免疫记忆：与抗原发生反应的抗体会作为记忆细胞将记忆成功地保存下来，当相似的抗原再次入侵时，这类记忆细胞会根据经验，受刺激并产生大量的抗体，从而大量缩短免疫反应时间。

2.免疫算法的基本步骤

（1）识别抗原。对问题进行可行性分析，构造出合适的目标函数和制定各种约束条件，作为抗原。

（2）产生初始抗体群。免疫算法不能直接解决问题空间中的参数，因此必须通过编码把问题的可行解表示成解空间中的抗体，一般将解的空间内随机产生的解作为初始抗体。采用简单的编码可以方便计算，实数编码不需要进行数值的转换，因此是比较理想的编码方法，每个抗体为一个实数向量。

（3）对群体中的抗体进行多样性评价，计算亲和力和排斥力。免疫算法对抗体的评价是以期望繁殖概率为标准的，其中包括亲和力的计算和抗体浓度的计算。

（4）形成父代群体。更新记忆细胞，保留与抗原亲和力高的抗体并将它存入记忆细胞中，利用抗体间排斥力的计算，淘汰与之亲和力最高的抗体。

（5）判断是否满足结束条件。如果产生的抗体中有与抗原相匹配的抗体，或者满足结束条件，则停止。

（6）利用免疫算子产生新种群。免疫算子包括选择、交叉和变异等操作。按照“优胜劣汰”的自然法则选择，亲和力高的抗体有较大的机会被选中。交叉和变异操作在后面章节中会介绍。

（7）转至步骤（3）。

3.3.3　基于免疫算法的TSP问题求解

TSP问题指寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X={1，2，…，n}（X的元素表示对n个城市的编号）的一个排列，使取最小值，其中，表示城市Vi到城市Vi+1的距离。由于它是诸多领域内出现的多种复杂问题的集中概括和简化形式，因此成为各种启发式搜索、优化算法的间接比较标准。在工程中，很多问题可以抽象为TSP问题，并且TSP问题经常被作为测试对象用于各种算法的性能比较，因此TSP问题是一个既有理论价值又有广泛的工程应用价值的组合优化问题。基于免疫算法的TSP问题求解实现步骤如下。

1.抗体编码方式及适应度函数

抗体采用以遍历城市的次序排列进行编码，每一抗体码串形如V1，V2，…，Vn，其中，Vi表示遍历城市的序号。程序中抗体定义为一维数组A（N），N表示TSP问题中的城市数目，数组中的各元素A（i）的取值为1～N中的整数，分别表示城市的序号。根据问题的约束条件，每一数组内的各元素值互不相同。

适应度函数取路径长度Td的倒数，即，表示第i个抗体所遍历的城市路径长度。

2.初始抗体群的产生

初始抗体在解空间中用随机方法产生I个初始抗体，形成初始抗体群。当待求解问题与记忆细胞中抗体相匹配时，则由匹配的记忆细胞组成初始抗体群，不足部分的抗体随机产生。

3.新抗体的产生

（1）字符换位操作。单对字符换位操作指对抗体随机取两个正整数i， j （i＞1，jn，i≠j），以一定的概率P （0< P <1）交换抗体A中的一对字符Vi， Vj的位置；多对字符换位操作指预先确定一个正整数u，随机取一个正整数r （1ru），在抗体A中随机取r对字符做字符换位操作。

（2）字符串移位操作。单个字符串移位操作指对抗体随机取两个正整数i， j （i＞1，jn，i≠j），从A中取出一个字符子串A1，，以一定的概率P （0 < P <1）依次往左（或往右）移动字符串A1中的各字符，最左（或最右）边的一个字符则移动到最右（或最左）边的位置；多个字符串换位操作指预先确定一个正整数u，随机取一个正整数r （1ru），再在抗体A中随机取r个字符子串做字符串移位操作。

（3）字符串逆转操作。单个字符串逆转操作指对抗体随机取两个正整数i， j （i＞1，jn，i≠j），从A中取出一个字符子串A1，，以一定的概率P （0 < P <1）使字符串A1中的各字符首尾倒置；多个字符串逆转操作指预先确定一个正整数u，随机取一个正整数r （1ru），再在抗体A中随机取r个字符子串做字符串逆转操作。

（4）字符重组操作。字符重组操作指在抗体中随机取一个字符子串A1，，以一定的概率P （0 < P <1）使字符串A1中的字符重新排列，重新排列的目的是提高抗体的亲和力。

4.免疫记忆

抗体记忆机制是免疫算法的较大优势。系统在完成一个问题的求解后，能保留一定规模的求解过程中的较优抗体，当系统接收到同类抗原时，其以所保留的记忆细胞作为初始群体，从而提高了问题求解的收敛速度，体现了免疫算法二次应答时的快速求解能力。在求解过程中，每一代的抗体群更新时，将适应度最好的M个抗体存入记忆细胞库，并比较库中是否有与入选抗体相同的记忆细胞，从而保证记忆细胞的多样性。

5.实验仿真及其结果

实验给出了42个城市之间的相互距离，模拟求42个城市之间最短路径问题。实验设定的各参数如下。

经过1500次迭代后，该算法基本上可以找到42个城市之间的最短路径值，约为1300。