基于采样的概率约束单调次模问题的帕累托优化
内容提要
本文研究了子模优化问题及其算法，包括贪心算法和多目标进化算法GSEMO-C，探讨了在社交网络和最大覆盖问题中的应用。提出了滑动窗口加速技术和不确定性感知搜索框架，显著提升了算法的性能和效率。
延伸解读
从机会约束到确定性分析：概率约束子模优化的演进
文章梳理了概率约束子模优化问题的研究脉络。早期工作使用机会约束和Chernoff边界估计约束违规，使贪心算法在社交网络等场景中高效获得高质量解。2023年的研究则转向确定性设定，提出新的分析方法，为贪心算法提供近似最优解的理论保证，并在最大覆盖和影响力最大化实验中验证有效性。这一演进反映了该领域从依赖概率估计到追求确定性理论保证的趋势。
多目标进化算法在子模最大化中的理论保证
针对子模最大化问题，文章介绍了基于多目标进化算法GSEMO-C的研究。该工作覆盖有/无大小约束的子模函数最大化以及有大小约束的单调逼近子模函数最大化，证明了算法能在多项式期望运行时间内达到良好的近似效果。这为进化算法求解子模问题提供了理论支撑，表明其不仅实验有效，而且具有可证明的性能保证。
滑动窗口加速与流式算法：提升大规模子模优化效率
文章提到滑动窗口加速技术，通过减少种群规模，在保持相同理论性能保证的同时，显著提升最大覆盖问题实例和约束设置的求解效果。此外，首个一次遍历流算法采用数据采样，在多种情况下获得最紧逼近保证，内存占用小且函数评估次数少，实验表明在大规模机器学习子模最大化中表现提升50倍以上。这些技术共同推动了子模优化在大规模场景下的实用化。
不确定性感知搜索与动态约束背包问题的进展
针对未知子模函数只能通过嘈杂数据访问的问题，文章介绍了不确定性感知搜索框架USeMO，它使用代理模型进行多目标黑盒优化，通过减少函数评估次数来近似真实Pareto集，在合成和真实基准问题上优于现有算法。同时，三目标进化算法被用于解决具有随机和动态约束的背包问题，将体重和容量建模为随机动态组成部分，相比二目标公式在动态问题中表现出明显优势。
Q&A
什么是子模优化问题？
子模优化问题是一类具有特定性质的优化问题，其中目标函数满足子模性，即增加某个元素的边际收益随着已选择元素的增加而递减。
贪心算法在社交网络问题中的应用效果如何？
贪心算法在社交网络问题中能够有效获得高品质解，并保持其有效性，尤其是在应用Chernoff边界进行约束违规估计时。
GSEMO-C算法的优势是什么？
GSEMO-C算法在多项式期望运行时间内实现了良好的近似效果，适用于子模最大化问题，包括有大小约束和无大小约束的情况。
滑动窗口加速技术的作用是什么？
滑动窗口加速技术通过减少算法中的种群规模，显著提高了解决最大覆盖问题的效果，同时保持理论性能保证。
不确定性感知搜索框架USeMO的优势是什么？
USeMO框架通过使用代理模型的多目标黑盒优化，减少函数评估数量，能够优于现有算法，提供更好的近似Pareto集。
三目标进化算法在动态背包问题中的表现如何？
三目标进化算法在处理具有随机和动态约束的背包问题时，表现优越，相较于二目标公式具有明显优势。
