《A Survey on Evolutionary Computation for Complex Continuous Optimization》笔记

大家好，欢迎来到IT知识分享网。

1 复杂连续优化问题

  （优化是许多领域中经常遇到的问题。对于非常简单的优化问题，人们可以使用试错法来测试不同的解决方案。然而随着经济和社会的发展，问题越来越复杂，试错法已经不再适用。因此许多基于数学和计算机辅助的优化技术得到了发展。其中进化计算（Evolutionary Computation, EC）在许多优化问题中已经成为一种很好的全局优化技术。EC技术起源于20世纪60年代，当时提出了解决全局优化问题的进化算法（Evolutionary Algorithms, EA），如遗传算法(GA)、进化规划(EP)、进化策略(ES)和遗传规划(GP) 。进化算法模拟了生物的进化过程和自然选择原理来优化问题。从20世纪90年代开始出现的一些优化技术，如差分进化(DE)和分布估计算法(EDA)，也被称为EA。除EA外，自20世纪90年代以来还出现了一些模拟蚂蚁、鸟类等群体智能行为的优化技术。它们包括蚁群算法(ACO)和粒子群算法(PSO)等，这些算法又被称为群智能（Swarm Intelligence, SI）算法。目前，EC家族主要包括EA和SI，并自20世纪90年代以来得到了迅速发展。）
  进化计算算法已成功应用于多种全局优化问题，但近几十年来优化问题中的新困难也给进化计算算法带来了巨大的挑战。例如在大数据环境中，复杂优化问题就像许多其他大数据问题一样，总是存在所谓的4-V挑战，即Volume、Velocity、Variety和Value，它们分别指数据量、变化速度、数据范围和数据有效性。具体来说，这些复杂优化问题通常是大规模的、动态的、有许多局部/全局最优的、有约束条件的、多目标的，并且具有非常昂贵目标函数评估的。
  本文首次引入5-M的概念，将复杂连续优化问题划分为5-M类：多维度(Many-dimensions)、多变化(Many-changes)、多优化(Many-optima)、多约束(Many-constraints)和多成本(Many-costs)。因此复杂的连续优化问题通常包括大规模优化问题(Large-scale Optimization Problems, LSOP)、动态优化问题(Dynamic Optimization Problems, DOP)、多模态优化问题(Multimodal Optimization Problems, MMOP)、多目标优化问题(Multi-objective Optimization Problems, MOP)、多目标优化问题(Many-objective Optimization Problems, MaOP)、约束优化问题(Constrained Optimization Problems, COP)和昂贵优化问题(Expensive Optimization Problems, EOP)。上述复杂连续优化问题和5-M、4-V的对应关系如图1所示。

2 分类法

  由于5-M挑战的存在，复杂连续优化问题比传统连续优化问题更加困难。具体来说，LSOP、DOP、MMOP、MOP/MaOP、COP和EOP所面临的挑战见表1。

  由于存在这些挑战和困难，我们必须调整EC算法来解决这些复杂问题。调整方法可以从三个角度来考虑：1）由于问题比较复杂，那么能否降低原问题的难度使EC算法能够解决该问题？例如将原来复杂的问题分解或转化为其他简单的问题。这可以看作是降低问题难度（“Reducing Problem Difficulty”）的方法；2）针对EC算法在复杂搜索环境下性能下降的问题，我们是否可以提高算法的能力？例如，如果算法容易陷入局部最优，我们可以增加多样性使算法具有更强的全局搜索能力。一般来说算法的多样性与种群信息有关，如种群位置数据和种群移动数据，因此可以通过使用各种参数/算子和多个种群来增强算法的多样性。再例如，如果搜索空间较大或计算时间较长，则可以加快算法收敛速度或减少运行时间。这些可以看作是增加算法多样性（“Increasing Algorithm Diversity”），加快收敛速度（“Accelerating Convergence Speed”），减少运行时间（“Reducing Running Time”）的方法。其中，较大的多样性通常与更强的探索能力有关，而更快的收敛速度通常与更好的开发能力有关；3）由于许多复杂连续优化问题来自于实际应用，我们是否可以根据问题实际特征来研究如何处理这些问题？这可以看作是扩展应用领域（“Extending Application Field”）的方法。
  根据前面讨论的方法的功能，本文提出了一种面向功能的分类方法，以对求解复杂连续优化问题的EC算法的现有研究工作进行系统的、结构化的分类，如图2所示。

3 现有工作分类

  本节根据图2中的分类法回顾了用于解决复杂连续优化问题的EC算法。具体来说，本节根据问题类型分为六个部分，分别为解决LSOP、DOP、MMOP、MOP/MaOP、COP和EOP问题的EC算法。在每一部分中，根据面向功能的分类方法对相关工作进行分类，部分或全部包括降低问题难度、增加算法多样性、加快收敛速度、减少运行时间和扩展应用领域的方法。

3.1 EC for large‑scale optimization problems

• 降低问题难度：利用分治思想（“divide-and-conquer”）的CC方法是一种著名的、常用的降低LSOP问题难度的方法。换句话说，CC方法的目标是将整个LSOP问题分解成几个决策变量较少且更容易解决的子问题。基于CC方法的EC算法发展路线图如图4所示，它表明利用CC方法降低问题难度以有效求解LSOP问题的研究是长期发展的，目前仍十分活跃。图4中基于CC的算法对子问题一视同仁，也就是说所有的子问题都由相同数量的计算资源进行优化。但由于不同子问题中变量的数量不同，子问题之间存在不平衡。因此也有很多关于不同子问题应该分配不同计算资源的研究。
  
  

• 增加算法多样性：由于LSOP问题的高维特征导致搜索多样性不足，一些算法可能陷入局部最优。因此，我们可以通过增加算法的多样性来提高算法求解LSOP的性能。这些方法主要可以分为三类：1）自适应控制参数：EC算法中一些可能影响算法多样性的参数可以自适应控制；2）设计新的算子：例如许多研究人员修改了标准粒子群算法的速度和位置更新方法，以增加算法的多样性；3）引入多个种群。
• 加快收敛速度：由于LSOP问题的高维特征，在收敛速度上存在一定的困难，因此收敛速度也是求解LSOP时需要考虑的问题。嵌入局部搜索是提高算法收敛速度的主要方法。

  
  

3.2 EC for dynamic optimization problems

• 降低问题难度：考虑到求解DOP问题的难度，有一个简单的思想是我们可以通过将复杂的DOP分解为一组更简单的问题来降低问题的难度。从问题的决策空间来看主要有两种方法：维度分组（decomposing the dimension into groups）（来源于CC方法）和搜索空间分块（Dividing the search space into pieces）。
• 增加算法多样性：在使用EC算法求解DOP时，种群在进化过程中会逐渐收敛，所以当环境发生变化时需要跳出之前的局部区域。保持多样性有利于避免算法陷入局部区域，不断探索搜索空间并找到新的最优解。因此人们提出了许多提高算法多样性的方法：
    1）多种群：使用多种群是算法增加多样性的一种常见方法。其中，在进化过程中维护多个种群，每个种群负责一项单独的任务。这些任务的目标可能相同，也可能不同。因此存在两种多种群模型，即异构模型和同构模型。在异构模型中，多个种群处于不同的层或具有不同的配置或任务；在同构模型中，每个种群都有相同的任务。此外种群的数量和大小可以是固定的或可变的，并且每个种群的搜索空间可以具有固定的大小或相互重叠。
    2）构建复合解：复合解是由几个组分解组成的特殊解，也可以看作是一个子种群。即复合解策略实际上隐式的将种群划分为多个子种群。
    3）设计新的解更新策略：设计新的解更新策略是通过生成更多的新解来增加算法多样性的另一种方法。它几乎适用于所有的进化计算算法，包括遗传算法(GA)、差分进化算法(DE)和粒子群优化算法(PSO)。
  
  
  
• 加快收敛速度：在求解DOP时，当环境发生变化时算法需要在新环境中快速定位最优解，这就要求算法具有较快的收敛速度。一般来说，连续动态环境之间往往具有很强的相关性，因此重用历史解在新环境中有很大的潜力加快收敛速度。重用历史解有两种方法：一是直接重用历史解；二是预测最优解的位置，并基于历史解获得有希望的初始种群。

  
  

3.3 EC for multimodal optimization problems

  多模态优化问题(MMOP)是指具有多个最优解的优化问题。一般来说，针对EC算法解决MMOP问题中挑战的研究工作可以按照面向功能的分类方法分为三类，如图6所示。

• 降低问题难度：MMOP问题中有多个最优解，这些最优解的适应度评估值是相同的。在这种情况下，适应度值可能不能提供足够的指导来驱动种群的进化，导致EC算法过早收敛。为了降低问题的难度，一些研究者尝试通过从问题中提取信息作为另一个目标将MMOP问题转换为MOP问题，以提供更多的指导从而帮助算法更容易搜索。
• 增加算法多样性：大量的研究集中在增强种群多样性上，以帮助在MMOP中尽可能多地找到最优解。这些研究工作可分为小生境法（Niching Method）和新算子两大类。1）小生境法是将种群划分为若干子种群，使种群局部进化以保持多样性；2）为EC算法设计新的算子来适应MMOP问题。（但很少有研究关注个体的选择，如果选择算子设计不好，即使已经生成了不同最优区域的多样性解，也不能将它们选择到下一代中。）
• 加快收敛速度：除了在MMOP中定位多个最优解外，加快收敛速度以细化所找到的近似最优解的精度也是一个具有挑战性的问题。一个流行的策略是局部搜索。通常算法都是基于一些概率模型对解进行扰动以提高其精度，其中高斯概率模型是应用最广泛的一种。使用高斯概率模型的一个解的一般局部搜索策略可以通过使用这个解作为均值并结合标准差来实现。因此在基于扰动的局部搜索策略设计中存在两个具有挑战性的问题：一个是标准差的设置；另一个是选择哪一个解用于局部搜索。

  
  

3.4 EC for multi‑objective and many‑objective optimization problems

  多目标优化问题（Multi）和多目标优化问题（Many）是两种复杂的连续优化问题，通常分别涉及两个/三个目标和三个以上目标。与求解MOP问题相比，求解MaOP问题由于目标的增加而变得更加困难。传统的EC算法在求解MOP和MaOP问题时，很难在所有目标上保持多样性和收敛性。一方面，随着目标数量的增加，目标空间显著增大，需要一致逼近真实帕累托前沿(PF)的解的数量也迅速增加。另一方面，由于Pareto支配关系是基于多个目标定义的，因此大多数解是非支配解，只有非常小的一部分解接近PF。因此如何沿着PF获得分布均匀且近似最优的解是一个值得研究的问题。根据面向功能的分类方法对使用EC算法求解MOP和MaOP问题的方法进行分类，如图7的右侧所示。图7的左边部分是多目标进化算法的传统分类(Mane and Rao 2017)。

• 降低问题难度：当我们应用简化问题的思想来求解MaOP问题时，这个思想被应用为：1）减少问题大小：在MaOP问题中，目标的数量通常超过3个，但并不是所有的目标都是冲突的。因此减少冗余目标可以帮助减少MaOP问题的规模，这是降低问题难度的一种直接方法；2）转换为单目标问题；3）缩小偏好区域：由于不是所有的Pareto解都符合决策者的实际需要，因此该方法只关注决策者偏好的区域而没有探索整个PF（只需找到决策者偏好区域的帕累托解集）。
• 增加算法多样性：由于MaOP问题的复杂性，许多研究都着重于增加解的多样性以帮助寻找全局最优PF。主要方法包括：1）定义新的多样性管理策略帮助EC算法生成分布均匀的多种解；2）随着搜索空间的扩大，一些方法倾向于使用不同的参考点和参考方向来增加算法的多样性。这些方法定义了不同的参考点和参考方向，保证了EC算法的基本多样性；3）另一种提高算法多样性的方法是使用多个协同进化种群，因为不同的种群可以配置不同的设置，或者它们可以合作搜索不同的区域。
• 加快收敛速度：为了使解尽可能接近真实PF，在MaOP问题中对加速收敛速度的研究也很有意义。主要方法包括：1）重新定义帕累托支配关系：由于MaOP问题中目标的数量较多，基于Pareto的EC算法得到的非支配解的数量会因难以满足Pareto支配定义而成指数增加。然而只有一小部分更接近真实PF的非支配解具有更强的引导种群收敛的能力。这导致了支配阻抗（Dominance Resistance）现象(Purshouse and Fleming 2007)，导致选择压力降低并影响了基于Pareto的EC算法的收敛性能。因此有必要对帕累托支配关系进行改进或重新定义；2）用有希望的解引导种群：也有一些研究倾向于根据特定的偏好策略从当前的帕累托集合中选择更有希望的解，从而引导种群更快地收敛；3）用收敛指标引导种群。
• 减少运行时间：对原算子进行优化和改进，可以有效降低原算法的复杂度和运行时间。此外一些研究人员建议减少基于指标的算法和基于分解的算法的执行时间。

  
  

3.5 EC for constrained optimization problems

  约束优化问题是一类需要满足一组约束条件的复杂问题。因此在搜索空间中存在大量的不可行解，因为它们可能不满足一个、一些或所有的约束条件，只有一小部分的搜索空间包含可行解。由于EC算法具有强大的搜索能力，近几十年来许多研究人员都将其用于求解COP问题。然而很难确定哪个解更好，因为位于COP不可行区域中的解也可能有很好的适应度值。因此在使用EC处理COP问题时，我们需要结合约束处理技术(Constraint Handling Techniques, CHTs)。其中EC算法作为搜索引擎，同时CHTs指导算法如何为下一代的种群选择解。解决COP问题的经典技术分类如图8的左侧所示。根据面向功能的分类方法对使用EC算法求解COP问题的方法进行分类，如图8的右侧所示。

• 降低问题难度：考虑到在搜索空间中寻找可行域的困难，降低COP的问题难度是一个很好的方法。降低COP问题难度的方法可分为三类：
    1）罚函数法：罚函数法是一种著名的降低问题难度的方法，因为它可以很简单直观地将COP问题转化为无约束问题。该方法将约束条件作为惩罚因子添加到适应度函数中，使目标函数和约束函数可以同时考虑在一个函数中。然而惩罚因子是问题相关的，很难设置一个合适的值。根据惩罚因子调整方法的不同，罚函数方法可分为以下四类：①最简单的罚函数法直接将惩罚因子设为正无穷，称为“Death Penalty”；②静态罚函数在演化过程中利用固定的惩罚因子；③动态罚函数在演化过程中改变了惩罚因子；④自适应罚函数根据种群反馈信息对惩罚因子进行调整。
    2）多目标化：将COP问题转化为MOP问题。它将整体约束条件作为另一个目标或将每个约束函数都作为一个目标，从而使算法能够轻松地找到MOP的可行解。
    3）将可行域映射为常规域。
  
  
  
• 增加算法多样性：在COP问题中，有些不可行解可能比可行解更接近最优可行解。因此如何选择下一个种群的解是COP的关键问题，提高算法的多样性对COP具有重要意义。目前的研究主要有两种提高算法多样性的方法：1）将目标和约束分开处理；2）结合不同特征的约束处理技术。
• 加快收敛速度：在求解COP时，如何快速收敛到可行域是一个值得思考的问题。上面讨论的约束处理技术通常用于比较两种解。然而近年来，一些研究人员转而使用约束处理技术来直接指导解的生成。这种方法主要是利用变异算子来加快COP求解的收敛速度。

  
  

3.6 EC for expensive optimization problems

  昂贵优化问题(EOP)是指需要计算昂贵的模拟或计算来评估候选解的优化问题(Jin 2005; Shan and Wang 2010; Tenne and Goh 2010)。根据面向功能的分类方法对使用EC算法求解EOP问题的方法进行分类，如图9所示。

• 降低问题难度：在许多优化问题中，评估候选解的数值或精确适应度函数可能不存在(Jin 2005)。在这种情况下，解只能通过计算昂贵的数值模拟或物理实验来评估，例如风洞实验。这给EC算法带来了巨大的挑战，因为大多数EC算法都是基于适应度评估来进化的。为了解决这一问题，减少优化难度，近似方法得到了广泛的研究。一般来说，现有的降低问题难度的近似方法主要可以分为两大类：问题近似和适应度近似。
    1）问题近似：问题近似是一种直接使用近似问题来代替原始问题的方法。新问题与原问题大致相同，但更容易解决。
    2）适应度近似：与问题逼近方法对原评估过程进行近似不同，适应度近似方法直接逼近候选解的适应度值。给定一些评估数据，即解及其对应的适应度值，EC算法可以采用适应度近似方法来逼近目标函数。在此之后，可以用近似的目标函数（也称为代理函数）来代替原始目标函数，并对新的候选解进行评估来驱动EC算法。
  
  
• 减少运行时间：由于EOP问题的计算量较大，因此有必要减少EC算法的运行时间，使其能够应用于实际的EOP问题。一般来说，减少昂贵适应度评估的运行时间有三种方法：
    1）适应度继承与模仿方法：由于适应度评价过程昂贵，适应度继承和模仿方法是基于其他个体的适应度值来近似新个体的适应度值，而不是通过执行适应度函数来计算适应度值。在适应度继承中，新个体的适应度值继承于父个体；在适应度模仿中，新个体的适应度值是根据其它相关的被评估个体估计得到的。
    2）多保真度适应度近似方法：在许多现实应用中，适应度评估的保真度可以手工控制且在保真度和计算代价之间有一个平衡(Wang et al. 2018a)。在这种情况下，多保真度适应度近似方法考虑的是如何更好地利用具有多个保真度的仿真和模型来寻找最优解，从而在更短的时间内获得可接受的解。
    3）并行和分布式技术。

  
  
  
  
  

4 未来工作

  本文从问题-算法两个层面考虑并讨论了未来的六个潜在研究方向，如图10所示。

4.1 Combination of 2‑M or X‑M challenges

4.2 Cooperation of diferent function‑oriented approaches

4.3 Crossing of multi‑disciplinary techniques

4.4 Bi‑directional interaction of problems and algorithms

4.5 Balance of solution accuracy and computational burden

4.6 Applications of more real‑world complex problems

  许多研究人员已经尝试使用EC算法来解决现实世界复杂的连续优化问题，并获得了一些有希望的结果。因此随着EC算法在处理复杂连续优化问题中5-M和4-V挑战方面的改进，EC算法在解决现实世界中更复杂的连续优化问题方面具有很大的潜力。这不仅在EC和复杂系统社区，而且在许多面临复杂持续优化问题的其他领域，都会是一个热点和长期存在的研究课题。