期刊
EVOLUTIONARY COMPUTATION
卷 24, 期 3, 页码 411-425出版社
MIT PRESS
DOI: 10.1162/EVCO_a_00157
关键词
Multiobjective optimization; subset selection; hypervolume; k-link shortest path
资金
- bilateral cooperation research project Tractability in multiobjective combinatorial optimization - Deutscher Akademischer Austausch Dienst
- bilateral cooperation research project Tractability in multiobjective combinatorial optimization - Fundacao para a Ciencia e a Tecnologia
- Federal Ministry of Education and Research Germany [FKZ13N12229]
- QREN [CENTRO-07-ST24-FEDER-002003]
- European Union's FEDER
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 O(k(n - k) + n log n) time. This improves upon the result of O(n(2)k) in Bader (2009), and slightly improves upon the result of O(nk + n log n) 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据