Hypervolume plus versus uncrowded hypervolume UHVI

[nikohansen]

I was looking at the new readme file

https://github.com/CMA-ES/moarchiving/pull/13/files#diff-b335630551682c19a781afebcf4d07bf978fb1f8ac04c6bf87428ed5106870f5

which starts with:

This library implements a multi-objective archive of non-dominated solutions (currently supporting only 2, 3 and 4 objectives). It provides easy and fast access to the hypervolume and hypervolume plus indicators, the contributing hypervolume of each solution, and to the uncrowded hypervolume improvement of any given point in the objective space.

• In the above linked IEEE reference, I don't find any mention of the term "hypervolume plus".
• I currently don't understand the difference between the uncrowded hypervolume (like analogously defined to the uncrowded hypervolume improvement but on a set and without the difference to indicate the improvement) and the "hypervolume plus". They are the same, right?

[ttusar]

In the above linked IEEE reference, I don't find any mention of the term "hypervolume plus".

It's in the appendix:

[ttusar]

I currently don't understand the difference between the uncrowded hypervolume (like analogously defined to the uncrowded hypervolume improvement but on a set and without the difference to indicate the improvement) and the "hypervolume plus". They are the same, right?

I think they are the same when you compute them on a set of points (but @naceee should confirm). The improvement part is different though and I'm unsure what is the best course of action to clarify that.

[brockho]

Hello. From my understanding, the "hypervolume plus" is what we do in COCO, i.e. normalization first wrt. ideal and nadir and then using the uncrowded hypervolume (improvement). In this sense, the two are not the same, I would say.

[ttusar]

Damn, now that you mention it, I'm not sure we are doing any normalization ...

[ttusar]

This would be a great feature to have, actually. If the ideal point is provided (in addition to the reference point, which is required for HV computation anyway), the results would be normalized ...

[brockho]

Damn, now that you mention it, I'm not sure we are doing any normalization ...

I don't think that by default there should be any normalization. And maybe, there even cannot be any reasonable normalization if no ideal and nadir point are known (any normalization, "relative", to the so-far-seen archive will be void and difficult, if not even impossible to revert as soon as new points come in).

[nikohansen]

This would be a great feature to have, actually. If the ideal point is provided (in addition to the reference point, which is required for HV computation anyway), the results would be normalized ...

Sounds doable. Making it more modular, it could also be a simple wrapping function class which can be called with an $f$-vector and returns the normalized values vector and is used when putting elements in the archive.

[nikohansen]

Getting back to the original issue, it seems the phrase

It provides easy and fast access to the hypervolume and hypervolume plus indicators

is not entirely correct and should be amended, right?

[naceee]

As far as I understand it hypervolume plus is an extension of hypervolume indicator, that also takes into account solutions that are dominated by the reference point, as explained here:

[naceee]

I was not familiar with uncrowded hypervolume for a set only, but those two could be the same thing

[nikohansen]

As far as I understand it hypervolume plus is an extension of hypervolume indicator, that also takes into account solutions that are dominated by the reference point, as explained here:

This is not the reference you were using, right? Could you give the pointer? Here, it's called $I^{\rm MOP}$, not $I^+$?

In the above given reference we have

When computing the multiobjective quality indicator IHV+, the objective space is first normalized so that the ROI [zideal, znadir] is mapped to $[0, 1]^m$. The indicator value depends on whether the archive dominates the nadir point. If the nadir point is dominated by at least one point in the archive, IHV+ is computed as the negative normalized hypervolume of the archive using the nadir point as the hypervolume reference point

As Dimo pointed out, it is defined with a normalization which we don't have in the archive module. We should be as concise as possible.

If it is correct (and $d$ is defined accordingly), we can just point to $I^{\rm MOP}$ for defining what we do.

[naceee]

This is not the reference you were using, right? Could you give the pointer? Here, it's called IMOP , not I+ ?

The snippet I sent is from here. Maybe @ttusar will know why we referenced the other paper?

[nikohansen]

The snippet I sent is from here. Maybe @ttusar will know why we referenced the other paper?

I guess it was the oversight of having a normalization, but it also doesn't matter: if it's not describing what we do, it must be either qualified accordingly or changed.

[naceee]

I agree. Then also the indicator for constraint problems is wrong, as we don't do any normalization there either.

[ttusar]

Let me try to clarify. In the I_CMOP paper, where we extended I_HV+ to constrained cases, we renamed I_HV+ to I_MOP to make it easier to follow the various indicators we defined (we also had an I_SOP indicator, an I_CSOP indicator and proposed the I_CMOP indicator). To "go back to origins" I suggested we use the original name I_HV+ here instead.

I missed the issue with the references - we should of course reference the I_HV+ paper for this indicator, not the I_CMOP paper (which I imagine we need to reference anyway for the I_CMOP indicator).

However, note that I_MOP and I_HV+ are both exactly the same - they both use normalization, it just looks like I_MOP doesn't because this is not contained in the snippet. So, we still have the problem that the implementation here is not I_HV+ (nor I_MOP), but the non-normalized I_HV+.

I would prefer we offer the normalized and non-normalized versions for the I_HV+ indicator (I recently needed the normalized one and was kind of a pain to have to do the normalization myself). In addition to being really useful, it would also be actually easier to explain.

Now, just to check - I_CMOP does require the knowledge of the ideal value (for normalization purposes), right?

Then also the indicator for constraint problems is wrong, as we don't do any normalization there either

That needs to be fixed, as without normalization it doesn't make much sense, I'm afraid.

[nikohansen]

I tend to prefer to first fix and merge the current pull request and only then integrate new functionality, but in the end it's up to you. In either case, we need to explain what hypervolume_plus means without normalization, so we cannot just put the reference.

[nikohansen]

Do you agree with this characterization?

    @property
    def hypervolume_plus(self):
        """uncrowded hypervolume of the entire archive.

        This returns the smallest distance of any element to the empirical
        pareto front times -1 if the hypervolume is zero and otherwise the
        hypervolume w.r.t. the reference point.

EDIT: when the HV is zero, the archive is empty anyways.

[brockho]

Do you agree with this characterization?

@property
def hypervolume_plus(self):
    """uncrowded hypervolume of the entire archive.

    This returns the smallest distance of any element to the empirical
    pareto front times -1 if the hypervolume is zero and otherwise the
    hypervolume w.r.t. the reference point.

EDIT: when the HV is zero, the archive is empty anyways.

Two comments/questions (otherwise, the docstring is fine besides changing the "p" in "pareto" to a capital "P"):

• Do we want to mention that it is the Euclidean distance?
• Does it become clear that the empirical Pareto front contains only the reference point in case the hypervolume is zero?

[ttusar]

Does it become clear that the empirical Pareto front contains only the reference point in case the hypervolume is zero?

Is this even true though? Isn't the empirical Pareto front empty when the hypervolume is zero?

[brockho]

Does it become clear that the empirical Pareto front contains only the reference point in case the hypervolume is zero?

Is this even true though? Isn't the empirical Pareto front empty when the hypervolume is zero?

The hypervolume is zero as long as no solution is found that (strictly) dominates the reference point. In this case, the UHVI is defined as the negative distance to the area/hypervolume below the reference point (when minimizing all objectives). This corresponds to the case where the reference point is the only point in the empirical Pareto front, if I am not mistaken.

[ttusar]

Yes, I know. My question was more basic because when the hypervolume is zero, you could have only the reference point in the archive or the archive could be empty. I'm not sure you can deduce which one it is ...

EDIT: The reference point can never be part of the archive since it does not dominate the reference point. So when the hypervolume is zero, the archive is empty.

[nikohansen]

We may be getting somewhere, 2nd attempt:

    @property
    def hypervolume_plus(self):
        """uncrowded hypervolume of the entire archive.

        `hypervolume_plus` equals to the hypervolume when the archive is
        nonempty, otherwise it is the smallest Euclidean distance to the
        hypervolume area (AKA reference domain) times -1 of any element
        that was previously added but rejected because it did not dominate
        the reference point.

        Details: conceptually, the distance computation is based on the
        nondominated archive as if it was not pruned by the reference
        point.