论文研读-多目标多任务优化MOMFEA-II

论文研读-多目标多任务优化MOMFEA-II

Cognizant Multitasking in Multi-Objective Multifactorial Evolution: MO-MFEA-II

• 此篇文章为 K.K. Bali, A. Gupta, Y.-S. Ong, P.S. Tan, Cognizant Multitasking in Multiobjective Multifactorial Evolution: MO-MFEA-II, IEEE Trans. Cybern. (2020) 1–13. https://doi.org/10.1109/TCYB.2020.2981733. 的论文学习笔记，只供学习使用，不作商业用途，侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正！

摘要

• 人类有能力在一生中遇到的不同情况下识别重复出现的模式，不断理解任务之间的关系并通过知识重用有效地解决它们。人工智能系统模仿此类认知行为以有效解决问题的能力被认为是无价的，尤其是在解决速度和准确性至关重要的现实世界问题时。最近，进化多任务处理的概念已被探索为一种使用单个进化个体群体同时解决多个优化任务的方法。在相关优化问题的高质量解决方案之间存在相似性（甚至部分重叠）的情况下，任务间遗传转移的结果范围通常会导致显着的性能加速——因为重新探索搜索空间重叠区域的成本是减少。虽然多任务求解器最近取得了成功，但现有方法的一个已知缺点是它们无法以原则性的方式适应转移的程度。因此，在缺乏关于优化函数之间关系的任何先验知识的情况下，主要是负面（有害）转移的威胁盛行。考虑到这一点，本论文提出了多目标优化领域内认知进化多任务引擎的实现。我们提出的算法基于从多任务处理过程中生成的数据得出的概率搜索分布的重叠来学习任务间关系 - 并相应地在线调整遗传转移的程度。该方法的有效性在多目标基准问题以及从低保真优化任务进行知识转移的实际案例研究中得到证实，以显着降低高保真优化的成本。

1. Introduction

• 人脑是一个自我学习系统。除其他外，它具有理解周围环境的一般能力——“意识到正在发生的事情”和“弄清楚”要做什么 [1, 2]。这种内在特征使人类能够从一个人的经历中得出推论，识别不同任务之间的重复模式（关系），并在相关问题之间共享知识 [3]。正是这种利用我们已知的知识来处理相关任务的能力，在提高我们解决问题和决策的效率方面发挥了重要作用 [4]。
• The ability to learn from experience is considered invaluable for machines as well. Given modern technologies with largescale data storage and seamless communication facilities, the development of machines that mimic human-like behaviors of autonomously extracting, processing and transferring learned knowledge across related problems is surely an attractive proposition. In this regard, the concept of multitasking has drawn much interest in the field of computational intelligence [5–9]. Not surprisingly, present day artificial intelligence systems are emerging as powerful tools for multitasking, capable of simultaneously handling myriad tasks with greater speed and accuracy.
• 进化多任务处理是进化计算领域相对较新的范式，最近被探索为一种基于群体的搜索方法，用于同时解决多个优化问题[7]。值得注意的是，在构成问题之间存在潜在关系的情况下，进化的多任务处理导致了富有成效的知识转移的可能性，从而促进了收敛特性的改进。因此，近年来出现了许多成功案例，包括离散、连续、单目标和多目标优化领域，包括机器学习中的各种应用 [10-22]。进化式多任务处理的实用性也已在制造过程设计 [14]、机器人控制器设计 [23]、车辆路由 [4, 7]、云计算 [24] 和软件工程 [24] 等广泛的实际应用中得到证明。25]，仅举几例。
• 虽然从业者有许多算法选项可供选择，但值得注意的是，当今多任务解决方案的适用性和成功在很大程度上取决于任务相关性。对于那些优化问题几乎没有共同之处的情况，盲目地在它们之间传递知识(以编码解决方案的形式)会导致主要的负面(有害)影响[14，26，27]。事实上，对消极任务间相互作用的易感性阻碍了整体的趋同行为[23]。现有的进化多任务算法，如多目标多因子进化算法(MO-MFEA) [14]，通常缺乏情境感知的认知能力[2]，因此无法动态破译和适应不同任务之间的相似度。
• 综上所述，越来越重要的是能够处理来自多个优化任务的传入数据流并识别它们之间的关系的算法的设计。基于此，本文提出了一种基于认知进化的多任务处理方法，并将其命名为MO-MFEA-II。MO-MFEA-II集成了多任务搜索过程中在线生成的数据的概率模型，以揭示不同任务之间重复出现的解决方案模式(通过搜索分布的相似性衡量)。提出的数据驱动的方法展示了对何时以及传递多少知识的意识——很像有意识的人类大脑，它决定专注于哪些任务，以及何时抑制无关信息[28]。我们注意到MO-MFEA-II的基础包含了最近引入的具有在线学习能力的多因子进化算法(MFEA-II)[23]中描述的思想。MFEAII专注于单目标优化，而本文提出的MOMFEA-II分析了类似的概念如何也可以应用于多目标优化领域。因此，据我们所知，本文是最早利用概率建模来捕获进化多任务环境下多目标优化任务间关系的研究之一。
• MO-MFEA-II的功效首先在一系列综合测试功能中展示。此外，我们强调了一个自然和实际有用的方法在多保真度优化领域的应用；即，利用低保真度函数近似值，通过多任务处理来加速相关高保真度任务的优化性能。
• 本文其余部分的组织如下。第二节介绍了多目标优化和相关的多目标进化算法的背景。此外，我们对文献中的相关工作进行了简要回顾，并对现有的MO-MFEA框架进行了总结。第三节给出了具有在线传输适应能力的MO-MFEA-II。第四节和第五节分别提供了关于广泛的多目标基准和实际案例研究的实验结果和分析。第六节对本文进行了总结，并对今后的工作进行了讨论。

2.BACKGROUND

• 在本节中，我们首先介绍多目标优化和相关的单任务进化算法的初步。然后，简要回顾了进化多任务处理的最新进展，特别是在多目标优化领域。本文概述的贡献是比较和对比那些可用的文献。最后，对现有的MO-MFEA进行了讨论，并指出了其潜在的局限性。

2.3 多任务多目标优化算法

• 自从进化多任务的概念出现以来，多目标优化领域也出现了相关算法的发展[14,37]。特别是，一些具有自适应知识转移能力的方法也已经出现。例如，Feng等[8]提出使用去噪自编码器学习不同连续多目标任务之间的最优线性映射。在这种方法中，学习到的映射作为任务之间的桥梁，提供了搜索空间(和解决方案)的转换，从而可以进行自适应的知识转移。
• 此外，在[38]中，采用基于信用分配的技术来以促进探索的方式调整任务之间的知识转移，从而防止解决方案被困在本地最佳局部。最近，林等。al。[21]使用增量朴素贝叶斯分类器选择要在多任务搜索期间转移的有价值的解决方案。在其提出的方法中，作者还使用随机映射，增强了转移解决方案的勘探能力，目的是提高整体收敛行为。[38] H. T. T. Binh, N. Q. Tuan, and D. C. T. Long, “A multi-objective multi-factorial evolutionary algorithm with reference-point-based approach,” in 2019 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2019, pp. 2824–2831 [21] J. Lin, H. Liu, B. Xue, M. Zhang, and F. Gu, “Multi-objective multi-tasking optimization based on incremental learning,” IEEE Transactions on Evolutionary Computation, pp. 1–1, 2019 (EMT-IL)
• 尽管对设计自适应多任务求解器的兴趣越来越大，但许多现有方法是基于任务相关性的先验假设设计的，使得来自源的解可以直接转移到目标任务。还提出了一些其他方法，学习任务之间的映射，目的是在它们各自的目标函数之间引入高(序数)相关性[27]。然后，将学习到的映射应用于转移的解决方案，增加它们对目标任务有益的可能性。然而，值得注意的是，现有方法通常不提供任何明确的措施来防范负迁移的威胁；例如，当学习的映射不准确时。在这方面，我们提出的算法的关键新颖之处在于，它采用了数据驱动的方法来明确防止负传输。我们的方法基于一个简单的想法，即通过学习不同任务的搜索分布重叠的程度，可以调整它们之间要传递的知识量。[27] K. K. Bali, A. Gupta, L. Feng, Y . S. Ong, and T. P . Siew, “Linearized domain adaptation in evolutionary multitasking,” in Evolutionary Com- putation (CEC), 2017 IEEE Congress on. IEEE, 2017, pp. 1295–1302.

2.4. Overview of the Existing MO-MFEA

• MO-MFEA[14]是最近提出的一种方法，通过促进全方位知识转移[10]，可以同时有效地分辨多个MOOPs。我们的意思是，所有的任务都可以通过相互的知识共享而受益。为了实现这一点，首先定义了所有组成优化任务的统一搜索空间编码解决方案。至少在盒约束连续优化的情况下，这种统一是通过任务特定解空间和统一空间[39]-之间的简单线性映射直接实现的，也是连续的，定义在[0,1]D范围内 [14] A. Gupta, Y .-S. Ong, L. Feng, and K. C. Tan, “Multiobjective multifac- torial optimization in evolutionary multitasking,” IEEE Transactions on cybernetics, 2017 [10] A. Gupta, Y .-S. Ong, and L. Feng, “Insights on transfer optimization: Because experience is the best teacher,” IEEE Transactions on Emerging Topics in Computational Intelligence, vol. 2, no. 1, pp. 51–64, 2017 [39] J. C. Bean, “Genetic algorithms and random keys for sequencing and optimization,” ORSA journal on computing, vol. 6, no. 2, pp. 154–160, 1994
• 在MO-MFEA模型中，属于不同任务的亲本解决方案之间的任务间交叉过程中，知识传递的主要方式是隐性遗传传递。从本质上讲，遗传传递的程度是由一个定义为随机交配概率(rmp)的用户定义的固定标量传递参数决定的。关于MO-MFEA的更多细节，请参阅[14]。
• 1) rmp参数调优:值得注意的是，MO-MFEA中的rmp参数是根据决策者的直觉手动指定的。也就是说，如果已知优化任务具有较高的任务间相似性，则rmp通常设置为接近1的值。另一方面，已知任务间相似性较低的优化任务之间规定了较低的rmp值(接近于0)。显然，这种离线rmp分配方案严重依赖于从业者头脑中关于不同优化问题之间关系的先验知识的存在。在实际设置中，对不同优化问题的领域特定知识的访问常常是有限的，特别是在一般的黑盒优化中。由于可能缺乏关于任务间关系的先验知识，对rmp的适当选择可能成为一个从业者的重大障碍。事实上，也有研究表明，不恰当(盲目)的rmp值(通过试错)可能会导致有害的基因转移，从而导致显著的性能减缓[23]。

3.COGNIZANT MULTITASKING MO-MFEA-II

• 本节提供了提议的MO-MFEAII的细节，它提供了其前身MO-MFEA的数据驱动和认知增强。具体来说，我们希望该算法能够自动决定何时以及传递多少知识，这样负传递的威胁就会最小化。为此，MO-MFEAII在线学习rmp参数(取代离线rmp分配)，从而适应多任务设置中不同任务之间的遗传转移程度。为了开发一种具有知识转移适应能力的在线rmp估计技术，在现有的MO-MFEA中引入了两个关键思想。这些包括:
• 利用RMP矩阵代替标量rmp，有效地跨两个以上的任务进行多任务处理，任务间的关系可能各不相同。例如，给定三个不同的优化任务，第一个和第二个任务之间的相似度可能不同于第一个和第三个任务之间的相似度。因此，对所有任务对使用相同的rmp值被认为限制太多。
• 从概率建模的角度定义维护对象-MFEA框架，以便根据搜索分布中重叠的量化来捕捉任务间的相似性。MO-MFEA-2装备有多任务搜索过程中在线生成的数据模型，以揭示不同任务之间重复出现的解决方案模式。

3.1 RMP矩阵

3.2 Latent Search Distributions in the MO-MFEA(MFEA模式中的潜在搜索分布)

• 在这里，我们简要描述了知识转移是如何在最初的MFEA任务中实现的，通过从不同任务中提取的搜索分布的隐式混合。
• 使用概率分布进行拟合

3.3 基于概率模型的搜索预备

• 对于一个理想的多任务引擎，其目标是尽可能促进有效的传输(例如，通过学习成对的正rmp值)，同时最小化负的任务间交互。提出的想法是利用多任务优化运行过程中生成的数据,和学习一个RM P矩阵导致一个有效的混合分布Eq。(3)。例如,如果搜索分布相互远离的各自的任务在一个统一的搜索空间,因此，不能推断出它们之间的关系，我们希望相应的成对RMP值自动地非常低(接近于零)。另一方面，如果搜索分布重叠，理想情况下应该指定更高的rmp值。这种学习策略期望在不影响不相关任务的表现的同时，使相关任务受益。
• 为了进行这一学习，我们借鉴了现有的基于概率模型的搜索算法的理论。这些算法通过迭代建立父解的概率模型来指导优化搜索，然后通过对这些模型进行采样来生成新的子代。典型的步骤可以总结如下。

• 定理1中总结了一个支持这类算法的著名结果。简单地说，该结果突出了学习概率模型q(x, t)的好处，该模型能够准确地捕获真正的潜在父分布p(x, t)，以便获得渐近收敛的保证。这一定理也是本文提出的在线学习RM P矩阵的数学程序的基础，详见(III-E)节。

• 定理1。考虑一个目标函数为f且全局最优的连续优化任务T。在搜索空间X中，从其采样初始解的先验分布q(x，0)在任何地方都被假定为正且连续的，N → ∞。这样，在基于概率模型的进化算法的每次迭代“t”中，如果子代被采样的学习模型q(x，t)与真正的父代分布p(x，t)相同，则搜索渐近收敛于分布p(x，∩) [40] Q. Zhang and H. Muhlenbein, “On the convergence of a class of estimation of distribution algorithms,” IEEE Transactions on evolutionary computation, vol. 8, no. 2, pp. 127–136, 2004
• 以上的证明可以在[40]中找到。我们注意到，这一结果最初属于单目标优化的情况，并已在[23]中用于学习单目标优化任务的多任务环境下的优化混合模型。相反，在本文中，我们也研究了相同的结果如何导致MO-MFEA的性能提高。接下来将介绍合成的MO-MFEA-II的细节。(其实这里是说，MFEA-II已经提出了这里提出MOMFEA-II)

3.4 概率混合模型MOMFEA-II

• 由定理1可知，在这种概率解释中，如果子代分布等于父分布，则保证在N→∞极限下渐近收敛。这一结果表明，对RM P矩阵的学习使Eq.(4)中的混合模型qk c(x, t)准确地复制了pk(x, t)，对于所有k∈{1,2，…， K}，会隐性地减少任务间负向交互作用的倾向。（意思就是通过调整RMP矩阵使得迁移后的分布尽可能和原来的子代分布接近~）

3.5 Learning the RMP Matrix Online in MO-MFEA-II

• 而为了学习这个分布，就是满足下面这个式子。具体原理如这个原理2所示。

• 以上的证明可以在[23]中找到，其中Kullback-Leibler散度被用作概率分布之间差异的标准度量。考虑到优化RM P矩阵的计算可操作性，我们注意到Eq.(5)中的数学程序是向上凸的。因此，在实践中，使用经典的凸优化求解器可以在很小的计算开销(只要K不太大)下学习RMP矩阵。
• 注意：模型太复杂，容易过拟合，如果过拟合，应该使用一些简单点的模型，或者在数据集中添加少量的均匀采样噪声

3.6 Summary of the MO-MFEA-II

• 总体而言，大部分和MOMFEA 一致，但是突出的是RMP的学习过程，即如何调整RMP。

• 对于子代的生成，首先通过二元竞赛选择(第9行)选择一个候选亲本P (t)。选择是基于每个个体的标量适应度，然后使用选定的父群体建立概率模型，并根据Eq.(5)学习RMP矩阵。请注意，RMP矩阵目前在每一次迭代t(第10行)在线学习和适应。
• 除了属于同一任务的父母解决方案之间的传统任务内交叉(第13 - 15行)，任务间交叉(第16 - 18行)也发生在属于不同任务的父母解决方案之间(即父母具有不同的技能因素)。特别是，MO-MFEA-II中隐性遗传转移的程度受学习到的RM P矩阵中的成对rmp值控制——该值规定了可能具有不同技能因素的两个解决方案xi和xj之间任务间交叉的概率。显然，如果学习到的RMP是单位矩阵，那么就不会实现知识转移。
• Selective evaluations in MO-MFEA-II: Each of the offspring individuals is evaluated with respect to only one task (its assigned skill factor) amongst all other tasks in the multi- tasking environment (line 26). This salient feature combats the issue of otherwise exhaustively evaluating every individual for every task, which would often be computationally demanding. Post evaluation, the fittest N · K individuals survive for the next iteration of the evolutionary search (line 30). The aforementioned steps (lines 7 − 31 in Algorithm 1) repeat until some stopping condition is met.
• MO-MFEA-II 中的选择性评估：在多任务环境中的所有其他任务（第 26 行）中，每个后代个体仅针对一项任务（其分配的技能因素）进行评估。这一显着特征解决了为每项任务详尽评估每个人的问题，而这通常需要大量计算。评估后，最适合的 N·K 个个体在进化搜索的下一次迭代中存活下来（第 30 行）。上述步骤（算法 1 中的第 7-31 行）重复进行，直到满足某个停止条件。