子集选择之帕累托优化方法的拓展研究

发布时间：2021-09-22 19:48

　　子集选择问题旨在从全集中挑选一个子集,使预先给定的评价指标达到最优。其在机器学习等领域有广泛应用,例如模型选择、特征选择、样本选择等任务都可归结为子集选择问题。子集选择是经典的NP难问题,因此研究者不断地在寻找适合该类问题的高效近似算法,例如贪心算法被证明在子模函数子集选择问题上具有常数近似率,也成为最为常用的子集选择近似算法。最近,研究者提出一种基于双目标优化的帕累托优化算法,并用于子集选择问题,形成子集选择算法POSS。POSS被证明具有优于贪心算法的逼近能力,受到了关注。然而,POSS算法存在求解效率不高、求解约束单一、求解环境无噪的限制。为了更好的求解实际问题中面临的子集选择问题,本文基于POSS逼近能力的优势,从求解效率、约束类型、环境噪音三方面进行拓展研究,取得了如下结果:1.在求解效率方面,针对双目标优化过程不区分阶段性导致优化过程缺乏着重点,提出了贯序分解方法,将其优化过程分解为多个阶段,在不同的时间着重优化其中一个阶段,并在多个问题上进行了时间复杂度分析,发现该方法可获得O（n）的加速;针对POSS算法顺序执行而难以利用现有多核计算设备加速的不足,提出了异步并行化方法... 

【文章来源】：南京大学江苏省 211工程院校 985工程院校 教育部直属院校

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

图３－３：?ｗ５ａ数据集（７０００样本，５０００个特征）??（算法成果已经发表在ＩＪＣＡＩ－１６上，如需更详细的结果，可以参考已经发表的??论文［３Ｇ］）

图４－２：传感器放置（ｅｎｔｒｏｐｙ：越大越好）??近似

图４－３：影响力传播（ｓｐｒｅａｄ：越大越好）??

【参考文献】：
期刊论文
[1]Variable solution structure can be helpful in evolutionary optimization[J]. QIAN Chao,YU Yang,ZHOU Zhi-Hua.  Science China（Information Sciences）. 2015(11)



本文编号：3404286