博文

综述 | 进化计算在大规模多目标优化问题中的进展

已有 5524 次阅读 2021-3-24 17:46 |个人分类:好文推荐|系统分类:论文交流

多目标进化算法在求解大规模(决策变量数多)多目优化问题时通常面临性能的急剧下降，引发决策变量维度高可扩放的多目标进化算法的研究热潮。算法可扩放性提升面临的难点是什么？如何增强多目标进化算法的可扩放性？南方科技大学唐珂教授团队围绕上述两个关键难题，综述了近十年来进化计算在大规模多目标优化问题中的研究进展。

现实生活中的许多优化问题都涉及多个目标，称为多目标优化问题(Multi-objective Optimization Problem, MOP)。比如设计汽车车身零部件时，要求设计的零件刚度大且质量轻，这就是一个两目标问题，同时还有一些条件约束，比如模态约束、尺寸约束等。同样地，金融领域中，投资者都希望投入的资金少、风险小，并且获利最大，这是一个三目标问题。

封面2.jpg

图片来自网络

多目标之间的冲突使得我们无法找到一个能同时实现所有目标最优的单一解决方案。因此，在冲突目标之间寻找多个不同程度的折衷，即寻找帕累托最优解(Pareto-optimal solution)，对于决策者而言至关重要。进化算法(Evolutionary Algorithm, EA)是解决这类问题的主流技术手段之一，其主要原因在于EA采用多点同时搜索的机制，能够在一次运行中逼近整个帕累托最优解集，并且其对问题的性质(如连续性、可微性)不做特别假设，尤其适合求解复杂的非线性与黑盒多目标优化问题。目前，进化算法已被广泛用于求解MOP(简称多目标进化算法，Multi-Objective EA, MOEA)，出现了许多强大的MOEAs。

算法的可扩放性(scalability)刻画了算法性能随问题规模变化的趋势，不仅是算法理论研究的核心主题之一，而且也关乎算法能否应用于解决更广泛的大规模现实问题。在MOP中，决策变量(decision variables)的数量和目标的数量是决定问题大小规模的两个关键因素。目标维度的可扩放性在过去的几十年间备受关注，超多目标优化问题(即目标数量多的MOP)的研究已经出现了许多不同时期不同视角的综述文章。

插图1.jpg

图片来自网络

相比超多目标优化受到的广泛关注，MOEA在决策变量维度的可扩放性在近十年间才逐渐受到重视，开始出现一些针对大规模MOP(即决策变量数多的MOP)的研究工作，目前还没有该领域的综述文章。具体地说，早期关于MOEA的研究主要是针对小规模(通常不超过30个决策变量)的MOP，直到2008年MOEA在决策变量维度的可扩放性首次得到系统性测试，并且结果表明，随着决策变量的数量增加，传统MOEA的效率将急剧下降。与此同时，现实生产应用对大规模MOP的求解提出了广泛的需求。

例如，深度神经网络(Deep Neural Network, DNN)的训练需要同时考虑经验风险(如训练误差)和结构风险(如网络稀疏性)，而典型的工业级DNN往往包含数百万量级的待训练的权值(weights)。又如，社交网络中的商业推广既需要影响力最大化，也需要成本最小化，而现实网络(如微博、Facebook、twitter等)中涉及的节点数量可以达到数百万甚至数亿量级。此外，物流调度、软件工程、模式挖掘等许多领域面临的问题也表现出大规模MOP的特点，迫切需要快速且有效的解决方法。至此，过去十年间，面向大规模MOP的高可扩放MOEA的研究逐渐引起了研究者们的关注。

插图2.jpg

图片来自网络

在研究高可扩放MOEA时面临两个关键难题：

1) MOEA可扩放性提升面临的难点是什么？算法的可扩放性是受其搜索机制和问题性质共同影响的。对于任一给定的搜索机制和任一给定问题特性，如果能够了解可扩放性提升面临的难点，就可以帮助算法更好地设计，提出行之有效的高可扩放MOEA。为此，一些学者系统研究了某些MOEA的可扩放性，并对算法所面临的挑战提出了一些新的发现。本文简要回顾了学界近年来在这方面所做的努力。

2) 如何增强MOEA的可扩放性？分治(divide-and-conquer)及降维(dimensionality reduction)通过切分或变换可以简化问题，增强搜索(enhanced search-based approaches)通过探索(exploration)与开发(exploitation)的再平衡可以提高算法的搜索能力，它们是增强算法可扩放性的三种宏观思路。本文基于这三种类别分别对可扩放MOEA的研究进展进行综述，而在介绍每一类时的关注点在于如何将MOP的问题特性和提升可扩放性面临的难点信息融合到算法设计中，以实现高可扩放的MOEA。

综上所述，本文面向MOEA在决策变量维度的可扩放性，围绕上述两个关键难题对近十年来进化计算在大规模MOP中的研究进展进行综述。