SaEF-AKT--自适应知识迁移的代理辅助多任务进化框架

SaEF-AKT–自适应知识迁移的代理辅助多任务进化框架

title：Surrogate-Assisted Evolutionary Framework with Adaptive Knowledge Transfer for Multi-task Optimization

author：Shijia Huang, Jinghui Zhong,and Wei-jie Yu

journal： IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING(TETC)

DOI：10.1109/TETC.2019.2945775

code:

1.主要贡献：

1）提出了一种代理辅助的多任务进化框架，可以用于解决昂贵优化问题。

2）设计了一种相似性度量方式

3）提出了一种自适应知识迁移策略来迁移有效的知识。

4）提出了一种基于信息素的方式来选择相似任务。

2.问题提出：

​ 在解决相似性事先未知的MaTO问题时，如何选择相似任务，如何进行知识迁移。

3.SaEF-AKT：

3.1 算法框架

​ 首先，为每个任务构建高斯过程经验模型（GPOP）。然后，使用KLD来计算任务间相似度。接着，根据信息素浓度和相似度来选择相似任务。最后，从相似任务中迁移有效的知识，并更新信息素。

3.2 构建经验模型

​ 高斯过程经验模型的预测精度取决于协方差矩阵及其相关参数。

​ 首先，GP是通过随机抽样一组初始点来构建的。然后，在接下来的每一代，都会在给定数据集上构建GP，并优化参数。接着，使用进化算法来搜索由GP构建的“近似问题”的最小值。最后，在EA结束后，使用真实的适应度函数来评估找到的最小值，并将其添加至数据集中。

​ 为了提高GP的预测质量，促进全局搜索，merit函数定义如下：
f M ( x ) = t ^ ( x ) − γ σ t ( x ) f_M(x)=\hat t(x)-\gamma\sigma_t(x) fM​(x)=t^(x)−γσt​(x)
其中， t ^ ( x ) \hat t(x) t^(x)表示通过GP经验模型得到的预测函数值， γ \gamma γ是一个平衡探索和开发的因子， σ t ( x ) \sigma_t(x) σt​(x)是GP预测的标准差。随着γ的增加，优化求解器将更有可能向未探索的区域移动。

​ 为了减少计算复杂度，提高精确度，本文所使用的GPOP的训练数据是由最近评估的 N R N_R NR​个点和最接近 x b e s t x_{best} xbest​的 N C N_C NC​个点组成。

​ 为了提高搜索效率，所搜区域被限制在 x b e s t x_{best} xbest​周围：
x b e s t − d / 2 ≤ x ≤ x b e s t + d / 2 x_{best}-d/2\le x\le x_{best}+d/2 xbest​−d/2≤x≤xbest​+d/2
其中 d d d超立方体的对角线集，用以反映 N C N_C NC​个最近点的分布：
d i = m a x c ( x c , i ) − m i n c ( x c , i ) d_i=max_c(x_{c,i})-min_c(x_{c,i}) di​=maxc​(xc,i​)−minc​(xc,i​)
其中， i i i是维度， c c c是 N C N_C NC​个最近点的点集。

3.3 相似度度量

1）使用多元正态分布来描述训练数据的分布：
N ( μ , σ 2 C ) μ = ∑ i = 1 λ ω i x i ∑ i = 1 λ ω i = 1 C = 1 λ − 1 ∑ i = 1 λ ( x i − 1 λ ∑ j = 1 λ x j ) ( x i − 1 λ ∑ j = 1 λ x j ) T N(\mu,\sigma^2C)\\ \mu=\sum^\lambda_{i=1}\omega_i x_i\\ \sum^\lambda_{i=1}\omega_i=1\\ C=\frac{1}{\lambda-1}\sum^\lambda_{i=1}\bigg(x_i-\frac 1\lambda\sum^\lambda_{j=1}x_j\bigg)\bigg(x_i-\frac 1\lambda\sum^\lambda_{j=1}x_j\bigg)^T N(μ,σ2C)μ=i=1∑λ​ωi​xi​i=1∑λ​ωi​=1C=λ−11​i=1∑λ​(xi​−λ1​j=1∑λ​xj​)(xi​−λ1​j=1∑λ​xj​)T
其中， x i x_i xi​是训练数据， ω i \omega_i ωi​是每个数据的权重， λ \lambda λ是数据的数目。

2）使用KLD来计算任务相似度：
K L D ( N 0 ∣ ∣ N 1 ) = 1 2 t r ( ( C 1 − 1 C 0 ) + ( μ 1 − μ 0 ) T C 1 − 1 ( μ 1 − μ 0 ) − k + l n ( / f r a c d e t C 1 d e t C 0 ) ) KLD(N_0||N_1)=\frac12tr((C^{-1}_1C_0)+(\mu_1-\mu_0)^TC^{-1}_1(\mu_1-\mu_0)-k+ln(/frac{detC_1}{detC_0})) KLD(N0​∣∣N1​)=21​tr((C1−1​C0​)+(μ1​−μ0​)TC1−1​(μ1​−μ0​)−k+ln(/fracdetC1​detC0​))
其中， N 0 , N 1 N_0,N_1 N0​,N1​是两个分布， μ 0 , μ 1 \mu_0,\mu_1 μ0​,μ1​是两个分布的均值， C 0 , C 1 C_0,C_1 C0​,C1​是两个分布的协方差矩阵， k k k是协方差矩阵的维度。注意，KLD是不对称的。

3.4 自适应知识迁移策略

1）通过相似度和信息素计算任务选择概率：
P k t ( r , s ) = τ ( r , s ) η ( r , s ) ∑ u ∈ U τ ( r , u ) η ( r , u ) P_{kt}(r,s)=\frac{\tau(r,s)\eta(r,s)}{\sum_{u\in U}\tau(r,u)\eta(r,u)} Pkt​(r,s)=∑u∈U​τ(r,u)η(r,u)τ(r,s)η(r,s)​
其中， U U U是任务集， τ ( r , s ) \tau(r,s) τ(r,s)是任务 s s s辅助任务 r r r的信息素浓度，范围为0至1， η ( r , s ) \eta(r,s) η(r,s)是任务 s s s与任务 r r r的相似度，
η ( r , s ) = 1 K L D ( r ∣ ∣ s ) \eta(r,s)=\frac{1}{KLD(r||s)} η(r,s)=KLD(r∣∣s)1​
归一化相似度：
η ( r , s ) = e x p ( η ( r , s ) ) ∑ u ∈ U e x p ( η ( r , u ) ) \eta(r,s)=\frac{exp(\eta(r,s))}{\sum_{u\in U}exp(\eta(r,u))} η(r,s)=∑u∈U​exp(η(r,u))exp(η(r,s))​
2)通过任务选择概率选择辅助任务：
A T ( r ) = { t a s k   w i t h   m a x i m u n   P k l ( r , ⋅ ) , i f   R a n d ( 0 , 1 ) < P m a x , R o u l e t t e   b a s e d   o n   P k l ( r , ⋅ ) , o t h e r w i s e . AT(r)=\begin{cases} task\ with\ maximun\ P_{kl}(r,\cdot),if\ Rand(0,1)<P_{max},\\ Roulette\ based\ on\ P_{kl}(r,\cdot),otherwise. \end{cases} AT(r)={task with maximun Pkl​(r,⋅),if Rand(0,1)<Pmax​,Roulette based on Pkl​(r,⋅),otherwise.​
其中 P m a x P_{max} Pmax​是预先设定的概率，用来选择具有最大 P k l P_{kl} Pkl​的任务作为辅助任务。

3）将辅助任务 A T ( r ) AT(r) AT(r)的最优解传递给任务 r r r，并通过传递的解的质量来更新信息素。
τ ( r , s ) = ( 1 − P h e α ) ∗ τ ( r , s ) \tau(r,s)=(1-Phe_{\alpha})*\tau(r,s) τ(r,s)=(1−Pheα​)∗τ(r,s)
当迁移解由于目标任务的最优解，则任务辅助任务对目标任务有帮助，信息素浓度更新如下：
τ ( r , s ) = P h e m a x \tau(r,s)=Phe_{max} τ(r,s)=Phemax​
在算法初始化阶段，信息素的值都设定为：
τ ( x , y ) = P h e m a x + P h e m a x 2 \tau(x,y)=\frac{Phe_{max}+Phe_{max}}2 τ(x,y)=2Phemax​+Phemax​​
其中， P h e m a x , P h e m a x Phe_{max},Phe_{max} Phemax​,Phemax​是信息素的上下界。

4.思考

1）与大部分算法不同的是，SaEF-AKT在选择相似任务时，采用了任务分布相似度和基于反馈的信息素两种策略。使用GPOP代理辅助模型来得到更好的解。所以SaEF-AKT适用于解决昂贵优化问题。

2）虽然SaEF-AKT提出了一种有效的源任务选择策略，但对源任务中的知识选择却没有进行研究。MTEA-AD–通过异常检测模型来解决Many多任务优化问题-CSDN博客

3）如何设计合理有效的知识迁移策略也是MTO的研究热点，例如混合迁移策略EMTO-HKT–带有混合知识迁移策略的多任务优化算法-CSDN博客，基于映射的知识迁移策略EMEA–多任务优化的另一种范式：显式多任务优化-CSDN博客，基于基因相似度的知识迁移策略MFEA-GSMT–通过基因相似性和镜像转换来解决多任务优化问题-CSDN博客。