多目标进化算法性能评价指标研究综述

Survey on Performance Indicators for Multi-Objective Evolutionary Algorithms

多目标进化算法根据性能评价指标衡量其优劣,主要从算法所求解集的质量、算法求解效率以及算法鲁棒性三方面来评价,并侧重于解集的质量,现有的相关工作缺乏对评价指标数学性质的分析.本文将评价指标按性能标准分为四类:计数指标、收敛性指标、多样性指标、综合性指标,其中计数指标统计符合指标要求的解个数或比例,收敛性指标衡量解集与参考集的贴近程度,多样性指标衡量解集分布的均匀程度与求解极端值的能力,并按性质类型分为分布性指标、延展性指标和同时衡量前两者的指标,综合性指标同时衡量收敛性和多样性,并按适用范围分为通用指标和专用指标.本文对比分析了77种指标的参考集、比较函数以及时间复杂度,并从高维目标适应性、离群点敏感性、参考集合理性、指标值最优性四个方面对部分指标进行了分析,为研究者们选择合适的指标提供方法,以应对不同环境下的复杂问题.最后展望了多目标进化算法性能评价有待进一步研究的方向.

The performance of multi-objective algorithms is evaluated by indicators,which mainly take three aspects into considering and focuses on the first aspect:the quality of the solution set obtained by the algorithms,the efficiency of the algorithms,and the robustness of the algorithms.Existing related work lacks mathematical analysis for indicators.In this paper,we categorize the indicators into four groups based on performance criteria:counting indicators,convergence indicators,diversity indicators,and comprehensive indicators.The counting indicators tally the amount or the ratio of non-dominated solutions or elite solutions that satisfy the criterion of the metrics,there are two main differences of counting indictors and non-counting indicators,one is whether the range of indicators is discrete,the other is whether the values of all objectives are only used for comparison but not directly participate in the calculation.The convergence indicators evaluate the convergency of the solution set mainly by calculating the distance of the solution set to the approximation of Pareto Front or the reference set,univariate convergence indicators evaluate the closeness between the solution set and Pareto Front,and binary convergence metrics evaluate the closeness between two different solution sets.According to property,the diversity indicators are further divided into distribution indicators,spread indicators,and indicators measuring both distributions and spread,the distribution of the solution set considers the uniformity in the objective space,and the spread of the solution set measures the capability to obtain extreme solutions.The comprehensive indicators evaluate the convergence and the diversity of the solution set at the same time,which are further divided into general indicators and special indicators by scope of application,what’s more,special indicators include that used for user-based evolutionary algorithms,dynamic evolution algorithms,and multi-modal evolutionary algorithms.We also illustrate the reference set,the comparison function,and the time complexity of 77 indicators.Specifically,the reference set is used to assist in the calculation of the performance indicators value,the comparison function can tell researchers whether the value of indicators bigger is better or smaller,and the time complexity reflects the difficulty to calculate the indicators.Then we analyze some indicators from four aspects:(1)many-objective adaptability,whether the indicators are applicative in high-dimensional objective space,(2)outlier sensitivity,assessing whether the values of the indicators are affected badly by outliers,(3)reference set rationality,discussing the reasonable range of values for the reference site,(4)value optimality,some mathematical work for the optimal value the indicators can reach.Through these analyses,we offer approaches for researchers to choose the right indicators to deal with complex problems under different circumstances.Finally,we end up with discussing some directions about performance indicators that show potential from nine different aspects:comprehensive indicators without any prior information,a new type of multivariate indicators for evaluating the performance of multitasking optimization,indicators used for many-objective evolutionary algorithms,performance measurement in large-scale optimization,the evaluation of the robustness of algorithms,novel indicators used for user-based,dynamic and multi-modal evolutionary algorithms to overcome the deficiency of the existing indicators,and last but not least,research on the mathematical properties of performance indicators.