On the genetic algorithm with adaptive mutation rate and selected statistical applications

Abstract

We give sufficient conditions which the mutation rate must satisfy for the convergence of the genetic algorithm when that rate is allowed to change throughout iterations. The empirical performance of the algorithm with regards to changes in the mutation parameter is explored via test functions, ARIMA model selection and maximum likelihood estimation illustrating the advantages of letting the mutation rate decrease from rather unusual high values to the commonly used low ones.

Appendix: Results from the literature

The definitions and results below are used in Sect. 2.

Throughout this paper we have adopted the $\infty$-norm $\Vert a \Vert = \max _{i \in E} a(i)$ with induced matrix norm $\Vert A \Vert = \max _i\sum _j A(i,j)$.

Definition 1

A nonhomogeneous Markov chain $\{P_t\}_{t\in \mathbb {N}}$ is said to be weakly ergodic if it satisfies

$$\begin{aligned} \lim _{k\rightarrow \infty } \Vert \mu _0P^{(t,k)}-\mu _1P^{(t,k)} \Vert = 0, \quad \forall t\ge 0, \end{aligned}$$

(12)

where $\mu _0$ and $\mu _1$ are any two finite probability distributions and the $k$-step transition from $t$ is given by the product of the transition matrices, $P^{(t,k)} = P_t P_{t+1}\ldots P_{t+k-1}$ (Markov property).

Strong ergodicity is characterized by the existence of a (row-constant) limit transition matrix $P_{\infty }$ such that $\lim _{k\rightarrow \infty } \Vert P^{(t,k)}-P_{\infty } \Vert =0$ $\forall t\ge 0$ but it will not be used here. We just note that Campos and Pereira (2012) show that weak ergodicity along with $\lim _{t\rightarrow \infty } \Vert P_t - P_{\infty } \Vert =0$ yield strong ergodicity.

Definition 2

Given a stochastic matrix $Q= \left[ q_{ij}\right] _{i,j\in E}$, the Dobrushin ergodic coefficient is defined by

$$\begin{aligned} \alpha (Q)=1-\sup _{i,k \in E}\sum _{j \in E} \left( q_{ij}-q_{kj}\right) ^{+} \quad \text{ with } \quad \left( q_{ij}-q_{kj}\right) ^{+}= \max \left\{ 0,q_{ij}-q_{kj}\right\} , \end{aligned}$$

and $\delta (Q)=1-\alpha (Q)$ is called the $delta$-coefficient. Note that (12) is equivalent to $\lim _{k\rightarrow \infty } \alpha (P^{(t,k)}) = 1$ or $\lim _{k\rightarrow \infty } \delta (P^{(t,k)})=0,\,\forall t\ge 0.$

We summarize Theorems 1, 2 and Corollary 3 from Rojas Cruz and Pereira (2013) in the following lemma.

Lemma 1

Let $\{X_t\}_{t \in \mathbb {N}}$ be the Markov chain which models the elitist NGA with stationary selection and crossover operators but time-dependent mutation rate $p_m^{(t)}$. Denote the transition matrices by $P_t= SCM _t$. Let $E^*$ be a subset of the state space containing an optimizer in it. Suppose that $0 < p_m^{(t)} < 1$ and that there exists a strictly positive sequence $\{\xi _t\}$ such that

$$\begin{aligned} \inf _{i\in E}P_t(i,j)\ge \xi _t,\; \forall j\in E \end{aligned}$$

and also

$$\begin{aligned} \sum _{t \ge 1}\xi _t=\infty . \end{aligned}$$

Then,

$$\begin{aligned} P\left( \lim _{t\rightarrow \infty }X_t\in E^*\right) =1. \end{aligned}$$

(13)

The next lemma is taken from Rojas Cruz (1998).

Lemma 2

Let $\{P_t\}_{t\in \mathbb {N}}$ be a nonhomogeneous Markov chain. If

$$\begin{aligned} \sum _{n=1}^{\infty } \Vert P_{t+1}-P_t \Vert < \infty \end{aligned}$$

then there exists a stochastic matrix $P_{\infty }$ such that

$$\begin{aligned} \lim _{n\rightarrow \infty } \Vert P_t - P_{\infty } \Vert =0. \end{aligned}$$

The next lemma bundles some results taken from the textbook of Isaacson and Madsen (1976).

Lemma 3

Let $P$, $Q$ and $R$ be transition matrices. Then,

$$\begin{aligned}&\Vert P(Q-R)\Vert \le \Vert Q-R \Vert ,\end{aligned}$$

(14)

$$\begin{aligned}&\Vert (P-Q)R \Vert \le \Vert P-Q \Vert \delta (R) \le \Vert P- Q \Vert ,\end{aligned}$$

(15)

$$\begin{aligned}&\vert \delta (P) - \delta (Q) \vert \le \Vert P-Q \Vert . \end{aligned}$$

(16)