免疫算法（Immune Algorithm)详解

关于免疫算法（IA），其功能与遗传算法、模拟退火等算法实现的功能是相同的，都是用来求最优解。例如求函数最值、旅行商问题等。从本质上说，免疫算法更像是遗传算法的一种延申。IA虽然其中借鉴了生物学（免疫学）的概念，但学习时需要注意，IA毕竟是一种算法，把算法中所有概念都与免疫学概念联系起来是容易难以理解算法的，甚至容易混淆。所以IA只是借鉴免疫学概念并受免疫过程的启发，最终其实还是需要回归到算法当中。

即便如此，兔兔在后面还是需要将算法与一些生物学概念联系，但是会辨别其中本质区别。而且学习时需要与遗传算法相结合，毕竟免疫算法从某种角度来说是遗传算法的一种延申。

根据高中的生物学知识，我们知道，抗原（细菌、病毒、疫苗等）进入生物体后，首先会被非特异性免疫消灭，但有时这种免疫防线会被突破。所以还有特异性免疫，即B细胞受抗原刺激后分化成浆细胞和记忆细胞，浆细胞分泌抗体抑制消灭抗原。记忆细胞在下次接受抗原时可以直接分化成浆细胞并分泌抗体，抑制抗原。

上面的概念虽然很多，但实际在算法中很多相关概念和过程是可以合并或忽略的。

在遗传算法中，我们把种群中的个体（即染色体）当作解，先初始种群（初始解），在进行交叉、突变、选择；这里的抗原、抗体在一开始时就代表初始解，抗原抗体在一开始是混在一起的，只不过我们把较优的一部分解叫“抗原”，不优的部分叫做”抗体“。之后的每次迭代过程我们叫做“打疫苗”。

在免疫学中，我们知道，当生物体接种疫苗后，相应的B细胞分化成浆细胞与记忆细胞，再次注射疫苗时记忆细胞在抗原刺激性又会分化成浆细胞，从而分泌更多的抗体。而且，免疫学中，抗原抗体，抗原与记忆细胞的识别是特异性结合的。在我们IA算法中，抗原抗体是几乎没有特异性结合这种过程的（有的文章中会把序列识别等当作特异性识别，其实是不准确的，不必在意）。而且，IA算法中几乎不区分浆细胞、记忆细胞、抗原这三者的概念的，或者说，这三者表示算法中同一个东西。算法中表示接种疫苗的过程是：把之前的抗原克隆复制（即把这些解复制多次），对这些克隆进行突变，选取较优的部分作新抗原（即新的较优解），再把这些抗原与新的疫苗抗体（即新的一些随机解）混合在一起（这个过程可以看作是接种疫苗），在从这些混合解中选取较优的部分作为新的抗原，这个新的抗原在进入下一次接种疫苗的过程中。在从混合解中选的过程中，我们也淘汰了一些不优的解，可以对应是抗体免疫抑制抗原（其中其实也包括了抗原复制扩增对抗体的一种抑制），但本质就是从中选较优的解，与是否是免疫抑制关系不是很大（但很多文章会是这样讲的）。

如果从现在来看的话，免疫算法与遗传算法区别并不是很大，主要就是除了之前的突变、交叉操作，多了一个接种疫苗的操作——即每次选一部分较优解（抗原、记忆细胞、浆细胞）复制选优后与随机解混合，从中选取较优解（抗原），再进行重复操作。

但是在免疫算法选择的步骤中，对遗传算法中由“适应度”进行选择的方法做了很大改进，引出了“亲和度”（affinity)、"抗体浓度"（density)、"激励度"（simulation)这三个在选择操作中的重要概念。其中的激励度是由亲和度与抗体浓度进行计算的。亲和度与抗体浓度是由这些解来计算的。

“亲和度”（affinty)本质上就是遗传算法中的“适应度”（fitness),所以亲和度本质上代表解与最优情况的接近程度。例如，当我们求函数f(x)的最大值时，亲和度就可以用f(x)来表示，f(x)越大，亲和度也就越大。

“抗体浓度”（density)本质上是一个解与集合中其它所有的解当中距离比较近(或者说比较相似）的解的个数，再除以集合中解的总数总数就是这个解的浓度，称作抗体浓度（准确来说就是浓度，因为集合是抗原抗体的混合）。那么怎么判断一个解与其它所有解距离较近的个数呢？

所以我们需要一种方法来度量距离，并且当距离小于某一个阈值（delta)时判断这个解就是其中一个离它比较近的解，否则不是。所以我们需要找到解直接的一种距离度量方法。（注；很多文章会说两个解之间的相似程度或距离叫做亲和度，并把计算距离或相似程度这个过程叫做亲和力计算，这样在算法中不太准确，而且会和前面那个亲和度概念弄混）。

距离度量方法

（1）实数编码的解。

对于实数编码的解，通常可以用欧氏距离来表示，如果是一维的数，就是两个数相减绝对值；如果是二维平面的点，就是平面两点距离公式：

多维的点以此类推。除了欧式距离，还有马式距离、闵式距离等，在多元统计、泛函分析等学科都有涉及，IA算法大多采用欧式距离。

（2）离散编码的解。

一般情况下，我们遇到的离散的解就是二进制的长串（兔兔在遗传算法中曾使用过，详解《遗传算法（GA）详解》一文）。如[0,1,1,1,0,0,1,0]。对于这种情况通常采用海明距离。

其中,ak,bk分布表示各自数组中位置k的元素（1或0）。这样两个链对应位置不一样的位置越多，距离就越远，很符合逻辑。

那么，现在我们找到了距离度量方法，当距离小于阈值delta时就认为两个解接近，然后累计该解与所有解距离近的个数，最后除以解的总个数就是该解的浓度了。

“激励度”（simulation)就是最终选择的评判标准了。激励度公式如下：

其中alpha通常是1，beta=2，实际可以根据需要进行调整。一个解的激励度越大，那么就越先优选。对应就是遗传算法在“适应度”——适应度越大，被选概率越大。只不过这里有了density一项的影响，只要simulation大，我们就一定选这个解，而不是以大的概率取选它。我们根据simulation选解的操作是：把解按照simulation的大小从大往小排，取其中simulation较大的前一半作为抗原（选较优解），后面一半全都不要；之后操作：克隆（把抗原复制多个），随机突变，再把这些计算simulation，按顺序排，取simulation较大的部分，与抗体疫苗混合（接种疫苗），把这个混合集合再计算simulation ,排序选较大的部分，就是新的抗体的，之后循环操作。

对simulation的理解

我们发现，如果让式子中beta一项为0，那么就是适应度（fitness)，即每次选择适应度最大的解。而减去了beta*density,就说明density值越大，其simulation就越小，就越可能不被选中。而density代表了这个解与所有解中比较相近的解的个数。所以浓度越低，激励度会越好，越容易被选中。

变异操作

与遗传算法相同，免疫算法在每次对抗体克隆后会对所有克隆进行变异。对于二进制的数组，变异方法与遗传算法中变异操作一致。而对于实数编码，变异操作可以表示为：

rand是0~1随机数，如果小于pm(即以概率pm选择是否突变），就进行突变，表示定义域区间长度。大于pm就不突变。

关于交叉操作，在IA中也是可以有的，但是有了变异操作，又有接种疫苗的操作，导致每次都有很大的随机性，所以多数情况是可以不用交叉。交叉操作与遗传算法中交叉操作一致。

在网上或其它文章中我们都可以看到关于免疫算法的流程图，而且有很多种，里面大多都是免疫学的概念，但其实回到算法当中，无外乎都是同种东西。所以关键还是算法流程，免疫学概念可以用来进行比喻帮助记忆。

（1）先初始n个解，n为种群个数。

（2）计算这些种群的亲和度、浓度，并计算出激励度。

（3）根据激励度对种群由大到小排列，取前n/2个做抗原，后面的不要。

（4）对抗原进行克隆，克隆m份，对mn/2个克隆进行变异。

（5）变异后计算亲和度、浓度，并计算激励度。根据激励度大小从大到小排列，取前n/2个做抗体。

（6）随机产生n/2个种群（即疫苗、抗体），与前面得到的抗体混合。

（7）混合后计算亲和度、浓度，并计算激励度，根据激励度从大到小排列，取前n/2做抗体。

（8）得到的抗体再回到（4），重复循环。

（9）在循环结束后，根据affinity排序，选取affinity最大的那个解作为最优解。

以上就是免疫算法的基本流程。

我们以求函数f(x)=sin(3x) （)求最大值为例。我们编码解的二进制数组长度binarylength为8，初始种群数popsize=40,突变概率pm为0.7，阈值delta=3,克隆数clone_num为10，alpha=1,beta=1,循环次数circle=30。