基于环境策略的免疫克隆约束多目标进化算法
徐志平+许峰
摘要：在常规免疫克隆约束多目标进化算法中，优秀不可行解易被淘汰，且无法直接学习进化经验。针对该问题，提出了基于环境策略的免疫克隆约束多目标进化算法。其基本思想是，在约束处理前，通过环境策略用Pareto支配形成初始抗体群，利用一个精英种群对初始抗体群进行存储；约束处理后，用环境策略变异替换克隆变异。数值实验结果表明，新算法不仅可以有效地处理约束条件，而且解的多样性和均匀性均得到一定程度改进。
关键词：多目标进化算法；环境策略；免疫克隆；约束处理
DOIDOI：10.11907/rjdk.172197
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001005604
Abstract：Constrained multiobjective optimization， the excellent infeasible solution was easy to be eliminated， the classic algorithm didn′t directly learn evolutionary experience. In this paper， Immune clonal constrained multiobjective optimization algorithm based on environmental strategy is proposed. The basic idea of method is that environmental strategy is introduced， on one hand through the environmental strategy Pareto domination to form initial antibody group and to store the initial antibody group by an elite population before constraint handling， on the other hand thought environmental strategy Mutation instead of clonal Mutation after constraint handling. According to numerical experiments， the results show that the new algorithm not only has perfect diversity and uniformity， but also convergence has been improved comparing with the classical algorithm.
Key Words：constrained multipleobjective； environmental strategy； immune clone； constraint handling
0引言
多目标优化约束处理技术有：惩罚函数法，通过罚因子对违反约束的个体施以惩罚，但罚因子难以选取；区分可行解与不可行解法，通过可行与不可行准则进行优劣判断，不利于保留不可行精英解；多目标法，将约束条件转换成目标函数，但该方法加大了计算量[1]。
免疫算法已成功应用于数据挖掘、计算机安全、异常检测、优化等领域。将免疫算法用于求解约束多目标优化成为近年来的研究热点，一些经典算法相继被提出。如Coello Coello等[2]提出MultiObjective Immune System Algorithm（MISA）；Cutello等[3]基于免疫操作对PAES进行改进，提出IPAES算法；Freschi等[4]提出Vector Artificial Immune Systems（VAIS）；Jiao和Gong等[56]提出免疫優势克隆多目标算法和非支配邻域免疫算法（NNIA）。免疫克隆算法也存在不足，如不可行精英解不宜保留，无法直接学习进化经验等[78]。针对上述不足，本文引入环境策略，对免疫克隆多目标优化算法（Immune Clone Multiobjective Optimization Algorithm，ICMOA）进行改进，使新算法能够充分利用不可行精英解，学习进化经验。
1约束多目标优化相关概念
1.1约束多目标优化问题
约束多目标优化问题可表述为：
5结语
本文针对经典免疫克隆约束多目标进化算法的不足，引入环境策略，提出基于环境策略的免疫克隆约束多目标进化算法。实施环境策略Pareto支配选择，不仅可以选择可行非支配解，而且可以充分利用不可行精英解。实施环境策略变异，使新算法具备学习进化经验的能力。通过数值实验和量化度量准则，对比结果表明，新算法解集的质量得到明显改进。然而，在约束多目标进化算法中，约束处理技术和可行支配解及非可行非支配解的选取等仍是亟待解决的问题。根据不同问题选取不同策略，或根据不同问题自适应选取不同约束处理技术，可能是今后的重点研究方向。
参考文献：
[1]王勇，蔡自兴，周育人，等.约束优化进化算法[J].软件学报，2009，20（1）：1129.
[2]COELLO COELLO CA， CORTES NC. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines，2005，6（2）：163190.
[3]CUTELLO V，NARZISI G，NICOSIA G.A class of Pareto archived evolution strategy algorithms using immune inspired operators for abinitio protein structure prediction[C].Proc.of the 3`d European Workshop on Evolutionary Computation and Bioinformatics， EvoWorkshops 2005.Berlin： SpringerVerlag，2005：5463.
[4]RESCHI F， REPETTO M.An artificial immune network for multiobjective optimization[J]. Engineering Optimization，2006，38（8）：975996.
[5]JIAO LC， GONG MG， SHANG RH， et al.Clonal selection with immune dominance and energy based muftiobjective optimization[C].Proc. of the 3rd Int1 Conf. on Evolutionary MuftiCriterion Optimization， Berlin： SpringerVerlag，2005：474489.
[6]GONG MG， JIAO LC， DU HF， et al.Multi objective immune nondominated neighborbased selected algorithm[J].Evolutionary Computation，2008，16（2）：225255.
[7]劉若辰，杜海峰，焦李成.基于柯西变异的免疫单克隆策略[J].西安电子科技大学学报，2004，31（4）：551556.
[8]VINCENZO CUTELLO. An immune algorithm for protein structure prediction on lattice models[J]. IEEE Transactions on Evolutionary Computation，2007，11（1）：101117.
[9]尚荣华，焦李成，马文萍.免疫克隆多目标优化算法求解约束优化问题[J].软件学报，2008，19（11）：29432956.
[10]杨虎，许峰.基于聚集密度的粒子群多目标优化算法[J].计算机工程与应用，2013，49（17）：190194.
[11]尚荣华，焦李成，马文萍.免疫克隆算法求解动态多目标优化问题[J].软件学报，2007，18（11）：27002711.
[12]徐海黎，朱志送，王恒，等.环境变异免疫克隆算法解决有约束优化问题[J].系统仿真报，2011，23（11）：24122416.
[13]VAN VELDHUIZEN DA， LAMONT GB. On measuring multiobjective evolutionary algorithm performance [C].Proc. of the Congress on Evolutionary Computation.Piscataway： IEEE Press，2000：204211.
[14]GOH CK， TAN KC. An investigation on noisy environments in evolutionary multiobjective optimization[J]. IEEE Trans. on Evolutionary Computation，2007，11（3）：354381.
[15]XIAO HS， ZU JW. A new constrained multiobjective optimization algorithm based on artificial immune systems[C].Proc.of the 2007 IEEE Intl Conf.on Mechatronics and Automation，2007：31223127.
（责任编辑：黄健）
摘要：在常规免疫克隆约束多目标进化算法中，优秀不可行解易被淘汰，且无法直接学习进化经验。针对该问题，提出了基于环境策略的免疫克隆约束多目标进化算法。其基本思想是，在约束处理前，通过环境策略用Pareto支配形成初始抗体群，利用一个精英种群对初始抗体群进行存储；约束处理后，用环境策略变异替换克隆变异。数值实验结果表明，新算法不仅可以有效地处理约束条件，而且解的多样性和均匀性均得到一定程度改进。
关键词：多目标进化算法；环境策略；免疫克隆；约束处理
DOIDOI：10.11907/rjdk.172197
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001005604
Abstract：Constrained multiobjective optimization， the excellent infeasible solution was easy to be eliminated， the classic algorithm didn′t directly learn evolutionary experience. In this paper， Immune clonal constrained multiobjective optimization algorithm based on environmental strategy is proposed. The basic idea of method is that environmental strategy is introduced， on one hand through the environmental strategy Pareto domination to form initial antibody group and to store the initial antibody group by an elite population before constraint handling， on the other hand thought environmental strategy Mutation instead of clonal Mutation after constraint handling. According to numerical experiments， the results show that the new algorithm not only has perfect diversity and uniformity， but also convergence has been improved comparing with the classical algorithm.
Key Words：constrained multipleobjective； environmental strategy； immune clone； constraint handling
0引言
多目标优化约束处理技术有：惩罚函数法，通过罚因子对违反约束的个体施以惩罚，但罚因子难以选取；区分可行解与不可行解法，通过可行与不可行准则进行优劣判断，不利于保留不可行精英解；多目标法，将约束条件转换成目标函数，但该方法加大了计算量[1]。
免疫算法已成功应用于数据挖掘、计算机安全、异常检测、优化等领域。将免疫算法用于求解约束多目标优化成为近年来的研究热点，一些经典算法相继被提出。如Coello Coello等[2]提出MultiObjective Immune System Algorithm（MISA）；Cutello等[3]基于免疫操作对PAES进行改进，提出IPAES算法；Freschi等[4]提出Vector Artificial Immune Systems（VAIS）；Jiao和Gong等[56]提出免疫優势克隆多目标算法和非支配邻域免疫算法（NNIA）。免疫克隆算法也存在不足，如不可行精英解不宜保留，无法直接学习进化经验等[78]。针对上述不足，本文引入环境策略，对免疫克隆多目标优化算法（Immune Clone Multiobjective Optimization Algorithm，ICMOA）进行改进，使新算法能够充分利用不可行精英解，学习进化经验。
1约束多目标优化相关概念
1.1约束多目标优化问题
约束多目标优化问题可表述为：
5结语
本文针对经典免疫克隆约束多目标进化算法的不足，引入环境策略，提出基于环境策略的免疫克隆约束多目标进化算法。实施环境策略Pareto支配选择，不仅可以选择可行非支配解，而且可以充分利用不可行精英解。实施环境策略变异，使新算法具备学习进化经验的能力。通过数值实验和量化度量准则，对比结果表明，新算法解集的质量得到明显改进。然而，在约束多目标进化算法中，约束处理技术和可行支配解及非可行非支配解的选取等仍是亟待解决的问题。根据不同问题选取不同策略，或根据不同问题自适应选取不同约束处理技术，可能是今后的重点研究方向。
参考文献：
[1]王勇，蔡自兴，周育人，等.约束优化进化算法[J].软件学报，2009，20（1）：1129.
[2]COELLO COELLO CA， CORTES NC. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines，2005，6（2）：163190.
[3]CUTELLO V，NARZISI G，NICOSIA G.A class of Pareto archived evolution strategy algorithms using immune inspired operators for abinitio protein structure prediction[C].Proc.of the 3`d European Workshop on Evolutionary Computation and Bioinformatics， EvoWorkshops 2005.Berlin： SpringerVerlag，2005：5463.
[4]RESCHI F， REPETTO M.An artificial immune network for multiobjective optimization[J]. Engineering Optimization，2006，38（8）：975996.
[5]JIAO LC， GONG MG， SHANG RH， et al.Clonal selection with immune dominance and energy based muftiobjective optimization[C].Proc. of the 3rd Int1 Conf. on Evolutionary MuftiCriterion Optimization， Berlin： SpringerVerlag，2005：474489.
[6]GONG MG， JIAO LC， DU HF， et al.Multi objective immune nondominated neighborbased selected algorithm[J].Evolutionary Computation，2008，16（2）：225255.
[7]劉若辰，杜海峰，焦李成.基于柯西变异的免疫单克隆策略[J].西安电子科技大学学报，2004，31（4）：551556.
[8]VINCENZO CUTELLO. An immune algorithm for protein structure prediction on lattice models[J]. IEEE Transactions on Evolutionary Computation，2007，11（1）：101117.
[9]尚荣华，焦李成，马文萍.免疫克隆多目标优化算法求解约束优化问题[J].软件学报，2008，19（11）：29432956.
[10]杨虎，许峰.基于聚集密度的粒子群多目标优化算法[J].计算机工程与应用，2013，49（17）：190194.
[11]尚荣华，焦李成，马文萍.免疫克隆算法求解动态多目标优化问题[J].软件学报，2007，18（11）：27002711.
[12]徐海黎，朱志送，王恒，等.环境变异免疫克隆算法解决有约束优化问题[J].系统仿真报，2011，23（11）：24122416.
[13]VAN VELDHUIZEN DA， LAMONT GB. On measuring multiobjective evolutionary algorithm performance [C].Proc. of the Congress on Evolutionary Computation.Piscataway： IEEE Press，2000：204211.
[14]GOH CK， TAN KC. An investigation on noisy environments in evolutionary multiobjective optimization[J]. IEEE Trans. on Evolutionary Computation，2007，11（3）：354381.
[15]XIAO HS， ZU JW. A new constrained multiobjective optimization algorithm based on artificial immune systems[C].Proc.of the 2007 IEEE Intl Conf.on Mechatronics and Automation，2007：31223127.
（责任编辑：黄健）
