下载掌阅APP，畅读海量书库
立即打开
生物免疫系统是一个复杂的自适应系统，能够识别出病原体，具有识别、学习和记忆能力，因此可以借鉴其信息处理机制来解决复杂优化问题。人工免疫算法正是基于生物免疫系统识别外部病原体，并产生抗体对抗病原体的学习机制而提出的。将待优化的问题对应免疫应答中的抗原；问题的可行解对应抗体（由于抗体由B细胞产生，此处对抗体和B细胞不作区分，都对应优化问题的可行解）；可行解质量对应免疫细胞与抗原的亲和力。如此，则把优化问题的寻优过程与生物免疫系统识别抗原并实现抗体进化的过程对应起来，将生物免疫应答中的进化过程抽象为求解优化问题的搜索寻优过程，形成一种智能优化算法。
依据算法原理的不同，目前可将人工免疫算法分为：Chun等人提出的基于信息熵的免疫遗传算法，Forrest等人提出的基于免疫特性的否定（反向）选择算法，Timmis等人提出的基于进化人工免疫网络的免疫网络算法，王磊提出的基于疫苗的免疫规划算法等。本书讲述的人工免疫算法是指由巴西Campinas大学的De Castro等人于2000年提出的克隆选择算法（Clone Selection Algorithms，CSA），对其他算法感兴趣的读者可自行查阅相关文献。
与遗传算法类似，人工免疫算法的搜索寻优过程也是通过不同算子来实现的。克隆免疫算法的算子包括亲和力评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆扩增算子、克隆变异算子、克隆抑制算子和种群刷新算子等。由于抗体的编码方式不同，这些算子的计算方法也有所不同。
1.亲和力评价算子
亲和力（Affinity）表征抗体与抗原的结合强度，与遗传算法中的适应度函数类似。亲和力评价算子通常是一个函数aff（ X i ），函数的输入 X i 为一个抗体个体（可行解），输出即为亲和力评价结果。亲和力评价函数应根据优化问题的特点来定义，通常函数优化问题可以用函数值或对函数值的简单处理（如取倒数、相反数等）作为亲和力评价函数，而对于组合优化问题或实际应用中更为复杂的优化问题，则需要具体问题具体分析。
2.抗体浓度评价算子
抗体浓度（Density）表征抗体种群多样性的好坏。抗体浓度过高意味着种群中非常类似的抗体个体大量存在，不利于全局优化。因此，优化算法中应对浓度过高的个体进行抑制以保证抗体的多样性。抗体 X i 的浓度通常定义为
式中，NP为抗体种群数量； S （ X i ， X j ）为抗体 X i 与抗体 X j 之间的相似度。抗体之间的相似度可利用抗体之间的距离来计算：
式中， d （ X i ， X j ）为抗体 X i 与抗体 X j 之间的距离；δ为距离阈值。
根据抗体编码形式的不同，两个抗体个体之间的常用距离包括欧氏距离（Euclidean Distance）、汉明距离（Hamming Distance）、曼哈顿距离（Manhattan Distance），计算公式分别为
式中， x i，n 和 x j，n 分别为抗体 X i 和抗体 X j 的第 n 维分量； N 为抗体编码长度。
3.激励度计算算子
抗体激励度是免疫选择算子选取优质抗体的重要依据，综合考虑了抗体亲和力和抗体浓度的影响，通常亲和力大而浓度低的抗体应得到较大的激励度。式（4-6）和式（4-7）给出了利用抗体亲和力和抗体浓度通过简单数学运算得到抗体激励度的计算方法：
式中，sim（ X i ）为抗体 X i 的激励度；aff（ X i ）为抗体 X i 的亲和力；den（ X i ）为抗体 X i 的浓度； a 、 b 为实系数，可以根据实际情况确定。
4.免疫选择算子
免疫选择算子是根据激励度选择一定数量的父辈抗体进入下一步免疫操作。在当代抗体种群中，激励度高的抗体综合质量更好，在搜索空间中价值更高，更有可能被选中获得进行下一步免疫操作的机会。具体选择方法可依据激励度由大到小对抗体排序，按照一定的选择比例，从种群中选取排序靠前的部分抗体。
5.克隆扩增算子
克隆（Clone）扩增算子是将免疫选择算子选中的抗体个体进行复制，形成一个克隆子群。抗体克隆数目既可以设定为常数，也可以设定为动态值。如果设定为常数，则被选中的抗体都具有相同的克隆倍数。如果要使亲和力大的个体具有较大的克隆倍数，而亲和力小的个体具有较小的克隆倍数，可以把抗体克隆倍数设计成与其亲和力成正相关的关系：
式中， K 为免疫选择算子选中的抗体数量； N c 为抗体克隆总倍数；aff（ X i ）为抗体 X i 的亲和力； M i 为抗体 X i 的克隆倍数；floor(·)表示沿-∞方向取整。
此种设计方法相当于将总克隆倍数依据抗体的亲和力按比例进行分配。需要注意，参数选择应该至少保证每个抗体的克隆数目不小于1，不能使克隆扩增算子失去意义。
6.克隆变异算子
克隆变异算子是对克隆子群中的个体进行变异操作，产生新抗体。针对不同的编码方式，克隆变异算子常常采用不同的变异方式。
（1）实数编码抗体的变异算子。实数编码抗体的变异方式通常是在原抗体向量上施加扰动，使其偏离原来的位置，得到新抗体，实现在原抗体邻域的局部搜索。实数编码抗体的克隆变异算子可以描述为
式中， x i ， n ， m 为抗体 X i 第 m 个克隆个体的第 n 维分量； K 为被免疫选择算子选中进行克隆的抗体数量； N 为抗体编码长度； M i 为抗体 X i 的克隆倍数；rand和rand 1 均为均匀分布随机数，rand∈[0，1]，rand 1 ∈[0，1]；Step为变异步长； P m 为克隆变异概率。
这里变异步长既可以采用固定值，也可以设计成根据进化代数自适应调整的动态值。同样，克隆变异概率可以采用固定值，也可以设计成与亲和力成反比例关系，即亲和力较大的个体采用较小的克隆变异概率，有利于防止优质抗体遭到破坏；亲和力较小的个体采用较大的克隆变异概率，有利于找到更多的优质抗体。根据需要，对克隆变异算子产生的新抗体进行边界条件处理。
（2）离散编码抗体的变异算子。对采用二进制编码的抗体，其变异方式通常是从原抗体位串中随机选取一个或几个码位，改变码位的取值（取反、倒序等）得到新抗体。
克隆扩增算子和克隆变异算子，并称为克隆算子，其中克隆倍数和变异方式对算法性能有很大影响。克隆算子实质是在被克隆抗体对应解的附近，通过克隆操作和变异操作产生了一个克隆变异子群，能够提高抗体的多样性，扩大搜索范围，提高算法的搜索能力。
7.克隆抑制算子
克隆抑制算子是对经过克隆变异后的抗体进行再选择，保留优质抗体进入下一代抗体种群。选择方法可以采用贪婪竞争选择方法和群体竞争选择方法。
（1）贪婪竞争选择方法。将被克隆父辈抗体与克隆变异操作产生的新生抗体群共同形成一个临时抗体集合，只选择其中最优抗体来替换被克隆个体，淘汰其他抗体。由于临时抗体集合中包含了被克隆父辈抗体，因此该方法在算法进化中隐含采用了最优抗体保留策略，但也容易过早淘汰掉一些优质抗体。
（2）群体竞争选择方法。将所有参与克隆复制的父辈抗体和所有克隆变异产生的新抗体组成一个临时抗体集合，从中选择与父辈抗体数量相同的优质抗体。该方法有利于保留优质抗体，能够加快收敛速度，但也容易出现“早熟”现象。
8.种群刷新算子
种群刷新算子是对原种群中未参与免疫操作的那些较差抗体进行刷新。通常用随机产生新抗体的方法予以替换，再与通过免疫操作产生的新抗体一起形成下一代抗体种群。
人工免疫算法是模拟生物免疫系统功能原理，结合进化理论和遗传学说，人工构造出的一种智能优化算法，采用群体搜索策略，通过迭代计算，能够以较大概率获得问题的最优解。人工免疫算法具有自适应性、随机性、并行性、种群多样性、全局收敛性等优点，是解决复杂问题的自适应智能系统，主要包括以下特点：
（1）全局搜索能力。人工免疫算法是一种具有全局搜索能力的优化算法，在进化迭代计算过程中对优质抗体克隆变异不断产生新抗体，探索可行解的新区域，通过克隆抑制算子和种群刷新算子保证算法能够逐步搜索到全局最优解。
（2）抗体多样性保持机制。人工免疫算法不是单纯地把亲和力作为选择抗体的唯一标准，而是同时考虑了抗体浓度这一重要因素的影响。抑制浓度高的抗体，使抗体种群具有较好的多样性，也保证了算法的全局收敛性。
（3）适应性和鲁棒性强。人工免疫算法对求解问题的要求不高，对参数设置和初始解的依赖性不强，具有很强的适应性和鲁棒性。算法利用自身免疫操作和进化机制，即使种群起步于劣质解，往往最终也可以搜索到较为满意的全局最优解。
（4）并行分布式搜索机制。人工免疫算法不需要集中控制，可以实现多进程的并行处理。在搜索到问题最优解的同时，可以得到问题的多个次优解。