论文研读-多目标优化中的多源选择迁移框架

2020-08-14 16:05:04 浏览数 (1)

论文研读-多目标优化中的多源选择迁移框架

Multisource Selective Transfer Framework in Multiobjective Optimization Problems

  • 此篇文章为 J. Zhang, W. Zhou, X. Chen, W. Yao and L. Cao, "Multisource Selective Transfer Framework in Multiobjective Optimization Problems," in IEEE Transactions on Evolutionary Computation, vol. 24, no. 3, pp. 424-438, June 2020, doi: 10.1109/TEVC.2019.2926107. 的论文学习笔记，只供学习使用，不作商业用途，侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正！

Abstract

  • 在实际复杂系统设计中，当启动具有另一个参数配置的新优化实例时，总是从头开始执行，浪费大量时间重复类似的搜索过程。受可以重用过去经验来解决相关任务的迁移学习的启发，许多研究人员更加注重探索如何从过去的优化实例中学习以加速目标实例。在实际应用中，数据库中已经存储了相似资源实例。基本问题是如何评价迁移能力以避免负迁移 ， 为了获得源实例与目标实例之间的关联性，我们开发了一种名为质心分布的优化实例表示方法，该方法借助于精英候选解在进化过程中估计分布算法（EDA）中学习的概率模型的帮助。Wasserstein 距离用于评估不同优化实例的质心分布之间的相似性，在此基础上，我们提出了一种新颖的框架，称为多源选择性转移优化，其中包括三种合理选择源的策略。为了选择合适的策略，根据源和目标质心分布之间的相似性总结了四个选择建议。该框架有利于选择最合适的资源，从而可以提高解决多目标优化问题的效率。 为了评价提出的框架和选择方法的有效性，我们进行了两个实验：
  1. 复杂多目标优化问题 benchmark
  2. 一个实际的卫星布局优化设计问题 实验结果证明，提出的算法有更好的收敛速度和 HV 值
  • 摘要：估计分布算法(EDA),多目标优化，多源迁移，迁移优化， Wasserstein distance

Introduction

  • 对于实际工程中的复杂系统设计问题，以卫星系统设计为例，有很多过去的经验，例如在启动新设计之前，已将不同布局的卫星布局解决方案设计存储在数据库中。利用以往的经验不仅可以提高优化效果，而且可以提高收敛速度。 对于复杂的系统设计而言，这非常重要，因为它通常涉及计算成本高昂的多学科分析[1]。但是，如何利用这些知识来加快新设计的速度，会使卫星设计者感到困惑。转移学习关注从一个域到另一个域的数据迁移。各种研究已成功应用于经典机器学习任务，如分类任务[2]-[4]，如情绪分析[5]，数字识别[6]。近年来，进化算法界的研究人员试图将迁移学习应用到优化任务[7]-[10]中。
  • 三个需要关注的问题
  • Q1 (可迁移性) :如何识别相似的问题的可迁移性以降低不合适的负迁移。
  • Q2 (迁移组件) :解决方案，结构，参数等。
  • Q3 (迁移算法) :最后步骤是如何重用从源问题中提取的信息。大多数研究关注于一对一的域自适应算法，例如 MNIST 数据集[13]和 WIFI 数据集[14]等基准测试中的传输成分分析（TCA）[11]，TrAdaBoost [12]。但是，很少有研究集中在多源迁移学习问题上。
  • 在迁移学习研究领域，大部分工作集中在 Q2 和 Q3，尤其是 Q3。但是，Q1 也非常重要，因为从不适当的来源迁移会导致负迁移。在本文中，我们特别关注多源问题的可迁移性，并研究如何衡量不同优化问题的相似性
  • [15]证明任务间的相关程度对于多任务学习的有效性十分重要,[16]发展了一个基于自编码器的多任务优化算法，其任务选择主要取决于 1)帕累托前沿解的交叉程度 2)任务适应度景观的相似性 ，这些因素保证了相关性。但是，在实际场景中，我们一开始无法获得目标问题的上述信息。
  • 为了评估不同优化问题的相关性，应首先确定不同优化实例的表示形式。Santana et al. [17] 通过一种估计分布算法-估计贝叶斯网络算法（EBNA）将优化问题视为一个图形。在他的工作中，任务用图形表示。可以通过网络分析方法获得任务的相关性，但是表示方法在很大程度上取决于人为的图形特征，可能会丢失任务的相关信息。Yu et al. [18] 发明了一种新的表示强化学习任务的表示方法，该学习方法具有通过均匀分布采样的不同参数。他使用原型策略通过几次迭代获得的奖励向量（称为浅试验）来表示任务，从而使过去的强化学习任务得以重用。但是，演化过程中的浅层试验会产生太多噪声，无法准确表示优化实例。
  • 在每一个世代，利用估计分布算法(EDA)表示种群分布，我们可以利用综合分布来表示实例，在这里称为质心分布。质心表示种群在一个世代中的中心。通过计算实例(任务)分布之间的 Wasserstein distance(WD)可以获得任务之间的相似性。有了相似性，可以使用三种不同的基于遗传算法的资源选择策略来获得迁移的知识以加速进化过程中的搜索过程，为了高效使用这种策略，采用四种选择机制
  • 以下是本文的贡献：
  1. 提出一种新的表示方式叫做 质心分布 来度量不同优化实例的相似性
  2. 提出一种新的基于 EDA，NSGA-II 三种策略的多源选择迁移优化框架来优化多目标优化问题
  3. 总结了迁移资源选择策略的四点建议，在此基础上，提出了应对负迁移问题的混合策略。
  • 以下为本文内容概述：
  1. 第二节总结了迁移学习，EDA(估计分布算法)，进化动态优化算法(EDO)
  2. 第三节总结了基于 EDA 和 NSGA-II 的多源选择迁移优化算法的基本框架和流程图
  3. 第四节在多目标烟花算法 benchmark 上做了实验，并总结了四种资源选择策略并在一个实际问题上验证了算法
  4. 第五节总结了本文算法

Related work

Transfer optimization

  • 最近，开发了许多致力于通过机器学习技术提高现有进化算法效率的工作，尤其是重用了过去从相关问题中获得的搜索经验。Feng [7] 为了解决多目标优化问题，提出了一种基于自动编码器模型的新传输方法，加快了进化算法的搜索过程。
  • 迁移优化可以两类：单源和多源 ，目前研究大多数是单源迁移算法， 多源优化算法不仅注重迁移方式还注重实例表示和源选择
  • 具体算法流程和示意如图 1 所示：

Estimation of Distribution Algorithms 估计分布算法 EDA

  • EDA 是随机优化方法，可通过学习和抽样精英候选解决方案的显式概率模型来指导寻找最佳点。EDA 与常规进化算法（遗传算法算法）之间的主要区别在于，后者通过变异和交叉操作生成新的候选解，可以将其视为隐式分布。但是，EDA 使用由概率模型表示的显式分布，例如多元正态分布，贝叶斯网络等。
  • EDA 常见算法结构如下图所示：

根据决策变量的相互依赖，EDA 可以被分为三类：

  1. 单变量分解算法：其中每个变量都是相互独立的。代表算法有：基于种群的 population-based incremental learning (PBIL) 基于种群的增量学习 [22], univariate marginal distribution algorithm (UMDA) 单变量边际分布算法 [23], compact genetic algorithm (cGA) 紧凑遗传算法 [24], etc.
  2. 二元分解：在此类模型中， 变量之间的关系形成树或者森林图。双变量分解使变量之间的依赖关系形成树或森林图。代表性算法包含互 mutual information maximizing input clustering 信息最大化输入聚类（MIMIC）[25]，基于依赖关系树和二元边际分布的估计分布算法[26]等。
  3. 多元分解，使用有向无环图或无向图表示依赖关系 。贝叶斯网络[27]和马尔可夫网络[28]是两个代表性的模型。
  • 近年来，EDA 已用于众多具有挑战性的优化问题，尤其是在多目标优化问题[29]-[33]和多峰优化问题[34]，[35]中。借助从精英解中学到的概率模型，许多类型的研究[36]都集中于如何重用过去经验中的模型以加速目标实例搜索。受 EDA 迁移学习研究的启发，我们提出了一种表示实例的新方法，称为质心分布。基于表示形式，我们提出了三种资源选择策略来产生合适的知识以进行迁移。

Evolutionary Dynamic Optimization 进化动态优化 EDO

  • EDO 是进化计算领域中最活跃的研究领域之一。在某些 EDO 情况下，随着环境的变化，问题具有一些常见的模式。受此启发，许多研究集中在重用类似环境中的过去搜索经验来加速进化过程[37]，[38]。
  1. 一种常见的方法是通过一些特殊的点来学习并预测最优点的移动，Li [39]提出了基于特殊点的预测策略(SPPS):例如 feed-forward center point,前馈中心点, boundary point 边界点, and knee point 拐点。Ruan 等人[40]提出了一种基于中心点的混合多样性维护方法，以提高预测精度。Zou 等[41]提出了一种基于拐点来预测非支配集合的方法，以使种群迅速收敛到 PF。
  2. 另一种方法是预测发生更改时应重新初始化个体或种群的位置。Zhou 的工作[42]利用历史搜索经验来指导类似的目标搜索，以有效解决动态优化问题。提出了两种重新初始化策略，一种是根据历史预测个体的新位置。另一个则是通过某种噪声来扰动 perturb 当前种群，这些噪声的方差由先前的变化估计。
  3. 当环境周期性变化时，第三种方法称为基于 memory 的方法通常用于通过重用存储在内存中的相关帕累托最优集（POS）信息来解决 EDO 问题[43]-[46]。Jiang 和 Yang[37]提出了一种新的方法，称为稳态和世代进化算法（SGEA），该方法重用了过去分布良好的解，并且当环境发生改变时，根据先前和当前环境的信息重新定位了与新帕累托前沿有关的解 此外，多种群机制是解决问题的有用方法[47]，[48]。
  4. 最近的一些工作直接将迁移学习算法（例如 TCA）与动态优化算法集成在一起。Jiang 以此方式提出了两个算法框架。一种叫做 Tr-DMOEA，它结合了迁移学习和基于种群的进化算法[8]，另一种则是领域自适应和基于非参数估计的 EDA 的组合，称为 DANE-EDA [9]。与他的工作不同，我们主要侧重于如何从多个源任务中选择合适的源以加速进化过程。
  • 本文认为动态问题利用历史信息，但是问题除了某些参数以外，问题的定义没有发生变化，但是迁移学习不一样，其要通过历史信息优化的完全是不一样的两个问题。因此如何度量两个问题的相似性并且选择合适的迁移源将是本文的重点。

多源选择迁移优化框架

  • 现有大多数研究对一对一传输优化更感兴趣，而忽略了实际场景中的多源属性。在本文中，我们提出了一个多源选择性迁移优化框架来解决多源实例的问题。
  • 图 2 首先引入了实例表示，然后提出了源-目标相似度度量方法，提出了是那种源实例选择策略。

优化实例表示

  • 质心表示的源选择策略
  • 通过运行 GA 风格的算法，我们可以通过选择操作获得精英群体，可以将选择的解决方案的分布作为 EDA 的显式概率模型来学习。我们称其为学习型质心分布，以表示空间中当前的人口扩散趋势。
  • 下面的表示很关键，需要注意！
  • 为避免负转移，应在迁移算法启动之前确定合适的来源。我们提出的表示方法可以反映进化过程中源和目标之间的一些相似性信息，可以帮助目标实例选择合适的源进行迁移 。

源和目标相似度度量

  • WD 是在给定度量空间[50]上的概率分布之间定义的距离函数。在本文中，我们使用 WD 计算源和目标任务质心分布之间的距离。
  • 由于质心分布 C 满足独立多变量标准分布，WD 计算公式如下所示：
  • 关于 WD 和 Kullback–Leibler divergence 可以参考以下博文资料多元高斯分布的 KL 散度[1]各维度不相关的多元高斯分布[2]多元高斯分布[3]两种群决策变量高斯分布的 KL 散度和 WD 距离[4]

迁移源选择策略

  • 因为使用不同的优化方法和不同的停止条件，即使是相同的优化任务也会得到不同的优化结果。并且对于高度复杂非线性和具有不同非连接局部最优的多模态优化问题，即使是使用相同的优化算子，每次得到的结果都有可能不一样。因此，即使迁移源看起来很不一样，也许其实是来自相似的任务。实际上，当给予大量的源数据并且没有优化函数和每个源使用的优化器的先验知识的时候，很难正确判断源与目标之间的差异是否源于任务之间的差异。 因此，在本文中，我们提出了“质心分布的距离越近，实例相关程度越高”的选择策略，这实际上是一个充分但不是必要的条件。如果距离很近，我们判断实例是相关的并且可以选择。但是相反，如果实例相关，则我们无法判断分布将是紧密的。
  • 根据以上的分析，根据相似性，提出了三种迁移源选择策略来生成到目标实例的迁移种群，如图 4 所示。

最近迁移策略--挑选质心分布最相似的任务进行迁移

  • 在 NSS 中 认为相似程度最高的任务中包含有最有用的迁移知识。

权重选择策略--利用所有资源知识

  • 在某些情况下，某些源可能几乎位于相同的相似度级别（也就是说多个源和目标的相似程度接近，难以挑选）。如果我们使用一个源进行迁移，则会丢失一些有关其他源的有用信息。在这种情况下，提出了一种利用所有源知识的新策略。由于不同源对迁移效率的贡献程度不同，因此最终源是当前这一代所有源的加权总和。该策略称为加权选择策略（WSS）。
  • 这里 wi 是一个标量，而 P 是一个矩阵
  • 在 WSS 中，所有源都是有用的，但是每个源的迁移程度，重要程度不同~

TopK 选择策略--按照相似度挑选 TopK 个源

  • WSS 的改进版，按照相似度挑选前 K 个源

策略选择建议

  • 在这一部分中，总结了四个建议，以指导在特定条件下选择合适的选择策略。
  1. 首先，提出最大相似率：
  • 这表示相似度最大的源任务能够占所有任务相似度的比。
  1. 相似度的方差引导，决定使用 WSS 还是 TopK
  • 相似度方差小--WSS，相似度方差大--TopK
  • 基于以上分析，选择源选择策略的建议可以总结如下:
  1. 最大相似度 msr 很大--NSS 选择最好的
  2. msr 较小，相似度方差小--WSS
  3. msr 较小，相似度方差大--TopK
  4. 当 msr 较低，且方差位于 WSS 和 Top-K 策略的临界范围时，不建议调用迁移操作。(是否忽视了不依赖相似度从而跳转的可能性？！)
  • 基于以上建议，提出了三种策略的混合版本，称为混合选择策略（MSS）。为了探索在进化过程中是否在每一代中需要进行转移，将每次触发源选择策略。根据所有源和目标之间的相似性信息，由以上建议确定是否转移。更多的相似度计算带来更多的计算成本，但实际上也利用了更多的信息。

Transfer Method 迁移模块

  • 使用[7]中提出的自编码器迁移进化算法进行迁移~
  • 具体而言：
  • 源种群和目标种群可以通过一层具有可靠理论推论的单层去噪自动编码器[7]连接起来。如图 5 所示，基于自动编码器的迁移方法的关键是学习从源到目标种群的映射 M。
  • 需要注意这个映射矩阵是随着迭代不断变化改进的，需要隔一定的世代重新构建一次。以往问题的优化解包含了大量的知识，可以提高目标优化搜索速度，使我们可以通过学习映射将以往经验中的最佳解转移到目标中。
  • 迁移矩阵最终由以下式子进行确定：

Proposed Framework 提出的框架

  • 提出的 MSSTO 的算法框架如图 6 所示，伪代码如算法 2 所示，G 设置为 10：
  • 其中使用的候选解有
  1. 上一代种群
  2. 经过交叉和变异后的子代种群
  3. 经过迁移算法得到的种群
  • 初始化之后，框架开始执行种群重组，信息迁移和选择操作的循环。为节省计算量，迁移操作只有在世代为 G 的倍数的时候调用，迁移算子被调用时，源实例和目标实例首先由质心分布表示，质心分布首先由（1）和（2）定义。然后，可以通过（3）和（4）来计算源和目标之间的相似性得分。接下来，将根据（5）–（9）选择合适的迁移源。最后，由（10）和（11）产生要迁移的学习种群。完成最终适应性评估后，循环停止。（5）-（9）中定义的三种选择策略可以为转移方法的后续过程提供最终的源种群。该策略不仅可以提高优化效果，而且可以提高收敛速度，从而减少适应性评价量。实际应用中较少的评估意味着更少的模拟或实验，从而可以节省大量的计算或实验成本。

参考资料

[1]多元高斯分布的KL散度: https://blog.csdn.net/u013555719/article/details/106797330

[2]各维度不相关的多元高斯分布: https://blog.csdn.net/u013555719/article/details/106794789

[3]多元高斯分布: https://blog.csdn.net/u013555719/article/details/106714411

[4]两种群决策变量高斯分布的KL散度和WD距离: https://blog.csdn.net/u013555719/article/details/106716351

编程算法 迁移 迁移学习 机器学习 强化学习

0 人点赞