Distance-based subset selection revisited

Shang，Ke; Ishibuchi，Hisao; Nan，Yang

10.1145/3449639.3459391

2021-06-26

2nd Genetic and Evolutionary Computation Conference (GECCO)

GECCO 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

439-447

JUL 10-14, 2021

null,null,ELECTR NETWORK

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

In this paper, we revisit the distance-based subset selection (DSS) algorithm in evolutionary multi-objective optimization. First, we show one drawback of the DSS algorithm, i.e., a uniformly distributed solution set cannot always be selected. Then, we show that this drawback can be overcome by maximizing the uniformity level of the selected solution set, which is defined by the minimum distance between two solutions in the solution set. Furthermore, we prove that the DSS algorithm is a greedy inclusion algorithm with respect to the maximization of the uniformity level. Based on this conclusion, we generalize DSS as a subset selection problem where the objective is to maximize the uniformity level of the subset. In addition to the greedy inclusion DSS algorithm, a greedy removal algorithm and an iterative algorithm are proposed for the generalized DSS problem. We also extend the Euclidean distance in the original DSS to other widely-used and user-defined distances. We conduct extensive experiments on solution sets over different types of Pareto fronts to compare the three DSS algorithms with different distances. Our results suggest the usefulness of the generalized DSS for selecting a uniform subset. The effect of using different distances on the selected subsets is also analyzed.

Evolutionary computation Multi-objective optimization Subset selection

第一 ; 通讯

英语

CPCI-S ; EI

National Natural Science Foundation of China[62002152,61876075]

Computer Science ; Operations Research & Management Science ; Mathematics

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Operations Research & Management Science ; Mathematics, Applied

WOS:000773791800053

20212910647378

Iterative methods ; Multiobjective optimization ; Set theory

Mathematics:921

2-s2.0-85110056050

Scopus

Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China

Shang，Ke,Ishibuchi，Hisao,Nan，Yang. Distance-based subset selection revisited[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2021:439-447.