Skip Nav Destination

*PDF*

Update search

### NARROW

Format

Journal

Date

Availability

1-1 of 1

Karl Bringmann

Close
**Follow your search**

Access your saved searches in your account

Would you like to receive an alert when new items match your search?

*Close Modal*

Sort by

Journal Articles

Publisher: Journals Gateway

*Evolutionary Computation*(2010) 18 (3): 383–402.

Published: 01 September 2010

Abstract

View article
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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3. Abstract 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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3. Abstract 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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3. Abstract 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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3. Abstract 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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3. Abstract 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 ( 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 for d = 3. We also analyze hypervolume indicator based optimization algorithms which remove λ > 1 solutions from a population of size n = μ + λ. We show that there are populations such that the hypervolume contribution of iteratively chosen λ solutions is much larger than the hypervolume contribution of an optimal set of λ solutions. Selecting the optimal set of λ solutions implies calculating 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 λ solutions. This gives an additive term of in the runtime of the calculation instead of a multiplicative factor of . More precisely, for a population of size n with d objectives, our algorithm can calculate a set of λ solutions with minimal hypervolume contribution in time ( n d /2 log n + n λ ) for d > 2. This improves all previously published algorithms by a factor of n min{λ, d /2} for d > 3 and by a factor of n for d = 3.