[文献阅读]An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints(Bian C)
前言
这篇文章为南京大学人工智能学院研究助理卞超所写,主要研究内容为提出了一个有效的进化算法求解子集选择问题。论文地址:http://www.lamda.nju.edu.cn/qianc/aaai20-eamc-final.pdf
下面为作者的简略总结:
1、问题背景
子集选择问题(subset selection problem),有广泛应用,例如最大覆盖问题(maximum coverage)、传感器放置(sensor placement)、最大影响力问题(influence maximization)等
2、subset selection problem模型
monotone function 的定义:
3、两个state-of-the-art算法(对比算法)
(1)贪婪:根据 f 和 c 的最大边际收益,增量式地一个一个增加元素;是一个有效地固定时间算法,但是性能受限;
(2)POMC:将原问题转化为多目标优化,最大化目标f,最小化约束c;通过逐位变异产生新个体,如果支配当前种群中个体则加入,删除被支配个体;但是由于种群数量不限,导致时间不可控,可能是指数增长
4、文章提出的EAMC
- 引入了一个代理目标 g
其中,
算法流程: - 种群初始为全零解集;
- 循环:从种群中随机选择一个个体逐位变异,若满足约束,则判断有无模相等的个体在种群里,若没有则将其加入种群,并且记录u_i和v_i都为当前个体(u_i和v_i分别表示模为 i 的f(x)和g(x)最大的解);否则,更新u_i和v_i,并将规模为 i 的所有个体从种群中删除,将u_i和v_i加入种群;
5、理论分析
证明了算法在多项式时间内,可找到目前已知最好的近似解。
其中,Eq.(4):
6、实验分析
(1)对比算法即本博客第3小节中介绍的两种,贪婪和POMC
(2)针对三个应用问题进行了测试,结果如下图
注:机器之心公众号也有一篇文章介绍了这篇论文,链接为https://mp.weixin.qq.com/s/QDbWwT5ZP2MNF3NVHX_SzQ
ps:初学此文,如有错误敬请包涵~