NSGA3 stops prematurly and yielding Nonetypes

[adelka-m]

Hi there,
thank you for your great library. I was hoping to get an explanation on the behavirour of NSGA3 algorithm. To me it seems to me as bug, because the algorithm stops soone but is not providing a suitable solution.

I am trying to solve my problem defined as

class MyProblem(ElementwiseProblem):
    def __init__(self, ..., number_of_objective_functions = 5, number_of_constraints = 4):
        self.number_of_objective_functions = number_of_objective_functions
        self.number_of_constraints         = number_of_constraints
        ...
        super().__init__(n_var   = lower_bounds.size,
                         n_obj   = self.number_of_objective_functions ,
                         n_constr= self.number_of_constraints,
                         xl      = lower_bounds, xu = upper_bounds)

    def _evaluate(self, x, out, *args, **kwargs):
        if some_condition:
            out["F"] = [1, 1, 1, 1, self.max_number_of_needles + 1]
            out["G"] = [1, 1, 1, 1]
            return
        ...
        out["F"] = [-f1, f2, -f3, -f4, -f5]
        out["G"] = [g1, g2, g3, g4]

I define the termination, algorithm

termination = MultiObjectiveSpaceToleranceTermination(tol = 0.025, n_last  = 10, n_max_gen   = 100, n_max_evals = None)
algorithm = NSGA3(ref_dirs = ref_directions, pop_size = 250, n_offsprings = 250, sampling = sampling, crossover  = crossover, mutation = mutation, eliminate_duplicates = True )

and then I run minimize function
res = minimize(problem, algorithm, termination, seed=1, return_least_infeasible=False, callback=callback, output = None, save_history=False, verbose=True)

The last output is

n_gen |  n_eval |   cv (min) |   cv (avg)   |  n_nds  |  eps  |  indicator  
============================================================
...
   57 |   14250 |  0.000175285 |  0.000659772 |       1 |  0.00000E+00 |            f
   58 |   14500 |  0.000131464 |  0.000566696 |       1 |  0.005363419 |        ideal
   59 |   14750 |  0.000131464 |  0.000521823 |       1 |  0.00000E+00 |            f
   60 |   15000 |  0.000131464 |  0.000485013 |       1 |  0.00000E+00 |            f

The algorithm stops already after 60 generations, but the res.F and X is a 'NoneType'.

Could anyone explain me the behavior?

Thank you very much!

[blankjul]

The algorithm terminates because no feasible solution could be found.

When you call the function as shown above you can set return_least_infeasible=True and you will instead of None get the least infeasible solution found.

[adelka-m]

Thanks for your answer. I think, I was using a wrong termination criterion. I would like to assure me of thwo more points though.

The constraint G values are only added to the F values, right? So in the end, also a non-feasible solutions can comply with the termination criterion and make the algorithm stop. Is that so?

So the MultiObjectiveSpaceToleranceTermination compares the optimization function values at nadir, ideal, f points, and if they are not changing from the nth to the n+1th generation too much, it stops. Do I understand it correctly?

(From pymoo.util.termination.f_tol)

    def _decide(self, metrics):
        delta_ideal = [e["delta_ideal"] for e in metrics]
        delta_nadir = [e["delta_nadir"] for e in metrics]
        delta_f = [e["delta_f"] for e in metrics]
        return max(max(delta_ideal), max(delta_nadir), max(delta_f)) > self.tol

[blankjul]

if you use the default termination multiple conditions are checked:

class DefaultMultiObjectiveTermination(DefaultTermination):

    def __init__(self, xtol=0.0005, cvtol=1e-8, ftol=0.005, n_skip=5, period=50, **kwargs) -> None:
        x = RobustTermination(DesignSpaceTermination(tol=xtol, n_skip=n_skip), period)
        cv = RobustTermination(ConstraintViolationTermination(cvtol, terminate_when_feasible=False, n_skip=n_skip), period)
        f = RobustTermination(MultiObjectiveSpaceTermination(ftol, only_feas=True, n_skip=n_skip), period)
        super().__init__(x, cv, f, **kwargs)

This is the copy from the implementation. The MultiObjectiveSpaceTermination is one of the criteria.

[adelka-m]

Hi @blankjul,
is there some readings on why ist makes sence to look at the delta_cv or delta_f and why is looks at decisions["x_tol"] and (decisions["cv_tol"] or decisions["f_tol"])? For me it is not clear, why should the evaluation stop if delta_cv.max() > self.tol and why does it take only the maximum value of cv?