What are most commons methods to measure improvement rate in a meta-heuristic?

Question

When I run a meta-heuristics, like a Genetic Algorithm or a Simulated Annealing, I want to have a termination criterion that stops the algorithms when there is not any significant fitness improvement.

What are good methods for that?

I tried something like

$$improvement=\frac{fit(Solution_{new})}{fit(Solution_{old})}$$

and

$$improvement={fit(Solution_{new})}-{fit(Solution_{old})}$$

Both options don't seem to be good, because as the old solutions get better and newer solutions even if they are good don't improve so much compare to the old.

Answer 1

You can use one of your suggested methods to calculate the relative improvement, but you need also to define a threshold value $\epsilon$ that determines when a relative improvement is negligible, and so you can terminate the algorithm. To be more concrete, you could terminate the genetic algorithm when, for example, the following condition is met

$$ |f(x_{t+1}) - f(x_{t})| < \epsilon, \tag{1}\label{1} $$

where

• $f$ is the fitness function
• $t$ is the iteration number of your iterative algorithm
• $x_t$ is a solution at iteration $t$
• $|\cdot|$ is the absolute value
• $\epsilon$ is the threshold value (a hyper-parameter of your algorithm), which is typically a small number (e.g. $10^{-6}$), but this also depends on the magnitude of the fitness of the solutions

This stopping criterion in \ref{1} (sometimes known as the absolute error) is not the only possible one. For example, you can stop the genetic algorithm when it has run for a certain maximum number of iterations. The stopping criterion (or criteria, i.e. you can use more than one stopping criteria) that you choose probably depends on what you want to achieve and this is not just specific to genetic algorithms, but, in general, this applies to any iterative numerical algorithm.

The MathWorks article How the Genetic Algorithm Works enumerates several stopping criteria for genetic algorithms.

If you want to know more about the topic, maybe take a look at this paper On Stopping Criteria for Genetic Algorithms (2004) by Martín Safe et al.