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