科研之友
微信
新浪微博
Facebook
分享链接
摘要
在许多现实的机器学习任务中,经常遇到从一组变量中挑选一个子集的问题,即子集选择问题.对于这类问题的求解是NP难的.最近,一种基于多目标演化算法的子集选择算法POSS被提出;无论是在理论上还是在实验上,POSS方法均获得了目前的最佳性能.然而,当问题规模很大的时候,POSS方法的运行时间变得难以令人满意,这阻碍了其在大规模实际问题中的应用.提出了一种基于分解策略的多目标演化子集选择算法DPOSS.DPOSS方法将整个子集空间分解成多个子空间,并依次调用POSS方法来求解.在理论上,DPOSS方法在获得和POSS方法相同近似性能下界的同时,运行时间随着分解个数的增加超线性下降.实验结果验证了这一理论,并显示出,DPOSS方法的实际性能随着分解个数的增加略有下降,但依然优于以往的贪婪算法.
- 单位
