Adding normalization

[ttusar]

After #13, we will have three HV variants (the third one is currently named differently, but this will change):

• hypervolume (for MOArchive and CMOArchive)
• hypervolume_plus (for MOArchive and CMOArchive), based on, but not completely equal to the one defined here
• hypervolume_plus_constr (for CMOArchive), based on, but not completely equal to the one defined here

None of them uses normalization of objectives and for all of them, larger values are better.

We do want to add normalized variants for all three. I see two options now, but of course, there might be others (feel free to expand and comment on these).

1st Option

If, when the archive is created, the ideal point is specified in addition to the reference point, the all solutions are normalized so that the ideal point equals $(0, ..., 0)$ and the reference point equals $(1, ..., 1)$. The names of HV properties don't change, they just return normalized values.

We would need to decide how to handle this under the hood:

• A: Keep only the normalized f-values. In this case, we would need to decide whether (and how) the user has access to the original values.
• B: Keep only the original values and take care of the normalization when the hypervolume is computed.
• C: Keep the original and normalized values (not sure yet exactly what this would entail).

2nd Option

If, when the archive is created, the ideal point is specified in addition to the reference point, we can access both the normalized and non-normalized HV values:

• hypervolume
• hypervolume_plus
• hypervolume_plus_constr
• norm_hypervolume
• norm_hypervolume_plus
• norm_hypervolume_plus_constr

Not sure what this means under the hood yet ...

[nikohansen]

all solutions are normalized so that the ideal point equals ...

I think it's less error prone and less confusing (and hence better) to keep the archive with the raw values as they were added. This is a recurrent observation: rather don't modify the data unless it is really necessary.

I like option 2.

As we are on this, why not allow for explicit weights for each objective (too)? They are by default one and they would only affect non-normalized HV computations. EDIT: individual weights are only effective in the distance to the empirical Pareto front. For the hypervolume computation, the weights are always multiplied to become the same single factor.

[brockho]

I am with @nikohansen, in particular because the only difference (besides numerical issues when not using Fraction) should be a division by a constant, right?

[ttusar]

3rd Option

When creating the archive, the user can add the ideal point (defaults to None) and/or weights (default to (1, ..., 1)). We could allow both, as this would just create new weights by multiplication (normalization just means that the weights are computed from the ideal and reference points instead of explicitly).

We would work with the original f-values in the archive and take into account the (combined) weights only when computing/updating the hypervolume.

Is there a good use case for providing both the HV and the norm_HV variants? Or can we assume that if the user specified the ideal point and/or weights, the corresponding HV value is the one the user is interested in?

I am with @nikohansen, in particular because the only difference (besides numerical issues when not using Fraction) should be a division by a constant, right?

Not in my understanding. I think you need to multiply by the weights in each dimension separately ...

[ttusar]

As a side issue: hypervolume_plus_constr is defined only for CMOArchive. Would it make sense to have the property also in the MOArchive (it would equal hypervolume_plus, it's just of a question of practicality in case one wants to switch from a problem with constraints to the same one without them)?

[brockho]

Not in my understanding. I think you need to multiply by the weights in each dimension separately ...

Yes, I only had in mind the normalization wrt. the ideal point, not additional weights for the objectives.

[ttusar]

It's the same, no?

[ttusar]

Just to clarify, @brockho, it is indeed "just a multiplication" (or division, same thing), but it has to be performed every time a point updates the archive, which (as far as I understand) affects multiple places in the code, so it is a bit annoying ...

[brockho]

Just to clarify, @brockho, it is indeed "just a multiplication" (or division, same thing), but it has to be performed every time a point updates the archive, which (as far as I understand) affects multiple places in the code, so it is a bit annoying ...

Not really. It just has to be done each time, the norm_... method is called (and actually only the first time it is called until the archive changes, because the current normalized hypervolume values can be stored without additional cost). Or am I wrong?

[ttusar]

Okay, so it took me an embarrassingly long time to realize that to get a weighted HV, you don't need to apply the weights to the individual HV contributions separately (nor care about which objective a weight is applied to), it's enough to just apply all the weights to the final result. Sorry for the needless confusion.

This simplifies the normalized/weighted indicators quite a bit, which is great. But I'm not yet convinced that having HV and norm_HV properties is the right way to go. What should the users expect to get when they define both the ideal point and weights? I find the term "normalized" in that case a bit misleading. What are your thoughts on this?

[nikohansen]

This simplifies the normalized/weighted indicators quite a bit, which is great.

AFAICS, this is unfortunately not as simple for the distance to the empirical Pareto front. For this, we need to use the weighting factors for each objective, unless we decide to not use them in this part of the computation. I think we do use them in the original definition of HVplus by rescaling the entire f-space.

What should the users expect to get when they define both the ideal point and weights? I find the term "normalized" in that case a bit misleading. What are your thoughts on this?

I wrote above that the weighting only applies to the nonnormalized case. I have no good idea whether this makes sense or what to reasonably expect.

[ttusar]

These are the conclusions from a discussion with @nikohansen:

• We only keep the three HV properties (no need for norm_HV ones).
• The user can specify the ideal point and/or weights in the constructor.
• The user can always inquire about the HV properties with a different ideal point and/or weights. This means that the factors don't get stored, but they are computed by the HV properties functions and applied to the stored "true HV" and the distance to the front.
• If both the ideal point and weights are specified, their factors are multiplied.

[nikohansen]

The user can always inquire about the HV properties with a different ideal point and/or weights.

The interface needs to be clarified. Properties do not have arguments to modify their behavior.

[nikohansen]

The simplest interface seems having two methods weights and ideal_point which return the weights and ideal point, respectively, and also set them when called with an argument.

This seems also to suggest that we should have a base class from which both MOArchiveParent and BiobjectiveNondominatedSortedList inherit?

[nikohansen]

class MOArchiveBase:
    """Provide functionality used with any number of objectives""""
    def weights(self, value=None):
        """return hypervolume weights, set to `value` when ``value is not None`` and return previous value"""
        if value is None:
            try:
                return self._weights
            except AttributeError:
                self._weights = None
            return None
        if len(value) != getattr(self, 'n_obj', len(value)):
            raise ValueError("{0} are not eligible weights when n_obj={1}".format(value, self.n_obj))
        value, self._weights = self._weights, value
        # update HV factor here?
        return value
    def ideal_point(self, value=None):
        """return ideal point, set to `value` when ``value is not None`` and return previous value"""
        if value is None:
            try:
                return self._ideal_point
            except AttributeError:
                self._ideal_point = None
            return None
        if len(value) != getattr(self, 'n_obj', len(value)):
            raise ValueError("{0} is not an eligible ideal point when n_obj={1}".format(value, self.n_obj))
        # TODO: also check consistency with reference point?
        value, self._ideal_point = self._ideal_point, value
        # update HV factor here?
        return value

[naceee]

I am starting with implementation and I have some questions:

1. We probably need two sets of weights (maybe _weights and _weights_ideal_point) to deal with the case when user defines both the ideal point and the weights?

2. I assume that weights when the ideal_point is specified are calculated like this:
   weight[i] = 1 / (reference_point[i] - ideal_point[i])
   Is this correct? Should we check that ideal_point < reference_point when it is set?

3. Should we add functions (distance_to_hypervolume_area, maybe some other as well) that are the same in both MOArchiveParent and BiobjectiveNondominatedSortedList in this class?