Journal
EVOLUTIONARY COMPUTATION
Volume 18, Issue 3, Pages 383-402Publisher
MIT PRESS
DOI: 10.1162/EVCO_a_00012
Keywords
-
Ask authors/readers for more resources
The hypervolume indicator serves as a sorting criterion in many recent multi-objective evolutionary algorithms (MOEAs). Typical algorithms remove the solution with the smallest loss with respect to the dominated hypervolume from the population. We present a new algorithm which determines for a population of size n with d objectives, a solution with minimal hypervolume contribution in time O(n(d/2) log n) for d > 2. This improves all previously published algorithms by a factor of n for all d > 3 and by a factor of root n for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove lambda > 1 solutions from a population of size n = mu + lambda. We show that there are populations such that the hypervolume contribution of iteratively chosen lambda solutions is much larger than the hypervolume contribution of an optimal set of lambda solutions. Selecting the optimal set of lambda solutions implies calculating ((n)(mu)) conventional hypervolume contributions, which is considered to be computationally too expensive. We present the first hypervolume algorithm which directly calculates the contribution of every set of lambda solutions. This gives an additive term of ((n)(mu)) in the runtime of the calculation instead of a multiplicative factor of ((n)(mu)). More precisely, for a population of size n with d objectives, our algorithm can calculate a set of A solutions with minimal hypervolume contribution in time O(n(d/2) log n + n(lambda)) for d > 2. This improves all previously published algorithms by a factor of n(min{lambda,d/2}) for d > 3 and by a factor of n for d = 3.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available