免疫算法

简述

传统免疫是指机体抗感染的防御能力，而现代免疫则指机体免疫系统识别和排除抗原性异物，从而维持机体生理平衡和稳定的功能。免疫是机体的一种生理反应，当病原体(即抗原)进入人体时，这些抗原将刺激免疫细胞(淋巴B细胞、T细胞)产生一种抵抗该病原生物的特殊蛋白质---抗体。抗体能将该病原生物消灭，并在将病原生物消灭之后，仍存留在人体内。当同样的病原生物再次侵入人体时，该病原生物就会很快地被体内存留的抗体消灭。
对于免疫算法，抗原就是待解决的优化问题，抗体就是对应问题的解的结构。然后针对抗体种群进行质量评价，评价准则是个体亲和度和个体浓度，评价得出的优质抗体将进行免疫操作，劣质抗体将会被刷新。 免疫操作：利用免疫选择、克隆、变异、克隆抑制、种群刷新等算子模拟生物免疫应答中的各种免疫操作，形成基于生物免疫系统克隆选择原理的进化规则和方法，实现对各种最优化问题的寻优搜索。

基本理论

与遗传算法等其他智能优化算法类似，免疫算法的进化寻优过程也是通过算子来实现的。免疫算法的算子包括:亲和度评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆算子、变异算子、克隆抑制算子和种群刷新算子等。

亲和度评价计算

亲和度表征免疫细胞与抗原的结合强度，与遗传算法中的适应度类似，针对不同问题设置不同的亲和度函数。通常表示为一个函数，其中ab_i表示为这一代的一个抗体。

亲和度评价

抗体浓度评价计算

抗体浓度表征抗体种群的多样性好坏。抗体浓度过高意味着种群中非常类似的个体大量存在，则寻优搜索会集中于可行解区间的一个区域，不利于全局优化。因此优化算法中应对浓度过高的个体进行抑制，保证个体的多样性。其中定义如下：

抗体浓度计算
其中N为种群规模，S(ab_i, ab_j)表示抗体间的相似度，具体表示如下
相似度
其中ab_i为种群中第i个抗体，aff(ab_i, ab_j)为抗体间的亲和度，δ_s为相似度阈值

基于欧式距离的抗体间亲和度计算

欧式距离

式中分别为抗体i的第k维和抗体j的第k维，L为抗体编码总维数。这是实数编码算法中最常见的抗体间亲和度的计算方法。离散的话用以下式子（是基于海明距离的）

海明距离
海明距离

激励度计算

激励度算子就是抗体的综合评价，计算方式如下，二者取其一，其本质目的是为了共同考虑亲和度和浓度，从而筛选下一代的抗体

激励度计算

免疫选择

免疫选择算子根据抗体的激励度确定选择哪些抗体进入克隆选择操作。在抗体群中激励度高的抗体个体具有更好的质量，更有可能被选中进行克隆选择操作，在搜索空间中更有搜索价值。

克隆操作

克隆算子将免疫选择算子选中的抗体个体进行复制，具体描述如下

克隆
式子中clone(ab_i)表示为由m个与ab_i相同的克隆抗体构成的集合；m为克隆的个数，可以事先预定，可以自适应的计算

实数编码算法变异计算

实数编码
变异操作是在克隆的个体中进行的，其中ab_i,j,m表示的是ab_i的克隆集合中第m个个体的第j维度（可以理解为第j个基因），δ是定义的邻域的范围，可以实现预定，也可以自适应的调整，P_m为变异概率。对于离散编码算法以二进制编码为主，其变异策略是从变异源抗体串中随机选取几位元，改变位元的取值(取反)，使其落在离散空间变异的邻域。

种群刷新

种群刷新操作用于对种群中激励度较低的抗体进行刷新，从抗体种群中删除这些抗体并以随机生成的新抗体替代，有利于保持抗体的多样性，实现全局搜索，探索新的可行解空间区域。

免疫算法的流程

1. 首先进行抗原识别，即理解待优化的问题，对问题进行可行性分析，提取先验知识，构造出合适的亲和度函数，并制定各种约束条件。
2. 然后产生初始抗体群，通过编码把问题的可行解表示成解空间中的抗体，在解的空间内随机产生一个初始种群。
3. 对种群中的每一个可行解进行亲和度评价。
4. 判断是否满足算法终止条件:如果满足条件，则终止算法寻优过程，输出计算结果;否则，继续寻优运算。
5. 计算抗体浓度和激励度。
6. 进行免疫处理，包括免疫选择、克隆、变异和克隆抑制：
   a. 免疫选择:根据种群中抗体的亲和度和浓度计算结果选择优质抗体，使其活化;
   b. 克隆:对活化的抗体进行克隆复制，得到若干副本;
   c. 变异:对克隆得到的副本进行变异操作，使其发生亲和度突变;
   d. 克隆抑制:对变异结果进行再选择，抑制亲和度低的抗体，保留亲和度高的变异结果。
7. 种群刷新，以随机生成的新抗体替代种群中激励度较低的抗体，形成新一代抗体，转步骤(3) 。