MFEA-GSMT--通过基因相似性和镜像转换来解决多任务优化问题

MFEA-GSMT–通过基因相似性和镜像转换来解决多任务优化问题

title：Improving Evolutionary Multitasking Optimization by Leveraging Inter-Task Gene Similarity and Mirror Transformation

author：Xiaoliang Ma, Yongjin Zheng, and Zexuan Zhu, Xiaodong Li, Lei Wang, Yutao Qi, Junshan Yang.

journal：IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE(IEEE CIM)

DOI：10.1109/MCI.2021.3108311

code:

1.主要贡献：

1）提出了基于基因相似性的知识迁移策略来提高仅有少量样本的高维空间的知识迁移效率。

2）提出了一种基于对立学习的镜像转换，来保持种群多样性。

2.问题提出：

1）在只有少量样本的高维空间中，整个种群的分布估计可能非常困难且不精确。

2）现有的基于对立点和广义对点的对立学习OBL策略只能搜索空间中的一个点或一条一维线（如下图所示），在大规模问题中探索能力有限，有时可能导致过早收敛。

对立点定义：给定一个点 x = ( x 1 , x 2 , . . . , x n ) , x i ∈ [ l i , u i ] x=(x_1,x_2,...,x_n),x_i\in[l_i,u_i] x=(x1​,x2​,...,xn​),xi​∈[li​,ui​]， l i , u i l_i,u_i li​,ui​是 x i x_i xi​的上下界。则对立点 x ˉ = ( x ˉ 1 , x ˉ 2 , . . . , x ˉ n ) \bar x=(\bar x_1,\bar x_2,...,\bar x_n) xˉ=(xˉ1​,xˉ2​,...,xˉn​)定义如下：
x ˉ i = l i + u i − x i , i = 1 , 2 , . . . , n . \bar x_i=l_i+u_i-x_i,i=1,2,...,n. xˉi​=li​+ui​−xi​,i=1,2,...,n.
广义对立点 x ^ = ( x ^ 1 , x ^ 2 , . . . , x ^ n ) \hat x=(\hat x_1,\hat x_2,...,\hat x_n) x^=(x^1​,x^2​,...,x^n​)定义如下：
x ^ i = α ( l i + u i ) − x i , i = 1 , 2 , . . . , n . \hat x_i=\alpha(l_i+u_i)-x_i,i=1,2,...,n. x^i​=α(li​+ui​)−xi​,i=1,2,...,n.

3.MFEA-GSMT：

1）算法框架：

如下图的算法1所示，MFEA-GSMT与MFEA的算法流程大致相似，主要区别在于如下三步操作：

首先，计算基于KLD任务间基因相似性（第6行）；其次，基于基因相似性来进行选择性交叉（第11行）；最后，镜像转换（第12-14行）

2）任务间基因相似性:

给定一个技能因子为 k k k，拥有 N k N_k Nk​个 n n n维个体的子种群 P = { X 1 , . . . , X N k } P=\{X_1,...,X_{N_k}\} P={X1​,...,XNk​​}，其中 X l = { x l , 1 , . . . , x l , n } X_l=\{x_{l,1},...,x_{l,n}\} Xl​={xl,1​,...,xl,n​}, l = 1 , . . . , N k l=1,...,N_k l=1,...,Nk​。则使用正态分布 N k , i ( μ k , i , σ k , i 2 ) {\cal{N}}_{k,i}({\mu}_{k,i},{\sigma}_{k,i}^{2}) Nk,i​(μk,i​,σk,i2​)来估计基因相似性如下：
μ k , i = 1 N k ∑ l = 1 N k x l , i , i = 1 , …   n σ k , i 2 = 1 N k − 1 ∑ l = 1 N k ( x l , i − μ k , i ) 2 , i = 1 , …   n \begin{align*}{\mu}_{k,i} & = \frac{1}{{N}_{k}}\mathop{\sum}\limits_{{l} = {1}}\limits^{{N}_{k}}{{x}_{l,i}},{i} = {1},{\ldots}\,{n} \\ {\sigma}_{k,i}^{2} & = \frac{1}{{N}_{k}{-}{1}}\mathop{\sum}\limits_{{l} = {1}}\limits^{{N}_{k}}{{(}{x}_{l,i}{-}{\mu}_{k,i}{)}^{2}},{i} = {1},{\ldots}\,{n} \end{align*} μk,i​σk,i2​​=Nk​1​l=1∑Nk​​xl,i​,i=1,…n=Nk​−11​l=1∑Nk​​(xl,i​−μk,i​)2,i=1,…n​
接着，两个基因分布的KLD可以通过如下公式计算：
K L D ( N k 1 , i   ∥   N k 2 , j ) = log ⁡ 2 σ k 2 , j σ k 1 , i + σ k 1 , i 2 + ( μ k 2 , j − μ k 1 , i ) 2 2 σ k 2 , j 2 − 1 2 (5) {KLD}\left({{{\cal{N}}_{{k}_{1},i}}\,{\Vert}\,{{\cal{N}}_{{k}_{2},j}}}\right) = {\log}_{2}\frac{{\sigma}_{{k}_{2},j}}{{\sigma}_{{k}_{1},i}} + \frac{{\sigma}_{{k}_{1},i}^{2} + {(}{\mu}_{{k}_{2},j}{-}{\mu}_{{k}_{1},i}{)}^{2}}{2{\sigma}_{{k}_{2},j}^{2}}{-}\frac{1}{2} \tag{5} KLD(Nk1​,i​∥Nk2​,j​)=log2​σk1​,i​σk2​,j​​+2σk2​,j2​σk1​,i2​+(μk2​,j​−μk1​,i​)2​−21​(5)
其中 N k 1 , i ( N k 2 , j ) {\cal{N}}_{{k}_{1},i}({\cal{N}}_{{k}_{2},j}) Nk1​,i​(Nk2​,j​)表示第i（第j）个基因在与相关任务 k 1 ( k 2 ) {k}_{1}({k}_{2}) k1​(k2​)的子群体上的分布。 μ k 1 , i {\mu}_{{k}_{1},i} μk1​,i​和 μ k 2 , i {\mu}_{{k}_{2},i} μk2​,i​分别是这两个基因分布的平均值。 σ k 1 , i {\sigma}_{{k}_{1},i} σk1​,i​和 σ k 2 , i {\sigma}_{{k}_{2},i} σk2​,i​分别表示两个基因分布的标准差。KLD值越小，说明这两个基因的分布越相似。

​

3）选择性交叉：

​ 首先，生成 x 1 x_1 x1​的副本 x 3 x_3 x3​。然后，基于KLD，寻找 x 2 x_2 x2​中与 x 1 x_1 x1​的每个基因 i i i相似的基因 θ \theta θ。接着，根据 θ \theta θ对 x 2 x_2 x2​进行基因重组保存到 x 3 x_3 x3​。最后，对 x 1 , x 3 x_1,x_3 x1​,x3​进行交叉产生后代。与 x 2 x_2 x2​相比，生成的 x 3 x_3 x3​更类似于 x 1 x_1 x1​。因此，通过 x 1 x_1 x1​和 x 3 x_3 x3​的交叉进行的知识转移往往比 x 1 x_1 x1​和 x 2 x_2 x2​的交叉更积极。

​

4）基于自适应镜像转换的子代生成：

​ 所提出的镜像转换被设计为搜索由对立点 x ˉ \bar x xˉ、中心点 c c c和搜索空间的边界定义的更大的区域。如下图所示，所提出的镜像变换自适应地搜索两个候选区域A和B，以改进探索。区域A由对立点 x ˉ \bar x xˉ和中心点 c c c所限制,区域B由对立点 x ˉ \bar x xˉ和搜索空间的边界所包围。

​ 首先，选择区域A和区域B的概率分别初始化为 P A = 50 % P_A = 50\% PA​=50%和 P B = 50 % P_B = 50\% PB​=50%。然后，这两个概率是由如下公式计算:
P A = P A   ∗   P A e P A   ∗   P A e + P B   ∗   P B e P B = 1 − P A \begin{align*}{P}_{A} & = \frac{{P}_{A}\,{\ast}\,{P}_{A}^{e}}{{P}_{A}\,{\ast}\,{P}_{A}^{e} + {P}_{B}\,{\ast}\,{P}_{B}^{e}} \\ {P}_{B} & = {1}{-}{P}_{A} \tag{6} \end{align*} PA​PB​​=PA​∗PAe​+PB​∗PBe​PA​∗PAe​​=1−PA​​(6)​
其中， P A e {P}_{A}^{e} PAe​和 P B e {P}_{B}^{e} PBe​分别为A区和B区精英后代个体被选择进入下一代的比例。 P A P_A PA​和 P B P_B PB​的定义有助于根据算法的性能搜索更有前途的领域。

​ 接着，基于自适应镜像转换的子代生成可以计算如下。给定一个解 x = ( x 1 , …   x n ) {\bf{x}} = {(}{\bf{x}}_{1},{\ldots}\,{x}_{n}{)} x=(x1​,…xn​)， l = ( l 1 , …   l n ) {\bf{l}} = {(}{l}_{1},{\ldots}\,{l}_{n}{)} l=(l1​,…ln​)和 u = ( u 1 , …   u n ) {\bf{u}} = {(}{u}_{1},{\ldots}\,{u}_{n}{)} u=(u1​,…un​)分别为搜索空间的下界和上界。则搜索空间的中心和x的相反点分别为 c = ( c 1 , …   c n ) = ( ( l 1 + u 1 ) / 2 , …   , ( l n + u n ) / 2 ) {\bf{c}} = {(}{c}_{1},{\ldots}\,{c}_{n}{)} = {((}{l}_{1} + {u}_{1}{)/}{2},{\ldots}\,,{(}{l}_{n} + {u}_{n}{)/}{2}{)} c=(c1​,…cn​)=((l1​+u1​)/2,…,(ln​+un​)/2)和 x ˉ = 2   ∗   c − x {\bar{\bf{x}}} = {2}\,{\ast}\,{\bf{c}} - {\bf{x}} xˉ=2∗c−x。生成子代 o = ( o 1 , …   o n ) {\bf{o}} = {(}{o}_{1},{\ldots}\,{o}_{n}{)} o=(o1​,…on​)通过下式：
o i = l i Area + r a n d ∗ ( u i Area − l i Area ) , i = 1 , …   n {o}_{i} = {l}_{i}^{\text{Area}} + {rand}\ast{(}{u}_{i}^{\text{Area}}{-}{l}_{i}^{\text{Area}}{),}{i} = {1},{\ldots}\,{n} oi​=liArea​+rand∗(uiArea​−liArea​),i=1,…n
其中rand是一个在[0,1]中的随机实数。 l i Area {l}_{i}^{\text{Area}} liArea​和 u i Area {u}_{i}^{\text{Area}} uiArea​分别表示搜索区域的下界和上界。其设置如下：
l i Area = c i , u i Area = x ˉ i  if  A  is selected and  x i   <   c i l i Area = x ˉ i , u i Area = c i  if  A  is selected and  x i   ≥   c i l i Area = x ˉ i , u i Area = u i  if  B  is selected and  x i   <   c i l i Area = l i , u i Area = x ˉ i  if  B  is selected and  x i   ≥   c i \begin{align*}{l}_{i}^{\text{Area}} & = {c}_{i},{u}_{i}^{\text{Area}} = {{\bar{x}}}_{i}{\text{ if }}{A}{\text{ is selected and }}{x}_{i}\,{<}\,{c}_{i} \\ {l}_{i}^{\text{Area}} & = {{\bar{x}}}_{i},{u}_{i}^{\text{Area}} = {c}_{i}{\text{ if }}{A}{\text{ is selected and }}{x}_{i}\,≥\,{c}_{i} \\ {l}_{i}^{\text{Area}} & = {{\bar{x}}}_{i},{u}_{i}^{\text{Area}} = {u}_{i}{\text{ if }}{B}{\text{ is selected and }}{x}_{i}\,{<}\,{c}_{i} \\ {l}_{i}^{\text{Area}} & = {l}_{i},{u}_{i}^{\text{Area}} = {{\bar{x}}}_{i}{\text{ if }}{B}{\text{ is selected and }}{x}_{i}\,≥\,{c}_{i} \end{align*} liArea​liArea​liArea​liArea​​=ci​,uiArea​=xˉi​ if A is selected and xi​<ci​=xˉi​,uiArea​=ci​ if A is selected and xi​≥ci​=xˉi​,uiArea​=ui​ if B is selected and xi​<ci​=li​,uiArea​=xˉi​ if B is selected and xi​≥ci​​
这四条规则分别对应于下图中所示的四种情况。

4.思考

1）MFEA-GSMT也可以解决在多任务优化中的异构问题，并且在低相关的MTO任务中也可以得到更好的效果，但是由于基因相似性的计算会带来额外的计算复杂度。并且现有的MTO算法大都考虑的是如何迁移有效的知识，还未曾考虑提高计算效率的问题。因此，提高计算效率也会是一个有前途的研究方向。

2）迁移频率：本文的迁移概率是固定的。MFEA-II–自适应迁移概率的MFEA-CSDN博客，SREMTO–自调节进化多任务优化-CSDN博客

3）MFEA-GSMT还被应用到神经网络的参数优化上，并且随着深度学习以及chat-GPT等大模型的发展，神经网络的参数会急剧增加，如何利用多任务优化来解决这种大规模优化问题也会是一个研究的热点。

4）迁移学习已经证明可以促进神经网络模型的优化，但当前的优化工具大多还是使用传统的确定性优化，如梯度下降法，Adam等，因为它们相对于不确定性优化来说更快。但是，基于种群的进化算法可以利用其并行性的优点以及多任务优化的技术来提高优化速率，希望未来可以设计出更多新的加速进化算法优化速率的方式，并使用其来解决现实问题。