Subset selection, which selects a subset of solutions according to certain criterion/indicator, is a topic closely related to evolutionary multiobjective optimization (EMO). The critical component of a multiobjective evolutionary algorithm (MOEA), environmental selection, is essentially a subset selection problem, i.e., selecting$N$solutions as the next-generation population from usually$2N$candidates (where$N$denotes the size of the population). Another use of subset selection is the solution preprocessing procedure for decision-making, in which typically a few representatives are selected from the final population or a large-size archive, in order not to overwhelm the decision maker. Existing work for subset selection in EMO is focused on developing greedy algorithms, but may suffer from being trapped in local optima. In this article, we approach the problem by providing a multiobjective evolutionary algorithmic framework. We consider several popular quality indicators for subset evaluation and present accelerated variants of a well-studied MOEA in the theoretical study area, global simple evolutionary multiobjective optimizer (GSEMO), for each indicator. We conduct rigorous theoretical analyses of the acceleration procedure. Moreover, we prove that our algorithms can achieve the best-so-far approximation guarantee by the submodularity of the indicators. We finally empirically show the effectiveness and scalability of the proposed algorithms, in addition to the potentials to be further improved by introducing popular MOEAs (e.g., using NSGA-II and MOEA/D to replace GSEMO).

Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations research. Previous studies mainly consider only one kind of constraint, while many real-world problems often involve several constraints. In this paper, we consider the problem of submodular maximization under the intersection of two commonly used constraints, i.e., k-matroid constraint and m-knapsack constraint, and propose a new algorithm SPROUT by incorporating partial enumeration into the simultaneous greedy framework. We prove that SPROUT can achieve a polynomial-time approximation guarantee better than the state-of-the-art algorithms. Then, we introduce the random enumeration and smooth techniques into SPROUT to improve its efficiency, resulting in the SPROUT++ algorithm, which can keep a similar approximation guarantee. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.