Terminating evolutionary algorithms at their steady state

Abstract

Assessing the reliability of termination conditions for evolutionary algorithms (EAs) is of prime importance. An erroneous or weak stop criterion can negatively affect both the computational effort and the final result. We introduce a statistical framework for assessing whether a termination condition is able to stop an EA at its steady state, so that its results can not be improved anymore. We use a regression model in order to determine the requirements ensuring that a measure derived from EA evolving population is related to the distance to the optimum in decision variable space. Our framework is analyzed across 24 benchmark test functions and two standard termination criteria based on function fitness value in objective function space and EA population decision variable space distribution for the differential evolution (DE) paradigm. Results validate our framework as a powerful tool for determining the capability of a measure for terminating EA and the results also identify the decision variable space distribution as the best-suited for accurately terminating DE in real-world applications.

Appendix

1.1 Proof of Proposition 1

Proof

The Cauchy-condition given by Definition 1 is satisfied if $\forall \epsilon$, $\exists k_0$ such that $\forall k_1,k_2 \le k_0$, we have that:

$$\begin{aligned} |Q_{k_1}-Q_{k_2}| < \epsilon \Rightarrow |Ref_{k_1}-Ref_{k_2}| < \epsilon \end{aligned}$$

By the regression model (4), we have that:

$$\begin{aligned} |Ref_{k_1}-Ref_{k_2}| =e^{\beta _0} |(Q_{k}^{\beta _1} e^{\varepsilon _{k_1}}-Q_{k_2}^{\beta _1} e^{\varepsilon _{k_2}})| \end{aligned}$$

for $\varepsilon _{k_1}$, $\varepsilon _{k_2}$ following a gaussian distribution $N(0,\sigma ^2)$. Given that $99.7\,\%$ of the values of a gaussian are in the interval given by three standard deviations, $[-3 \sigma , 3 \sigma ]$, we have that:

$$\begin{aligned}&|Ref_{k_1}-Ref_{k_2}| \le e^{\beta _0} |Q_{k_1}^{\beta _1} e^{3 \sigma }-Q_{k_2}^{\beta _1} e^{-3 \sigma }|\nonumber \\&\quad =e^{\beta _0} |Q_{k_1}^{\beta _1} e^{3 \sigma }-Q_{k_1}^{\beta _1} e^{-3 \sigma }+Q_{k_1}^{\beta _1} e^{-3 \sigma }-Q_{k_2}^{\beta _1} e^{-3 \sigma }|\nonumber \\&\quad \le e^{\beta _0} (Q_{k_1}^{\beta _1} |e^{3 \sigma }- e^{-3 \sigma }|+ e^{-3 \sigma } |Q_{k_1}^{\beta _1}-Q_{k_2}^{\beta _1}|) \nonumber \\&\quad = e^{\beta _0}(T_1+T_2) \end{aligned}$$

(16)

Since EA has converged to the minimum, $Ref_k \rightarrow 0$ and, by the linear regression, also $Q_k \rightarrow 0$. If $\beta _1>0$, then $Q_{k_1}^{\beta _1}$ is also convergent to zero. Therefore, $T_1$ and $T_2$ are bounded by:

$$\begin{aligned}&T_1 \le \epsilon |e^{3 \sigma }- e^{-3 \sigma }| \\&T_2 \le \epsilon e^{-3 \sigma } \end{aligned}$$

for $k_1$, $k_2$ large enough. Substituting in (16) and taking into account that $e^{3 \sigma }- e^{-3 \sigma }>0$, we have that:

$$\begin{aligned} |Ref_{k_1}-Ref_{k_2}| \le \epsilon e^{\beta _0} e^{3 \sigma } \end{aligned}$$

Therefore $|Ref_{k_1}-Ref_{k_2}| \le \epsilon$ holds provided that:

$$\begin{aligned} \epsilon e^{\beta _0} e^{3 \sigma } \le \epsilon \end{aligned}$$

Finally, taking logarithms we have that:

$$\begin{aligned} \beta _0 + 3 \sigma \le 0 \end{aligned}$$

The relation between $\varepsilon$ and the model accuracy ($\sigma$) proves the Proposition. $\square$

We would like to note that Proposition 1 is proven using a set of inequalities $\le$ which achieve strict values for some cases and, thus, it is a sufficient but not necessary condition. This means that any measure satisfying the inequality is Cauchy, but implies by no means that all Cauchy measures should fulfill it. In this context, Proposition 1 is a way of verifying that a measure is Cauchy rather than a means of discarding non-Cauchy measures.