.png){kind=icon}
Return
Fast Greedy Subset Selection From Large Candidate Solution Sets in Evolutionary Multiobjective Optimization
.png){kind=icon}
OA
AI
DOI：10.1109/TEVC.2021.3103386.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. Greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators.
Keywords:
Optimization
Greedy algorithms
Statistics
Sociology
Approximation algorithms
Evolutionary computation
Clustering algorithms
Evolutionary many-objective optimization
evolutionary multiobjective optimization (EMO)
performance indicators
submodularity
subset selection
Journal
IF:
12
Papers:
1.9K
Citations:
2.4W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSave
ShareSaveShareSave
View more