多目标优化 MOP （六）：遗传算法 Two_Arch2 2015

论文：Two_Arch2： An Improved Two-Archive Algorithm for Many-Objective Optimization

进化算法在解决MaOP问题的时候经常遇到2个问题dominance resistance (DR) 和 the active diversity promotion (ADP)，为了解决以上问题，可以采用4中方法：non-Pareto-based approaches, objective reduction, preference-based approaches, 和 dominance relation.non-Pareto-based approaches包括基于aggregation functions的MOEA/D，基于indicatior的IBEA等；objective reduction包括Pareto corner search evolutionary algorithm (PCSEA)；preference-based approaches可以帮助决策制定者找到PF，可以分为交互的和非交互的方法。

这篇文章提出了两个存档的方法，两个档案分别是indicator-based和Pareto-based，Pareto-based用于保存收敛性好的solution(CA)，indicator-based保存多样性好的solution（DA）。采用了一种心的Lp-norm-based ( p < 1) 多样性维护机制。

Two_Arch2特点：兼顾了收敛性、多样性和复杂度，不需要参考点和其他人为设置。

A.Two_Arch算法流程：

Two_Arch的重组和迭代过程与MOEA相似，重组中的交叉和变异阶段，CA和DA的合集可以看作父代，选择操作也没有特别之处，CA和DA根据不同的不表有不同的更新规则。

当种群通过交叉变异后获得offsrping子代后，对于子代中的非支配解，如果该解支配CA或DA中任何一个解则被放入CA，同时删除CA和DA中被支配的解，如果该解没有支配其他解则放入DA，CA和DA中都是非支配解。如果CA和DA中解的和大于N，则删除DA中距离CA最小的解。在Two_Arch中，CA和DA没有固定的大小，只有他们的和的大小为N的限制，删除的解都来自于DA.

Two_Arch仍然是一个Pareto-based的算法，在MaOP问题中仍然会失效，另外，在CA中没有多样性维护机制，虽然CA的作用是保持收敛性，如果CF在true PF上而CA中非支配解满足总的个数N，此时没有DA的空间可以存放非支配解了，这时整个DA被删除了也就没有多样性的机制优势了。

TWO_ARCH2算法：

为了保持很好的收敛性和多样性和可接受的复杂度，只使用pareto dominance relation是不够的。作者发现IBEA算法中可以保持良好的收敛性和多样性，因此作者在外部存档中引入了这个方法，但是CA和DA根据不同的dominance relations更新。在TWO_ARCH2中，CA和DA的角色更加清晰，CA引导种群收敛到true PF,DA在高维目标空间增加种群的多样性。这是为什么交叉操作发生在CA和DA中，但是只有CA发生变异，同时，CA和DA的存档个数都是固定的。在选择操作中，CA和DA的子代选择都是独立的，采用不同的方法，因为CA的多样性差，DA作为最后的输出结果。

B. Convergence Archive(CA)

表示一个solution在目标空间中要支配另一个solution所需要的最小距离，公式如下

Two_Arch2在CA更新中，offspring首先被添加到CA中，然后删除适应度值小的多余的solution，然后更新CA中的个体适应度值

C. Diversity Archive

多样性可以理解为：solution应该分布在目标空间中接近PF的位置，同时，当solution投影到低维目标空间时，差异应该最大化

1）DA中的选择操作：DA中的更新基于pareto dominance，只有非支配解才能加入到DA中，在 Two_Arch2中，采用加入到DA中而不是删除DA中的个体。如果DA中的solutions数量溢出，首先将最大或最小solution添加到DA中，然后将最步相似的solution添加到DA中，计算相似度采用L p -norm-based distance。

2）Similarity in High-Dimensional Space

fractional distances ( L p -norm, p < 1) 被证明在高维空间表现很好，当p取小于1的值时，可以表示不同solution之间的较大差异。

Computational Complexity Analysis

N个solution的m个目标问题，IBEA的复杂度是