日前，AAAI 2020 已在美国纽约隆重召开。不久之前，大会官方公布了今年的论文收录信息：收到 8800 篇提交论文，评审了 7737 篇，接收 1591 篇，接收率 20.6%。为向读者们分享更多的优质内容、促进学术交流，机器之心策划了多期AAAI 2020 论文线上分享。

近日，机器之心邀请了南京大学人工智能学院研究助理卞超通过线上分享的方式介绍他们入选 AAAI 2020 的研究论文《An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints》。这篇论文提出了一个高效的演化算法 EAMC，来解决一般约束下的子集选择问题。本文将对这项研究成果进行介绍。

子集选择问题是一个 NP-hard 问题，并且具有很多应用场景，比如最大覆盖、影响力最大化和传感器放置。该问题的目标是从 n 个元素中，选择满足约束 c 的一个子集，使得目标函数 f 的值最大：

其中 f 和 c 都是单调的，但并不一定满足子模性。

针对这类问题，现有的代表性算法有广义贪心算法和 POMC。广义贪心算法耗时较短，但是受限于它的贪心行为，其找到的解质量往往一般；POMC 作为随机优化算法，可以使用更多的时间来找到质量更好的解，但是其缺乏多项式的运行时间保证。为此，这篇 AAAI 2020 论文提出了一个高效的演化算法 EAMC。通过优化一个整合了 f 和 c 的代理函数，它可以在多项式时间内找到目前已知最好的近似解。研究者还在最大覆盖、影响力最大化和传感器放置等任务上进行了实验，结果表明该算法的表现优于广义贪心算法。