Two_Arch2:改进的双档案多目标优化算法

Two_Arch2:改进的双档案多目标优化算法

参考文献
《Two_Arch2: An Improved Two-Archive Algorithm for Many-Objective Optimization, Handing Wang, Student Member , IEEE, Licheng Jiao, Senior Member , IEEE, and Xin Yao, Fellow, IEEE》

要点

• 多目标优化问题（ManyOPs）通常指的是具有三个以上目标的多目标问题（MOPs）。它们的大量目标在收敛性，多样性和复杂性方面给多目标进化算法（MOEA）带来了挑战。大多数现有的MOEA只能在这三个方面之一中表现良好。本文旨在同时针对这三个方面在ManyOPs上设计更加均衡的MOEA。
• 在现有的MOEA中，双归档算法（Two_Arch）是一种低复杂度算法，具有两个分别关注收敛和多样性的档案。受Two_Arch思想的启发，为ManyOPs提出了一种显著改进的双档案算法（即Two_Arch2）。
• 在Two_Arch2中，我们为两个档案分配了不同的选择原则（基于指标和基于帕累托的）。此外，我们为Two_Arch2中的ManyOP设计了一种新的基于Lp范数（p<1）的多样性维护方案。

一、介绍

在本文中，我们旨在设计一种针对ManyOP的MOEA，该MOEA在收敛性，多样性和复杂性方面都具有良好的性能，而无需事先进行任何参考点或其他手动设置。主要思想之一是在进化搜索过程中维护两个档案，其中每个档案分别促进收敛性（CA）和多样性（DA）。然而，原始的双档案算法（Two_Arch）在具有大量目标的ManyOP上效果不佳，尽管双档案的想法很有吸引力。我们对原始算法进行了实质性改进，并引入了两项主要创新，包括为两个档案分配不同的选择原则（CA是基于指标的，DA是基于Pareto的），设计了一个新的基于Lp范数（p <1）的多样性ManyOP的维护方案。这些新技术已被并入本文的新算法Two_Arch2中。

二、Two_Arch算法

A、基本流程

Two_Arch的流程图如图所示

Two_Arch使用非支配子代来更新CA和DA。将在CA或DA中占支配地位的非支配子代添加到CA，将在CA和DA两者都不占支配地位的非支配子代添加到DA。在此过程中，将删除CA，DA和非子代集合中的所有支配解。CA和DA更新的详细信息如算法1。

三、提议的新算法：Two_Arch2

A、主要思想

在Two_Arch2中，CA和DA的作用比Two_Arch更清晰。 CA旨在引导种群快速收敛到真实PF，而DA则旨在在高维度的目标空间中为种群增加更多的多样性。这就是为什么Two_Arch2在CA和DA之间进行交叉，但在繁殖过程中仅在CA上进行突变（交叉和突变在Two_Arch2中是独立的）。 CA和DA的大小分别固定，不再灵活。 CA和DA的子代的选择通过不同的方法相互独立。由于CA的多样性太差，我们将DA用作最终输出，这与Two_Arch中CA和DA的并集不同。

B、收敛性档案

在Two_Arch2中选择IBEA中的质量指标Iε+作为CA的选择原则。

在Two_Arch2中更新CA的步骤中，首先将子代添加到CA。然后，Two_Arch2根据适应性删除CA中的其他解。

C、多样性档案

ManyOP的多样性很难维持。 ManyOP的多样性是双重的。一方面，解应分布在整个高维目标空间中，以尽可能提供PF的信息。另一方面，当解被投影到低维目标空间时，解之间的差异应最大化。因此，DA是Two_Arch2中多样性的关键。

• 在DA中选择：在Two_Arch2中，DA的更新基于帕累托支配。这意味着只能将非支配解添加到DA。如果DA溢出，则会根据相似性删除额外的解，这是基于Pareto的MOEA的普遍思想。在我们的Two_Arch2中，我们采用了相反的想法，采用选择而不是删除。算法3中显示了溢出DA中选择的伪代码。当DA溢出时，首先选择边界解（具有最大或最小目标值的解）。然后，进入迭代过程，在每次迭代中将与所选解差异最大的解添加到DA。采用距离作为DA中的相似性度量，这与大多数多样性维护方法相同。众所周知，这种基于距离的多样性维护方法在ManyOPs上效果不佳。我们发现它们失败的原因是ManyOPs没有正确使用距离（欧氏距离或曼哈顿距离）。因此，我们需要选择合适的距离（基于Lp范数的距离）以改善ManyOP的多样性。

• 高维空间中的相似性：相关理论和实验证明，高维空间中的欧几里德距离（L2-范数）的意义较小。欧几里得距离降低了其在高维空间中的相似性索引性能。相反，曼哈顿距离（L1-范数）和分数距离（Lp-范数，p <1）在高维空间中表现更好。我们逐渐增加数据集的维数，并计算了最近邻居和最远邻居之间的差dmax- dmin。下图显示了基于Lp范数（p = 2，p = 1，p = 0.75，p = 0.5，p = 0.25和p = 0.1）的距离随距离增大的dmax- dmin结果。 在L2-范数下，dmax- dmin不会随维数增加。它以一个常数为界。而在所有其他情况下，dmax- dmin随尺寸的增加而增加。理论上证明，dmax- dmin对Dimension^(1 / p-1 / 2)的依赖性通常是不变的。这就是为什么L2范数在高维空间中被常数限制的原因。参数p越小，最远和最近的邻居之间的对比度越高。因此，在Two_Arch2中DA的更新步骤中，我们使用基于Lp范数的距离（p <1）而不是基于L2范数或基于L1范数的距离。对于具有不同目标数量的ManyOP，基于Lp范数（p <1）且具有固定p的距离可能并不适合所有情况。在Two_Arch2中将p设置为1 / m（m是目标数）。

扩展：Lp距离、L1范数、L2范数

Lp距离

L1范数

L2范数