多⽬标进化算法的性能评价指标总结
⽂章⽬录
hop⼀、多⽬标进化算法
多⽬标进化算法 (MOEA )是⼀类模拟⽣物进化机制⽽形成的全局性概率优化搜索⽅法 ，在 20世纪 90年代中期开始迅速发展 ，其发展可以分为两个阶段。
第⼀阶段主要有两种⽅法即不基于 Pareto优化的⽅法和基于 Pareto优化的⽅法 ；第⼆个阶段就是在此基础上提出了外部集这个概念 ，外部集存放的是当前代的所有⾮⽀配个体 ，从⽽使解集保持较好的分布度。这个时期提出的多⽬标进化算法更多地强调算法的效率和有效性。在这两个阶段中 , ⽐较典型的多⽬标进化算法有 NS2 GA2[ 3 ]、PESA2和 SPEA2。
对于这三种算法⽽⾔ ，其优点较多但是其缺点也⽐较明显的。如 NSGA2的优点在于运⾏效率⾼、解集有良好的分布性 ，特别对于低维优化问题具有较好的表现 ；其缺点在于在⾼维问题中解集过程具有缺陷 ，解集的多样性不理想。PESA2的优点在于其解的收敛性很好 ,⽐较容易接近最优⾯ ，特别是在⾼维问题情况下 ；但其不⾜之处在于选择操作⼀次只能选取⼀个个体 ，时间消耗很⼤ ,⽽且阶级的多样性不佳。SPEA2的优点在于可以取得⼀个分布度很好的解集 ，特别是在⾼维问题的求解上 ，但是其聚类过程保持多样性耗时较长 ，运⾏效率不⾼。
多⽬标进化算法的基本原理描述如下 : 多⽬标进化算法从⼀组随机⽣成的种群出发 ，通过对种群执⾏选择、交叉和变异等进化操作 ，经过多代进化 ，种群中个体的适应度不断提⾼ , 从⽽逐步逼近多⽬标优化问题的 Pareto最优解集。与单⽬标进化算法不同 ，多⽬标进化算法具有特殊的适应度评价机制。为了充分发挥进化算法的群体搜索优势 ,⼤多数 MOEA均采⽤基于 Pareto排序的适应度评价⽅法。在实际应⽤中 ，为使算法更好地收敛到多⽬标优化问题的 Pareto最优解 ，现有的MOEA通常还采⽤了精英策略、⼩⽣境和设置外部集等关键技术。
MOEA⼀般框架所描述的算法思想如下 : MOEA通过对种群 X ( t)执⾏选择、交叉和变异等操作产⽣下⼀代种群 X ( t + 1) 。在每⼀代进化过程中 ,⾸先将种群 X ( t)中的所有⾮劣解个体都复制到外部集 A ( t)中 ，然后运⽤⼩⽣境截断算⼦剔除A ( t)中的劣解和⼀些距离较近的⾮劣解个体 ，以得到个体分布更为均匀的下⼀代外部集 A ( t + 1) ，并且按照概率 pe从 A ( t + 1)中选择⼀定数量的优秀个体进⼊下代种群。在进化结束时 ，将外部集中的⾮劣解个体作为最优解输出 , ⽬前 , MOEA研究取得了⼤量成果 ，已被应⽤于许多领域 ，如⼯程领域、⼯业领域和科学领域。其中 ,⼯程领域的应⽤最多 ，如电⼦⼯程、⽔利⼯程、风电⼯程和控制等。
⼆、指标的常见分类⽅法
1.考虑指标同时能评估的解集数⽬（1个或2个解集），可将指标分为⼀元和⼆元指标。
⼀元指标：接受⼀个解集作为参数进⾏评估。
⼆元指标：接受两个解集作为参数，通过⽐较两个解集的⽀配关系或其他⽅⾯，给出哪个解集更好的判断。
2.多⽬标进化算法解集的性能评价指标主要分为三个⽅⾯：
1）解集的收敛性评价(convergence), 反映解集与真实Pareto前沿之间的逼近程度（距离）。⼀般我们希望所得解集距离PF尽可能近。2）解集的均匀性评价(uniformity / evenness), 体现解集中个体分布的均匀程度。⼀般我们希望所得解集在PF上分布尽可能均匀。
thinkabout
3）解集的⼴泛性评价(spread), 反映整个解集在⽬标空间中分布的⼴泛程度。⼀般我们希望所得解集在PF上分布尽可能⼴、尽可能完整地表达PF。
也有⼀些学者，不这样分类，分为基数指标，收敛性指标，和多样性/分布性指标，认为多样性包括均匀性（evenness）和⼴泛性/范围（spread），具体如下：
严慧晶1）基数指标：评估解集中存在的解的个数。
2）收敛性指标（精确度指标）：评估解集到理论帕累托最优前沿的距离（逼近程度）。
好听的花名
3）多样性指标：包括评估解集分布的均匀性（evenness）和⼴泛性/范围（spread）。均匀性体现解集中个体分布的均匀程度；⼴泛性反映整个解集在⽬标空间中分布的⼴泛程度。
⼆、常⽤性能评价指标回顾
*1.GD：解集P中的每个点到参考集P 中的平均最⼩距离表⽰。GD值越⼩，表⽰收敛性越好。
其中P是算法求得的解集，P 是从PF上采样的⼀组均匀分布的参考点，⽽dis（x，y）表⽰解集P中的点y和参考集P中的点x之间的欧式距离。
reminding优点：相⽐HV，计算代价是轻量级的。
缺点：1）仅度量解集的收敛性，⽆法评估多样性；
2）需要参考集，使得这个测度很容易不客观；
*2.convergence metric γ：解集P中的每个点到参考集P 中的最⼩距离的平均值。（类似GD）
其中P是算法求得的解集，P 是从PF上采样的均匀分布的参考点集，⽽dis（x，y）表⽰参考集P中的点x和解集P中的点y之间的欧式距离。
3.Spacing：度量每个解到其他解的最⼩距离的标准差。Spacing值越⼩，说明解集越均匀。
其中表⽰第di个解到P中其他解的最⼩距离，d-表⽰所有di的均值。
歌舞青春 歌曲缺点：仅度量解集的均匀性，⽽不考虑它的⼴泛性。
4.diversity metric △：衡量所获得的解集的⼴泛程度。
参数df和dl是极端解与所获得的⾮⽀配集的边界解之间的欧⼏⾥德距;di 是所获得的⾮⽀配解集中的连续解之间的欧⼏⾥德距离;
d是di 的平均值。
假设最佳⾮⽀配前沿有N个解。使⽤N个解，有N-1个连续距离。当只有⼀个解，即N=1时，分母=分⼦。值得注意的是，这不是解可能的最坏情况。我们可以有⼀个场景，其中di 存在很⼤的差异。在这种情况下，度量可能⼤于1。因此，上述度量的最⼤值可以⼤于1.然⽽，良好的分布将使所有距离di 等于d并且将使得df=dl = 0（在⾮⽀配集合中存在极端解）。因此，对于最⼴泛和均匀展开的⾮⽀配解集，△的分⼦将为零，使得度量值为零。对于任何其他分布，度量的值将⼤于零。
对于具有相同df和dl值的两个分布，度量△在极端解中具有更⾼的值和更差的解的分布。
5.超体积指标（HV，Hypervolume）：算法获得的⾮⽀配解集与参照点围成的⽬标空间中区域的体积。HV值越⼤，说明算法的综合性能越好。
词典在线查询
代表δ表⽰ Lebesgue 测度，⽤来测量体积。 |S| 表⽰⾮⽀配解集的数⽬， vi表⽰参照点与解集中第 i 个解构成的超体积。
优点：1）同时评价收敛性和多样性；
2）⽆需知道PF或参考集；
缺点：1）计算复杂度⾼，尤其是⾼维多⽬标优化问题；
2）参考点的选择在⼀定程度上决定超体积指标值的准确性；
6.反转世代距离（IGD，Inverted Generational Distance）：每个参考点到最近的解的距离的平均值。IGD值越⼩，说明算法综合性能越好。
其中P是算法求得的解集，P 是从PF上采样的⼀组均匀分布的参考点，⽽dis（x，y）表⽰参考集P中的点x到解集P中的点y之间的欧式距离。
优点：1）可同时评价收敛性和多样性；
2）计算代价⼩；
缺点：2）需要参考集；
7.C-metric解集覆盖率：
分⼦表⽰B中被A中⾄少⼀个解⽀配的解的数⽬；分母表⽰B中包含的解的总数。
C(A,B)=1表⽰B中所有解都被A中的⼀些解所⽀配；C(A,B)=0表⽰B中没有解被A中的任⼀解所⽀配。
8.IGD-NS 注：为什么要识别⾮贡献解呢？因为⾮贡献解影响收敛
P是PF上均匀采样的参考点集，P是算法获得的解集，P’是P中的⾮贡献解集。
hen怎么读公式的前⼀部分和IGD很相似，控制P的收敛性和多样性；
第⼆部分是每个⾮贡献解到参考集P的点的最⼩距离之和。
因此，IGD-NS值越⼩，说明收敛和多样性越好，且解集的⾮贡献解尽可能少。
9.KD：衡量是否每个解集都⾄少包含⼀个与拐点相近的解或该解集是否包括全部拐点。
其中d(vi,G)是K中的第i个真实拐点vi到G中最接近解之间的欧⼏⾥得距离。
KD值越⼩，说明检测拐点的能⼒越完整；
北京电影学院表演班当所获的解集覆盖到所有的拐点时，KD=0。
envision
三、参考集的缺陷
不少指标在计算时都需要参考集，因为有参考集的存在，指标的客观型就值得怀疑，如下图所⽰。
解集B肯定⽐A要好，可是因为选⽤了图中的参考集。⽽且，绝⼤多数实际问题都没参考集。四、⽀配关系的缺陷
在⾼维多⽬标⾥，很多解集或解都相互不⽀配，这时候⽀配关系这种东西就很鸡肋了。
