Average convergence rate estimation of clonal selection algorithm

Abstract

Considering that average convergence rate estimation of clonal selection algorithms is a difficult problem and is still in its infancy, this article researches the convergence rate of an elitist clonal selection algorithm. It derives the best individual transition probability matrix from the directional transition probability of best individuals in algorithm populations and constructs matrix norms that meet certain requirements to resolve difficulties in calculating the matrix caused by large algorithm populations in practical applications, thereby proposing a simple and effective method of estimating average convergence rate of the algorithm. In addition, simulation experiments are performed to validate universality and validity of the estimation method.

Introduction

Artificial immune algorithm is an intelligent algorithm that is inspired by biological immune mechanisms and utilized to solve complex issues. As an important branch of artificial immune algorithm, clonal selection algorithm has received increasing attention by domestic and international scholars and experts in computational intelligence.^1,2 Although scholars have made fruitful achievements in studying clonal selection algorithms in recent years, the studies focus on algorithm implementation, improvement, and engineering application, and the theoretical analyses concentrate on algorithm convergence. Convergence rate, which is an important part of theoretical researches on clonal selection algorithms, not only illustrates the algorithm convergence but also plays an important role in establishing proper stropping criteria and measurement standards to comprehensively and objectively evaluate execution strategies. ³ The convergence rate is influenced by the selection of parameters and the characteristics of objective functions. Due to the lack of effective analytical methods, however, there are few reports on convergence rate of clonal selection algorithms and no strict theoretical conclusions. Moreover, such mathematics-based shortage restricts further expansion, development, and application of clonal selection algorithms. ⁴

Currently, researches on the convergence rate of clonal selection algorithms are still in their infancy. ⁵ The existing researches mostly base on the Markov Chain theory and estimate the convergence rate by studying characteristic values of state transition matrices: ⁶ (1) this method obtains approximate convergence rate by estimating the maximum eigenvalue that is smaller than 1 in the state transition matrix while reasonable estimate of the characteristic value needs to be further discussed and (2) since antibody populations in the steady-state distribution are made up of satisfactory solutions, the method is too conservative. In practical applications, not all antibodies are required to achieve optimal solutions. It is acceptable as long as one or one kind of antibodies achieve optimal solutions. Timmis et al. ⁷ show a convergence rate estimation method based on Markov Chain models. Since some parameters need to be further discussed, the method is unsuitable for practical applications. What’s more, these methods achieve qualitative research results and merely apply to specific forms of clonal selection algorithms, thereby failing to estimate the convergence rate of ordinary clonal selection algorithms. ⁸

The elitist strategy is a basic condition to ensure algorithm convergence. Therefore, this article draws lessons from convergence rate analysis in genetic algorithms, employs relevant knowledge of stochastic processes, proceeds from the best individual transition probability matrix, and constructs the best individual transition probability matrix to matrix norms that meet certain requirements, thereby proposing a simpler and more effective method of estimating average convergence rate of elitist clonal selection algorithms. In addition, simulation experiments are performed on different elitist strategies to validate universality and validity of the estimation method.

Elitist clonal selection algorithms

Clonal selection is one of the most famous biological immunological mechanisms. ⁹ Clonal selection algorithm, which is based on clonal selection, takes unknown objective functions as the antigens and possible optimal solutions as the antibodies. In this case, the affinity between antibodies and antigens represents feasible solutions to the function values. Only cells able to recognize antigens will divide, proliferate, and be selected. Moreover, the selected cells are restricted by affinity maturation. Due to the intrinsic characteristics, clonal selection algorithms have enormous potential for solving optimization problems. It is predictable that clonal selection algorithms will be widely used in the optimization field in the future. Wherein, CLONALG proposed by De Castro and Von Zuben ¹⁰ in 2002 is one of the most representative clonal selection algorithms in recent years since it marks the beginning of optimization resolution on the basis of intelligent algorithms. After that, researchers have drawn lessons from clonal selection from multiple perspectives and proposed different clonal selection algorithms. Moreover, most of these algorithms are based on elitist strategy.^11–14 In order to illustrate the problems conveniently, the article demonstrates basic procedures and flowchart graphs of elitist clonal selection algorithm:

• Step 1. Initialization: let $i=0$ and randomly generate an initial set of antibodies— $\overrightarrow{X}(0)=\{X_1,X_2,\dots ,X_N\}$ (the $N$ antibodies are in a binary code with length $L$ );

• Step 2. Affinity calculation: calculate the affinity of all antibodies in $\overrightarrow{X}(i)$ ;

• Step 3. Elite preservation: select individuals with the highest affinity in $\overrightarrow{X}(i)$ ;

• Step 4. Affinity maturation: perform clone operations and mutation operations on the $N-1$ antibodies in $\overrightarrow{X}(i)$ , thereby generating a new set of antibodies— $\overrightarrow{X}(i+1)$ ;

• Step 5. Immunization update: generate d antibodies to substitute d individuals with the lowest affinity in $\overrightarrow{X}(i+1)$ ;

• Step 6. $i=i+1$ . Repeat the above steps (Step 2–6) till the termination condition is met.

The basic flowchart graph of the algorithm is shown in Figure 1.

Figure 1.

A flowchart graph of elitist clonal selection algorithms.

Convergence rate analysis

When the number of iterations approaches to the infinity, global convergence of such clonal selection algorithms has been proved. In addition, global optimal solutions are included in the steady-state distribution. ¹⁵ The above analysis shows that changes of the best antibodies reflect the convergence rate accurately. Therefore, it is possible to estimate the convergence rate of elitist clonal selection algorithms by virtue of the best individual transition probability matrix.

For simplicity, it is assumed that there is only one optimal solution; $\overrightarrow{X}=\{X_1,X_2,\dots ,X_N\}\in S^N$ ( $S^N$ is the state space of antibodies; $X_i$ is composed of $L$ binary codes), the best individual $X^{*}=\{X_i|\forall j\ne i,f(X_i)\ge f(X_j)\}$ $(i,j=1,2,\dots ,N)$ , the transition probability matrix is $\mathbf{Q}$ , and the number of dimensions is $2^L$ . These states are coded in order from highest to lowest affinity.

In order to calculate the best individual transition matrix $\mathbf{Q}$ , $2^L$ groups are extracted. Let the best individual of the $k\mathrm{th}$ group $(1\le k\le 2^L)$ be $t$ and expressed by $G_{\iota }$ then

$$G_{\iota }=\{\overrightarrow{X}|(\overrightarrow{X}\in S^N)\cap (X^{*}=\iota )\}$$

(1)

For any two states, $1\le x,y\le 2^L$ . The probability of transiting from state x to state y is

$$q_{\mathrm{xy}}=\{\begin{array}{c}\begin{array}{cc}0\hfill & \begin{array}{ccc}\begin{array}{ccc}\hfill & \hfill & \hfill \end{array}\hfill & \hfill & x<y\hfill \end{array}\hfill \end{array}\hfill \\ \multicolumn{1}{c}{\sum _{x\in G_i}\sum _{y\in G_j}{p}_{\mathrm{ij}}>0\begin{array}{c}x\ge y\hfill \end{array}}\end{array}$$

(2)

Obviously, the best individual transition probability matrix is as follows

$$\mathbf{Q}=\left(q_{\mathrm{xy}}\right)=\left[\begin{array}{cccc}1\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{q_{21}}& q_{22}\hfill & \cdots \hfill & 0\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{q_{k1}}& q_{k2}\hfill & \cdots \hfill & q_{\mathrm{kk}}\hfill \end{array}\right]$$

(3)

Let the sub-matrix constituted by elements of the state transition matrix $\mathbf{Q}$ at non-recurrent state be ${\mathbf{Q}}^{\prime }$ , then

$${\mathbf{Q}}^{\prime }=\left[\begin{array}{cccc}{q}_{22}\hfill & 0\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{q_{32}}& q_{32}\hfill & \cdots \hfill & 0\hfill \\ \multicolumn{1}{c}{⋮}& ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{q_{k2}}& q_{k3}\hfill & \cdots \hfill & q_{\mathrm{kk}}\hfill \end{array}\right]$$

The state transition matrix of clonal selection algorithms is a random matrix (a homogeneous Markov chain) and the matrix $\mathbf{Q}$ is a constant random matrix. According to Formula (3), all the elements, except q₁₁ (q₁₁ = 1), are smaller than 1. Therefore, state transition of the best individuals also constitutes a limited and homogeneous Markov chain and state 1 is the only absorption state of the Markov chain.

On this basis, Theorem 1 and Lemma 1 are given.

Lemma 1

Let $T$ be the set of non-recurrent states and ${\mu }_x$ be the average steps of the Markov chain to transit from non-absorbing state $(x\in T)$ to absorption state. ¹⁶ Then

$${\mu }_x=1+\sum _{y=2}^k{q}_{\mathrm{xy}}{\mu }_y$$

(4)

Theorem 1

Let $\mathbf{Z}=(\mathbf{I}-{\mathbf{Q}}^{\prime }{)}^{-1}$ when the best individuals obey uniform distribution, then the average convergence algebra is

$$\mathrm{H}=\frac{1}{k}\sum _{x=1}^{k-1}\sum _{y=1}^{k-1}{z}_{\mathrm{xy}}=\frac{1}{k}\Psi \left(\mathbf{Z}\right)$$

In the formula, $\Psi (\mathbf{Z})=\sum _{x=1}^{k-1}\sum _{y=1}^{k-1}{z}_{\mathrm{xy}}$ is the sum of all elements of the matrix $\mathbf{Z}$ ; $\mathbf{I}$ is the identity matrix.

Proof

The non-recurrent matrix ${\mathbf{Q}}^{\prime }$ has finite non-recurrent states. Equation (4) can be expressed as matrix forms

$$\mathbf{M}=\mathbf{I}+{\mathbf{Q}}^{\prime }\mathbf{M}$$

In the formula, $\mathbf{M}=[{\mu }_2,{\mu }_3,\dots ,{\mu }_k{]}^T$ ; $\mathbf{I}=[1,1,\dots ,1{]}^T$ . To solve the equation

$$\mathbf{M}={(\mathbf{I}-{\mathbf{Q}}^{\prime })}^{-1}\mathbf{I}=\mathbf{ZI}$$

For any non-absorbing state $(x\in T)$

$${\mu }_x=\sum _{y=1}^{k-1}{z}_{\mathrm{xy}}$$

Since best individuals of the initial populations obey uniform distribution, then

$$P(X_0=x,x=1,2,\dots ,k)=\frac{1}{k}$$

Let ${\mu }_1$ be the average transition number from non-absorption state 1 to absorption state 1. Obviously, ${\mu }_1=0$ . Therefore, the average convergence number is

$$\begin{array}{l}\mathrm{H}={\displaystyle \sum _{x=1}^{k}P\left(X_0=x\right)}{\mu }_x={\displaystyle \sum _{x=1}^k\frac{1}{k}}{\mu }_x\\ =\frac{1}{k}{\displaystyle \sum _{x=1}^{k-1}{\displaystyle \sum _{y=1}^{k-1}{z}_{xy}}}=\frac{1}{k}\Psi \left(Z\right)\end{array}$$

(5)

Justified

Antibodies have multiple states in practical applications, not to mention the populations constituted by antibodies, which makes it difficult to calculate Matrix $\mathbf{P}$ , Matrix $\mathbf{Q}$ and Matrix $\mathbf{Z}=(\mathbf{I}-{\mathbf{Q}}^{\prime }{)}^{-1}$ . Therefore, the following theorems are introduced to simplify the estimation of average convergence number.

Lemma 2

Let $\mathbf{A}\in C^{n\times n}$ and $\Vert \mathbf{A}{\Vert }_a$ be the matrix norm of the vector norm $\Vert \mathbf{x}{\Vert }_a$ . ¹⁷ If $\Vert \mathbf{A}{\Vert }_a<1$ , then

1. The matrices $\mathbf{I}-\mathbf{A}$ is invertible;

2. $\Vert {(\mathbf{I}-\mathbf{A})}^{-1}{\Vert }_a\le \frac{{\Vert \mathbf{I}\Vert }_a}{1-{\Vert \mathbf{A}\Vert }_a}$ .

It is possible to estimate the average convergence number as long as the best individual transition probability matrix $\mathbf{Q}$ is constructed to matrix norms $\Vert {\mathbf{Q}}^{\prime }{\Vert }_a$ that meet certain requirements.

Considering the general measurable function, let the code length be $L$ , the Hamming distance between individuals be $M$ , the multiples be $c$ , and the mutation rate be $p_m$ . $\Vert {\mathbf{Q}}^{\prime }{\Vert }_{\infty }=\underset{1\le i\le k-1}{max}\sum _{j=1}^{k-1}{q}_{\mathrm{ij}}^{\prime }$ . Since $\mathbf{Q}$ is a random matrix, the sum of the various elements is 1, then

$$\Vert {\mathbf{Q}}^{\prime }{\Vert }_{\infty }=\underset{1\le i\le k-1}{max}\sum _{j=1}^{k-1}{q}_{\mathrm{ij}}^{\prime }=1-\underset{1\le i\le k-1}{min}{q}_{i1}$$

(6)

For general measurable functions, when the Hamming distance between the best individuals of the initial populations and the global optimal individuals is $l$ and $0<l\le L$ , the best individuals are the least likely to transit to global optimal individuals

$$p=1-{(1-p_m^l)}^c\approx {\mathrm{cp}}_m^l$$

Let the average transition probability of other individuals be $p_{\Sigma }$ , then the transition probability of the whole populations is $q_{i1}=1-(1-{\mathrm{cp}}_m^l)(1-p_{\Sigma })>{\mathrm{cp}}_m^l$ . Therefore

$$\Vert {\mathbf{Q}}^{\prime }{\Vert }_{\infty }=1-\underset{1\le i\le k-1}{min}{q}_{i1}<1-{\mathrm{cp}}_m^l$$

According to Lemma 2

$$\begin{array}{l}{\Vert Z\Vert }_{\infty }={\Vert {\left(\mathrm{I}-Q^{\prime }\right)}^{-1}\Vert }_{\infty }\\ =\max {\displaystyle \sum _{j=1}^{k-1}{z}_{ij}}<\frac{{\Vert I\Vert }_{\infty }}{1-{\Vert Q^{\prime }\Vert }_{\infty }}<\frac{1}{1-\left(1-c{p}_m^l\right)}=\frac{1}{c{p}_m^l}\end{array}$$

According to Theorem 1, the average convergence number of elitist clonal selection algorithms is

$$\begin{array}{l}H=\frac{1}{k}{\displaystyle \sum _{x=1}^{k-1}{\displaystyle \sum _{y=1}^{k-1}{z}_{xy}}}<\frac{1}{2^L}{\displaystyle \sum _{x=1}^{2^L-1}\max {\displaystyle \sum _{y=1}^{2_L-1}{z}_{xy}}}\\ <\frac{2^L-1}{2^L}\frac{1}{c{p}_m^l}=\frac{1-2^{-L}}{c{p}_m^l}\end{array}$$

(7)

In the formula, $0<l\le L$ . The upper limit of average convergence rate of elitist clonal selection algorithms depends on the cloning multiples c, the mutation rate $p_m$ , and the Hamming distance $l$ between the best individuals of the initial populations and global optimal individuals. The results give specific mathematical expressions of the average convergence number, which is more practical than Formula (5).

Simulation experiment

In order to validate the universality and validity of the estimation method proposed, immune memory clonal selection algorithms (IMCSA), real clonal selection algorithms (RCSA), and clonal selection algorithm for classification (CCSA) are employed to perform simulation experiments on the following two multi-modal functions:

1. Test $f_1$

$$\begin{array}{l}f\left(x_1,x_2\right)={\displaystyle \sum _{i=1}^{5}i\cos \left[\left(i+1\right)x_1+i\right]}\\ \times {\displaystyle \sum _{j=1}^{5}j\cos \left[\left(j+1\right)x_2+j\right]}\end{array}$$

In the formula, $-10<x_1,x_2<10$ . The function has a total of 760 local minima and 18 global minimum points, with the optimal value $f^{*}=-176.542$ .

• 2. Test $f_2$

$$\begin{array}{l}f\left(x\right)={\sin }^2\left(\pi y_1\right)\\ +{\displaystyle \sum _{i=1}^{n-1}{\left(y_i-1\right)}^2}\left[1+10{\sin }^2\left(\pi y_{i+1}\right)\right]+{\left(y_n-1\right)}^2\end{array}$$

In the formula, $y_i=1+((x_i-1)/4)$ , $-10\le x_i\le 10$ , $i=1,2,...,n$ . When $n=3$ and $x^{*}=(1,1,1{)}^T$ , the function obtains the minimum value $(f^{*}=0)$ and has about 125 local minima. For details on the parameter settings, see Luo and Wei, ¹² Zhang et al., ¹⁸ and Zhang. ¹⁹ Wherein, the main parameters of convergence rate estimation are shown in Table 1. Each test function is executed 10 times and the experimental results are shown in Table 2.

Table 1.

Parameter settings of the three algorithms.

Algorithm	$f$	$L$	$l$	$c$	$p_m$
IMCSA	$f_1$	10	5	10	0.1
	$f_2$	15	7	20	0.2
RCSA	$f_1$	10	5	10	0.2
	$f_2$	15	6	20	0.1
CCSA	$f_1$	10	5	10	0.1
	$f_2$	15	8	20	0.2

IMCSA: immune memory clonal selection algorithms; RCSA: real clonal selection algorithms; CCSA: clonal selection algorithm for classification.

Table 2.

Experimental results of the three algorithms.

Algorithm	$f$	Convergence iterations										$H$
IMCSA	$f_1$	2.3 + e3	1.6 + e3	7.3 + e2	5.2 + e3	4.3 + e2	6.4 + e2	3.3 + e3	8.4 + e2	6.7 + e3	1.6 + e3	1.0 + e4
	$f_2$	4.3 + e2	5.1 + e2	1.6 + e3	3.3 + e2	7.4 + e2	9.4 + e1	6.8 + e2	1.3 + e3	7.5 + e2	4.8 + e2	3.9 + e3
RCSA	$f_1$	8.8 + e1	5.3 + e2	8.5 + e2	6.1 + e2	1.9 + e2	9.6 + e1	3.3 + e2	6.7 + e2	1.6 + e1	6.3 + e2	1.6 + e3
	$f_2$	7.1 + e3	1.3 + e4	2.3 + e3	5.5 + e3	1.9 + e3	6.2 + e2	5.3 + e3	1.2 + e2	7.3 + e3	4.5 + e4	5.0 + e4
CCSA	$f_1$	8.2 + e3	6.4 + e2	5.5 + e3	7.2 + e3	1.9 + e3	4.2 + e3	8.6 + e2	2.3 + e3	6.8 + e2	7.3 + e3	1.0 + e4
	$f_2$	2.6 + e2	4.9 + e3	1.8 + e3	8.3 + e2	7.2 + e3	6.2 + e3	8.6 + e2	3.6 + e3	5.3 + e3	1.2 + e4	2.0 + e4

IMCSA: immune memory clonal selection algorithms; RCSA: real clonal selection algorithms; CCSA: clonal selection algorithm for classification.

In Table 2, $H$ represents the theoretical upper limit of the average convergence rate. According to Table 2, the convergence rate of the three algorithms is always lower than the theoretical value, which validates universality and validity of the estimation method proposed. The closer the best antibodies in initial populations are to global optimal antibodies (the smaller $l$ is), the more quickly the convergence rate will increase, which is manifested in Formula (7). Therefore, it is advised to generate high-quality initial populations on the basis of given information about optimal solutions, thereby greatly improving the convergence rate.

Conclusion

This article introduces the best individual transition probability matrix to research average convergence rate of elitist clonal selection algorithms. Considering that the large algorithm population size in practical applications may cause difficulties in calculating the best individual transition probability matrix, the article constructs the best individual transition probability matrix into matrix norms that meet certain requirements, thereby proposing a new method of estimating average convergence rate of clonal selection algorithms. In addition, simulation experiments are performed to validate universality and validity of the estimation method. It is important to note that Formula (7) is targeted at ordinary measurable functions and $\Vert •{\Vert }_{\infty }$ This article merely considers the transition of global optimal individuals. Therefore, further studies are needed to research how to better transfer to adjacent individuals and how to construct a proper matrix norm.