学习笔记--基于范围选择的进化多目标优化（PESA-II）

基于范围选择的进化多目标优化PESA-II

摘要：这篇文章对进化多目标优化算法提出了一个新的选择技术—目标空间中的选择单元是一个超立方体。在这项技术中，与给每个个体分配一个选择适应度不同的是，适应度值被分配给被当前至少一个接近帕累托前沿的个体占据的当前目标空间中的超立方体。然后从这块空间中随机选择个体作为结果。

第二部分简要介绍现代进化多目标算法中的选择方案以及基于区域选择的概念。第三部分算法测试；第五部分描述结果，第六部分得出结论。

图1将会解释在当前多目标进化算法中的主要选择方案。对于在目标空间中假定的两个目标问题，我们在图中画出了许多点，想象目标是沿着两个轴线的最小化问题。目标空间被分割成许多正方形，通常情况下我们的超立方体是在高维问题中的。在PAES和PESA中，算法都被分割成目标空间中的一小部分到超长方体。

在PESA中超立方体的相关占据信息被用作选择方案。一个持续只包含非支配解的存档，作为算法的当前接近帕累托前沿，只从存档中选择。每个个体的选择适应度仅仅只是其它解的数量（个体占据相同的超立方体），被叫做压缩因子。然后用二项锦标赛选择方法朝压缩因子小的方向选择父代双亲。

在PAES中，选择是不同的事情，PAES相当于是一个局部搜索方法。在任何时候都只有一个当前解，因此它常常被选作突变的父代。然而，当变体和当前解都是非支配的时候，就得决定将谁看作新的当前解（在下一次的迭代中直接被选择的父代）了。我们指出提出的目的，PESA利用了超立方体占据。

SPEA中的选择方法是通过强度帕累托方案产生的。这是一种给基于当前种群中个体的数量的个体分配选择适应度的方法。在SPEA中有两个种群一个内部一个外部。外部种群仅包含非支配个体，内部种群包括通过遗传算子产生的最后的子代，可能包含被外部种群中支配的个体。图一可能代表在一次运行中的组合种群。点X是非支配的，因此是在外部种群里边，它支配了外部种群中的两个个体（成员）。对非支配个体的强度测量仅仅是它包含的内部种群中的个体数目。而内部种群成员的强度测量是通过包含它们的外部种群中的个体强度和推导出的。图1中Y可能比X有一个更好的选择强度。

NSGA-II使用了比其它方案表现良好的不同选择方案，既高效又表现良好。通过朝高隔离值靠近的。图1中Y比A的隔离值高。

基于区域的选择提供了一个可选择的，前面的目标是更直接地完成。基于范围的选择：选择单元是一个超立方体而不是一个个体。选择适应度是通过超长方体推导出的，选择任意的标准选择方法，用遗传算子选择的最终结果个体是从超立方体中随机选择的。例如图1中，超立方体区域C要比B有更好的选择适应度。

下面简要分析下为什么基于区域的选择要比基于个体的选择要好。假设我们采用二进制锦标赛来根据选择适应度选择个体。无论这些选择适应度是否是基于个体的还是基于超立方体的。首先要考虑的特殊案例是占据当前靠近帕累托前沿近似值的超长方体只有两个，其中一个超立方体被9个个体占据，另一个被一个个体占据。那么这个一个个体就是我们认为最被隔离的那一个。在基于个体选择的方案中，使用二进制锦标赛选择，那我们最好的个体（也就是最被隔离的那个）被选择的概率是1-（9/10）^2=0.19.那么我们选择过度拥挤的那9个个体的概率就是0.81.这似乎没有朝产生低拥挤区域提供合适的高偏移。然而，在基于区域的选择中，被选择的单元是两个被占据的超立方体。那么最不被占据的区域被选择的概率是1-（1/2) ^ 2=0.75，那么选择更拥挤个体的概率就是0.25.由此可见，基于个体选择的方案我们更可能选择不被隔离的个体，而基于区域的选择方案我们更可能选择被隔离的个体。

那么更一般地，我们仍然关注选择一个最被隔离的个体的相关概率，然后继续使用二进制锦标赛的选择方案。假设帕累托前沿的近似值有b个被占据的超立方体，在第i个超立方体中有ni个个体，所有被占据的超立方体的个体总数为P。不失一般性，假设现在一个超立方体j有最大的bi，另一个超立方体有最小的ni，最不拥挤和最拥挤的超立方体中的个体数分别是l和m。

当使用基于个体的选择时，从最不拥挤的超立方体中选择一个个体的概率是1-（（P-l）/P）^2.同理，最拥挤的超立方体中的个体被选中的概率是（m/P） ^2

当m高于l时，选择拥挤区域的个体的可能性就较高了，看起来不太合理。

相比之下，基于区域的选择方式相应的比率就是2b-1.当超过1个被占据的超长方体时，一般不会小于1，至少是3.也就是说选择不拥挤区域的概率高。

当锦标赛的规模很大时，收敛非常快，而且种群间的个体分布非常平坦，在这种情况下基于个体的选择方式在选择最不拥挤的区域选择个体的可能性就比较小了。