ai算法强化的能力（多目标免疫算法综述）

ai算法强化的能力（多目标免疫算法综述）1.1 模拟克隆选择原理的多目标免疫算法在实际问题中，遇到具有多个目标冲突的优化问题是十分常见的。通常情况下，将具有两个或两个以上冲突目标的优化问题称为多目标优化问题 (MOPs)。由于没有一个全局 PS 可以同时优化所有的冲突目标，因此，求解多目标优化问题的主要目的是寻找一组 PS，这组解能包含所有冲突目标之间的最优权衡。1999 年，J. Yoo 等首次将生物免疫系统中抗体 - 抗原亲和的概念应用到标准遗传算法的适应度分配机制中。该文指出，虽然遗传算法在解决混合离散、连续和整数设计变量的问题时表现出一定优势，但是相较于遗传算法，免疫算法具备生物免疫系统可以产生多种特异性抗体的特性，该特性被证明是一种有效生成 Pareto-Edgeworth 端面有效的途径。因此，这也被视为将免疫算法应用到解决多目标优化问题的首次尝试。随后，为了提升多目标免疫算法解决多目标优化问题时的性能，大量的多目标

摘 要

多目标免疫算法具备免疫系统中抗体克隆选择、抗原自动识别等特性，因此成为了继进化算法后，又一个多目标优化领域的研究热点。根据待解决问题类型，本文将多目标免疫算法分成用于求解多目标优化问题的免疫算法、用于求解动态多目标优化问题的免疫算法，以及用于求解约束优化问题的免疫算法三大类，详细地阐述了每个算法的特点、原理和设计思想，并介绍当前多目标免疫算法存在的不足和未来发展的趋势。

关键字

多目标优化；免疫算法；克隆选择；约束优化；动态优化

0 引言

遗传算法是多目标优化领域内最为常见的一种启发式算法，它是模拟达尔文生物进化论自然选择和遗传学原理的计算模型，即通过模拟大自然界中自然进化过程搜索 Pareto set (PS)的方法。由于遗传算法能快速地、准确地找到较好的优化结果，因此，其被广泛地应用在组合优化、机器学习和人工智能等领域。然而，对于遗传算法中的两个主要遗传算子来说，它们都是在一定发生概率的条件下，随机地、没有指导性地进行迭代搜索。因此，遗传算法在为种群中每个个体提供进化机会的同时，可能会出现退化现象。另外，由于遗传算法中交叉和变异操作算子是相对固定的，因此，这将导致遗传算法在求解优化问题时灵活程度较小。针对遗传算法存在的缺陷，许多学者将免疫概念和理论应用到遗传算法中，即在保留了遗传算法原有优良特性的前提下，借助免疫原理有选择、有目的地利用待求解问题中的一些特征信息或知识来抑制其优化过程中出现的退化现象，这种算法称为免疫算法（IA）。

1 求解多目标优化问题的免疫算法综述

在实际问题中，遇到具有多个目标冲突的优化问题是十分常见的。通常情况下，将具有两个或两个以上冲突目标的优化问题称为多目标优化问题 (MOPs)。由于没有一个全局 PS 可以同时优化所有的冲突目标，因此，求解多目标优化问题的主要目的是寻找一组 PS，这组解能包含所有冲突目标之间的最优权衡。1999 年，J. Yoo 等首次将生物免疫系统中抗体 - 抗原亲和的概念应用到标准遗传算法的适应度分配机制中。该文指出，虽然遗传算法在解决混合离散、连续和整数设计变量的问题时表现出一定优势，但是相较于遗传算法，免疫算法具备生物免疫系统可以产生多种特异性抗体的特性，该特性被证明是一种有效生成 Pareto-Edgeworth 端面有效的途径。因此，这也被视为将免疫算法应用到解决多目标优化问题的首次尝试。随后，为了提升多目标免疫算法解决多目标优化问题时的性能，大量的多目标免疫算法相继提出。根据算法的设计原理，绝大多数现存的用于求解多目标优化问题的免疫算法主要分为三大类，依次是基于克隆选择机制的多目标免疫算法、基于免疫网络原理的多目标免疫算法，以及将其他启发式操作算子嵌入到免疫算法中的多目标免疫算法。

1.1 模拟克隆选择原理的多目标免疫算法

在生物免疫系统里，克隆选择原理的基本思想是只有能识别抗原的细胞才能进行扩增，即只有这些能识别抗原的细胞能被选择并保留下来；反之，那些不能识别抗原的细胞不能存活在生物免疫系统内。因此，受到生物免疫系统中的克隆选择原理的启发，一系列模拟克隆选择原理的多目标免疫算法相继提出，并在处理不同类型的多目标优化问题时，展现了一定的优势和特点。类似于生物免疫系统，在多目标免疫算法的克隆选择策略中，根据种群中个体的性能表现，只有对种群性能的提升有促进作用的个体才能被保留，并被选择成为克隆父代。从而达到提升整个种群性能的目的。

2008 年，公茂果等首次提出一种基于非支配邻居选择的多目标免疫算法 NNIA，根据算法NNIA 中提出的克隆选择机制，种群中只有少数的、非支配的个体将被选择进行克隆操作。另外，在算法 NNIA 中首次提出了基于种群拥挤度距离的按比例克隆策略，即根据种群中个体对应的拥挤度距离进行克隆数目的分配。种群拥挤度距离越大的个体，其克隆数目也越多。因此，基于拥挤度距离的按比例克隆策略将更多地关注种群中较为稀疏的区域，以此来增强整个种群的分布。随后，国内外学者在此基础上相继提出了许多新颖的基于克隆选择原理的多目标免疫算法。

针对免疫算法在保持种群多样性的能力不足、容易陷入局部最优的问题，许多新颖的免疫算法从种群的角度来增强算法保持多样性的能力。例如，朱庆灵等设计了一个动态克隆种群策略，即在进化过程中，克隆种群的大小将随着外部存档的状态变化而改变。当外部存档达到饱和状态时，克隆种群的大小将会减小，这样能节省一部分的计算资源；相反，克隆种群大小将会增大，这样能产生更多的优秀克隆个体，从而提升整个种群的多样性。徐建伟等设计了一种基于多种群的多目标免疫算法MOIA-MP，通过不同子种群之间优秀个体的交换信息，提高种群的多样性，从而解决传统多目标免疫算法容易陷入局部最优的问题。万青等针对免疫算法在克隆增殖的过程中，部分抗体会逐渐占据优势，从而导致整个种群陷入局部优化的问题，提出了一种改进的多抗体集自适应免疫算法 AIAMA。翟志波等将局部搜索能力较强的克隆选择和全局搜索能力较强的教与学优化策略相结合，提出了一种基于双种群策略的算法 MTLBO-ICA，通过双种群的设计，增强免疫算法在种群多样性保持上的能力。

由于传统的基于拥挤度距离采用的直线距离公式不能很好地反映 Pareto 端面拐弯处的拥挤程度和弯曲程度，即不能准确反映拐弯处邻域内的拥挤度信息，从而会出现因部分空间信息缺失而导致的解集分布不均匀的问题。针对这类现象，马元峰等提出了一种基于动态拥挤度距离的混合多目标免疫优化算法 DHMOP。首先，算法按照拥挤度距离进行降序排序，然后一次性淘汰拥挤度距离较小的个体；在传统的拥挤度距离基础上，其引入了基于相邻拥挤度距离的标准差指标，以此来反映各维度目标拥挤度距离的差异程度。另外，由于基于信息熵的多目标免疫算法需要包含信息熵、抗体相似度和抗体浓度等大量计算，导致运行效率非常慢。针对这一现象，郑日荣等提出了一种全新的判断抗体之间相似度方法，避免了信息熵等相关指标的大量计算，从而提高了免疫算法的运行速度。类似的，算法 DBAIA 和DBAIA-m 中均使用欧式距离代替信息熵来反映抗体之间的多样性。邹锐等提出了一种基于双重阈值检测的自适应人工免疫算法，双重阈值包括抗原亲和度阈值和抗体亲和度阈值。当抗体的抗原亲和度大于抗原亲和度阈值时，则计算该抗体和记忆库中所有抗体的亲和度；当且仅当两个抗体之间的亲和度小于抗原亲和度阈值时，则亲和度较高的抗体入库，亲和度较低的抗体出库。通过这种双重阈值检测的自适应方法，实现了记忆库的自动更新，从而保证了记忆库中抗体的多样性和优越性。算法 AGMIMOEA 提出了一种基于自适应网格策略的多目标免疫算法，其中，自适应网格方法中的网格边界是动态的，会根据种群中个体分布的情况进行相应调整。若新产生的子代落在网格边界外但属于非支配解，则调整边界将新的个体纳入到该网格内，以保证优秀的个体能保留下来，从而提高整个种群的分布。为了提升多目标免疫算法在解决复杂多目标优化问题时的性能，算法 MOIADCSS 使用基于权重的聚合函数值提升度来选择能进行克隆的个体，该策略能够增强免疫算法保持多样性的能力，从而提升了免疫算法解决复杂多目标优化问题时的性能。

1.2 基于免疫网络原理的多目标免疫算法

1974 年，N.K. Jeme 首次提出免疫网络的基本模型。该模型指出免疫系统是由细胞分子调整网络所构成，而这些细胞即使在没有抗原的情况下，也是能实现相互识别的。同时，该模型还指出淋巴细胞在抗原和抗体相互作用下实现动态联系，即淋巴细胞所产生的抗体在一定程度上也能抑制其他淋巴细胞的作用。1996年，Hajela 首次将免疫网络原理应用到多目标优化领域。2002 年，Castro 提出了一种离散型免疫网络模型，在该免疫网络系统内，根据欧式距离来进行抗体之间的识别，其中距离越近，意味着两个抗体之间的相似性也越大。当免疫网络系统达到相对稳定的状态后，距离较近的抗体将从网络中去掉并引入新产生的优秀抗体进行替代。通过引入这种离散型的网络模型，改善了整个免疫网络系统中抗体的分布。实验结果表明，这种基于离散型免疫网络的算法计算规模相对于一般的免疫算法要小 5 倍，大大节省了计算资源和计算成本。在此基础上，越来越多基于免疫网络原理的多目标免疫算法相继提出，并用于解决各类不同的优化问题，同时也表现出了一定的优势。针对多目标优化问题，利用人工免疫系统的模拟退火策略和免疫优势，R.C. Chen 提出了一种模拟退火免疫优势算法 SAIA。首先，算法 SAIA 将在每个时刻的所有抗体分为活性抗体和“冬眠”抗体两类。其中，利用克隆增殖和重组增强对活性抗体的局部搜索，而“冬眠”抗体当前是没有用处，但在随后可以被激活并利用。因此，这种策略搜索可以有效地充分利用空间中的所有抗体。

1.3 嵌入其他启发式操作算子的多目标免疫算法

近些年，许多研究学者将研究重心放在了如何利用其他启发式操作算子来提升免疫算法的全局搜索能力上来。在免疫克隆算法优化的进程中，通过引入一些有利于种群扰动，增强全局搜索能力的启发式操作算子，从而克服了传统免疫算法在解决优化问题所面临的一些瓶颈和困难。

（1）与聚类方法结合的免疫算法

算法 KIFCM-IMOIA 提出了一种基于核函数直觉模糊 C 均值聚类的多目标免疫算法。首先，为了提高算法处理噪声干扰的能力，算法KIFCM-IMOIA 将核函数和直觉模糊熵引入到目标函数中；然后，为了防止算法陷入局部最优，在算法中设计了一种基于网格的克隆选择策略的多目标免疫算法（IMOIA），通过基于网格的克隆选择策略代替了传统基于拥挤度距离的策略来克服免疫算法容易陷入局部最优的问题。算法 NCAIA 运用了小生境技术和聚类分析策略来解决免疫算法存在的早熟、后期收敛速度较慢的问题。首先，嵌入了进化标记的小生境技术能有效地保持种群多样性，避免了早熟收敛的现象；采用进化标记的种群能加速整个算法的收敛速度，避免了免疫算法后期收敛速度较慢的问题。其次，聚类分析技术的运用能使种群在各极点附近形成一个聚类区域，然后在不同的聚类区域采用趋同算子和异化算子进行搜索，从而保证了算法在全局搜索时的速度和精度。

（2）与差分进化算子结合的免疫算法

算法 ADE-MOIA 将差分进化算子与多目标免疫算法相结合，使算法不仅具备免疫算法的优势，同时还具备了差分进化较强的扰动能力，从而弥补了免疫算法全局搜索能力不足的缺陷。算法 AQCCSA 提出了一种自适应量子交叉算子，随着进化进程的推进，算子将自适应做出相应的改变。类似，算法 AIMA 则将整个进化过程分成了三个进化时期，并相应地设计了三种具有不同扰动能力的差分进化算子，来满足不同进化阶段对于种群多样性和收敛速度不同的需求。通过分阶段采用不同特性的操作算子，实现了算法在进化过程中整个种群多样性和收敛性的动态平衡。

（3）基于多种群协作的免疫算法

为了提升免疫算法的全局优化能力并降低计算复杂度，郭忠全等设计了一种基于多种群、多方法协作的免疫进化算法 MCIEA。首先，由于抗体之间存在差异性，算法 MCIEA 将抗体种群分别划分成精英种群、普通种群和劣等种群，并针对不同种群内抗体的特性，在优化的过程中使用不同的操作算子来增强免疫算法的全局搜索能力。为了更好地解决免疫算法存在的收敛速度较慢，以及全局搜索能力较弱等问题，赵伟等提出一种将最速下降法和传统免疫克隆算法结合的免疫算法，傅龙天等提出了一种高斯变异和免疫克隆算子相结合的免疫算法。针对复杂多目标优化问题，算法 HEIA 设计了一种混合多目标免疫进化算法的框架。在该框架中，不同的子种群采用不同的进化策略，从而提升了算法解决复杂多目标优化问题的能力。算法 DMMO 设计了一种双进化模型，即双进化模型同时进化并分别用于提升算法收敛速度和种群的多样性。

2 求解 DMOP 的免疫算法综述

不同于多目标优化问题（MOP）其目标函数等因素是恒定不变的，DMOP 的目标函数、约束条件和相关参数都会随着时间动态变化。因此，算法在解决 DMOP 时，不仅要能追踪到PS，还要具备较强的快速响应环境变化的能力。2004 年 Farina. M 指出，根据问题的 PS 和 PF随着时间动态变化的不同组合，可以将 DMOP分成以下四类：① PS 改变，PF 不变；② PS 改变，PF 改变；③ PS 不变，PF 改变；④ PS 不变，PF 不变。

对于 DMOP 而言，其主要困难在于目标函数、约束条件和相关问题参数是随着时间不断变化的。想要有效地解决这类动态优化问题，一般情况下需要解决好以下两点：① 当环境发生变化时，算法必须快速地检测到环境的变化并且做出有效的响应；② 当环境未发生改变时，算法需要尽可能快地追踪到当前环境下的PS。近些年，国内外许多学者将研究重点放在DMOP 的求解上，由于免疫系统具有自动识别、记忆功能，因此免疫算法成为研究学者们用于解决动态优化问题常见的算法之一。

算法 CCSA 提出了一种基于聚类克隆选择策略的免疫算法。首先，根据空间的位置将种群划分成多个类；然后，每个类使用一种基于学习的克隆选择策略独立进化。另外，为了有效地跟踪环境的变化，算法 CCSA 还引入了记忆存储机制，即将历史搜索的信息存储起来，这样能使算法对环境的变化做出及时的应对。算法 DMOIAS 利用抗体被控度和浓度作为计算抗体间亲和度的指标。同时，在算法 DMOIAS 中引入了环境记忆选择池来保存种群中优秀抗体，从而提高了算法响应环境变化的能力。陈善龙等设计了一种环境识别的免疫算子来检测当前的进化环境，若当前环境为相似或相同的环境，则利用已有的历史信息，从而加快整个免疫应答的过程，提高了整个免疫算法的执行效率。

钱淑渠等提出了一种基于模拟退火选择的动态免疫算法 DIASA。首先，种群中抗体的亲和力将随着进化而变化；其次，算法 DIASA 根据动态突变、突变概率和抗体浓度因素，将抗体分成了可行抗体和不可行抗体，而对于不可行抗体将按照价值密度进行贪婪修正。为了更好地保持 Pareto 最优端面的多样性，算法 ICCoA 在全局搜索中引入了协同进化原理，同时设计了一种协同进化的竞争与合作操作算子，来进一步提高种群内个体的分布性和多样性。

3 求解约束多目标优化问题的免疫算法综述

在许多的现实工程优化领域，约束优化问题 (CMOP) 是十分常见的。所谓的约束优化问题指的是包涵许多条件约束的优化问题，而往往这些条件的限制给问题的优化造成了极大的困难。通常情况下，约束优化问题中的约束条件涵盖了决策变量上下界的约束、等式或不等式的约束等。在约束条件下，可以将解分为可行解和不可行解。其中，满足所有约束条件的解是可行解，而所有的可行解组成可行域；不满足任意一个约束条件的解被称为不可行解，所有的不可行解组成不可行域。

不同于普通的多目标优化问题，由于约束条件的存在，将决策变量的搜索空间划分成了可行域和不可行域两个部分。因此，如何处理好这一类带有限制条件的约束优化问题，也成为了近期研究热点。近些年，许多的研究学者提出了多种约束处理的方法。其中，免疫算法因具有免疫记忆、克隆选择等特性，在解决带有约束条件的优化问题时，展现了其特有的优势，因此也成为了解决约束优化问题常用的方法之一。

为了解决免疫算法在保持种群多样性能力不足，容易陷入局部最优等问题，算法CNMOIA 设计了一种与多样性相关的约束处理策略来加速整个算法的收敛速度。为了提升算法在种群分布性保持的能力，算法 IHIA 设计了一种基于多种操作算子的选择机制。其中，精英变异算子是以产生抗体在亲和度的突变来实现局部搜索，从而增强了局部区域搜索的能力，加速了整个算法的收敛速度。而设计局部混沌优化算子的目的是用来判断算法是否陷入了局部收敛。若算法已出现局部收敛，则抗体记忆库将执行该混沌优化算子来跳出局部收敛。尚荣华等分别在算法 ICMOA 和算法 IMCCMO中运用了将约束条件转化成一个优化目标的思想，通过这种转化策略，将一个约束优化问题转化成为了一个传统的多目标优化问题；此外，为了保证在种群优化的过程中，抗体解集能从可行域内部，以及不可行域的边缘向约束最优Pareto 端面不断逼近，在算法中引入了免疫克隆和免疫系统的记忆机制，使得抗体的进化和记忆抗单元的进化能并行进行，从而能更好地实现抗体间的相互协作。针对动态约束优化问题，算法 DMIOA 设计了一种随机约束选择算子来提高算法处理约束的能力；同时，通过环境识别算子来自适应判断当前环境的变化，根据环境识别的结果，选择使用相应新环境下所产生的初始抗体种群。算法 CDMOIAs 则根据抗体浓度将种群中抗体分为优秀抗体和普通抗体，其中对优秀抗体进行克隆操作，而将其他抗体分离成多个子种群，并进行独立的进化。

4 结束语

本文首先对多目标免疫算法进行了详细的介绍与总结，并按照求解优化问题类型的不同，将免疫算法主要分成三大类：① 用于求解多目标优化问题的免疫算法；② 用于求解 DMOP 的免疫算法；③ 用于求解约束多目标优化问题的免疫算法。然后，依次介绍了每个多目标免疫算法的原理和创新。最后，分别对算法在解决各类优化问题时的优势和存在的不足进行了阐述。

近些年，免疫算法在多目标优化领域应用广泛，并展现了其特有的优势。但是，随着优化目标维度的增加，传统免疫算法保持种群多样性能力较差的缺陷进一步凸显。因此，如何提高免疫算法在解决超多目标优化问题的能力，成为了未来一大研究难题。由于在现实生活中，大量的优化问题往往包含了三个或三个以上的相互冲突的目标函数，因此，研究免疫算法解决超多目标优化问题具有极强的现实意义。提升免疫算法在高维的目标空间中保持多样性的能力，从而使得免疫算法能有效地解决超多目标优化问题，这将进一步拓展免疫算法在实际工程优化领域的应用场景。现将免疫算法未来一些仍需提升、研究的方向总结如下：① 提升免疫算法在高维空间中求解的能力；② 提升免疫算法在复杂的大规模问题中的应用能力；③ 提升免疫算法求解基于偏好的多目标优化问题的能力；④ 免疫算法与高斯回归等数学模型结合，从而解决各类优化问题；⑤ 免疫算法在机器学习、深度学习等领域内参数优化的应用；⑥ 免疫算法在未来智能生活、智能城市中的应用。

（参考文献略）

选自《中国人工智能学会通讯》

2021年第11卷第3期

免疫计算专题