Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets

• URL: http://arxiv.org/abs/2007.02050v1
• Date: Sat, 4 Jul 2020 09:19:45 GMT
• Title: Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets
• Authors: Weiyu Chen, Hisao Ishibuhci, and Ke Shang
• Abstract summary: We propose a new lazy greedy algorithm exploiting the submodular property of the hypervolume indicator. Experimental results show that the proposed algorithm is hundreds of times faster than the original greedy inclusion algorithm.
• Score: 5.222705629027499
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Effective anytime algorithm for multiobjective combinatorial optimization problems [3.2061579211871383]
  A set of efficient solutions that are well-spread in the objective space is preferred to provide the decision maker with a great variety of solutions. We propose a new exact algorithm for multiobjective optimization combining three novel ideas to enhance the anytime behavior.
  arXiv  Detail & Related papers  (2024-02-06T11:53:44Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Fast Greedy Subset Selection from Large Candidate Solution Sets in Evolutionary Multi-objective Optimization [11.110675371854988]
  We discuss the efficiency of greedy subset selection for the hypervolume, IGD and IGD+ indicators. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency.
  arXiv  Detail & Related papers  (2021-02-01T16:14:15Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates. We show that meta-algorithm-selection can indeed prove beneficial in some cases.
  arXiv  Detail & Related papers  (2020-11-17T17:27:33Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.