pymoo
Latest Version: pymoo==0.3.2

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.

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.

[1]:
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.0831435338 | 3.1025851756 | 0.0000000000
2     | 200     | 2.0831435338 | 2.7762579284 | 0.0000000000
3     | 300     | 1.4397631492 | 2.6202677161 | 0.0000000000

Number of Generations (‘n_gen’)

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

[2]:
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.0831435338 | 3.1025851756 | 0.0000000000
2     | 200     | 2.0831435338 | 2.7762579284 | 0.0000000000
3     | 300     | 1.4397631492 | 2.6202677161 | 0.0000000000
4     | 400     | 1.4397631492 | 2.5084234772 | 0.0000000000
5     | 500     | 1.3868587086 | 2.2914029594 | 0.0000000000
6     | 600     | 1.2823153200 | 2.1250941821 | 0.0000000000
7     | 700     | 1.1733227807 | 2.0375213076 | 0.0000000000
8     | 800     | 1.0649222876 | 1.8189030621 | 0.0000000000
9     | 900     | 0.8197972200 | 1.6041517113 | 0.0025056832
10    | 1000    | 0.7952518411 | 1.5300429731 | 0.0028316497

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’.

[3]:
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("x_tol", tol=0.001, n_last=20, n_max_gen=None, nth_gen=10)

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

print(res.algorithm.n_gen)

130

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.

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

problem = get_problem("zdt3")
algorithm = NSGA2(pop_size=100)
termination = get_termination("f_tol", tol=0.001, n_last=20, n_max_gen=1000, nth_gen=10)

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

print(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()

90
../_images/misc_termination_criterion_17_1.png