AEMTO--一种自适应进化多任务优化框架

AEMTO–一种自适应进化多任务优化框架

title： Evolutionary Multitask Optimization With Adaptive Knowledge Transfer

author： Hao Xu, A. K. Qin, and Siyu Xia.

journal： IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION (TEVC)

DOI：10.1109/TEVC.2021.3107435

code: GitHub - haoxuhao/AEMTO: Source code for paper AEMTO: Evolutionary Multi-task Optimization with Adaptive Knowledge Transfer ，AEMTO（AEMTO在MTO-Platform上的实现）

1.主要贡献：

1）平衡自我进化与知识转移：使用每一代种群成员的更新率作为奖励，使用知识迁移与自我进化的历史积累奖励的比率来在线地估计知识转移的帮助程度。并使用这个估计自适应地调整转移概率和控制知识转移的频率。

2）知识源选择：使用从源任务到目标任务的知识重用成功率作为奖励，使用在线估计地从源任务到目标任务地帮助度作为历史积累奖励。并且在所有候选源任务地帮助度上应用概率匹配(PM)策略来计算源任务选择概率。

3）知识转移强度：在源任务选择概率上应用随机通用选择(SUS)来选择源任务的目标任务和确定知识的数量，应用轮盘赌选择(RWS)策略在确定的源任务中选择迁移解。并且使用选定的迁移解作为知识迁移至目标任务。

2.问题提出：

EMTO面临的一个关键挑战是从无用的知识源向目标任务的负向知识转移，特别是当任务数量增加时。已有工作试图通过从知识转移频率、知识源选择和知识转移强度等方面设计各种自适应策略来解决这个问题。然而，目前还没有研究人员从协同的角度来考虑这三个方面。

1）调整知识传递频率：平衡任务内自我进化和任务间知识迁移；

2）知识源选择：为一个目标任务选择最有用的知识来源（从许多候选任务中），以充分利用多个可用的知识来源；

3）知识转移强度：确定从被选择的源任务到目标任务的知识转移强度，使得历史上更有用的源任务对目标任务提供更强的帮助。

3.AEMTO：

3.1 算法框架

下图（a）是AEMTO的算法框架，首先，每个任务都有一个种群和求解器；然后，所有的任务将会以一代一代的方式解决，直到满足某个终止标准。并且在每一代中，每一个任务都在通过知识迁移途径迁移进来的知识的帮助下，在一定程度上一个接一个地独立解决。

下图（b）是每个任务求解器在每一代中的工作原理。任务求解器有两个关键模块：任务内自我进化intraSE和任务间知识迁移interKT。其中，interKT模块首先根据每个源任务的历史帮助度（源任务选择概率）从T-1个任务中选择最有用的源任务，根据每个源任务的帮助度比例来确定知识的数量。然后，通过知识重用操作，利用生成的知识来更新目标任务的种群。最后，在线地更新知识迁移概率和源任务选择概率。

3.2 自适应策略

每个任务求解器都有两种概率随着代数的增加而动态调整，即平衡intraSE和interKT的知识转移概率 $p^{tsf}_i$ 和多个可用知识源的源任务选择概率 $p^{sel}_i=\{p^j_i|j=1，...，T；j\ne i\}$ 。本文使用PM策略[15]来自适应地更新这些概率。

1）知识转移概率：在每一代中，每个任务 $T_i,i\in\{1，...，T\}$ 需要先根据 $p^{tsf}_i$ 的值来选择应用intraSE 或interKT。为了通过PM策略调整这个概率，我们使用 $q^s_i$ 和 $q^o_i$ 来分别估计应用intraSE和interKT的预期质量，上标 $s$ 和 $o$ 表示“自我self”和“其他other”。在应用interSE或interKT后，通过奖励 $r$ 来衡量其帮助当前一代的任务解决过程的有效性，然后使用奖励 $r$ 来更新 $q^∗_i$ 如下：
$q^∗_i = \alpha q^∗_i + (1 − \alpha)r$
其中，*表示 $s$ 或 $o$ ， $\alpha$ 表示质量更新系数。奖励 $r$ 是通过种群成员更新率来计算的：
$\begin{equation*} r = \frac {\left |{\boldsymbol {pop}_{i,g}}\right | - \left |{\boldsymbol {pop}_{i,g} \cap \boldsymbol {pop}_{i,g+1}}\right |}{\left |{\boldsymbol {pop}_{i,g}}\right |}\tag{2}\end{equation*}$
其中， $|\cdot|$ 表示一个集合的基数。

在每一代结束时，根据更新后的 $q^s_i$ 或 $q^o_i$ 重新计算 $p^{tsf}_i$ ，如下：
$\begin{equation*} p_{i}^{ tsf} = p_{lb}^{tsf} + \frac {q_{i}^{o}}{q_{i}^{o} + q_{i}^{s}+ \epsilon } \left ({p_{ub}^{ tsf} - p_{lb}^{tsf}}\right).\tag{3}\end{equation*}$
其中， $\epsilon$ 是一个用于避免除以零的小正数。 $p_{lb}^{tsf}$ 和 $p_{ub}^{tsf}$ 是 $p_{i}^{tsf}$ 的下界和上界。

2）源任务选择概率：每个任务 $\tau _{i}, i \in \{1,\ldots, T\}$ 都有（T−1）个源任务。在interKT中，使用源任务选择概率从（T−1）个候选任务中选择一些最有用的源任务，同时确定从选定的源任务中提取的知识量，以便历史上更有用的源任务可以通过提供更多的知识来提供更强的帮助。为了通过PM策略调整这种概率，我们使用 $q_{i}^{\mathrm{ sel}} = \{q_{i}^{j} | j = 1,\ldots, T; j \neq i\}$ 来估计每个源任务对目标任务的期望帮助度。

在应用了知识重用后，当前一代中每个源任务对目标任务 $T_i$ 的帮助度是通过奖励 $r_{i}^{j}$ 来衡量的，使用源任务 $T_j$ 通过知识重用帮助目标任务 $T_i$ ，然后更新 $q_{i}^{j}$ 如下：
$\begin{equation*} q_{i}^{j} = \alpha q_{i}^{j} + (1-\alpha)r_{i}^{j}.\tag{4}\end{equation*}$
其中， $r_i^j$ 是从源任务 $T_j$ 中成功替换目标任务 $T_i$ 的种群成员的知识的百分比，即 $r_{i}^{j} = ns_{i}^{j} / n_{i}^{j}$ 。这里， $n_{i}^{j}$ 和 $ns_{i}^{j}$ 表示从 $T_j$ 中提取的有希望的候选解的总数，以及通过知识重用生成候选解的总数，它们分别替换了 $T_i$ 的一些种群成员。值得注意的是，如果没有选择 $T_j$ 来帮助 $T_i$ ，则 $r_i^j$ 被设置为零。更新 $\boldsymbol q_{i}^{\mathrm{ sel}}$ 后， $\boldsymbol p_{i}^{\mathrm{ sel}} = \{p_{i}^{j} | j = 1,\ldots, T; j \neq i\}$ 更新如下：
$\begin{equation*} p_{i}^{j} = p_{\mathrm{ min}} + \left ({1 - (T-1)\cdot p_{\mathrm{ min}}}\right)\frac {q_{i}^{j}}{\sum _{l=1,l\neq i}^{T} q_{i}^{l} + \epsilon }.\tag{5}\end{equation*}$
其中， $\epsilon$ 是一个用于避免除以零的小正数。 $p_{min}$ 表示每个源任务的最小选择概率。

3.3 算法实现

AEMTO的整体框架如算法1所示。首先，初始化种群以及知识转移概率 $p^{tsf}_i$ 和源任务选择概率 $q_{i}^{sel}$ ，如1-8行所示；然后，当rand< $p^{tsf}_i$ 时，应用interKT（任务间知识迁移，算法2）并计算 $q^o_i$ ，如13-14行所示，否则，应用intraSE（任务内自我进化，算法3）并计算 $q^s_i$ ，如16-17行所示；最后，更新 $p^{tsf}_i$ ，如20行所示。

任务间知识迁移如算法2所示。首先，在源任务选择概率 $q_{i}^{sel}$ 上应用SUS来选择源任务并确定每个源任务的知识迁移量 $n^j_i$ ，如第1行所示；其次，根据目标值采用RWS在每个源任务中选择知识，如2-7所示；接着，使用知识交叉算子算子来对所选择的知识和目标任务种群进行知识重用，如9-25行；最后，更新源任务选择概率以及奖励，如26-38行。

任务内自我进化如算法3所示。首先，采用DE算子对父代种群产生子代，接着，计算奖励。

其中，混沌匹配的描述如下：SUS是基于RWS改进而来的，假设我们需要5个值，那么RWS需要转动5次，而SUS则只需要转动1次。因为RWS只有一个指针，而SUS可以存在多个等间距的指针。这样的话，数组中值较大的区域就可以被多个指针选中，也就是任务迁移强度；值较小的区域也会存在被选中的概率，增加了选择的多样性。