Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets

Chen，Weiyu; Ishibuchi，Hisao; Shang，Ke

10.1109/CEC48606.2020.9185878

2020-07-01

IEEE Congress on Evolutionary Computation (CEC) as part of the IEEE World Congress on Computational Intelligence (IEEE WCCI)

978-1-7281-6930-9

2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings

1-8

JUL 19-24, 2020

null,null,ELECTR NETWORK

345 E 47TH ST, NEW YORK, NY 10017 USA

IEEE

Subset selection is a popular topic in recent years and a number of subset selection methods have been proposed. Among those methods, hypervolume subset selection is widely used. Greedy hypervolume subset selection algorithms can achieve good approximations to the optimal subset. However, when the candidate set is large (e.g., an unbounded external archive with a large number of solutions), the algorithm is very time-consuming. In this paper, we propose a new lazy greedy algorithm exploiting the submodular property of the hypervolume indicator. The core idea is to avoid unnecessary hypervolume contribution calculation when finding the solution with the largest contribution. Experimental results show that the proposed algorithm is hundreds of times faster than the original greedy inclusion algorithm and several times faster than the fastest known greedy inclusion algorithm on many test problems.

greedy inclusion algorithms hypervolume contribution Hypervolume subset selection problem (HSSP) submodularity unbounded external archive

第一

英语

EI ; CPCI-S

National Natural Science Foundation of China[61876075] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Program for Guangdong Introducing Innovative and Enterpreneurial Teams[2017ZT07X386] ; Shenzhen Science and Technology Program[KQTD2016112514355531] ; Program for University Key Laboratory of Guangdong Province[2017KSYS008]

Computer Science ; Engineering ; Mathematical & Computational Biology ; Operations Research & Management Science

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Mathematical & Computational Biology ; Operations Research & Management Science

WOS:000703998203007

20204109316814

Approximation algorithms ; Evolutionary algorithms ; Feature Selection

Mathematics:921 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4

2-s2.0-85092043063

Scopus

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

Chen，Weiyu,Ishibuchi，Hisao,Shang，Ke. Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:IEEE,2020:1-8.