AAAI 2020线上分享 | 南京大学：一般约束下子集选择问题的高效演化算法

无法出门，不如在家读论文。最新一期的机器之心 AAAI 2020 线上分享，我们邀请到了南京大学人工智能学院研究助理卞超为我们做分享。

疫情严重，不仅影响了我们的日常生活，还给全球范围内的学术会议、交流活动带来了很大不便。

作为今年首个召开的人工智能顶会，AAAI 2020 也受到了极大影响。 国内众多论文作者无法正常参与此顶会，进行学术交流。

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

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

演讲概要 ： 子集选择问题旨在从 n 个元素中，选择满足约束 c 的一个子集，以最大化目标函数 f。 它有很多应用，包括影响力最大化，传感器放置等等。 针对这类问题，现有的代表性算法有广义贪心算法和 POMC。 广义贪心算法耗时较短，但是受限于它的贪心行为，其找到的解质量往往一般； POMC 作为随机优化算法，可以使用更多的时间来找到质量更好的解，但是其缺乏多项式的运行时间保证。 因此，我们提出一个高效的演化算法 EAMC。 通过优化一个整合了 f 和 c 的代理函数，它可以在多项式时间内找到目前已知最好的近似解，并且其在多类问题上的试验也显示出比广义贪心算法更好的性能。

论文链接： http://www.lamda.nju.edu.cn/qianc/aaai20-eamc-final.pdf

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

AAAI 2020 机器之心线上分享

在 AAAI 2020 收录的大量优秀论文中，我们将选出数篇优质论文，邀请论文作者来做线上分享。 整场分享包括两个部分： 论文解读和互动答疑。

线上分享将在「AAAI 2020 交流群」中进行，加群方式： 添加机器之心小助手（syncedai4），备注「AAAI」，邀请入群。 入群后将会公布直播链接。