基于分解策略的多目标演化子集选择算法

发布时间：2017-10-24 23:28

  本文关键词：基于分解策略的多目标演化子集选择算法

  更多相关文章： 机器学习 子集选择 多目标优化 多目标演化算法 分解策略

【摘要】：在许多现实的机器学习任务中,经常遇到从一组变量中挑选一个子集的问题,即子集选择问题.对于这类问题的求解是NP难的.最近,一种基于多目标演化算法的子集选择算法POSS被提出;无论是在理论上还是在实验上,POSS方法均获得了目前的最佳性能.然而,当问题规模很大的时候,POSS方法的运行时间变得难以令人满意,这阻碍了其在大规模实际问题中的应用.提出了一种基于分解策略的多目标演化子集选择算法DPOSS.DPOSS方法将整个子集空间分解成多个子空间,并依次调用POSS方法来求解.在理论上,DPOSS方法在获得和POSS方法相同近似性能下界的同时,运行时间随着分解个数的增加超线性下降.实验结果验证了这一理论,并显示出,DPOSS方法的实际性能随着分解个数的增加略有下降,但依然优于以往的贪婪算法.
【作者单位】： 南京大学计算机软件新技术国家重点实验室;软件新技术与产业化协同创新中心;中国科学技术大学计算机科学与技术学院;
【关键词】： 机器学习 子集选择 多目标优化 多目标演化算法 分解策略
【基金】：国家自然科学基金(批准号:61333014,61321491)资助项目
【分类号】：TP18
【正文快照】： 国家自然科学基金(批准号:61333014,61321491)资助项目1引言在许多现实的机器学习任务中,经常遇到这样一类问题:从给定的n个变量中选择大小不超过k的一个子集来优化某个给定的目标.这类问题被称为子集选择(subset selection)问题,其起源于矩阵列选择问题,即从一个给定的矩阵中，

本文编号：1091063