AAAI 2020 分享｜南京大学：具有一般约束的子集选择问题的高效进化算法

如果你不能出去，最好在家看你的论文。在最新一期机器之心AAAI 2020线上分享中，我们邀请到了南京大学人工智能学院研究助理卞超与我们分享。

严重的疫情不仅影响了我们的日常生活，也给世界各地的学术会议和交流活动带来了极大的不便。

作为今年举办的第一届人工智能峰会，AAAI 2020也受到了很大的影响。许多国内论文作者无法正常参加本次峰会并进行学术交流。

为了与读者分享更多优质内容，让大家在不能出门的日子里高效学习，机器之心将继续组织AAAI 2020线上论文分享。在最新的在线分享中，我们邀请了南京大学人工智能学院研究助理卞超在论文《An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints》中介绍了他们提出的进化算法EAMC。

卞超，现任南京大学人工智能学院研究助理。导师为南京大学于洋教授和钱超副教授。研究兴趣包括不确定性优化（包括噪声优化和动态优化）下进化算法的理论分析，以及多目标优化。进化算法的理论分析；在理论指导下，针对实际优化问题设计高效的进化算法。邮箱：chaobian12@gmail.com

谈话总结：子集选择问题旨在选择满足约束 c 的 n 个元素的子集，以最大化目标函数 f。它有许多应用，包括影响最大化、传感器放置等。针对此类问题，现有的代表性算法有广义贪心算法和POMC。广义贪心算法花费的时间更少子集和问题 近似算法，但受限于其贪心行为，它找到的解决方案的质量通常是平均的；POMC作为一种随机优化算法，可以用更多的时间找到质量更好的解，但缺乏多项式Uptime保证。因此，我们提出了一种高效的进化算法EAMC。通过优化集成 f 和 c 的代理函数，它可以在多项式时间内找到最佳已知的近似解，

论文链接：

时间：北京时间2月7日20:00-21:00

AAAI 2020 机器之心在线分享

在 AAAI 2020 收录的大量优秀论文中，我们将精选几篇优质论文，邀请其作者在线分享。整个分享由论文解读和互动问答两部分组成。

线上分享将在“AAAI 2020交流群”进行。入群方法：加机器之心小助手（syncedai4），备注“AAAI”子集和问题 近似算法，邀请入群，入群后会公布直播链接。