Greedy approximated hypervolume subset selection for many-objective optimization

Shang，Ke; Ishibuchi，Hisao; Chen，Weiyu

10.1145/3449639.3459390

2021-06-26

2nd Genetic and Evolutionary Computation Conference (GECCO)

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

448-456

JUL 10-14, 2021

null,null,ELECTR NETWORK

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

ASSOC COMPUTING MACHINERY

Hypervolume subset selection (HSS) aims to select a subset from a candidate solution set so that the hypervolume of the selected subset is maximized. Due to its NP-hardness nature, the greedy algorithms are the most efficient for solving HSS in many-objective optimization. However, when the number of objectives is large, the calculation of the hypervolume contribution in the greedy HSS is time-consuming, which makes the greedy HSS inefficient. To solve this issue, in this paper we propose a greedy approximated HSS algorithm. The main idea is to use an R2-based hypervolume contribution approximation method in the greedy HSS. In the algorithm implementation, a utility tensor structure is introduced to facilitate the calculation of the hypervolume contribution approximation. In addition, the tensor information in the last step is utilized in the current step to accelerate the calculation. We also apply the lazy strategy in the proposed algorithm to further improve its efficiency. We test the greedy approximated HSS algorithm on 3-10 objective candidate solution sets. The experimental results show that the proposed algorithm is much faster than the state-of-the-art greedy HSS algorithm in many-objective optimization while their hypervolume performance is almost the same.

Greedy algorithm Hypervolume Many-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:000773791800054

20212910647377

Evolutionary algorithms ; NP-hard ; Set theory ; Tensors

Mathematics:921

2-s2.0-85110107328

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,Chen，Weiyu. Greedy approximated hypervolume subset selection for many-objective optimization[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2021:448-456.