Nov, 2017

多目标进化算法优化子模函数或单调近似子模函数

PDF
TL;DR本论文研究基于多目标进化算法 GSEMO-C 的子模最大化问题（包括有 / 无大小约束的子模函数最大化问题，以及有大小约束的单调逼近子模函数最大化问题），证明了该算法可以在多项式期望运行时间内实现很好的近似效果。
evolutionary algorithmscombinatorial optimizationgsemo-csubmodular functionsapproximation guarantees
发现论文，激发创造
  • 基于存档的单目标进化算法在子模规化优化问题上的应用

    我们首次引入了单目标算法，其可成功用于不同类别的约束子模拟最大化问题，并通过增加搜索空间的可行区域来处理这些问题。

    Jun, 2024

  • 并行下考虑拟阵约束和装箱限制的子模块最大化

    本文提出了一种在单个 matroid 约束或多个 packing 约束下，通过小量自适应查询轮次来最大化 submodular 函数的多线性扩展的算法，该算法在 submodular maximization with a matroid constraint 和 non-monotone submodular maximization subject to packing constraints 两个问题上均获得了近乎最佳的拟合比例，并且在自适应轮次和并行运行时间上提出了指数级别的加速。

    Aug, 2018

  • 约束子模最大化问题：超越 1/e

    本研究提出了一种新的算法，用于在普遍限制条件下最大化非单调子模函数。该算法在下闭多面体上找到了一个函数的多线性扩展的近似分数解，其近似保证是 0.372，这是在 1/e 近似之上的首次改进，由连续贪心算法 [Feldman 等，FOCS2011] 实现。

    Aug, 2016

  • 通过多项式估计进行随机子模最大化

    本研究以连续贪心算法为基础，研究了具有一般性骨架约束的随机子模最大化问题，主要应用于在线学习，团队形成，设施位置，影响最大化，主动学习和感知目标函数。实验表明，使用多项式梯度估计代替样本估计，可有效减少随机性并缩短执行时间。

    Mar, 2023

  • 模拟退火算法进行子模最大化

    提出一种基于模拟退火的新算法用于解决子模块最大化问题，证明该算法支持两种问题的改进近似，在数值预言模型中，子模块最大化问题在独立约束和基约束条件下都不可能有更好的解决方案。

    Jul, 2010

  • 在噪声存在的情况下多目标进化算法的运行分析

    通过数学运行分析一个简单的多目标进化算法 (MOEA) 在评估函数噪声存在的情况下对模拟基准的第一次 Pareto 前沿的发现表明，MOEA 的稳健性源于其隐式多样性机制，该机制旨在使其能够计算涵盖整个 Pareto 前沿的人口。

    May, 2023

  • 可微子模最大化

    本文提出一种针对子模函数的数据学习算法，可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布，本文提出一种可微的方式对模型进行优化。实证研究表明，该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。

    Mar, 2018

  • 基于采样的概率约束单调次模问题的帕累托优化

    基于采样的方法用于直接评估机会约束，研究结果表明，采用不同评估方法的算法性能是可比较的，而采用基于采样的方法的 ASW-GSEMO 算法优于其他算法。

    Apr, 2024

  • 具有近似最优的适应性和查询复杂度的子模最大化

    本文研究自适应子模型优化的适应性和查询复杂度，提出了适用于最大基数约束的单调子模型函数的分布式算法，并将其推广到子模型覆盖问题。

    Jul, 2018

  • 利用 MOEA/D 求解多目标最小权重基问题的严格运行时分析

    研究了多目标最小重量基问题的性质，并给出了 MOEA/D 算法的运行时间分析，表明在理论和实践方面都比已有的算法更优，可望在预期的多项式时间内找到所有的极值点。

    Jun, 2023