《Swarm and Evolutionary Computation》:A methodology for multi-label algorithm selection in constrained multiobjective optimization
编辑推荐:
研究人员提出了一种允许多个算法被识别为最优性能的算法选择 methodology。该 methodology 的核心思想是:在优化问题中,当多个算法表现相当时,应将所有表现相当的算法均视为最优,而非强制指定单一胜者。具体而言,该 methodology 首先采
研究人员提出了一种允许多个算法被识别为最优性能的算法选择 methodology。该 methodology 的核心思想是:在优化问题中,当多个算法表现相当时,应将所有表现相当的算法均视为最优,而非强制指定单一胜者。具体而言,该 methodology 首先采用统计检验识别表现最优的算法集合,继而利用能够预测多标签的机器学习模型进行算法选择预测,最后引入算法选择精确度(Algorithm Selection Precision, ASP)评估模型性能。该研究将所提出的 methodology 应用于约束多目标优化(Constrained Multiobjective Optimization, CMO)领域。
在约束多目标优化问题(Constrained Multiobjective Optimization Problem, CMOP)中,任务是在满足给定约束条件下优化多个目标函数。研究人员采用探索性景观分析(Exploratory Landscape Analysis, ELA)特征作为机器学习模型的输入,这些特征包括多目标景观特征、违反约束景观特征以及多目标-违反约束交互景观特征三类,共计80个特征。算法性能评估采用ICMOP指标,该指标是对IHV+指标的扩展,能够处理不可行解的情况。
在识别最优算法方面,研究人员为避免多重比较带来的I类错误膨胀,首先通过中位数绝对偏差(Median Absolute Deviation, MAD)筛选可能的最优算法,继而采用方差分析(ANOVA)检验算法间差异谈一谈,最后使用Tukey's HSD事后检验进行两两比较。多标签分类采用分类器链(classifier chain)方法,基于k近邻(kNN)、随机森林(Random Forest)和决策树(Decision Tree)构建模型,并以虚拟分类器(dummy classifier)作为基线对照。
研究背景与问题提出
算法选择(algorithm selection)旨在针对特定优化问题预测表现最优的算法。传统方法通常为每个问题指定单一最优算法,这种做法存在明显缺陷:其一,忽略性能指标值的分布特征,无法识别多个表现相当的算法;其二,迫使模型过度关注算法间微小且无统计显著性的性能差异,易导致过拟合;其三,基于不同批次运行结果可能得出不同的"最优"算法,使得选择方法缺乏稳定性与可重复性。此外,算法在时间复杂度、内存占用、实现可及性及用户熟悉度等方面的差异,也为用户提供了除纯性能之外的其他选择依据。因此,开发能够识别多个最优算法的 methodology 具有重要意义。
研究人员开展的研究及主要结论
该研究提出了多标签算法选择 methodology,并于《Swarm and Evolutionary Computation》发表。研究在2维(2D)、5维(5D)和10维(10D)的双目标约束多目标优化问题上进行了系统验证,涉及C-DTLZ、CF、CTP、DAS-CMOP、DC-DTLZ、MW和NCTP七个基准测试套件,共计33个2D问题、56个5D问题和56个10D问题。研究纳入NSGA-II、NSGA-III、MOEA/D-I
Epsilon、AGE、C-TAEA、SPEA2、GDE3、NSDE和NSDE-R九种多目标优化算法,每种算法在每个问题上独立运行31次。
研究结果表明:随着评估次数增加,被识别为最优的算法数量减少,但即使在运行末期(n次评估后),大多数CMOP仍存在多个最优算法;2D问题上SPEA2最常被识别为单一最优算法,而5D和10D问题上则为MOEA/D-I
Epsilon;随机森林和kNN分类器在预测最优算法方面表现最佳;虚拟模型在早期评估阶段的ASP值高于后期,表明算法选择任务在运行初期相对更容易。该研究的重要意义在于:首次系统建立了面向约束多目标优化的多标签算法选择框架,提出的ASP评估指标直接针对算法选择的实际需求,为构建更通用可靠的算法选择模型奠定了基础。
主要技术方法
样本队列来源于七个基准测试套件的165个CMOP实例(2D:33个,5D:56个,10D:56个)。特征提取采用Alsouly等人提出的CMOP专用ELA特征,基于拉丁超立方采样生成样本,并通过随机游走获取特征,计算过程重复100次以获得100组特征集。统计检验采用MAD筛选结合ANOVA与Tukey's HSD的两阶段方法,显著性水平设置为p=0.005、α=0.005。机器学习采用分类器链架构的kNN、随机森林和决策树多标签分类器。模型评估采用研究者提出的ASP指标及留一问题交叉验证策略。
研究结果
最优算法识别结果:通过n/4、n/6、n/2和n四个目标评估节点(n=200×300×D次解评估)分析最优算法分布。随着评估次数增加,单一最优算法的比例上升,但多最优算法现象仍普遍存在。NSDE与NSDE-R在各维度上均呈正相关,NSGA-IINSGA-III与SPEA2在5D和10D上高度正相关,验证了分类器链考虑算法间依赖关系的合理性。
最优算法预测结果:多标签分类模型始终优于虚拟基线模型。随机森林在2D n/4(ASP=0.798)、2D n/6(ASP=0.658)、2D n/2(ASP=0.670)和2D n(ASP=0.612)上表现最优;kNN在5D n/4(ASP=0.746)、5D n/6(ASP=0.609)和10D n/4(ASP=0.714)上表现最优。模型提升幅度在虚拟模型表现不佳时更为显著,如10D n评估时从0.195提升至0.524(随机森林)。
方法论优势与局限:优势包括避免过拟合微小性能差异、提供多重算法选择以兼容用户偏好、以及ASP指标的直接适用性。局限包括统计参数敏感性、评估范围受限、未涵盖更高维问题(尽管多数实际CMOP维度低于10D)、仅使用人工基准问题而非真实问题、以及仅在CMO领域验证。
研究结论
研究人员提出了一种新颖的算法选择 methodology,该 methodology 假设多个算法可在单一优化问题上表现相当并因而被选为最优。该 methodology 聚焦于给定解评估次数后识别最优算法,核心步骤包括:通过统计检验(34次运行结果的MAD筛选、ANOVA和Tukey's HSD)识别表现相当的算法集合;采用分类器链架构的多标签分类(决策树、随机森林、kNN及虚拟分类器)进行预测;使用专为算法选择设计的ASP指标评估模型。该 methodology 在2D、3D和10D CMOP上验证,采用七种基准套件、九种多目标优化算法及CMO专用ELA特征,通过留一问题交叉验证评估。
结果显示:虚拟模型在早期评估阶段的ASP值更高,表明算法选择任务在运行初期更易完成;所有算法选择模型均优于虚拟模型,随机森林在多数情况下表现最佳;最关键的是,即使运行末期,统计检验仍在大多数CMOP中识别出多个最优算法,凸显了该 methodology 构建通用可靠算法选择模型的重要性。