文档介绍：多目标进化算法性能评价指标综述
摘 要:多目标进化算法常用于解决较复杂的多目标优化问题,该类算法是基于种群的进化算法,通过产生一组近似Pareto最优解集满足决策者偏好。介绍了多目标优化问题背景知识及相关定义,根据评价指标衡量包含由[n]维决策空间[Ω]映射到[m]维目标空间[θ]的[m]个实值目标函数,[Rm]被称为目标空间,[F(x)|x∈Ω]表示为该问题的可行目标解。当目标数[m]<3时,式(1)被称为多目标优化问题;当目标数[m]≥4时,则称式(1)为超多目标优化问题。
多目标优化问题的重要概念及定义如下文所示。
定义1(Pareto支配):设[u=(u1,u2,?,um)]和[v=(v1,v2,][?,vm)]是目標空间[Rm]中的两个向量,称[u]Pareto支配[v],当且仅当
[?i∈1,?,m, ui≤vi ∧ ?j∈1,?,m, ui<vi] (2)
记为[u?v]。
定义2(非支配解集):对于解集[P]中的每个解[x]而言,若[x]不被[P]中任何解所Pareto支配,则由[x]组成的解集被称为[P]的非支配解集。
定义3(Pareto最优解):对于式(1)中任意可行解[x*∈Ω],则称[x*]是Pareto最优解,当且仅当: [??x∈Ω, x?x*] (3)
定义4(Pareto最优解集):一个多目标优化问题中所有Pareto最优解构成的集合称为Pareto最优解集(Pareto Set,PS)。
定义5(Pareto前沿):Pareto最优解集中的解在其目标空间中对应目标向量组成的集合称Pareto前沿(Pareto Front,PF),即:
[PF=F(x)∈Rm|x∈PS] (4)
定义6(理想点):在最小化多目标优化问题目标空间中,由在各个目标上有最小值的可行解组成的向量称为理想点,记为[z*] ,即:
[z*j=minfj(x), j∈1,?,m] (5)
定义7(极值点):在最小化多目标优化问题目标空间中,由在各个目标上有最大值的Pareto最优解集中的解组成的向量称为极值点,记为[znad],即:
[znadj=maxx∈PSfj(x), j∈1,?,m] (6)
2 多目标进化算法性能评价角度分类
对多目标进化算法的性能评价主要考虑3个方面:所求解集的质量、计算效率与鲁棒性。对于每一类性能评价,均有相应的评价工具。
解集质量
每运行一个多目标进化算法后,会得到一组近似解集,只有获得的近似解集有较高的质量,该多目标进化算法才有意义。因为多目标优化问题往往具有较复杂的目标函数等特点,通过多目标进化算法得到目标空间上完整的Pareto最优解集是不现实的。一般而言,只需得到一组包含有限个解并且非常逼近帕里托前沿的PF近似解集,帮助决策者根据偏好选择合适的解,从而帮助其决策。
在评价解集质量时,对于已知最优解的测试问题,如DTLZ[5]、WFG[6]测试问题集等,常要求解集满足以下两点:①收敛性,其衡量对象是近似解集趋近于Pareto前沿程度,旨在解决如何指引种群朝着Pareto前沿进行搜索。PF近似解集应尽可能逼近真实Pareto前沿;②多样性,其衡量近似解集中解的多样化程度。一个良好的保持种群多样性的方法可以在整个Pareto前沿上提供分布均匀的解决方案。衡量解集的多样性可以进一步分为衡量解集分布的均匀性与延展性[7]。均匀性衡量近似解集中解与解之间距离相等程度,延展性衡量近似解集中解在目标空间中能扩展的范围程度。
效率
在确保所求解质量的前提下,多目标进化算法运行效率也是一项重要的考察指标。可以通过多目标进化算法运行的CPU时间或达到某种效果所需迭代次数,衡量多目标进化算法时间效率。在多目标进化算法收敛过程中,其求解集质量往往随时间而变化。一般情况下,解集质量会随时间增加而改进,该规律可以通过“质量—时间”曲线描述。因为不同的多目标进化算法采用进化策略、非支配解集的构造方法不尽相同,对不同阶段的时间分析有利于深入研究多目标进化算法的进化特性。
鲁棒性
如果一个多目标进化算法只有在特定问题特性上才能有较好的求解能力与表现,则该多目标进化算法不是鲁棒的。一个鲁棒的多目标进化算法应能解决特点各异的不同问题,并且在求解问题时表现出较好的稳定性能。一个多目标进化算法对所求解问题特征的敏感性、对待处理数据质量的敏感性及对不同参数设置敏感性等均为衡量其鲁棒性的重要指标。
3 多目标进化算法性能评价指标