Subset Selection by Pareto Optimization with Recombination

Authors

  • Chao Qian Nanjing University
  • Chao Bian Nanjing University
  • Chao Feng University of Science and Technology of China

DOI:

https://doi.org/10.1609/aaai.v34i03.5621

Abstract

Subset selection, i.e., to select a limited number of items optimizing some given objective function, is a fundamental problem with various applications such as unsupervised feature selection and sparse regression. By employing a multi-objective evolutionary algorithm (EA) with mutation only to optimize the given objective function and minimize the number of selected items simultaneously, the recently proposed POSS algorithm achieves state-of-the-art performance for subset selection. In this paper, we propose the PORSS algorithm by incorporating recombination, a characterizing feature of EAs, into POSS. We prove that PORSS can achieve the optimal polynomial-time approximation guarantee as POSS when the objective function is monotone, and can find an optimal solution efficiently in some cases whereas POSS cannot. Extensive experiments on unsupervised feature selection and sparse regression show the superiority of PORSS over POSS. Our analysis also theoretically discloses that recombination from diverse solutions can be more likely than mutation alone to generate various variations, thereby leading to better exploration; this may be of independent interest for understanding the influence of recombination.

Downloads

Published

2020-04-03

How to Cite

Qian, C., Bian, C., & Feng, C. (2020). Subset Selection by Pareto Optimization with Recombination. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2408-2415. https://doi.org/10.1609/aaai.v34i03.5621

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization