Negative hypervolume contribution (Assertion Error)

[mgharafi]

This happens when the NDA contains an optimal solution.

The case that generates this error is the following:

def fitMO(fun):
    def wrapper(x):
        return [f(x) for f in fun]
    return wrapper

def UHVI_func(x):

    x = np.array(x)

    fitness = (
        cma.ff.sphere,
        lambda x : cma.ff.sphere(x - np.array([3, *[0 for _ in range(len(x)-1)]]))
        )

    fitness = fitMO(fitness) # just computes f1 and f2

    y = fitness(x) # Solution that we want to compute the Hypervolume Improvement for
    print(f'{fitness(x)=}\n')
    xopt = np.array([1, *[0 for _ in range(len(x) - 1)]])
    fopt = fitness(xopt) # f values of the optimum added to the NDA list

    nda = NDA([fopt], reference_point=[10, 10])
    u = nda.hypervolume_improvement(y)

    return u

xe = [ 2.20085089, -0.3407483,  -0.10757458, -0.21121627, -0.08123651, -0.02822955, 0.14314837,  0.0654786,   0.14775976,  0.10432714]

print(f'x={xe}')

UHVI_func(xe)

A log of the variables just before the error

x=[2.20085089, -0.3407483, -0.10757458, -0.21121627, -0.08123651, -0.02822955, 0.14314837, 0.0654786, 0.14775976, 0.10432714]
fitness(x)=[5.080930926699208, 0.8758255866992083]
---------------from moarchiving module ------------------------
self[idx][0]=5.080930926699208
self[idx][1]=0.8758255866992083
x=10
y=4
Fc=<class 'fractions.Fraction'>
Fc(x)=Fraction(10, 1)
Fc(self[idx][0])=Fraction(2860309828522223, 562949953421312)
Fc(y)=Fraction(4, 1)
Fc(self[idx][1])=Fraction(7888735571800201, 9007199254740992)

(Fc(x) - Fc(self[idx][0])) * (Fc(y) - Fc(self[idx][1]))=Fraction(-2646344297089409049, 5070602400912917605986812821504)
dHV=Fraction(-2646344297089409049, 5070602400912917605986812821504)

Full output of the error

self[idx][0]=5.080930931365556
self[idx][1]=0.8758255853182146
x=10
y=4

Fc=<class 'fractions.Fraction'>

Fc(x)=Fraction(10, 1)
Fc(self[idx][0])=Fraction(2860309831149143, 562949953421312)
Fc(y)=Fraction(4, 1)
Fc(self[idx][1])=Fraction(1972183889840329, 2251799813685248)

(Fc(x) - Fc(self[idx][0])) * (Fc(y) - Fc(self[idx][1]))=Fraction(-5279681954710941105, 1267650600228229401496703205376)

dHV=Fraction(-5279681954710941105, 1267650600228229401496703205376)

c:\Users\moham\anaconda3\lib\fractions.py:401: RuntimeWarning: overflow encountered in longlong_scalars
  return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
~\AppData\Local\Temp/ipykernel_15324/3341594244.py in <module>
     21     for s in X:
     22         print(s)
---> 23         F_ += [true_fun(s)]
     24     ken += [kendall_tau(F, F_)]
     25     feval += [fun.evaluations]

~\AppData\Local\Temp/ipykernel_15324/1034421402.py in UHVI_func(x)
     13     print(fopt)
     14     nda = NDA([fopt], reference_point=[10, 10])
---> 15     u = nda.hypervolume_improvement(y)
     16     return u

c:\Users\moham\anaconda3\lib\site-packages\moarchiving\moarchiving.py in hypervolume_improvement(self, f_pair)
    657         state = self._state()
    658         removed = self.discarded  # to get back previous state
--> 659         added = self.add(f_pair) is not None
    660         if added and self.discarded is not removed:
    661             add_back = self.discarded

c:\Users\moham\anaconda3\lib\site-packages\moarchiving\moarchiving.py in add(self, f_pair, info)
    182         assert idx == len(self) or not f_pair == self[idx]
    183         # here f_pair now is non-dominated
--> 184         self._add_at(idx, f_pair, info)
    185         # self.make_expensive_asserts and self._asserts()
    186         return idx

c:\Users\moham\anaconda3\lib\site-packages\moarchiving\moarchiving.py in _add_at(self, idx, f_pair, info)
    199             if self._infos is not None:  # if the list exists it needs to be updated
    200                 self._infos.insert(idx, info)  # also insert None, otherwise lists get out of sync
--> 201             self._add_HV(idx)
    202             # self.make_expensive_asserts and self._asserts()
    203             return

c:\Users\moham\anaconda3\lib\site-packages\moarchiving\moarchiving.py in _add_HV(self, idx)
    772         TODO: also update list of contributing hypervolumes in case.
    773         """
--> 774         dHV = self.contributing_hypervolume(idx)
    775         if self.maintain_contributing_hypervolumes:
    776             """Exerimental code:

c:\Users\moham\anaconda3\lib\site-packages\moarchiving\moarchiving.py in contributing_hypervolume(self, idx)
    566         print(f"{dHV=}")
    567 
--> 568         assert dHV >= 0
    569         return dHV
    570 

AssertionError: 

When computed outside the moarchiving module we get a positive value:

"""

Fc(x)=Fraction(10, 1)
Fc(self[idx][0])=Fraction(2860309831149143, 562949953421312)
Fc(y)=Fraction(4, 1)
Fc(self[idx][1])=Fraction(1972183889840329, 2251799813685248)

dHV=Fraction(-5064087602066653273, 5070602400912917605986812821504)
"""
Fc = NDA.hypervolume_computation_float_type

x=Fraction(10, 1)
sx=Fraction(2860309831149143, 562949953421312)
y=Fraction(4, 1)
sy=Fraction(1972183889840329, 2251799813685248)

dHV = (x-sx) * (y-sy)

print(dHV)
print(f'{float(x)=}\n{float(sx)=}\n{float(y)=}\n{float(sy)=}\n')

The ouput:

19481292109379782775473338716751/1267650600228229401496703205376
float(x)=10.0
float(sx)=5.080930931365556
float(y)=4.0
float(sy)=0.8758255853182146

[mgharafi]

The following shows that there is several variables that has numpy types which are limited.

type(self[idx][0])=<class 'numpy.float64'>
type(self[idx][1])=<class 'numpy.float64'>
type(x)=<class 'int'>
type(y)=<class 'numpy.intc'> # The bad type

They are also transferred to the Fraction object.

type((Fc(y) - Fc(self[idx][1])).numerator)=<class 'numpy.int64'>

And in my code that calls the moarchiving module I found several places where changing the types, solved the problem.

old code (not working)

xopt = np.array([1, *[0 for _ in range(len(x) - 1)]]) # This is an list of int
fopt = fitness(xopt) # Also a list of int

The bad type comes from the objective function values when x is a list of int

type(fopt[0])=<class 'numpy.intc'>
type(fopt[1])=<class 'numpy.intc'>

new code (working)

xopt = np.array([1., *[0. for _ in range(len(x) - 1)]]) # This is an list of floats
fopt = fitness(xopt) # Also a list of floats

[nikohansen]

Will be fixed in the upcoming v0.7.1.

[nikohansen]

see commit 8addc5f945bed32913c412584b30a804c1bee613