多个目标的优化问题

　　现实世界当中存在大量具有多个目标的优化问题（MultiobjectiveOptimizationProblems），例如软件工程师希望寻找到一个经济的软件测试方案，同时需要保证该方案尽可能提升测试的覆盖率〔1〕；物流网络的设计旨在解决一个双目标的优化问题，即减少成本的同时不断提高顾客满意度〔2〕；医生在为肿瘤病人制定治疗方案时，需要平衡病灶的攻击性、对健康器官的潜在影响和病人身体的整体素质这三方面的因素〔3〕。随着实际需求的增加和研究的深入，越来越多的因素开始作为优化指标供决策者制定方案使用。其中，四个目标以上的多维目标优化问题被定义为高维多目标优化问题（ManyobjectiveOptimizationProblems），该类问题不断地受到重视并给予特别地定义〔4〕，其原因主要来自两方面：
　　一方面，现实中不断涌现出大量的高维多目标优化问题，涉及范围颇广。例如，在对引擎的自动校准中，需同时对涉及质量和敏感度等10维目标的问题进行优化〔5〕；在土地开发管理中，方案的选择在于求解一个考虑成本、碳排放、沉降等因素的14维优化问题〔6〕；在软件工程的代码自动重构问题中，需解决一个考虑最小化代码数量、最小化继承树深度和最小化环路复杂度等15维多目标优化问题〔7〕；对医院的护士进行排班调度的实质，在于求解一个考虑成本、最小化倒班次数、最大化护士与病人的匹配度等的一个20维多目标优化问题〔8〕。可预见的是，随着人们对环保、工作及生活质量需求的不断提升，未来将会有更多的高维多目标问题不断涌现。因此，对于此类实际问题迫切需要适合的算法进行求解。
　　另一方面，传统的低维多目标优化方法，在解决此类问题时经常会遭遇到诸多困难。基于种群的进化算法，由于其能在单次评估内即可得到一组近似解，已成为解决多目标优化问题的基础算法之一。然而，传统的多目标进化算法在解决高维多目标优化问题时遭遇到维度灾难现象，无法有效地收敛到相应的Pareto面前沿。而由于高维空间当中存在大量的非支配解，基于支配关系的算法（Paretobaseddominancealgorithms）在解决此类问题时，会产生支配阻抗现象（Dominanceresistancephenomenon）〔9〕。即：由于目标维数的增多，解之间无法根据严格的支配关系进行比较。算法因无法从大量的非支配解中挑选出精英解而丧失选择能力。此外，由于高维空间当中的搜索空间急剧膨胀，传统的单种群进化算子的作用被弱化，无法持续产生优于上一代的解〔9〕。
　　因此，在处理高维多目标优化问题时，出现了之前求解低维多目标优化问题时不曾遇到的困难。针对这些困难，大量的研究成果被提出。例如，针对上述支配阻抗现象，所提出的基于松弛支配定义的方法，通过松弛传统严格的支配规则直接提升算法收敛到Pareto前沿的能力。支配方法作为该类方法的代表成果之一〔10〕。其思想是将目标空间分为多个网格且每一网格仅包含一个解。最终解之间的支配关系被网格间的支配关系所取代，支配关系的范围以此得到提升。在此基础上，Deb等人将支配的概念与多目标优化相结合，开发出一个稳态的多目标优化算法〔11〕。至此，利用网格方法对支配关系进行缩放成为提升Pareto支配方法解决高维多目标优化问题的一个有效思路。依照此研究方向，Yang等人设计出一种动态构建网格的方法，以增强算法对可行解的选择压力〔12〕。除使用网格的方法外，遵循松弛支配思想的方法还包括模糊Pareto支配〔13〕、支配〔14〕等。作为解决支配阻抗现象的最直接方法，松弛支配方法的优点在于可直接将这些新的支配关系引入到传统的Pareto支配方法的框架中。理论上，以松弛的支配关系替代传统低维多目标优化算法的支配关系，即可缓解支配阻抗现象。然而，在实际应用中发现，多数松弛支配的方法需引入一个松弛变量，该变量的设置严重依赖于所需解决的实际问题，参数敏感性较强。此外，上述以个体为核心的网格计算方法在目标数增大的情况下，存在一定的退化风险。
　　因此，诸多研究者尝试跳出传统的基于支配关系的框架以解决高维多目标优化问题。其中，基于指标的方法是将个体在解空间中的综合性能以单一指标的形式给出，其核心概念可追溯于Zizler的IBEA算法〔15〕。由于具备良好理论特性，超体积方法（Hypervolume，HV）成为最常见的衡量多目标优化个体性能的指标。可通过理论证明，在算法迭代的过程中最大化HV指标即等价于寻找指定问题的Pareto面前沿〔16〕。然而，基于指标算法的最大缺陷在于其计算复杂度会随着目标数的增长而显著提升。此外，以MOEAD（MultiobjectiveEvolutionaryAlgorithmbasedonDecomposition）为代表的基于分解的方法，成为目标解决高维多目标优化问题的主流方法之一〔17〕。
　　然而，基于分解方法在解决高维多目标优化问题时，也遭遇到诸多困难。其中，较为突出的问题就是收敛性与多样性的平衡问题。相对于基于支配关系的方法，基于分解的方法在求解高维多目标优化问题时，收敛性依然可以保障。但是，算法对多样性的维护相对较弱，造成基于分解方法在求解高维多目标优化问题时收敛性与多样性难以平衡。针对该问题，大量的改进算法被提出：例如YuanYuan等人所提出的MOEADDU〔18〕，则不再以固定邻域作为解的替换范围。而是利用当前解到各个权值向量的投影距离的降序排列确定若干子问题，在子问题范围内进行进化与选择操作。对于收敛性与多样性的平衡，则依赖于子问题数量的选取。本课题申请者所提出的附加排序算法（Clusteringrankingmethod，crEA），旨在结合MOEAD在收敛性方面和NSGAIII〔19〕在多样性维护方面的优势〔20〕。选择算子在选取精英解时，按照不同附加聚类中，排序由低到高分层进行选取的原则，以平衡算法的收敛性与多样性。
　　基于分解方法的另一个问题，是在求解复杂Pareto面问题时无论是收敛性与多样性都难以保障。其主要原因为：基于分解方法的实施，主要依赖算法初期在目标空间中所建立的权值向量，以该权值向量确定所需解决的子问题。这些权值向量是以正规的形式均匀散布在目标空间当中，确保所得解的多样性。然而，在处理一些特殊问题时，如果所处理的Pareto面非正规（不连续、退化或者Pareto面局部聚集等），都会严重影响算法的性能。针对此问题，以动态调整子问题的权值向量为思路，一些改进的方法被提出。例如Qi等人提出一种改进的MOEAD算法：MOEADAWA〔21〕。在原始切比雪夫函数几何性质的基础上，提出一种新的权值向量初始化方法，该方法以周期性的方式不断调整权值向量，以增强解分布的均匀性。Liu等人最近所提出的MOEADAM2M方法，在进化过程中不断调整限定替换子区域大小和相应权值的分布，而调整的依据是以当前种群作为Pareto面流形的近似，迭代选择出合适的权值向量〔22〕。基于同样的假设，Gu等人则利用自组织映射的方法，对相邻多代种群采用非监督学习方法进行学习，最终以自组织映射的神经元权值作为子问题的权值向量〔23〕。
　　如上所述，虽然基于分解的方法性能较优。然而，在处理高维多目标优化问题时，受限于原有单一种群进化方式的框架和固定子问题范围的限制，很难进一步提升算法的综合性能。所面临的问题可总结为：首先，同时确保种群收敛性和多样性较难。目前，大多数多目标优化算法均采用收敛性为先，多样性在后的设计方式，收敛性与多样性的保障有一定的耦合性。因此，算法在一方面的褪化，必然影响到另一方面的性能。此外，在收敛性和多样性都能确保的前提下，对两者的平衡能力有限。例如，对一些特殊的Pareto面多目标优化问题求解中，要求算法的求解更加强化多样性。种群中单一且固定的环境选择机制在应对此类问题时缺少灵活性。鉴于此，不少研究者期望打破传统单一进化方式的限制，以多种群方法求解高维多目标问题。相关方法包括Deb所提出的MOEA算法〔11〕、KeLi等人所提出的双种群框架（Dualpopulationparadigm）〔24〕、MiqingLi等人所提出的双标准进化框架（BiCriterionEvolution）〔25〕和RuiWang等人所提出的偏好协同算法（PreferenceInspiredCoevolutionaryAlgorithm）〔26〕。而双档案算法（Twoarchivealgorithm，TwoArch）是首次依照多目标优化的基本需求明确每个种群基本偏好的算法〔27〕。该方法在迭代的过程中，维护两个档案：CA（ConvergenceArchive）和DA（DiversityArchive）。并在算法迭代的过程中维护不同的归档策略：CA不断收集所产生的非支配解，DA不断收集支配解。当CA与DA中个体数量增长到一定规模时，DA以欧式距离为指标剔除多样性差的解。针对TwoArch方法求解高维多目标优化问题的不足，李丙栋等人提出一种改进的双档案算法〔28〕。在CA中引入截断策略，并替换了DA多样性维护的策略。为进一步提升双档案算法在高维多目标优化问题中的性能，王晗丁等人提出第二代双档案算法，在CA与DA中分别限定种群规模，且两者的选择过程相对独立〔29〕。至此，双档案算法真正实现根据不同目的进行独立更新策略，并在求解高维多目标优化问题上取得较为满意的效果。受启发于该算法，课题申请者最近所提出的基于聚合方法的双档案算法（TwoArchA），利用了相似的双档案框架求解高维多目标优化问题〔30〕。该方法的基本思想是在种群中利用各不同的分解策略进行独立进化，而最终收敛性与多样性的平衡则委托给交叉算子。
　　上述可知，目前在求解高维多目标优化问题时，现有方法虽然能在一定程度上缓解高维空间所带来的支配阻抗现象。但是，如何在高维空间当中平衡所得解的收敛性与多样性，仍然是该研究邻域的一个难点。将基本种群扩展为多种群的方法是解决该问题较为理想的一个方案。而双档案方法作为该类方法的代表，将算法收敛性与多样性的需求进行解耦，并在合适的时机进行融合。理论上将更加有益于平衡收敛性与多样性。然而，现有的双档案方法形式较为单一，在进化过程中，在相关归档过程中的信息未得到有效地交互。此外，目前双档案算法中对于收敛性与多样性的平衡，单纯地依赖于交叉算子，因此无法实现复杂问题下的收敛性与多样性的平衡。为此，本课题将针对高维多目标优化问题，研究求解高维多目标优化问题的双档案方法。旨在将收敛性与多样性这两个基本需求委托给不同的归档过程去完成。同时，还将对搜索过程中不同归档方法的交互与协同进行研究。本课题对解决高维多目标问题的理论意义和现实价值如下：
　　首先，以多种群方法中的双归档方法为研究重点，弥补现有研究只注重挖掘单种群方法平衡收敛性与多样性的问题，促进基于种群的高维多目标优化理论方法的发展。其次，归档过程中的交互与协同作用，所诞生的用于平衡收敛性与多样性的策略，可为解决高维多目标优化问题提供一定的理论依据。最后，在双归档作用下对具有较复杂Pareto面问题的求解进行研究，可为实际应用中的高维多目标优化问题提供新的解决方案。所研究课题的潜在优势为：首先，作为多种群方法的代表，双档案方法本身可作为天然的混合策略框架。鉴于目前混合策略对于求解高维多目标优化问题的鲁棒性〔31〕，双档案方法可为研究新的混合策略提供可能。其次，双档案方法无需在单一种群中同时考虑收敛性与多样性，因此算法可承担其它需求的能力显著提高。例如，由于不在承担收敛性的需求，在多样性档案中可利用自身的种群特性对Pareto面的流形进行估计。