Answers.Body: <p>You can use one of your suggested methods to calculate the relative improvement, but you need also to define a threshold value <span class="math-container">$\epsilon$</span> 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</p>
  <p><span class="math-container">$$
  |f(x_{t+1}) - f(x_{t})| &lt; \epsilon, \tag{1}\label{1}
  $$</span></p>
  <p>where</p>
  <ul>
  <li><span class="math-container">$f$</span> is the fitness function</li>
  <li><span class="math-container">$t$</span> is the iteration number of your iterative algorithm</li>
  <li><span class="math-container">$x_t$</span> is a solution at iteration <span class="math-container">$t$</span></li>
  <li><span class="math-container">$|\cdot|$</span> is the absolute value</li>
  <li><span class="math-container">$\epsilon$</span> is the threshold value (a hyper-parameter of your algorithm), which is typically a small number (e.g. <span class="math-container">$10^{-6}$</span>), but this also depends on the magnitude of the fitness of the solutions</li>
  </ul>
  <p>This stopping criterion in \ref{1} (sometimes known as the <a href="https://mathworld.wolfram.com/AbsoluteError.html" rel="nofollow noreferrer"><em>absolute error</em></a>) 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.</p>
  <p>The MathWorks article <a href="https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html" rel="nofollow noreferrer">How the Genetic Algorithm Works</a> enumerates several stopping criteria for genetic algorithms.</p>
  <p>If you want to know more about the topic, maybe take a look at this paper <a href="https://www.researchgate.net/profile/Martin_Safe/publication/220974459_On_Stopping_Criteria_for_Genetic_Algorithms/links/5720cbef08aead26e7213007.pdf" rel="nofollow noreferrer">On Stopping Criteria for Genetic Algorithms</a> (2004) by Martín Safe et al.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-18T12:55:34.613Z
Answers.LastActivityDate: 2020-09-18T13:07:11.480Z
Answers.LastEditDate: 2020-09-18T13:07:11.480Z
Answers.UserDisplayName: nbro
Body: <p>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.</p>
  <p>What are good methods for that?</p>
  <p>I tried something like</p>
  <p><span class="math-container">$$improvement=\frac{fit(Solution_{new})}{fit(Solution_{old})}$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$improvement={fit(Solution_{new})}-{fit(Solution_{old})}$$</span></p>
  <p>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.</p>
  
Tags: <genetic-algorithms><simulated-annealing><meta-heuristics><stopping-conditions><numerical-algorithms>
Title: What are most commons methods to measure improvement rate in a meta-heuristic?
UserDisplayName: MScott
ThreadText: # What are most commons methods to measure improvement rate in a meta-heuristic?
  
  (Asked by: username_0 on 2020-09-17)
  
  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.
  
  **Tags:** genetic-algorithms, simulated-annealing, meta-heuristics, stopping-conditions, numerical-algorithms
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-09-18. Score: 2
  
  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*](https://mathworld.wolfram.com/AbsoluteError.html)) 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](https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html) 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](https://www.researchgate.net/profile/Martin_Safe/publication/220974459_On_Stopping_Criteria_for_Genetic_Algorithms/links/5720cbef08aead26e7213007.pdf) (2004) by Martín Safe et al.
  
  
  ---
  
  