pymoo
Latest Version: pymoo==0.4.1

Termination Criterion

Whenever an algorithm is executed it needs to be decided whether a next iteration should be started or not. For single-objective algorithms a naive implementation can consider the relative improvement in the last \(n\) generations.

Default Termination (‘default’)

We have added recently developed a termination criterion which is set if no termination is supplied to the minimize() method:

[1]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem
from pymoo.optimize import minimize

problem = get_problem("zdt1")
algorithm = NSGA2(pop_size=100)

res = minimize(problem,
               algorithm,
               pf=False,
               seed=2,
               verbose=False)

print(res.algorithm.n_gen)
145

This is allows you to terminated based on a couple of criteria also explained later on this page. Commonly used are the movement in the design space f_tol and the convergence in the constraint cv_tol and objective space f_tol. To provide an upper bound for the algorithm, we also recommend to supply a maximum number of generations n_max_gen or function evaluations n_max_evals.

Moreover, it is worth mentioning that the tolerance termination is based on a sliding window. Not only the last, but a sequence of the n_last generations are used to calculate compare the tolerances with an bound defined by the user.

By default for multi-objective problems the termination will be set to

[2]:
from pymoo.util.termination.default import MultiObjectiveDefaultTermination

termination = MultiObjectiveDefaultTermination(
    x_tol=1e-8,
    cv_tol=1e-6,
    f_tol=0.0025,
    nth_gen=5,
    n_last=30,
    n_max_gen=1000,
    n_max_evals=100000
)

And for single-optimization to

[3]:
from pymoo.util.termination.default import SingleObjectiveDefaultTermination

termination = SingleObjectiveDefaultTermination(
    x_tol=1e-8,
    cv_tol=1e-6,
    f_tol=1e-6,
    nth_gen=5,
    n_last=20,
    n_max_gen=1000,
    n_max_evals=100000
)

Number of Evaluations (‘n_eval’)

The termination can simply be reached by providing an upper bound for the number of function evaluations. Whenever, in an iteration the number of function evaluations is larger than this upper bound the algorithm terminates.

[4]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem, get_termination
from pymoo.optimize import minimize

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = get_termination("n_eval", 300)

res = minimize(problem,
               algorithm,
               termination,
               pf=problem.pareto_front(),
               seed=1,
               verbose=True)
============================================================
n_gen |  n_eval |     igd      |      gd      |      hv
============================================================
    1 |     100 |  2.083143534 |  2.470275711 |  0.00000E+00
    2 |     200 |  2.083143534 |  2.541455861 |  0.00000E+00
    3 |     300 |  1.439763149 |  2.254136798 |  0.00000E+00

Number of Generations (‘n_gen’)

Moreover, the number of generations / iterations can be limited as well.

[5]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem, get_termination
from pymoo.optimize import minimize

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = get_termination("n_gen", 10)

res = minimize(problem,
               algorithm,
               termination,
               pf=problem.pareto_front(),
               seed=1,
               verbose=True)
============================================================
n_gen |  n_eval |     igd      |      gd      |      hv
============================================================
    1 |     100 |  2.083143534 |  2.470275711 |  0.00000E+00
    2 |     200 |  2.083143534 |  2.541455861 |  0.00000E+00
    3 |     300 |  1.439763149 |  2.254136798 |  0.00000E+00
    4 |     400 |  1.322049373 |  2.211177241 |  0.00000E+00
    5 |     500 |  1.322049373 |  2.049932619 |  0.00000E+00
    6 |     600 |  1.322049373 |  2.252465552 |  0.00000E+00
    7 |     700 |  1.174569841 |  2.093527386 |  0.00000E+00
    8 |     800 |  1.174569841 |  1.930483702 |  0.00000E+00
    9 |     900 |  1.023102225 |  1.607960322 |  0.003340339
   10 |    1000 |  0.980982415 |  1.352084952 |  0.003340339

Based on Time (‘time’)

The termination can be also based on the time of the algorithm to be executed. For instance, to run an algorithm for 3 seconds the termination can be defined by get_termination("time", "00:00:03") or for 1 hour and 30 minutes by get_termination("time", "01:30:00").

[6]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem, get_termination
from pymoo.optimize import minimize

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = get_termination("time", "00:00:03")

res = minimize(problem,
               algorithm,
               termination,
               pf=problem.pareto_front(),
               seed=1,
               verbose=False)

print(res.algorithm.n_gen)

467

Design Space Tolerance (‘x_tol’)

Also, we can track the change in the design space. For a parameter explanation please have a look at ‘ftol’.

[7]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem
from pymoo.optimize import minimize
from pymoo.util.termination.x_tol import DesignSpaceToleranceTermination

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = DesignSpaceToleranceTermination(tol=0.0025, n_last=20)

res = minimize(problem,
               algorithm,
               termination,
               pf=problem.pareto_front(),
               seed=1,
               verbose=False)

print(res.algorithm.n_gen)

167

Objective Space Tolerance (‘f_tol’)

Probably the most interesting stopping criterion is to use the objective space change to make decision whether to continue or not. Here, we mostly use a naive and efficient procedure to determine whether to stop or not. We aim to improve it further in the future. If somebody in interested in collaborating please let us know.

The parameters of our implementation are:

tol: What is the tolerance in the objective space in average. If the value is below this bound we terminate.

n_last: To make the criterion more robust, we consider the last \(n\) generations and take the maximum. This considers the worst case in a window.

n_max_gen: As a fallback the generation number can be used. For some problems the termination criterion might not be reached, however, an upper bound for generations can be defined to stop in that case.

nth_gen: Defines whenever the termination criterion is calculated. By default, every 10th generation.

[8]:
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_problem
from pymoo.optimize import minimize
from pymoo.util.termination.f_tol import MultiObjectiveSpaceToleranceTermination
from pymoo.visualization.scatter import Scatter

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = MultiObjectiveSpaceToleranceTermination(tol=0.0025,
                                                      n_last=30,
                                                      nth_gen=5,
                                                      n_max_gen=None,
                                                      n_max_evals=None)

res = minimize(problem,
               algorithm,
               termination,
               pf=True,
               seed=1,
               verbose=False)

print("Generations", res.algorithm.n_gen)
plot = Scatter(title="ZDT3")
plot.add(problem.pareto_front(use_cache=False, flatten=False), plot_type="line", color="black")
plot.add(res.F, color="red", alpha=0.8, s=20)
plot.show()

Generations 165
../_images/interface_termination_29_1.png