论文研读-多因子进化算法中的自适应知识迁移MFEA-AKT

演化计算与人工智能

发布于 2022-01-24 14:05:54

1K0

发布于 2022-01-24 14:05:54

文章被收录于专栏：人工智能与演化计算成长与进阶人工智能与演化计算成长与进阶

论文研读-多因子进化算法中的自适应知识迁移MFEA-AKT

Toward Adaptive Knowledge Transfer in Multifactorial Evolutionary Computation

觉得有用的话,欢迎一起讨论相互学习~

此篇文章为 [1]L. Zhou, L. Feng, K.C. Tan, J. Zhong, Z. Zhu, K. Liu, C. Chen, Toward Adaptive Knowledge Transfer in Multifactorial Evolutionary Computation, IEEE Transactions on Cybernetics. 51 (2021) 2563–2576. https://doi.org/10.1109/TCYB.2020.2974100. 的论文学习笔记，只供学习使用，不作商业用途，侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正！
这篇文章有趣的一点是第一次从自适应交叉算子的角度考虑迁移~重点在4.2节

摘要

多因子进化算法(MFEA)是最近提出的一种进化多任务优化算法，它可以同时优化多个优化任务。通过设计不同任务间的知识转移，MFEA在收敛速度和解的质量上都优于单任务。在MFEA中，任务间的知识转移是通过具有不同技能因素的解决方案之间的交叉来实现的。因此，这种交叉对MFEA的性能是必不可少的。然而，我们注意到目前的MFEA及其大多数现有变种仅采用单一交叉知识转移，并在进化搜索过程中对其进行修正。由于不同的交叉算子在生成子代时具有独特的偏倚，因此在MFEA中为知识转移配置适当的交叉算子是实现鲁棒搜索性能、解决不同问题的必要条件。然而，据我们所知，MFEA中对于知识转移的跨界者的自适应配置还没有进行任何努力，因此本文试图填补这一空白。特别地，在这里，我们首先研究了不同类型的交叉如何影响MFEA中的单目标(SO)和多目标(MO)连续优化问题的知识转移。此外，为了实现鲁棒高效的多任务优化性能，提出了一种具有自适应知识转移的MFEA (MFEA-akt)算法，该算法基于进化搜索过程中收集的信息自适应知识转移的交叉算子。（探索交叉算子）

Introduction

Multi - factorial optimization (MFO)是Gupta等人在2016年提出的一种新的进化优化范式，用于多任务优化[1]，[2]。与传统的进化算法(EA)在一次运行中只优化一个任务不同，MFO可以同时优化多个任务。在多任务优化过程中，由于任务间的隐性知识转移，MFO在收敛速度和求解质量方面都优于单任务匹配，包括连续、离散、以及连续和离散混合优化问题[3]-[7]。
MFFO在[1]中提出了Multifactorial EA（MFEA），其用作MFO范例的特定实现。由于其简单的实施和强大的搜索能力，它引起了很多研究的关注，因为它提出了它。例如，yuan等人[8]提出基于置换的MFEA，以有效地解决组合问题，例如旅行推销员问题（TSP），二次分配问题（QAP）和作业调度问题（JSP）。Gupta等在多目标（MO）优化[9]和Bilevel优化域中，将MFEA扩展到多任务处理[9]和Bilevel优化[7]。此外，LiAW和TING [10]扩展了MFEA，用于解决许多任务优化问题，其中优化的任务数量超过两个。在[11]中，将线性化域适配策略集成到MFEA中，以将简单任务的搜索空间转换为类似但复杂任务的搜索空间，以便可以减轻负转移。此外，丁等人[12]提出了一种称为G-MFEA的广义MFEA，以用分离的最佳和不同的可变尺寸来解决任务。龚等人[13]和Wen和Ting [14]将资源重新分配到MFEA中的综合资源重新分配策略，该策略根据复杂性分配计算资源的任务。Tang等人[15]提出了一种基于群体的MFEA来对类似类型的任务进行分组，遗传信息只能在同一群体内转移。最近，提出了一种增强的MFEA (MFEA- ii)，它采用在线传输参数估计方案动态控制任务[16]之间的知识交换程度。在这些多任务算法中，所有任务都由单个个体群体进行优化，使用一个通用的解决方案表示，将不同的问题域集成到一个统一的搜索空间中。每个个体都被分配了一个技能因素，这个技能因素表示个体表现最好的任务。当两个具有不同技能因素的个体通过交叉方式产生后代时，任务间的知识转移隐式发生。
在文献中，针对不同的优化问题，提出了许多具有不同搜索能力的交叉算子[17]-[20]。例如，一点和两点交叉[21]，[22];均匀交叉[23]，[24];模拟二进制交叉(SBX) [25]， [26];等，都被引入来解决连续优化问题，而顺序交叉(OX) [27]， [28];部分映射交叉(PMX) [29]， [30];等，进行了组合优化设计。研究发现，不同的crossover operator对于解决不同的问题具有不同的能力。特别是在[31]中，有报道称，在具有单峰、多峰、噪声和离散搜索空间等各种属性的12个基准函数[32]上，多点和均匀交叉的性能显著优于一点和两点交叉。Michalewicz等人[33]的研究表明，在大多数无约束连续问题上，几何交叉优于算术交叉。作者还提出，几何交叉在全局最优位于可行域边界的问题上表现良好。在[25]中，我们发现SBX在困难的测试函数如双峰、不相等扩散函数和极点问题中表现优于其他实数编码的交叉，如BLX-α交叉。在这些工作中，我们可以观察到，不同的交叉具有独特的偏见产生后代，以指导进化搜索。因此，在进化多任务处理中，这些交叉点也可能具有不同的内隐知识转移能力。显然，交叉决定了任务间知识转移的质量。由于不同的交叉解在解生成过程中具有独特的偏倚性，因此利用适当的交叉解实现任务间的知识转移对进化多任务处理的性能至关重要。但值得注意的是，现有的进化多任务算法[8]-[16]采用单一且固定的交叉算子进行知识传递，当配置的交叉算子不能很好地匹配所遇到的问题时，会阻碍多任务处理。为了提高多任务处理的效率和有效性，需要使MFEA具有自适应的知识转移能力，以便针对不同的问题采用不同的知识转移crossover operator。然而，据我们所知，文献中没有关于自适应MFEA设计的研究。因此，本文试图填补这一空白。[25] R. B. Agrawal, K. Deb, and R. B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Syst., vol. 9, no. 2, pp. 115–148, 1995.
特别是，在本文中，我们首先研究了不同的知识转移交叉对MFEA多任务优化性能的影响。通过使用[34]和[35]中的单目标(SO)和MO多任务基准，可以观察到不同的crossover operator在不同的任务上取得了更好的性能。根据“没有免费的午餐”[36]理论，知识转移不存在单一的交叉，可以很好地完成所有的基准任务。此外，为了在不同优化任务上实现鲁棒高效的多任务处理，我们提出了一种新的具有自适应知识转移的MFEA，称为MFEA-AKT。在该算法中，基于在线进化搜索过程中收集到的信息自适应地配置任务间知识转移的交叉算子。特别是，在MFEA-AKT中，每个个体都分配了一个转移交叉指标(Tci)，该指标用于确定用于知识转移的交叉。每个个体的Tci根据每一代任务中生成的后代的表现进行更新。为了验证所提MFEA-AKT的有效性，本文分别对常用SO和MO多任务基准[34]、[35]以及基于CEC2014 SO测试包[37]和LZ09 MO基准[38]构建的新的SO和MO多任务问题进行了综合实验。实验结果表明，与固定知识转移交叉算子的MFEAAKT相比，所提出的自适应交叉配置在SO和MO优化问题上都能获得更优或更具竞争力的性能。
本文的其余部分组织如下。第二节对MFEA进行了简要介绍，并对文献中代表性的交叉算子进行了综述。第三节研究了不同crossover operator配置为知识转移时MFEA的多任务性能。在此基础上，第四节给出了提出的MFEA-AKT的详细信息，第五节给出了MFEA-AKT的实验结果并进行了讨论。最后，第六节给出了本文的结论。

PRELIMINARIES

在本节中，我们首先介绍[1]中提出的MFEA。接下来，对文献中提出的用于连续优化的代表性交叉算子进行回顾和讨论。

2.1 MFEA

MFEA最早由Gupta等人提出，旨在同时解决多个优化问题。在MFEA中，不同的问题通过在统一的搜索空间中定义的单个个体群体进行优化。为了评估多任务处理的个体，为每个个体定义了以下属性。

2.2 代表性交叉算子

通常，交叉表示重组操作者，其在父母之间交换遗传物质以在EA中产生后代。在过去的几十年中，在文献中提出了许多交叉算子，在广泛的优化问题中提出了[39] - [41]。在本节中，我们简要介绍了现有的代表交叉算子，并讨论了这些交叉以了解知识转移的差异。特别是，根据调查[42]，现有的交叉可以分为三个类，那是：1）离散交叉; 2）基于聚合的交叉;3）基于领域的交叉。让p、c和n分别表示个体的父代、后代和维度。代表性的现有交叉算子综述如下。

2.2.1 离散交叉

2.2.2 聚合交叉

将两个亲本的组合遗传片段转移到具有聚集功能的后代，如图2所示。由于聚合函数确定时后代的位置是固定的，所以遗传是确定的。交叉的例子包括算术交叉[45]，几何交叉[46]，线性交叉[47]等。在本文中，算术交叉和几何交叉被认为是该组中具有代表性的交叉算子，其给出如下。
Crossovers belonging to ABCOs transfer the combined genetic segments of the two parents to the offspring with an aggregation function, which is illustrated in Fig. 2. As the position of the offspring is fixed when the aggre-gation function is determined, the genetic inheritance is deterministic. Examples of ABCOs include arithmetical crossover [45], geometrical crossover [46], linear crossover (LX) [47], etc. In this article, the arithmetical crossover and the geometrical crossover are considered as the representative crossover operators in this group, which are given as follows.

2.2.2.1 算数交叉

子代决策变量是两个选择的亲本的线性组合

where λ is a predefined coefficient, which ranges from 0 to 1.

2.2.2.2 几何交叉

子代第i位的元素是两个选定亲本的指数组合

2.2.3 邻域交叉

这个组中的杂交从父母之间的间隔中提取遗传物质，具有预定的概率分布。这个区间定义为父母的邻域。与前面提到的其他两组交叉相比，我们可以看到NBCOs给出了一种更灵活的生成后代的方法，从而可以在进化搜索过程中引入更高的多样性。该组中有代表性的杂交包括模糊重组[48]，BLX-α [49]，SBX [50]等。特别地，BLX-α交叉和SBX交叉在这里被用作研究的说明性交叉，它们分别基于均匀和指数概率分布。如图3所示，这两个交叉算子的细节如下。

As can be observed, different crossovers have various forms that possess unique bias in generating offspring. Since crossover has also been employed in MFEA for implicit knowledge transfer across tasks, it may lead to different forms of knowledge transfer when different crossovers are config- ured, which could result in diverse multitask optimization performance
可以观察到，不同的杂交有不同的形式，在产生后代时有独特的偏好。由于交叉在MFEA也被用于跨任务的隐性知识转移，当配置不同的交叉时，可能导致不同形式的知识转移，这可能导致不同的多任务优化性能。

KNOWLEDGE TRANSFER VIA DIFFERENT CROSSOVER OPERA TORS IN MFEA

在本节中，我们使用[34]和[35]中常见的多任务优化问题，研究了不同的知识转移交叉算子如何影响MFEA的性能。
In particular, the PILS and NIMS SO multitask problems, and the CIHS and NIMS MO multitask problems are studied in this section. More details of the multitask benchmarks and configurations of the crossovers will be presented later in Section V. Fig. 4 presents the averaged convergence graphs of MFEA with six different crossover operators for knowledge transfer on the four multitask problems, over 20 independent runs. In Fig. 4(a) and (b), the y-axis denotes the averaged fitness (objective value) in log scale, and the x-axis is the generation number. Further, in Fig. 4(c) and (d), the y-axis represents the averaged IGD value in log scale, and the x-axis denotes the generation number.
As can be observed in Fig. 4, the performance of MFEA varies when different crossover operators have been employed for knowledge transfer. The performance gap in terms of objective value and IGD can be observed clearly from Fig. 4. For instance, on NIMS2 of Fig. 4(d), the BLX-α crossover converges about two times faster than the SBX crossover since the 200th generation. Furthermore, the arithmetical and geo- metrical crossover achieved the best performance on both SO PILS and SO NIMS. Particularly, on PILS [see Fig. 4(a)], while other operators are all stagnated at the early optimization stage, the arithmetical and geometrical crossover converged fast and obtained much better solutions. However, on MO CIHS, these two crossovers degraded to the worst crossover operators, as shown in Fig. 4(c). Further, on the MO prob- lems, the BLX-α crossover achieved the best IGD on MO PILS, while the geometrical crossover outperformed the others on MO NIMS2. These observations confirmed that different optimization problems may require different configurations of crossover for knowledge transfer across tasks, for efficient multitask optimization performance, and there is no single- crossover operator can perform well on all the SO and MO problems.
Toward robust and efficient multitask optimization performance when different problems are encountered, here,we thus propose a new MFEA with an adaptive configuration of crossover for knowledge transfer, called MFEA-AKT, which will be presented in the next section.

PROPOSED MFEA WITH ADAPTIVE KNOWLEDGE TRANSFER

This section presents the details of the proposed MFEA- AKT. In particular, the framework of MFEA-AKT is illustrated in Fig. 5, where the main differences between MFEA-AKT and the original MFEA are highlighted in the dashed boxes. In the proposed MFEA-AKT, we first introduce three new definitions, which are given as follows.

定义1(转移交叉指标):个体的转移交叉指标(Tci)为[1，m]范围内的整数，其中m为可用于知识转移的交叉算子个数。特别是，Tci= i表示个体更喜欢使用第I个交叉算子与其他个体共享知识。
定义2(转移后代):转移后代是指具有不同技能因素的父母通过交叉产生的解。
定义3(直系父母):与被转移的后代具有相同技能因素的父母被定义为后代的直系父母。
在MFEA-AKT中，对于适应性知识转移，每个个体的转移交叉指标最初是随机分配的。接下来，自适应分类交配开始基于交配个体的Tci自适应地配置用于跨任务的知识转移的交叉算子。根据进化搜索过程中收集的信息更新每个个体的Tci。此外，每个后代个体的Tci是通过适应性垂直文化传播获得的。最后但并非最不重要的是，MFEA-AKT的其他程序，如初始化、解评估和选择，保持与[1]中的MFEA相同。