Document Type

Journal Article

Publisher

IEEE

Faculty

Computing, Health and Science

School

Computer and Information Science

RAS ID

4818

Comments

This article was originally published as: While, L., Hingston, P., Barone, L., & Huband, S. (2006). A Faster Algorithm for Calculating Hypervolume. IEEE Transactions on Evolutionary Computation, 10(1), pp. 29-38. Original article available here

© 2006 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Abstract

We present an algorithm for calculating hypervolume exactly, the Hypervolume by Slicing Objectives (HSO) algorithm, that is faster than any that has previously been published. HSO processes objectives instead of points, an idea that has been considered before but that has never been properly evaluated in the literature. We show that both previously studied exact hypervolume algorithms are exponential in at least the number of objectives and that although HSO is also exponential in the number of objectives in the worst case, it runs in significantly less time, i.e., two to three orders of magnitude less for randomly generated and benchmark data in three to eight objectives. Thus, HSO increases the utility of hypervolume, both as a metric for general optimization algorithms and as a diversity mechanism for evolutionary algorithms

DOI

10.1109/TEVC.2005.851275

Access Rights

free_to_read

 
COinS
 

Link to publisher version (DOI)

10.1109/TEVC.2005.851275