基于自适应网格方法的免疫多目标进化算法
吕文鹏 许峰
摘 要：针对免疫多目标进化算法分布性欠佳的缺陷，提出一种基于自适应网格方法的免疫多目标进化算法。基本思想是：对抗体群进行免疫克隆、免疫基因和克隆选择操作后，利用自适应网格方法提高抗体群的多样性。仿真实验结果和统计指标显示，改进算法与常规免疫多目标进化算法相比较，在解的分布性方面有了较大程度的改进。
关键词：多目标进化；人工免疫；自适应网格方法；分布性
中图分类号：TP312 文献标识码：A
1 引言（Introduction）
20世纪70年代，Jerne最早建立了免疫网络的数学模型。1996年12月，人工免疫系统（Artificial Immune System，AIS）概念正式提出。其后，人工免疫算法的研究进入快速发展期。鉴于人工免疫算法天然的并行性，1998年，人工免疫算法即被引入多目标优化算法，并取得了众多成果[1]。从此以后，人工免疫多目标优化算法便一直是智能计算领域中的一个研究热点[2-5]。
早在1991年，西安交通大学的靳蕃教授就指出“免疫系统所具有的信息处理和防卫功能具有非常深远的意义”。2002年，莫宏伟出版了国内第一本人工免疫系统著作。西安电子科技大学焦李成教授领导的团队系统、全面地研究了人工免疫优化算法，并出版了专著《免疫优化计算学习与识别》。近年来，国内学者在人工免疫算法特别是人工免疫多目标优化算法及应用方面取得了一系列的成果。钱淑渠[6]和刘若辰[7]等研究了动态多目标免疫优化算法；林浒[8]等研究了适应度共享多目标优化免疫克隆算法；刘楠楠[9]较为系统地研究了克隆选择多目标优化算法；武慧虹[10]等研究了基于混沌克隆的混杂多目标免疫优化算法；王晓磊[11]研究了多目标人工免疫算法在无功优化中的应用；柴争义[12]等研究了混沌免疫多目标算法在认知引擎参数优化问题中的应用；朱思峰[13]等研究了多目标优化量子免疫算法在基站选址问题中的应用；邢志伟[14]等研究了多目标免疫优化算法在飞机滑行轨迹中的应用。
本文提出了一种基于自适应网格方法的免疫多目标优化算法（Adaptive Grid Method Immune Multi-Objective Evolution Algorithm，AGMIMOEA）。算法的设计依据是：利用自适应网格方法進一步提多目标最优解的多样性。根据对比仿真实验和统计指标，对该算法进行了性能测试。
2 人工免疫算法（Artificial immune algorithm）
常见的人工免疫算法有B细胞网络算法、免疫遗传算法、克隆选择算法、免疫规划算法等，算法的流程图如图1所示。
3 自适应网格方法（Adaptive grid method）
衡量多目标优化算法通常有收敛性、分布性、计算复杂度三个指标。网格方法是保持多目标进化种群分布性的常用方法，在PESA、PAES、MGAMOO和DMOGA等方法中，算法的设计者均以不同方式采用网格方法保持进化种群的多样性[15]。2003年，Knowles对网络方法进行了改进，提出了自适应网格方法。下面简要介绍自适应网格方法。
3.1 网络边界（Grid and boundary）
根据网格方法，对于有个目标的优化问题，需要设置有个边界的网格：下界和上界。如图2所示是一个两目标网格，共有四个边界：。
根据进化种群的规模和待优化问题的目标数，将一个网络分割成若干个小区域，称之为Hyper-Cube（HC）。将每个HC表示为，是每一维上的分割次数，通常为大于2的自然数。在图2中，。对应于每个的边界可以表示为
其中，为每一个小区域在第维上的宽度，，为第维上的域宽。
若将域宽设为，则有，从而得上边界点为，下边界点为。
3.2 个体在网格中的定位（The location of the individual
in the grid）
在网格中设置小区域的目的是判断个体是否落在小区域内。设有个体，对区域，若且，则认为个体在区域中。
在图2中，区域A中有三个个体，区域B中有一个个体，区域C中有两个个体。
在某个目标上取最小的个体称为极点。由于极点总是在端点，有利于使得进化种群具有更好的分布性，所以在选择时，通常不能丢失极点。极点的定义为
3.3 自适应网格（Adaptive grid）
自适应网格方法对一般网格方法做了下列改进：
（1）网格的边界是动态的，不是固定的；
（2）每次进化时，根据当前个体分布情况自适应地调整边界；
（3）若新个体在边界外且为非支配的，则将其入到归档集中。
4 基于自适应网格方法的免疫多目标优化算法
（Immune multi-objective evolutionary algorithm
based on adaptive grid method）
为了进一步提高常规免疫多目标优化算法的分布性，本文将自适应网格方法引入免疫多目标优化算法，基于自适应网格方法的免疫多目标进化算法的流程如下：
步骤1 种群初始化。设定初始代数，进化代数，抗体种群大小N，克隆规模大小R；初始化抗体群：
。
步骤2 对进行克隆：。
步骤3 对以概率进行免疫操作：。
步骤4 对进行选择操作：。
（1）对中的每个抗体，通过计算目标函数值，得到函数值矩阵。
（2）将划分为支配抗体群和非支配抗体群。
（3）选择非支配抗体群及相应的函数值矩阵。
步骤5 根据自适应网格方法更新，得到新的抗体群：及函数值矩阵。
步骤6 若，则输出及；否则
，返回步骤2。
5 数值实验结果（Numerical experiment results）
下面用基于自适应网格方法的免疫多目标优化算法对两个多目标测试函数Deb2和DTLZ7进行仿真计算，并将计算结果与NSGAII和常规免疫多目标进化算法（IMOEA）的计算结果进行了比较。
为了进一步定量地评测基于自适应网格方法的免疫多目标优化算法的分布性，图9和图10分别给出了NSGAII、IMOEA和AGMIMOEA的U-measure图。
图3—图10直观表明，AGMIMOEA在解的分布性和均匀性方面均明显优于NSGA II和IMOEA。
6 结论（Conclusion）
本文为了提高免疫多目标优化算法的分布性，引入了自适应网格方法。数值实验表明，改进算法可在一定程度上改善算法的分布性和均匀性。
必须指出的是，人工免疫算法理论体系尚不完善，收敛性和分布性等关键理论问题有待进一步研究。对算法的改进只能依赖对比实验，这无疑限制和阻碍了量子遗传算法的进一步研究。
参考文献（References）
[1] Coello C.A.，Crue Cort N.Solving multi-objective optimization problem using an artificial immune system[J].Genetic Programming and Evolvable Machine，2005，6：163-190.
[2] Qiuzhen Lin，Yueping Ma，Jianyong Chen.An adaptive immune-inspired multi-objective algorithm with multiple differential evolution strategies[J].Information Sciences，2018，430-431：46-64.
[3] Maria-Guadalupe Martínez-Pealoza，Efren Mezura-Montes.Immune Generalized Differential Evolution for dynamic multi-objective environments：An empirical study[J].Knowledge-Based Systems，2018，142：192-219.
[4] Zhuhong Zhang，Xiaoxia Wang，Jiaxuan Lu.Multi-objective immune genetic algorithm solving nonlinear interval-valued programming[J].Engineering Applications of Artificial Intelligence，2018，67：235-245.
[5] Bin Cao，Jianwei Zhao，Po Yang.Distributed parallel cooperative coevolutionary multi-objective large-scale immune algorithm for deployment of wireless sensor networks[J].Future Generation Computer Systems，2018，82：256-267.
[6] 錢淑渠，张著洪.动态多目标免疫优化算法及性能测试研究[J].智能系统学报，2007，2（5）：68-77.
[7] 刘若辰，马亚娟，张浪.基于预测策略的动态多目标免疫优化算法[J].计算机学报，2015，38（5）：1544-1560.
[8] 林浒，彭勇.面向多目标优化的适应度共享免疫克隆算法[J].控制理论与应用，2011，28（2）：206-214.
[9] 刘楠楠.克隆选择多目标优化算法及其应用研究[D].宁波大学，2013.
[10] 武慧虹，钱淑渠，王海英.基于混沌克隆的混杂多目标免疫优化算法[J].吉林师范大学学报，2014，1：40-46.
[11] 王晓磊.多目标人工免疫算法及其在无功优化中的应用[D].东北大学，2008.
[12] 柴争义，陈亮，朱思峰.混沌免疫多目标算法求解认知引擎参数优化问题[J].物理学报，2012，61（5）：1-7.
[13] 朱思峰，陈国强，张新刚.多目标优化量子免疫算法求解基站选址问题[J].华中科技大学学报（自然科学版），2012，40（1）：
49-53.
[14] 邢志伟，宋晓鹏，罗谦.基于多目标免疫优化的飞机滑行轨迹[J].计算机工程与设计，2016，37（5）：1224-1228.
[15] 郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.
[16] Knowles Joshus，David W Corne.Properties of an adaptive archiving algorithm for storing nondominated vectors[J].IEEE Transaction on Evolutionary Vomputation，2003，7（2）：100-115.
作者简介：
吕文鹏（1992-），男，硕士生.研究领域：进化算法.
许 峰（1963-），男，硕士，教授.研究领域：进化算法，数值计算.
摘 要：针对免疫多目标进化算法分布性欠佳的缺陷，提出一种基于自适应网格方法的免疫多目标进化算法。基本思想是：对抗体群进行免疫克隆、免疫基因和克隆选择操作后，利用自适应网格方法提高抗体群的多样性。仿真实验结果和统计指标显示，改进算法与常规免疫多目标进化算法相比较，在解的分布性方面有了较大程度的改进。
关键词：多目标进化；人工免疫；自适应网格方法；分布性
中图分类号：TP312 文献标识码：A
1 引言（Introduction）
20世纪70年代，Jerne最早建立了免疫网络的数学模型。1996年12月，人工免疫系统（Artificial Immune System，AIS）概念正式提出。其后，人工免疫算法的研究进入快速发展期。鉴于人工免疫算法天然的并行性，1998年，人工免疫算法即被引入多目标优化算法，并取得了众多成果[1]。从此以后，人工免疫多目标优化算法便一直是智能计算领域中的一个研究热点[2-5]。
早在1991年，西安交通大学的靳蕃教授就指出“免疫系统所具有的信息处理和防卫功能具有非常深远的意义”。2002年，莫宏伟出版了国内第一本人工免疫系统著作。西安电子科技大学焦李成教授领导的团队系统、全面地研究了人工免疫优化算法，并出版了专著《免疫优化计算学习与识别》。近年来，国内学者在人工免疫算法特别是人工免疫多目标优化算法及应用方面取得了一系列的成果。钱淑渠[6]和刘若辰[7]等研究了动态多目标免疫优化算法；林浒[8]等研究了适应度共享多目标优化免疫克隆算法；刘楠楠[9]较为系统地研究了克隆选择多目标优化算法；武慧虹[10]等研究了基于混沌克隆的混杂多目标免疫优化算法；王晓磊[11]研究了多目标人工免疫算法在无功优化中的应用；柴争义[12]等研究了混沌免疫多目标算法在认知引擎参数优化问题中的应用；朱思峰[13]等研究了多目标优化量子免疫算法在基站选址问题中的应用；邢志伟[14]等研究了多目标免疫优化算法在飞机滑行轨迹中的应用。
本文提出了一种基于自适应网格方法的免疫多目标优化算法（Adaptive Grid Method Immune Multi-Objective Evolution Algorithm，AGMIMOEA）。算法的设计依据是：利用自适应网格方法進一步提多目标最优解的多样性。根据对比仿真实验和统计指标，对该算法进行了性能测试。
2 人工免疫算法（Artificial immune algorithm）
常见的人工免疫算法有B细胞网络算法、免疫遗传算法、克隆选择算法、免疫规划算法等，算法的流程图如图1所示。
3 自适应网格方法（Adaptive grid method）
衡量多目标优化算法通常有收敛性、分布性、计算复杂度三个指标。网格方法是保持多目标进化种群分布性的常用方法，在PESA、PAES、MGAMOO和DMOGA等方法中，算法的设计者均以不同方式采用网格方法保持进化种群的多样性[15]。2003年，Knowles对网络方法进行了改进，提出了自适应网格方法。下面简要介绍自适应网格方法。
3.1 网络边界（Grid and boundary）
根据网格方法，对于有个目标的优化问题，需要设置有个边界的网格：下界和上界。如图2所示是一个两目标网格，共有四个边界：。
根据进化种群的规模和待优化问题的目标数，将一个网络分割成若干个小区域，称之为Hyper-Cube（HC）。将每个HC表示为，是每一维上的分割次数，通常为大于2的自然数。在图2中，。对应于每个的边界可以表示为
其中，为每一个小区域在第维上的宽度，，为第维上的域宽。
若将域宽设为，则有，从而得上边界点为，下边界点为。
3.2 个体在网格中的定位（The location of the individual
in the grid）
在网格中设置小区域的目的是判断个体是否落在小区域内。设有个体，对区域，若且，则认为个体在区域中。
在图2中，区域A中有三个个体，区域B中有一个个体，区域C中有两个个体。
在某个目标上取最小的个体称为极点。由于极点总是在端点，有利于使得进化种群具有更好的分布性，所以在选择时，通常不能丢失极点。极点的定义为
3.3 自适应网格（Adaptive grid）
自适应网格方法对一般网格方法做了下列改进：
（1）网格的边界是动态的，不是固定的；
（2）每次进化时，根据当前个体分布情况自适应地调整边界；
（3）若新个体在边界外且为非支配的，则将其入到归档集中。
4 基于自适应网格方法的免疫多目标优化算法
（Immune multi-objective evolutionary algorithm
based on adaptive grid method）
为了进一步提高常规免疫多目标优化算法的分布性，本文将自适应网格方法引入免疫多目标优化算法，基于自适应网格方法的免疫多目标进化算法的流程如下：
步骤1 种群初始化。设定初始代数，进化代数，抗体种群大小N，克隆规模大小R；初始化抗体群：
。
步骤2 对进行克隆：。
步骤3 对以概率进行免疫操作：。
步骤4 对进行选择操作：。
（1）对中的每个抗体，通过计算目标函数值，得到函数值矩阵。
（2）将划分为支配抗体群和非支配抗体群。
（3）选择非支配抗体群及相应的函数值矩阵。
步骤5 根据自适应网格方法更新，得到新的抗体群：及函数值矩阵。
步骤6 若，则输出及；否则
，返回步骤2。
5 数值实验结果（Numerical experiment results）
下面用基于自适应网格方法的免疫多目标优化算法对两个多目标测试函数Deb2和DTLZ7进行仿真计算，并将计算结果与NSGAII和常规免疫多目标进化算法（IMOEA）的计算结果进行了比较。
为了进一步定量地评测基于自适应网格方法的免疫多目标优化算法的分布性，图9和图10分别给出了NSGAII、IMOEA和AGMIMOEA的U-measure图。
图3—图10直观表明，AGMIMOEA在解的分布性和均匀性方面均明显优于NSGA II和IMOEA。
6 结论（Conclusion）
本文为了提高免疫多目标优化算法的分布性，引入了自适应网格方法。数值实验表明，改进算法可在一定程度上改善算法的分布性和均匀性。
必须指出的是，人工免疫算法理论体系尚不完善，收敛性和分布性等关键理论问题有待进一步研究。对算法的改进只能依赖对比实验，这无疑限制和阻碍了量子遗传算法的进一步研究。
参考文献（References）
[1] Coello C.A.，Crue Cort N.Solving multi-objective optimization problem using an artificial immune system[J].Genetic Programming and Evolvable Machine，2005，6：163-190.
[2] Qiuzhen Lin，Yueping Ma，Jianyong Chen.An adaptive immune-inspired multi-objective algorithm with multiple differential evolution strategies[J].Information Sciences，2018，430-431：46-64.
[3] Maria-Guadalupe Martínez-Pealoza，Efren Mezura-Montes.Immune Generalized Differential Evolution for dynamic multi-objective environments：An empirical study[J].Knowledge-Based Systems，2018，142：192-219.
[4] Zhuhong Zhang，Xiaoxia Wang，Jiaxuan Lu.Multi-objective immune genetic algorithm solving nonlinear interval-valued programming[J].Engineering Applications of Artificial Intelligence，2018，67：235-245.
[5] Bin Cao，Jianwei Zhao，Po Yang.Distributed parallel cooperative coevolutionary multi-objective large-scale immune algorithm for deployment of wireless sensor networks[J].Future Generation Computer Systems，2018，82：256-267.
[6] 錢淑渠，张著洪.动态多目标免疫优化算法及性能测试研究[J].智能系统学报，2007，2（5）：68-77.
[7] 刘若辰，马亚娟，张浪.基于预测策略的动态多目标免疫优化算法[J].计算机学报，2015，38（5）：1544-1560.
[8] 林浒，彭勇.面向多目标优化的适应度共享免疫克隆算法[J].控制理论与应用，2011，28（2）：206-214.
[9] 刘楠楠.克隆选择多目标优化算法及其应用研究[D].宁波大学，2013.
[10] 武慧虹，钱淑渠，王海英.基于混沌克隆的混杂多目标免疫优化算法[J].吉林师范大学学报，2014，1：40-46.
[11] 王晓磊.多目标人工免疫算法及其在无功优化中的应用[D].东北大学，2008.
[12] 柴争义，陈亮，朱思峰.混沌免疫多目标算法求解认知引擎参数优化问题[J].物理学报，2012，61（5）：1-7.
[13] 朱思峰，陈国强，张新刚.多目标优化量子免疫算法求解基站选址问题[J].华中科技大学学报（自然科学版），2012，40（1）：
49-53.
[14] 邢志伟，宋晓鹏，罗谦.基于多目标免疫优化的飞机滑行轨迹[J].计算机工程与设计，2016，37（5）：1224-1228.
[15] 郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.
[16] Knowles Joshus，David W Corne.Properties of an adaptive archiving algorithm for storing nondominated vectors[J].IEEE Transaction on Evolutionary Vomputation，2003，7（2）：100-115.
作者简介：
吕文鹏（1992-），男，硕士生.研究领域：进化算法.
许 峰（1963-），男，硕士，教授.研究领域：进化算法，数值计算.
