More Information
Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37
List of All Issues » Issue TOC

Evolutionary Computation

Fall 2016, Vol. 24, No. 3, Pages 411-425
(doi: 10.1162/EVCO_a_00157)
© 2016 Massachusetts Institute of Technology
Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms
Article PDF (799.14 KB)
Tobias Kuhn
Mathematical Institute, University of Kaiserslautern, Germany
Carlos M. Fonseca
CISUC, Department of Informatics Engineering, University of Coimbra, Portugal
Luís Paquete
CISUC, Department of Informatics Engineering, University of Coimbra, Portugal
Stefan Ruzika
Mathematical Institute, University of Koblenz-Landau, Campus Koblenz, Germany
Miguel M. Duarte
CISUC, Department of Informatics Engineering, University of Coimbra, Portugal
José Rui Figueira
CEG-IST, Instituto Superior Técnico, Universidade de Lisboa, Portugal
Abstract

The hypervolume subset selection problem consists of finding a subset, with a given cardinality k, 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 k-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 (2009), and slightly improves upon the result of in Bringmann et al. (2014b), which was developed independently from this work using different techniques. Numerical results are shown for several values of n and k.