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