Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms

The hypervolume subset selection problem consists of finding a subset, with a given cardinality , of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically ef...

Full description

Saved in:
Bibliographic Details
Published in:Evolutionary computation 2016-09, Vol.24 (3), p.411-425
Main Authors: Kuhn, Tobias, Fonseca, Carlos M., Paquete, Luís, Ruzika, Stefan, Duarte, Miguel M., Figueira, José Rui
Format: Article
Language:English
Subjects:
Algorithms
Evolutionary algorithms
Graph theory
hypervolume
Integer programming
link shortest path
Mathematical models
Models, Theoretical
Multiobjective optimization
Multiple objective analysis
Optimization
Shortest-path problems
subset selection
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The hypervolume subset selection problem consists of finding a subset, with a given cardinality , of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem. The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a -link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in time. This improves upon the result of in Bader ( ), and slightly improves upon the result of in Bringmann et al. ( ), which was developed independently from this work using different techniques. Numerical results are shown for several values of and .
ISSN:1063-6560
1530-9304
DOI:10.1162/EVCO_a_00157