高维多目标集成算法研究综述

张江江，崔志华

(太原科技大学 计算机科学与技术学院，山西 太原 030024)

1 引言

现实生活中，所面临的许多问题受到多个因素的相互影响。因而，通常将要使那些影响因素得到尽可能优化的问题视为多目标优化问题(Multi-objective optimization problems，MOPs)。为了进行更加深入研究，MOPs定义为[1]

(1)

其中x=(x1，x2，…，xD)T是在搜索空间Ω内有界的一个D维决策向量，gi(x)和hj(x)分别表示第i个不等式和第j个等式约束；M是目标数量。值得注意的是：当目标数量为2和3时，该问题定义为MOPs；当目标数量大于3时，该问题定义为高维多目标优化问题(Many-objective optimization problems，MaOPs)[2]。假设这里给定两个决策矢量x，y∈Ω，当且仅当满足以下条件，则x帕累托支配y，记作：xy.

∀i∈{1，2，…，M}：fi(x)≤fi(y)，
∃i∈{1，2，…，M}：fi(x)

(2)

若不存在x∈Ω使得xx*，则x*∈Ω被称为帕累托最优(Pareto optimal)；f(x*)被称为Pareto最优目标矢量；通常，一个问题不同目标的潜在冲突性是其成为一个多目标优化问题的前提属性，该属性某程度上就已经决定了各个目标值无法同时获得最优结果。换言之，在令某个目标达到最优的同时，其它几个目标的性能有可能会降低，因此，只能尽最大努力使各个目标值接近最优。不同于只拥有唯一最优解的单目标优化问题，多目标优化问题的最优解是一组由众多Pareto最优目标矢量组成的Pareto最优解集(Pareto-optimal set，PS)，集合中的各个元素称为Pareto最优解。PS在目标空间中的映射称为Pareto最优前沿(Pareto-optimal front，PF)。

由于在多目标优化问题中，目标之间存在固有的冲突，没有最佳的解决方案。因此如何获得Pareto最优解集，一直是众多学者研究的问题。近年来随着进化算法(evolutionary algorithm，EA)的快速发展，它已经逐步被认为是解决多目标优化问题的有效工具。

传统的多目标优化算法已经被证明能够有效解决2个或3个目标的多目标优化问题，而在遇到实际生产生活中具有复杂特性(例如非线性，不连续性，多模态，退化和高维决策空间)的高维多目标优化问题时，这些方法将不再被适用。因此，致力于研究解决MaOPs的优化算法，毫无疑问是符合社会发展的迫切需要的命题，且具有非常重大的实际意义。然而如何获取性能高效的优化算法，这将是一项值得深入探讨的研究工程。

根据无免费午餐(No-Free Lunch，NFL)定理指出，理论上是不存在某种算法在解决所有优化问题时都优于其他算法[3]。在实践中，NFL定理表明，在解决具有不同特征的优化问题时，不可能设计出比其它所有算法性能效果都要有效的算法。然而，研究人员一直致力于开发适用于多种优化问题的通用优化算法。此外，从成千上万的候选算法中选择一个有效的算法是非常耗时的。那么有没有可能存在一种实用的算法可以处理一组不同特征的优化问题?答案是肯定的。这是因为尽管NFL告诉人们没有一种算法可以有效地解决所有可能的优化问题，但在实践中所考虑的问题一般总是待优化问题的子集。因此，若能在现有优化算法的基础上，利用已经提出的各种算子，考虑每个算子都在算法的不同时间片段的优势作用，将这些算子的一系列改进策略有机地集成起来，使其相互协调，共同作用，可以大幅提高算法性能[4]。

从仿生学的角度来看，自然计算主要是对生物单一功能的模拟，如蚁群算法[5]、粒子群优化算法[6-7]、萤火虫算法[8-9]和鸽群优化算法[10]分别是对蚁群、粒子群、萤火虫和鸽群行为的模拟。不同生物经过亿万年的进化，可以展现出多种多样的功能特征，成为了对生存环境具有最佳适应性和高度协调性的系统。而对于一个优越的算法，它的性能通常需要算法内部各种机制相互协调，共同作用，而不仅仅依靠其中某个因素。换句话说，单一机制作用的算法解决的问题相对局限。而将互相依存、互相影响的多个因素，在适当的集成机制或协同策略作用下，所设计的集成算法或将会产生更好的效能。

此外，固定策略可能不适合整个搜索过程。因此，在优化过程中，随着种群向全局最优解演化过程中搜索的变化，需要不断更新搜索策略以适应搜索过程。采用适当的自适应机制的多策略集合可以使算法在优化过程中有更高的概率选择最合适的策略[25]。此外，集成还可以使不同能力的搜索策略相互支持，从而大大增强了算法的性能。

集成算法的主要思想是在不同的学习者中构建一个集合形成一种获得更准确，更强大的学习者的算法[26-27]。实践已经证明，集成策略学习通常表现出比个体学习者更好的性能。例如，神经网络集成是一种成功的学习方式，它将为同一任务训练的有限数量的神经网络集合在一起，从而在同一任务上获得更好的性能。另外，还能提高预测的可靠性并减少分类错误的风险。近年来集成算法在不同领域都有成功的应用[28]，如计算机视觉中的对象检测，识别和跟踪，计算机安全中的入侵检测以及计算机辅助医学诊断中的肺癌细胞识别等方面，这些应用都证明了集成算法的优越性。

首先，集成策略的设计对一个算法性能的优劣具有重要作用。一个较优的策略，在算法执行过程中，表现为能根据问题的特性，来动态选择性能较优的算子。通过该方式作用下旨在结合现有不同算子的优势特性，使其相互协调、共同作用，来获得性能更好的高维多目标优化算法。因此，在第二节对集成策略的原理进行介绍。然后，在第三节分别对集成算法的理论研究和应用研究进行综述。最后，展望了一些高维多目标集成算法未来发展趋势。

2 集成策略设计

通常算法在种群迭代过程的不同阶段(如前期，中期和后期)，对问题解决操作算子的需求也在发生动态变化。具体来讲，一个性能良好的算法所包含的操作算子应该在种群迭代的前期具有快速收敛和擅长全局搜索的属性，进而保证近似最优解能够被快速锁定，而当锁定近似最优解范围后，需要执行局部搜索操作算子发挥作用，进而最终确定最优解或最优解集。因此一般的集成方法设计原则，通常是围绕两个问题来进行的：一方面是集成算法中具体应该包括哪些操作算子，另一方面是如何设计集成策略来执行这些操作算子。

针对第一个问题，一般解决思路是针对问题的不同特性，挑选适合的具有独特属性的操作算子。例如，为了使用优化算法来解决约束、多模态、动态问题和多目标等问题，可以采用约束处理、小生境、多样性增强技术和非支配排序方法等。由于每种操作算子对应的策略和参数值可能存在不同的组合，因此需要通过排列组合机制，构造不同的集成方式。在对应问题上测试所有潜在的组合方式，然后利用评价度量标准来比较不同的集成方式性能效果，从而挑选最佳集成方式的集成算法。

为了解决第二个问题，一些优秀的集成策略已经被提出，如用于解决MOPs的合作—竞争策略[29]和协同进化策略[30]等，还有用于解决MaOPs的集成池策略等。这些策略通常能自适应地执行所需要的操作算子[31]。通过这些集成策略，使得算法能根据迭代过程的不同阶段，动态灵活地使用各种算子搜索选择机制，从而提高算法搜索效率，改善算法性能，最终有效解决不同类型的优化问题。为了便于理解，这里介绍几种集成策略原理。

“六书”，即象形、指事、会意、形声、转注、假借，六种造字的方法，此“六书”既规定其叫法，同时也规定其顺序和每一种具体造字方法的注释。我们现在所沿用的“六书”内涵，是在漫长的历史发展中经过不断修正与完善，经历几代大家的不断思考与沉淀，最后集众家之长而定型，沿用至今。

2.1 合作—竞争策略

合作—竞争策略是指操作算子之间保持着一种动态合作竞争关系，最终需要实现共赢局面，即整个算法最终能够获得较好的性能效果。合作—竞争策略本质上强调了操作算子之间的相互依存、互惠互利的关系，然后利用这种关系使得信息能够相互及时补偿、交换和调整，最终达到改善算法性能的目的。假设一个算法存在两个操作算子机制，通过竞争，获得胜利的一方可被称为“胜利者”，则另一方被称为“失败者”。“胜利者”需要引导其他个体朝更好地方向进化，而“失败者”需要向“胜利者”不断学习，如变异方式等。在每隔若干代的下一次评价度量时，“失败者”和“胜利者”的身份将会发生动态变化，即上次的“失败者”将在此次成为“胜利者”，而上次的“胜利者”将在此次成为“失败者”。然而不论谁成为“胜利者”或“失败者”，对于整个算法而言，种群整体都是朝着较好方向进化的，因此算法获得较好性能的可能性也将不断增大。换言之，算法较好性能的获得，可以看作是操作算子之间相互竞争、相互合作、共同作用的结果。

2.2 协同进化策略

协同进化策略认为种群进化过程中需要将个体与个体，个体与其进化环境的因素纳入影响种群朝着较好方向进化的考虑范围。因为种群中个体的进化，不仅与其它个体进化有关，一定程度上还受到其进化环境的影响。因此，在对个体进行评价时，需要利用其它个体的信息，即个体对个体进行适应度评估，不再仅由目标函数决定，还由其它个体决定。在协同进化多目标优化中，种群之间是相互影响、相互制约、相互协同和共同进化的。通常一个种群会被分为多个子种群，然后同时对这些子种群采用“分而治之”的方法进行操作。而对于一个MOP，经过分解后形成多个子问题，要分别对这些子问题进行最优解求解。因此，该多目标优化问题的最优解将是由这些多个子问题的最优解共同组成。而一个种群被分为多个子种群，各个子种群独立进化，在计算个体适应度值时进行信息交流，这是因为每个子种群的个体只是整个种群最终解的一部分，还需要与其它种群的优秀个体结合，才能最终形成完整的最终解。其过程能被描述如图1所示。

2.3 集成池策略

不同于合作—竞争策略和协同进化策略偏向于解决MOPs时具有较好性能，集成池策略旨在用于求解复杂的MaOPs，并且包含概率选择和并发选择(无概率选择)两种集成策略。通常，将种群通过执行不同操作算子策略获得的解，存储在一个抽象“池”中，从而形成备选解集成池。该集成池能够集成许多优秀的算子，在它们相互协调、共同作用下，使得种群在进化过程中获得更广泛的备选解。

图2描述了一般集成池平面图，简单来说，先是将不同特性的算子放入一个“池”中，犹如江河水汇入大海，这里的“池”与一般意义的大海相似。该池中能够汇聚不同策略方法，如约束处理机制、启发式方法、不同的进化策略和选择策略等。通过构造集成池，提高算法整体进化效率。并且在集成池选解机制的作用下，确保种群的收敛性和多样性被综合考虑。而对于集成策略的描述，接下来将一一说明。

图1 协同进化策略示意图 图2 集成池示意图

2.3.1 概率集成策略

概率集成策略作为算法机制中最为常用的策略之一，它的设计与运用对于整个算法性能具有举足轻重的影响。由于实际问题的不同，工程师对概率选择策略要求也不尽相同，并且为了防止因每次迭代评价造成的时间成本浪费，通常采用每隔若干代评价一次来节省时间成本。这里只介绍两种较为常用的等概率集成和动态概率集成两种策略。

(1)等概率集成

等概率集成策略是指对于算法中涉及的操作算子以相同的概率被选择执行，并且通常在种群迭代的整个过程中，操作算子被选择概率也不发生变化。该策略适用于解决对公平机制要求较高的实际问题，但面对一些易遭受不确定性因素影响的问题时，将不再适用。

(2)动态概率集成

在动态概率集成策略的设计中，参数设置常常起到关键作用。设计者通常希望通过改变变量参数值，从而间接改变不同操作算子被选择概率，进而影响算法性能效果。动态概率集成策略中通常要求各操作算子被选择的概率随着种群进化的不同阶段而发生变化。当在算法中涉及的某种操作算子在若干代的评价度量表现良好，则理论上应适当增加该操作算子的被选择的概率，相应的其它操作算子被选择概率应当不变或减少(这里对3个操作算子而言)。具体来讲，当种群经过每隔若干代进化后，需进行度量评价，对3个操作算子被选择概率依次排序，排名第一的操作算子被选择概率应当增大，对于后两种操作算子被选择概率分两种情况：

情况1 排名第二的操作算子概率不变，排名第三的操作算子被选择概率减小，减小的概率值应与排名第一操作算子增大的概率值相等；

情况2 排名第二和排名第三的操作算子被选择的概率值都减小，并且两算子减小的概率值之和应与排名第一的操作算子被选择概率值增加的相同，而至于排名第二和排名第三的操作算子被选择的具体概率值应变化多少，则需要额外度量标准评价，然后再按照以上流程执行即可。由于在实际应用中情况2更符合现实，这里仅以情况2方式进行举例描述。

2.3.2 并发集成策略(无概率集成)

概率集成策略虽然能够随着种群进化要求来动态的调整操作算子被选择概率，然而这种策略有一个共性问题是解决相关问题时所执行的操作算子仅对其包含算子的一种进行选择执行，这种方式很大程度上将减少种群解的多样性，不利于种群获得较广泛的前沿面，即获得相对最优解。为了解决这个问题，提出不同于概率集成策略的并发集成策略，即无概率集成。在种群迭代过程中，不再只选择所包含算子的一种来执行，而是对每个算子都进行运作，从而每次迭代都可以获得比执行单一算子相对较优的子代解。

图3 不同操作算子产生的备选解集成池

同时为了更好地理解和可视化集成操作算子集成池的思想，图3给出了一个关于集成池的示意图。可以看出，Q1、Q2和Q3分别是Operator1、Operator2和Operator3算子产生的子代。图3的重叠区域展示了一些特殊情况：相同的后代是由不同的操作算子产生的，即使发生概率很小，在种群进化过程中也不可忽视。例如，Q12表示Operator1和Operator2算子产生的相同子代。Q13和Q23分别代表Operator1和Operator3算子、Operator2和Operator3算子生成的相同子代。Q123是Operator1、Operator2和Operator3算子产生的相同子代。显然，集成池中备选解(Q=Q1+Q2+Q3)将比单一Operator1算子(Q1)、Operator2算子(Q2)或Operator3算子(Q3)产生的子代提供了更好的集成池备选解。

3 高维多目标集成算法研究

3.1 集成算法的理论研究

对于Pareto最优近似解集的获得，在过去的几十年中，学者们已经提出了多目标EA(multi-objective evolutionary algorithm，MOEA)，其中典型的算法包括NSGA-II[32-33]，SPEA2[34]，PESA-II[35]和MOEA/D[36]等。但是，有关MOEA的早期研究大多集中在具有两个或3个目标的问题上。随着目标数量的增加，目标空间维度出现呈指数增长。同时原来的MOEA在算法运行后期选择压力下降，性能降低。特别是在高维目标空间中，种群中较大比例的个体互不支配，从而导致出现目标空间急剧震荡现象。另外，维持种群多样性的难度也愈发增加。这些问题是MOEA面临的重大挑战，特别是对于那些基于Pareto支配关系的选择算法而言[37-38]。MaOPs在带来挑战的同时，也不断激励着研究人员设计新算法机制，并且通常将用于解决目标个数在3个以上的MaOPs的MOEA称为高维多目标优化算法(Many-objective evolutionary algorithm，MaOEA)。开发的MaOEAs可以大致分为如图4(a)所示的6类，而这些算法按照选择机制的不同又可以划分为如图4(b)所示的3类。

图4 高维多目标优化算法分类

另外，这些性能较好的MaOEAs被证明通常只能很好地解决某些特定种类的MaOPs，但在其它问题上却表现不佳。因此到目前为止，MaOPs尚未得到充分解决，MaOEA的整体性能仍有提高的空间。

近几十年来，随着一些新颖的高效机制被不断提出，如启发式方法[39]，邻域大小[40]，小生境方法[41]，约束处理技术[42]，度量指标评价机制[43-44]和其它相关方法等，集成算法的研究也获得了广泛的关注并取得了令人鼓舞的成果。针对问题的不同特性，提出了从不同角度的集成方法，如多搜索策略集成[45]、参数设置集成[46]以及多EA变量的集成等[47]。Cai[48]等人提出一种蝙蝠集成算法用来解决大规模单目标优化问题，该算法通过将6种不同蝙蝠算法(bat algorithm，BA)搜索模式集成，在概率选择的集成策略作用下，使得算法搜索性能大幅度提升。Wang[49]等人采用不同的集成思路，将8种不同BA搜索模式集成，用于解决单目标复杂的DV-Hop定位问题，结果证明所设计的集成算法能有效改善定位的准确度。Wang[29]等提出一种新颖的多目标集成算法(EF-PD)来解决MOPs，该算法充分发挥了不同进化算子之间的竞争以及不同选择标准间的合作关系。EF-PD主要是利用分解的方法和资源分配策略用于驱动多个进化算子的竞争运行，而优良后代的移动是通过合作选择机制进行的。Peng[50]等人设计了一种在协同进化框架下具有多模态属性的多目标优化算法。具体来讲，首先将种群分解成多个子种群，采用分而治之的方法，同时利用适应度值和多样性评价机制分别对各子种群分别进行度量，然后在每个子种群中挑选多个相对最优解，将这些从各种群中得到的最优解作为各种群之间交换的信息，从而最终实现信息的交互与补偿。并且证明通过这种方式，在解决大规模优化问题时可以节省大量计算成本。另外，在BCE算法[51]中，Li等人认为在解决某些要求快速收敛的多目标问题时，种群迭代前期需要采用非Pareto支配的选择策略挑选解，后期则需利用Pareto支配的选择方法作为算法的多样性维护机制。在Two_Arch2[52]，该算法将基于指标的优点和基于Pareto支配的选择标准进行融合，使得算法能够将收敛性较好和多样性较好的解，分别存储在不同的外部解集中。在D2MOPSO[53]中，基于帕累托的排序机制通过与粒子群优化算法(particle swarm optimization，PSO)合作，来构建外部解集用于存储迭代过程中的最优解，旨在通过该方法加快种群收敛性。而基于分解方法被用来更新粒子的移动方向，从而使种群向收敛性较好的近似PF方向进化。

3.2 集成算法的应用研究

多目标优化问题在实际工程中非常普遍，并且处于较为重要的地位[54-55]。自 20世纪 60年代早期以来，吸引了越来越多的不同背景研究人员。Zeynali[56]等人提出考虑插电式电动汽车等不同不确定性的电力系统可再生分布式发电和电容器组的多目标优化短期规划方法，并将该方法应用于典型的径向配电网络问题。结果表明，在没有分布式电源的情况下，插电式电动汽车的负荷需求存在显著增加，这可能导致配电系统电压崩溃。并且，所提出的概率集成方法将可再生分布式发电和电容器组的多目标优化短期规划方法能以最优的方式保证配电系统的安全运行。Azab[57]等人设计了基于粒子群优化的单相分布式能源网格集成系统无源滤波器的多目标方法，实验结果验证了该方法的有效性，在满足IEEE标准519等网格集成相关规范的要求下，得到了理论最优滤波分量和良好的衰减谐波。Babaei[58]等人提出的基于实例的p2p贷款投资建议多目标决策支持系统，在与单目标模型相比下，其设计的多目标模型可以改善贷款人对两个投资目标的投资决策。Slabi[59]等人对从冷榨粉中提取向日葵总蛋白进行多目标优化统计分析，然后通过仿真设计证明得到的各提取准则的多项式模型对响应的预测是可靠的。Gao[60]等人对基于响应面法的填料床潜热储热系统热性能进行优化，并且其多目标优化结果表明，与优化前的基本工况相比，有效蓄热时间、有效蓄热、火用效率分别降低了30.24%、39.81%、7.50%。Shang[61]等人将高硫天然气净化装置看作一个多目标优化问题进行优化，结果表明其有效地降低了综合能耗，进一步提高了净化气的生产效率。Feng[62]等人对应急物流管理中救援站的选择进行优化，分析了提高模型求解效率的关键参数。通过算式计算和灵敏度分析，验证了模型的正确性和优越性。

然而在实际应用问题中，遇到的目标数量常常是3个以上，是MaOPs。例如，工业调度问题[63]，供水组合计划[64]，汽车控制器优化[65]和软件模块集群[66-67]等。Adeem Ali[68]等人提出了一种改进的基于分解的进化算法，用于解决3个以上目标的车辆延迟时间的取送问题。通过对各种小型，中型和大型问题进行实验，结果表明该算法在解决该类问题上具有很明显的优势。Khodabandeh[69]等人结合多目标蚁群算法和有限元方法提出了一种新颖的夹具布局优化方法，用于优化汽车侧面加固的固定装置布局。结果表明，所提出的方法可以有效地优化车身夹具的布局。Pei[70]等人针对灵敏度矩阵进行直接反演通常会产生不确定的问题，将识别问题放入优化框架中，提出了一种有效的数据辅助优化方法，用于故障识别。为了在解决方案多样性和收敛性之间取得平衡，建立了支持ε-优势的多目标模拟退火算法。系统的数值和实验案例研究证明了该方法的有效性。Zhou[71]等人为解决任务分配的问题，将名为D-NSGA3的分布式多目标进化算法与贪婪算法相结合，在D-NSGA3和贪婪算法之间进行交替搜索以增强局部优化能力。实验结果表明，该方法可以有效地解决大规模任务分配问题。Xiang[72]等人通过对21个特征模型进行一系列实证研究来解决同时使用多个(通常是3个以上)优化目标的功能模型中的最佳软件产品选择问题，为解决多目标最优软件产品选择问题提供了实用指南。

4 高维多目标集成算法发展趋势

高维多目标优化算法所呈现出的各种功能，不仅仅是单一因素的作用，而是互相依存、互相影响的多个因素通过适当的机制集成和协同作用的结果。然而，已有的高维多目标优化算法大多数都是采用单一算法的策略来解决高维多目标优化问题的。因此，设计高效的高维多目标集成算法相比单一算法能获得更好的结果。高维多目标集成算法既能保持高维多目标优化算法的优点来解决复杂度较高的问题，又能针对不同问题的特性，有目的的选用不同的算子来提高求解问题的效率，进而提高算法的整体进化效率。另外，在解决高维多目标优化问题时，种群的进化前期需要偏重收敛性，进化后期需要偏重分布性。因此，为了综合考虑收敛性和分布性在进化不同阶段的重要性，需要考虑在设计高维多目标集成算法过程中使两者随进化进程动态平衡。

另外，通过分析发现现有的集成算法大多致力于解决单目标或MOPs问题，而对于解决MaOPs问题的高维多目标集成算法的研究却少之又少。因此，为了解决该问题，未来需要重点研究设计出性能高效的高维多目标集成优化算法。通俗的来讲，高维多目标集成优化算法是针对算子个数大于等于3的不同算子，在集成策略的作用下，使各算子能够发挥其不同的优势特性，通过相互协调，共同作用，从而达到“强强联合”，获得较好的性能效果。

在高维多目标集成优化算法的研究中，为了增强算法性能，需要讨论引入的算子个数不断增多，一方面，需要将算子属性之间的潜在冲突性纳入考虑范围，防止出现“1+1+1<3”的情况；另一方面，设计高维多目标集成算法的复杂度也应成为衡量的重要方面，通常希望在算法复杂度许可的范围内，尽可能获得较好的性能；若不从该角度考虑，片面追求较好性能效果，而算法复杂度过高，往往在实际操作中取得事半功倍，不切实际的效应。当然，除了以上两方面，也需要考虑其它影响因素，由于篇幅限制这里将不做详细阐述。为了更好的阐述高维多目标集成算法设计思想，这里仅对算子个数为3的高维多目标集成优化算法进行了说明，而对于将更多数量算子进行集成，有兴趣的读者可以自行研究。

5 结束语

首先介绍了多目标优化问题的定义和多目标优化算法的相关概述，对集成算法从理论上，以NFL定理为依据说明不存在任何算法在解决所有可能的优化问题时优于其它算法；从仿生学角度，说明算法表现的功能，依靠算法内集成了众多操作算子，通过各个操作算子之间的有机结合，相互协调，共同作用来获得高效性能，最终表明了研究高维多目标集成算法的必要性。详细介绍了合作—竞争策略，协同进化策略和集成池策略的原理；其中集成池旨在通过结合现有不同操作算子的优势特性，使其相互协调、共同作用，从而达到“强强联合”，获得较好的性能效果。然后对现有一些集成算法的理论研究和应用研究分别进行了综述，最后对高维多目标集成算法未来的研究方向进行了展望。