MO-CMA-ES

今天要介绍的文献是《Covariance Matrix Adaptation for Multi-objective Optimization》。该文献提出了MO-CMA-ES算法，该算法是CMA-ES在多目标优化问题上的扩展。

1. (1+$\lambda$λ)-CMA-ES

所谓(1+$\lambda$λ) 是指该算法的父代个体数量为1，所产生的子代个体数量为$\lambda$λ，使用’+'选择算子（一种精英策略，将父代和子代合在一起选择出最好的个体进入下一代）。算法伪码如下


算法流程很简单。每个个体都用一个五元组$a$a来表示，即$a=\left[\boldsymbol{x}, \overline{p}_{\text { succ }}, \sigma, \boldsymbol{p}_{c}, \boldsymbol{C}\right]$a=[x,p​ succ ​,σ,pc​,C]，其中$\boldsymbol{x}$x表示决策变量；$\bar{p}_{\mathrm{succ}}\in[0,1]$pˉ​succ​∈[0,1]为平均成功率；$\sigma$σ表示全局步长；$\boldsymbol{p}_{c}$pc​为进化路径；$\boldsymbol{C}$C为协方差。首先初始化种群$a^{(0)}_{parent}=[\mathrm{x},\bar{p}_\mathrm{succ}^\mathrm{target},\sigma_0,\boldsymbol{0},\boldsymbol{I}]$aparent(0)​=[x,pˉ​succtarget​,σ0​,0,I]（种群大小为1），参数的建议值如表1所示。接下来对多元正态分布$\mathcal{N}\left(x_{\text { parent }}^{(g)}, \sigma^{(g)^{2}} C^{(g)}\right)$N(x parent (g)​,σ(g)2C(g))进行采样，得到$\lambda$λ个子代个体的决策变量$\boldsymbol{x}_{k}^{(g+1)}$xk(g+1)​。然后分别更新步长和协方差矩阵，重复以上操作，直到满足终止条件。更新步长与更新协方差矩阵这两个步骤的伪码如下。

该步骤的输入参数有两个：（1）父代个体；（2）成功率$p_{\mathrm{succ}}=\lambda_{\mathrm{succ}}^{(g+1)} / \lambda$psucc​=λsucc(g+1)​/λ，其中
$\lambda_{\mathrm{succ}}^{(g+1)}=\left|\left\{i=1, \ldots, \lambda | f\left(\boldsymbol{x}_{i}^{(g+1)}\right) \leq f\left(\boldsymbol{x}_{\mathrm{parent}}^{(g)}\right)\right\}\right|$λsucc(g+1)​=∣∣∣​{i=1,…,λ∣f(xi(g+1)​)≤f(xparent(g)​)}∣∣∣​，即$p_{\mathrm{succ}}$psucc​表示所生成的个体中比父代好的个体的比例。，$c_p(0&lt;c_p\leq1)$cp​(0<cp​≤1)为学习率，$d$d为阻尼系数。ES中的一个原则是当成功率较大时应该增大步长$\sigma$σ，反之当成功率较小时应减小步长。这个原则通过exp函数的参数体现，即当$\bar{p}_{\mathrm{succ}} &gt; p^{\mathrm{target}}_{\mathrm{succ}}$pˉ​succ​>psucctarget​时，$\sigma$σ会增大，反之当$\bar{p}_{\mathrm{succ}} &lt; p^{\mathrm{target}}_{\mathrm{succ}}$pˉ​succ​<psucctarget​时，$\sigma$σ会减小，而当$\bar{p}_{\mathrm{succ}} = p^{\mathrm{target}}_{\mathrm{succ}}$pˉ​succ​=psucctarget​时，$\sigma$σ保持不变。当$p^{\mathrm{target}}_{\mathrm{succ}}&lt;0.5$psucctarget​<0.5时，exp函数的参数值介于$-1/d$−1/d与$1/d$1/d之间。因此阻尼系数$d$d控制了步长的变化率。
Algorithm 1中的$f(\boldsymbol{x}_{1 : \lambda}^{(g+1)})$f(x1:λ(g+1)​)表示所产生的$\lambda$λ个子代个体中最好的一个个体。也就是说，当子代个体中最好的个体比父代还要好时，就用这个个体作为下一代的父代个体，并更新协方差矩阵。同样，对于更新协方差矩阵这一步骤也有两个输入参数（1）更新后的父代个体$a$a；（2）父代个体的变化量$x_{step}=(\boldsymbol{x}_{\text { parent }}^{(g+1)}-\boldsymbol{x}_{\text { parent }}^{(g)})/\sigma_{\text { parent }}^{(g)}$xstep​=(x parent (g+1)​−x parent (g)​)/σ parent (g)​。进化路径$\boldsymbol{p}_c$pc​依赖于$\bar{p}_{\mathrm{succ}}$pˉ​succ​的值，当$\bar{p}_{\mathrm{succ}}&gt;p_\mathrm{thresh}$pˉ​succ​>pthresh​($p_\mathrm{thresh}&lt;0.5$pthresh​<0.5)时，进化路径的更新停止。这可以防止当步长过小时，$\boldsymbol{C}$C的坐标轴过快增长。

2. MO-CMA-ES

基于 (1+$\lambda$λ)-CMA-ES，该文又提出了针对多目标优化问题的MO-CMA-ES算法。该算法采用了NSGA-II中的非支配排序，并将拥挤度或HV值作为额外的选择标准。在$\lambda_{\mathrm{MO}}\times$λMO​× (1+$\lambda$λ)-MO-CMA-ES算法中，将维持$\lambda_{\mathrm{MO}}$λMO​个(1+$\lambda$λ)-CMA-ES中的种群。取$\lambda=1$λ=1，$\lambda_{\mathrm{MO}}\times$λMO​×(1+1)-CMA-ES算法伪码如下：

测试该算法时，感觉其的效果并不是很好。在处理带Box-constraint的问题时，MO-CMA总会产生大量可行域外的解，导致搜索效率很低。不过由于其具有旋转不变性，在旋转问题上的效果还是好过使用SBX+PM的EA。

此仅为本人阅读论文时的笔记，若有理解有误的地方还请批评指正。