Two-phase procedure for efficiently removing dominated solutions from large solution sets

Shu，Tianye; Nan，Yang; Shang，Ke; Ishibuchi，Hisao

10.1145/3583131.3590404

2023-07-15

Genetic and Evolutionary Computation Conference (GECCO)

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

740-748

JUL 15-19, 2023

null,Lisbon,PORTUGAL

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

ASSOC COMPUTING MACHINERY

In evolutionary multi-objective optimization (EMO), one important procedure is to remove all dominated solutions from a solution set (e.g., solutions in an archive) to obtain an approximated Pareto front, which is called a static nondominance problem. Recently, an unbounded external archive (UEA) is used in EMO algorithms in many studies to store all solutions examined during the evolutionary process. In these studies, the candidate set in the static nondominance problem includes all the examined solutions. Although many methods have been proposed to solve the static nondominance problem, the dominated solution removal is still time-consuming for a large-scale candidate set. To tackle this issue, we propose a simple and general two-phase procedure to improve the efficiency of existing dominated solution removal methods. In the first phase of our procedure, a large-scale candidate set is divided into several subsets. Dominated solutions are removed from each subset independently, and remaining solutions are merged. In the second phase, dominated solutions are removed from the merged set. Compared with directly removing all dominated solutions from the candidate set, our experimental results show that the proposed two-phase procedure can drastically decrease the computation time when the percentage of nondominated solutions in the candidate set is small.

dominated solution removal multi-objective optimization

First ; Corresponding

English

CPCI-S

National Natural Science Foundation of China["62002152","62250710163","62250710682"] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Program for Guangdong Introducing Innovative and Enterpreneurial Teams[2017ZT07X386] ; Stable Support Plan Program of Shenzhen Natural Science Fund[20200925174447003] ; Shenzhen Science and Technology Program[KQTD201611 2514355531]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems

WOS:001031455100083

2-s2.0-85167659789

Scopus

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

Shu，Tianye,Nan，Yang,Shang，Ke,et al. Two-phase procedure for efficiently removing dominated solutions from large solution sets[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023:740-748.