非支配排序遗传算法 III(NSGA-III)的数学运行时分析
本研究证明使用 NSGA-II 算法,结合两种经典的变异算子和四种不同的父母选择方式,当种群大小为前沿帕累托曲线大小的 4 倍时,可以满足与 SEMO 和 GSEMO 算法在基本的 OneMinMax 和 LeadingOnesTrailingZeros 基准测试中相同的渐近运行时保证,但如果种群大小仅等于前沿帕累托曲线的大小时,NSGA-II 算法无法高效地计算完整的帕累托前沿。
Dec, 2021
本文使用数学运行时分析严格证明和量化了 NSGA-II 算法在多目标问题中呈现的困难现象,并表明在计算拥挤距离时,不同目标被视为独立。
Nov, 2022
对于 NP 完全的双目标最小生成树问题,我们通过数学手段证明了 Non-dominated Sorting Genetic Algorithm-II 的好性能,并且可以计算出 Pareto 前沿上所有极点的期望迭代次数。
May, 2023
本文针对一个由两个多峰目标组成的基准问题,进行 NSGA-II 算法的第一次运行时间分析,结果表明,当种群大小 N 至少是 Pareto 前沿的 4 倍时,NSGA-II 能够在时间复杂度为 O(N n^k)的情况下,使用四种不同的选择父母方式和位操作变异来优化 OneJumpZeroJump 基准测试,其中跳跃大小为 2≤k≤n/ 4。使用快速变异时,最近提出的重尾变异算子使这一保证提高了 k^Ω(k)倍。总体上,本研究表明,NSGA-II 至少可以胜任 OneJumpZeroJump 问题的局部最优解,不输于全局 SEMO 算法。
Apr, 2022
通过第一次对 NSGA-II 人口动态的数学理解,我们证明了适当的人口规模的 NSGA-II 需要 O(Nnlogn)函数评估来查找 OneMinMax 问题的 Pareto 前沿,并且需要 O(Nn^k)个评估来解决带跳跃大小为 k 的 OneJumpZeroJump 问题,这些界限与以前显示的上界相一致,并且表明即使在并行运行时间(迭代次数)方面,NSGA-II 在较大的种群大小上也不会获益。
Sep, 2022
本文通过数学分析证实采用交叉操作时,NSGA-II 可以更快地优化 OneJumpZeroJump benchmark,并证明了这种交叉操作对单目标优化也有帮助,实验结果与证明相符。
Aug, 2022
本研究分析了 NSGA-II 算法在无法计算完整 Pareto 前沿时的逼近情况,使用瞬时拥挤距离的算法要比以前版本更好地逼近了 Pareto 前沿。
Mar, 2022
本研究对于遗传算法在随机 3-SAT 问题上的运行时间进行了严格的分析,并针对较弱的适应性 - 距离相似性提出了解决方案。研究结果表明,引入一个上限可以避免种群大小过大而导致的问题,并证明了该算法可以有效地解决组合搜索和优化问题。
Apr, 2017
特征选择是机器学习和数据挖掘中的一项复杂任务,其目标是去除无关和多余的特征,以提高分类准确性和减少内存需求。我们提出了一种多目标二进制优化算法 Compact NSGA-II,通过紧凑表示将种群视为概率分布,从而减少适应度评估次数,有效地探索搜索空间并在有限预算内表现出更高的效率。该算法是首个用于特征选择的紧凑多目标算法,并在五个数据集上的昂贵优化案例中取得了比 NSGA-II 更好的性能表现。
Feb, 2024
通过数学运行分析一个简单的多目标进化算法 (MOEA) 在评估函数噪声存在的情况下对模拟基准的第一次 Pareto 前沿的发现表明,MOEA 的稳健性源于其隐式多样性机制,该机制旨在使其能够计算涵盖整个 Pareto 前沿的人口。
May, 2023