论文研读-多目标自适应memetic算法

论文研读-多目标自适应memetic算法

Adaptive Memetic Computing for Evolutionary Multiobjective Optimization

• 此篇文章为 V. A. Shim, K. C. Tan and H. Tang, "Adaptive Memetic Computing for Evolutionary Multiobjective Optimization," in IEEE Transactions on Cybernetics, vol. 45, no. 4, pp. 610-621, April 2015, doi: 10.1109/TCYB.2014.2331994. 的论文学习笔记，只供学习使用，不作商业用途，侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正！

Abstract

• 目前已经提出了很多种进化算法，但是这些算法在某些方面很强，因此在特定的问题中占优势。然而考虑更多的问题，没有一个算法能够一直好。因此合理组合这些算法是一种比较好的提升搜索能力的方式，基于这个想法，这篇文章提出了组合了GA，DE和EDA的一种自适应的memetic 算法。这一代中不同算子产生的更好的解的数量决定了下一代中算子的适应性特征。随后，解的子集使用进化梯度搜索算法evolutionary gradient search algorithm EGS 进行局部搜索。这种memetic技术运用到两种多目标优化框架-基于支配和基于分解
• 关键词：DE,EDA,EGS,GA,MC,MOP
• Differential evolution, estimation of distribution algorithm, evolutionary gradient search, genetic algorithm, memetic computing, multiobjective optimization.

Introduction

1. 先常规的介绍一下MOP的概念

2. 将近些年来MOP的研究主要分为了算法和框架这两部分

• 算法：GA[1],DE[2],EDA[3]，很多研究已经证明了这些算法的高效，但是这些算法都不是通用的算法[4].
• 框架：两个问题，如何定义解的优势(如何评价解)和保持解的多样(maintain the multiple tradeoff Pareto optimal solutions) 主要分为非支配和分解两种框架
• 非支配通过非支配关系进行解的评价
• 分解算法将MOP分解为多个标量优化子问题

3. memetic 算法

• 受模因和自然进化概念的启发，模因算法（MA）被作为混合GA的局部优化方法引入[6]。从那时起，提出了许多MA变体，涉及简单代理和模因的协同或组合算法[4]，多种启发式方法或运算符的算法[7]，多种群的全局搜索算法[8]或全局搜索和局部搜索算法混合的算法[9]，[10]。此外，除了合并一些现有的优化器或运算符之外，还有对种群采取随机扰动策略的MA[11]，不同阶段周期性进行探索的MA[12]和通过不同进化策略并行优化的MA[13]。在[4]中，MA被定义为在生成周期内具有局部搜索的进化算法，而模因计算方法则包括使用混合算子对解进行扰动。尽管这些MA之间存在区别，但所有这些都基于这样的猜想，即不同的优化器，算子或进化策略之间的协同作用是通过将模因传播到接收者的子群体或在群体内共享信息来实现的。

4.本文目的

1. 提出了一个整合有GA,DE,EDA三种策略的自适应MA，**生成的更好解的比例作为下一代时的自适应特征。

• 随后，产生的解的子集进行局部搜索，以生成更适合的解。这种协同作用意味着不同主体之间的交流，使得模因成为提高染色体适应性的信息或特征[14]，可以共享并广播到种群中。

1. 将自适应memetic的算法融入得到支配和分解的算法中
2. 在38个benchmark中进行

两个议题

• 如何根据适应度景观或者问题特征自适应交换信息--如果一个优化器探测到一个有希望的区域，则更多的利用这个优化器优化区域周围的信息。但是，应该引入一种控制机制来逐步监测搜索，以便管理信息共享的平衡。
• 如何在多个优化器中挑选最合适的优化器--选择能在生成大量不同后代的优化器。EDA使用适应度景观的解的概率分布所以只使用全局的信息。DE具有很好的exploration能力，能够很好的保持多样generate diverse solution set。GA兼顾exploration和exploitation，收敛和多样。EGS只使用局部搜索的方法，具有很好的exploitation能力。

本文贡献

• 设计了一种自适应模因计算方法用于多目标优化。虽然本文提出的自适应原理与AMALGAM[16]和Borg MOEA[17]有相似的概念，但两种算法都缺少一种渐进控制范式。
• 考虑了自适应模因计算中的多种全局和一种局部搜索算法。AMALGAM和Borg MOEA都不涉及任何局部搜索算法。此外，还在算法中实现了不同的优化器。
• 实现了基于支配和分解两种框架中的算法。AMALGAM基于支配关系，Borg MOEA基于指标。
• 提出的MA在广泛的benchmark中均有良好的表现

背景

A. MOEAs

1) GA式

• NSGA-II--支配框架，MOEA/D--分解框架。
• 这些算法都使用SBX和多样式变异来explore(多样)和exploit(收敛)
• SBX explore多样--挑两个相互较远的解，exploit收敛--挑两个比较近的解
• 缺点 但是SBX也有缺点,PS比较复杂时，生成解缺少多样性并且经常产生劣质解[19],更多SBX[20]

2) DE式

• DE最大的优点是简单和强大的多样性exploration性能
• 支配框架NSDE[19],[21]-- 在带旋转的问题上，NSDE有比NSGA-II更好的性能
• 分解框架MOEA/D with DE[19]--在复杂PS问题上有更好的表现 --能生成大量不同的解
• 了解更多[19]
• 缺点
• 在非线性可分问题上表现不好[22]，容易陷入局部最优[23]

3)EDA式

• 和GA与DE不同，EDA通过父代的概率分布生成子代
• 优点
• 对于epistatic 和 deceptive test problems [24], [26]问题效果不错，在噪音环境的鲁棒性不错[27] [28] ,并且在高维MOP中表现较好[29].EDA的缺点包括建立概率模型非常耗时[30]，它们在产生多样的解方面较弱，并且容易陷入局部最优状态。这是由于：EDA在重组个体时仅使用全局信息但是不使用局部信息。[30] [31] 。在本文中，仅考虑采用RBM作为其建模方法的EDA(REDA)。REDA的完整演化过程涉及三个主要步骤。首先，将父代用作RBM的训练数据。然后通过无监督的对比发散学习对其进行训练[32]，[33]，以使网络达到一定程度的热平衡。(个人而言，对于这一块不太理解，如果有会的小伙伴，欢迎讨论) 第二步，基于网络的能量函数构建概率模型。第三，通过对构建的概率模型进行采样来产生子代。REDA的技术细节可以参考[31]。

4）进化梯度搜索算法EGS

• 局部搜索算法对现有解造成很小的扰动，可获得略有不同的解。实验证明，同时使用全局和局部搜索算法可以提供更好的搜索性能[34]，[35]。在本文中，我们将EGS作为一种局部搜索算法来实现，该算法利用了解的轨迹运动的梯度信息。该算法的详细信息在算法1中给出。如[36]中所建议，将ε设置为1.8。EGS的工作方式如下。从种群中随机选择初始解（xj）。应用均值为零且方差为σ2的正态变异，对xj引入小扰动，以创建L个局部邻居。通过计算其目标函数来评估局部邻居。然后，如算法1的步骤5所示，计算全局梯度方向。随后根据全局梯度方向和步长生成后代。接下来，更新步长和解。被选出的解应当具有更低的目标值。通过这种方式，EGS可以逐步寻找更合适的解。通过将所选解视为初始解，重复上述过程，直到达到停止标准为止。

B. 框架

1) 基于支配的框架：

• 在基于支配的MOEA中，解的适应度取决于支配原则。最终输出是一组折衷的非支配的解。为了保持解的多样性，应用了拥挤距离或小生境等技术。在此框架下的一些MOEA是强度帕累托进化算法（SPEA）[37]和NSGA-II。但是，这种方法有几个局限性。

局限

• 在many目标的问题中有太多非支配解以产生支配抵抗[17],[38],[39],难以确定候选解。更多的关于many目标问题的可参考NSGA-III [40], HypE [41], PICEA-g [42], and cornet sort approach [43]等研究。另外还需要有多样性保持策略，即使存在一个多样的解集，解的分布也难以保持[18]

2) 基于分解的框架：

• 基于分解的框架中，一个MOP会被分解为几个标量优化子问题。然后，通过对所有子问题并行优化，确定一个折衷最优解集-MOEA/D[18] 在MOEA / D中，使用加权和，Tchebycheff或边界相交方法将MOP分解为N个标量优化子问题。解的优越性通过比较标量目标值来确定。随后，通过将子问题的解与其相邻解进行交配来产生新的解。在[44]中，提出了一种具有动态资源分配的新MOEA / D（MOEA / D-DRA），并在CEC09无约束MOPs测试问题上进行了测试。在此MOEA / D中，将不同的计算工作分配给不同的子问题。该算法已在CEC09竞赛中获得无约束多目标优化的最佳MOEA。

3) Memetic algorithm

• 在[45]中，介绍了一种多目标遗传局部搜索算法（MOGLS）。在此MA中，使用加权和方法汇总MOP的多个目标。权重向量是为每个经过局部搜索的解随机生成的。在[46]中提出了另一种尝试使用加权和方法进行局部搜索来求解MOP的尝试。加权和方法被引入到NSGA-II中，其中权重向量不是随机生成的，而是由每个解上携带的信息确定的。此外，权重向量也可以通过使用[47]中所述的模拟退火算法来确定。
• 在[48]中，作者提出了帕累托存档进化策略算法（M-PAES）的MA。进化策略充当局部搜索算法，而存档解的交叉充当全局搜索机制。Goh等[36]开发了一种多目标进化梯度搜索（EGS）算法。EGS能够根据种群的梯度信息进行多向搜索， 几种方法可被用于求出MOP中的梯度信息，例如具有随机权重向量的加权和方法，目标编程技术以及基于HV指标的方法。有关这些主题的详细介绍，请参见[4]，[8]。

提出的算法

• 将自适应memetic算法分别应用到支配和分解两种框架中--分别提出mNSEA和mMOEA/D

1. 初始化阶段，每个优化算子都有相同的概率生成初始解
2. 较优秀的解会被选出并存进存档中
3. 在子代解生成之前，每个优化算子的概率会根据算法2进行计算，原理是生成更多优势解的算子会被赋予更大的概率。引入作为学习率。

• 此处设置了学习率的概念，这是因为不同的进化算子在不同的进化阶段具有不同的优势，有的进化算子在某些问题上能够快速收敛，支配了其他算子的表现，这样就违背了自适应算法的初衷，即单一算子具有持续性的垄断地位，因此使用学习率来进行平衡。

mNSGA

• mNSGA算法流程如算法3所示，首先使用非支配排序，并使用拥挤距离保持多样，挑选出N个有希望的解。
• 然后通过算法2计算每个进化算子的adaptive proportion rate
• 如果GA被激活，使用SBX和多项式变异；如果DE被激活，使用DE和多项式变异；如果EDA被激活，则从概率模型中挑选出一个解。
• 在archiving state，对2N的种群进行非支配排序和拥挤距离计算。
• 在elitism state，挑选出N个优秀的解
• 随后，种群中K%的解被挑选出来成为一个子集并且使用EGS算法。注意局部搜索策略只会在特定的情况下会被激活，这需要考虑LS(局部搜索率)

mMOEA/D

• 算法4中列出完整的mMOEA/D伪代码