# Convergence Analysis of a Class of Computational Intelligence Approaches

Authors: Junfeng Chen; Jianjun Ni; Mingang Hua
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Computational intelligence approaches is a relatively new interdisciplinary field of research with many promising application areas. Although the computational intelligence approaches have gained huge popularity, it is difficult to analyze the convergence. In this paper, a computational model is built up for a class of computational intelligence approaches represented by the canonical forms of generic algorithms, ant colony optimization, and particle swarm optimization in order to describe the common features of these algorithms. And then, two quantification indices, that is, the variation rate and the progress rate, are defined, respectively, to indicate the variety and the optimality of the solution sets generated in the search process of the model. Moreover, we give four types of probabilistic convergence for the solution set updating sequences, and their relations are discussed. Finally, the sufficient conditions are derived for the almost sure weak convergence and the almost sure strong convergence of the model by introducing the martingale theory into the Markov chain analysis.


---

## Body

## 1. Introduction

Computational intelligence approaches (CIAs) are a set of nature-inspired computational methodologies to interpret and construct the processes of optimization problems solving from different biological points of view, based on which a large number of derived approaches have been developed [1]. An example of particularly successful research direction in CIAs is genetic algorithm (GA) [2] which generates solutions to optimization problems using techniques inspired by natural evolution, such as selection, crossover, and mutation. Differential evolution (DE) [3, 4], proposed by Storn and Price, is similar to GA in the sense that it uses same evolutionary operators like mutation, crossover, and selection for guiding the population towards the optimum solution. Ant colony optimization (ACO) [5] is another very popular CIA, which was initially proposed by Marco Dorigo in his Ph.D. thesis. The first ACO was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food. The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants. Particle swarm optimization (PSO) [6], introduced in 1995, was intended for simulating birds flocking or fishes schooling. PSO optimizes a problem by having a population of particles and moving these particles around in the search space according to mathematical formulae over the particle's position and velocity. Innumerable variants and hybrids of these techniques have been proposed, and many more applications of CIAs to specific problems have been reported [7–9]. In the basic methodology, however, these algorithms have some features in common: (i) looking for global solutions of optimization problems by means of random search with heuristic information; (ii) promoting problem solving efficiency by multipoint search strategies; and (iii) synthesizing the information involved in a number of currently obtained candidate solutions to produce subsequent search decision. Due to the similarity, these algorithms possess several common advantages such as the robustness against the faint mathematical descriptions and the odd mathematical properties of optimization problems, as well as the capability to attain global optima. But they also share some shortcomings. One of the most well-known disadvantages is that the algorithm parameters are determined by experience rather than theoretical guidance. Therefore, when the algorithm parameters are improperly set up, the search process is apt to sink into a stagnant status; that is, no any better candidate solutions that are superior to their parents will be yielded (or the candidate solutions converged too early, resulting in being suboptimal).A number of theoretical studies have been conducted in order to seek the seeds of the stagnation problems. Rudolph [10] analyzed the convergence properties of the canonical GA (CGA) and proved that in the sense of probability, CGA does not converge to global optima for any selection of initial population, crossover operator, and objective function, but some variants of CGA with an elite reserve policy are shown to converge in probability. Xu et al. [11] considered a class of GA with the strategy in which parental populations are put into competition with their offspring. It is shown that a variant of CGA with such a strategy can reach global optima after a finite number of iterations in probability one. Rastegar [12] gave the lower boundaries of the probability in which the compact genetic algorithm (cGA) converges to global optima and proved that the algorithm converges almost surely to the global optima of a special class of functions as the learning rate is sufficiently small. In the studies on ACO, Gütjahr [13, 14] first proved the convergence of the graph-based ant system by means of the graph theory. It is shown that under certain conditions, the candidate solutions generated in each iteration converge to the global solution of a given problem instance in a probability that can be made arbitrarily close to one. Stützle and Dorigo [15] and Badr and Fahmy [16] studied the convergence properties of ACO with the aid of the algebraic theory, but their work was incomplete due to too many hypotheses made in their proofs. Duan et al. [17] regarded the pheromone trail vector in ACO as a Markov chain and presented a new approach for analyzing the almost sure convergence properties of ACO based on the martingale theory. However, the pheromone trail vector is not self-contained if the path information is unknown. Thus further discussions are needed for Duan’s conclusions. The convergence of PSO is also an issue of concern in the work on CIAs. Clerc and Kennedy [18] analyzed a sole particle’s trajectory in simplified PSO systems and led their analysis to a generalized algorithm model in which a set of coefficients are used to control the system convergence. Based on Clerc’s analysis, the dynamic behavior and the convergence of the simplified (deterministic) PSO algorithm were analyzed by Trelea [19] with the aid of tools from the discrete-time dynamic system theory. Van den Bergh and Engelbrecht [20] investigated the influence of the inertia factor on particle trajectories in PSO and provided a formal proof that each particle converges to a stable point. Poli [21] presented a method that allowed one to exactly determine the sampling distribution of PSO and explained how it changes over time during stagnation for a large class of PSO variants. Liu et al. [22] proved that PSO converges to global optima in probability one based on an iterative function model and the probabilistic theory. Chen and Jiang [23] analyzed the behavior of PSO on the facet of particle interaction and proposed a statistical interpretation of PSO in order to capture the stochastic behavior of the entire swarm. Based on a social-only model, they derived the upper and lower boundaries of the expected particle norm.The basic methodology in the aforementioned studies is that the convergence properties are first investigated from a specific implementation of GA, ACO, or PSO and then to be extended to a wider area of the corresponding algorithm. In this paper, the authors attempt to analyze the general convergence properties of these algorithms on the basis of their common features in methodology. The main attention is paid to the characteristics of heuristic search strategies which play crucial roles in problem solving. The purpose of this paper is to have a deeper understanding on the essence of the convergence of the CIAs and, based on which, to develop more efficient algorithms for complex problems optimization.The rest of this paper is organized as follows. In Section2, a computational model of a class of CIAs is built up on the basis of several common features of the heuristic search strategies adopted by GA, ACO, and PSO, and a set of definitions are given to describe the external and internal changes of a solution set updating sequence in CIAs. In Section 3, the concepts of convergence in probability and almost sure convergence are defined for the solution set updating sequences generated in the search process of the computational model, and their relations are discussed. In Section 4, the conditions under which the computational model converges almost surely to a space of weakly optimal solution sets are studied based on the Markov chain properties of the solution set updating sequences. Then the almost sure convergence to a strongly optimal solution space is proved for the computational model with the aid of the martingale theory. Several conclusive remarks are given in Section 5.


## 2. The CIA Model

In this section, the characteristics of solution sets representation and solution sets update in CIAs are analyzed, and based on that, the computational model of a class of the CIAs is established. Moreover, variation rate of set component and progress rate of solution set are defined, respectively, to describe the variety and the optimality of the solution sets generated in the search process of the model.Without loss of generality, consider the optimization problem of the following type:(1)maxX{f(X)∣X∈S},
where S is usually called a search (or solution) space, and f(X) is an evaluation function satisfying 0<f(X)<∞.A problem-solving procedure observing the following principles is stipulated as the computational model of a class of the CIAs (“the CIA model” for short) under study in this paper.Step 1.
Transform the feasible spaceS into the coded space of variables.Step 2.
Generate a certain number of candidate solutions to composite an initial solution set.Step 3.
Produce a new generation of solution set based on the heuristic information involved in the current solution set and corresponding evaluation values, and set the size of the solution set fixed.Step 4.
Stop the iterations and output the best candidate solution within the current solution set if a predefined termination criterion is satisfied; otherwise go back to Step3.Obviously, the canonical forms of GA, ACO, and PSO and most of their derived algorithms obey the aforementioned computational rules, thus can be regarded as the realization instances of the CIA model.We consider a set of candidate solutions (“solution set” for short)X={X1,X2,…,XN}∈SN composed by N strings of length L in CIAs, where S is the search space of candidate solutions, and SN=S×S×⋯×S︸N is the search space of solution sets of Nth order. A candidate solution is composed of L bit numbers as its components (“solution components” for short). The candidate solution and its component have the special meaning in different CIAs. Table 1 illustrates the expressions of solution candidate and solution component in GA, ACO, and PSO. Therefore, a solution set X generated by CIAs can be written in the following vector and matrix forms:
(2)X=[X1X2⋮XN]=[x11x12⋯x1Lx21x22⋯x2L⋮⋮⋮⋮xN1xN2⋯xNL]=[C1,C2,…,CL],
where Xi=(xi1,xi2,…,xiL)∈S is the ith candidate solution in X, and xij is the jth solution component of the ith candidate solution, i=1,2,…,N,  j=1,2,…,L. For the sake of convenience, the jth vector which consists of the jth components of all the candidate solutions in X is called the jth set component, written as Cj=(x1j,x2j,…,xNj)T.Table 1
The expressions of solution candidate and solution component.
CIA model
GA
ACO
PSO
Solution candidate
Chromosome
Searching path
Multidimensional position of a particle
Solution component
Gene
Path segment
One-dimensional position of a particleAs we know, a new generation of solution set in the CIA model generally relies on the heuristic information involved in the current solution set rather than the previous solution sets. Thereby, a state transition sequence of solution set can be expressed as a Markov chain, denoted by{X(t),t≥0} [24]. In essence, the search procedure of the CIA model can be regarded as the updating process of solution sets expressed by
(3)X(t+1)=H(X(t)),
where H(·) is the solution set updating operator or in other words, the heuristic search strategy adopted by the CIA model. It is instantiated by the evolutionary operations composed of selection, crossover, and mutation in GA; by the path search guided by pheromone updating and path selection in ACO; and by the particle motion adjusted by velocity and position updating in PSO.It is well known that “elite reserve” is a commonly used strategy in many realisation instances of the CIA model. In this strategy, the best candidate solution of the previous generation is always retained in the current generation, so the best candidate solution obtained so far will not be missed in the future search process. We assume that an elitist strategy is always adopted by the CIA model.It is reasonable to estimate the evolution trend of a solution set by the change of its solution components. In order to quantify the variation of solution components, the solution setX is first pretreated as a canonical form in the following way (see Figure 1). First of all, according to the element values of set component C1, solution set X can be divided into two parts:
(4)X10={Xisatisfyingxi1>∑i=1Nxi1N,∀i∈{1,2,…N}},X11={Xisatisfyingxi1≤∑i=1Nxi1N,∀i∈{1,2,…N}},
where X10∪X11=X and X10∩X11=∅.Figure 1
The sorting process of the solution candidates inX.Then, depending upon the element values of set componentC2, X10 and X11 can be further decomposed into two parts, respectively, denoted by
(5)X10X20={Xisatisfying(xi1>∑i=1Nxi1N),(xi2>∑i=1Nxi2N),∀i∈{1,2,…N}(xi2>∑i=1Nxi2N)},X10X21={Xisatisfying(xi1>∑i=1Nxi1N),(xi2≤∑i=1Nxi2N),∀i∈{1,2,…N}(xi2>∑i=1Nxi2N)},X11X20={Xisatisfying(xi1≤∑i=1Nxi1N),(xi2>∑i=1Nxi2N),∀i∈{1,2,…N}(xi2>∑i=1Nxi2N)},X11X21={Xisatisfying(xi1≤∑i=1Nxi1N),(xi2≤∑i=1Nxi2N),∀i∈{1,2,…N}(xi2>∑i=1Nxi2N)},
where X10X20∪X10X21=X10,  X10X20∩X10X21=∅,  X11X20∪X11X21=X11, and X11X20∩X11X21=∅. The process continues until the last set component CL is treated.LetT(t) be a descriptive function of the set component variation from the (t-1)th generation to the tth generation of solution set based on the canonical form, defined by
(6)T(t)=[T1(t),T2(t),…,TL(t)]=X(t)⊕X(t-1),
where the jth element of T(t), Tj(t)=[x1j(t)⊕x1j(t-1),…,xNj(t)⊕xNj(t-1)]T. The sign “⊕” expresses the operator which is very similar to the logical exclusive-OR; that is, the output of two compared values is 0 only if both xij(t-1) and xij(t) are the same. Equation (6) implies that an element of T(t) is 1 if the corresponding components of X(t) and X(t-1) have different values; otherwise the element is 0.Based on the descriptive functionT(t) we can define an index to measure the evolution trend of a solution set quantitatively.Definition 1 (variation rate of set component).
Let{X(t),t≥0} be the solution set updating sequence generated by the CIA model, and let ∑Tj be the sum of all the element values in Tj. We call pj(t)=∑Tj(t)/N the variation rate of the jth set component of solution set X evolving from X(t-1) to X(t).From Definition1 we know that in view of the fact that 0≤∑Tj(t)≤N,  0≤pj(t)≤1, for all t. The variation rate of a set component measures the variation of the set component by calculating the percentage of its elements which change their values from the previous generation to the current generation. Thus, if pj(t)=0, then all the elements in set component Cj keep unchanged. Otherwise, if pj(t)=1, it implies that all the values in Cj have changed from X(t-1) to X(t).Without loss of generality, it is assumed that the objective functionf(·) of the optimization problem (1) is used as the evaluation function in the CIA model. In order to quantitatively estimate the optimality of the candidate solutions in a solution set, it is useful to introduce the concept of progress rate of solution set as follows.Definition 2 (progress rate of solution set).
Let{X(t),t≥0} be the solution set updating sequence generated by the CIA model. Let f-(X(t)) denote the mean evaluation value of the candidate solutions in solution set X(t), calculated by f-(X(t))=∑i=1Nf(Xi(t))/N; and f^(X(t)) the maximal evaluation value of the candidate solutions in X(t), calculated by f^(X(t))=maxi=1,2,…,Nf(Xi(t)). Then α(t)=f-(X(t))/f^(X(t)) is called the progress rate of solution set X at the tth generation.From Definition2, we know that 0<α(t)≤1. α(t) approaches 0 if most of the candidate solutions are far worse than the best candidate solution in X(t). On the other hand, α(t) approaches 1 if the evaluation values of most of the candidate solutions in X(t) are very close to the evaluation value of the best candidate solution.


## 3. The Basic Concepts on the Convergence of the CIA Model

In this section, we first present two different notions of convergence of random variables in probability theory. Then, these concepts are introduced into the solution set updating sequence in the CIA model. Finally, the relationships among the different types of convergence are discussed.There exist several different notions of convergence of random variables, and the convergence of sequences of random variables to some limit random variable is an important concept in probability theory. We assume that{δn,n=1,2,…} is a sequence of random variables, and δ is a random variable.Definition 3 (convergence in probability [25]).
A sequence{δn,n=1,2,…}of random variables converges in probability towards δif for all ε>0,
(7)limn→∞P(|δn-δ|≥ε)=0.Definition 4 (almost sure convergence [25]).
A sequence{δn,n=1,2,…} of random variables converges almost surely or almost everywhere towards δ means that
(8)P(limn→∞δn=δ)=1.
This means that the values ofδn approach the value of δ, in the sense that events for which δn does not converge to δ have probability 0.
Almost sure convergence implies convergence in probability. Convergence in probability is the type of convergence established by the weak law of large numbers, while almost sure convergence is the type of convergence established by the strong law of large numbers.
The definition of convergence may be extended from random variables to more complex random elements in CIAs. Before giving the definitions of the convergence of the CIAs, we explain two different concepts of the space of optimal solution sets.
Let the global optimal value of the evaluation functionf(X) be denoted by  fmax=maxX∈Sf(X), and let the set of the global optimal solutions of problem (1) be represented as OC={X∈S∣forallY∈S,f(X)≥f(Y)}. Obviously, for all X∈OC, we have f(X)=fmax.
The solution setX∈SN satisfying f^(X)=fmax is called the weakly optimal solution set. All the weakly optimal solution sets produced by the CIA model in its search process constitute a space of weakly optimal solution set, denoted by WOS={X∈SN∣f^(X)=fmax}. The solution set X∈SN satisfying f-(X)=fmax is called the strongly optimal solution set. All the strongly optimal solution sets constitute a space of strongly optimal solution set, denoted by SOS={X∈SN∣f-(X)=fmax}.
From the aforementioned definitions, we know that∃Xi∈X∈WOS, the equality f(Xi)=fmax holds. Otherwise, if for all Xi∈X∉WOS, the inequality f(Xi)<fmax can be deduced. Similarly, if for all Xi∈X∈SOS, we have f(Xi)=fmax, and if ∃Xi∈X∉SOS, we can conclude that f(Xi)<fmax. So it is easy to deduce the relationship among the space of strongly optimal solution sets, the space of weak optimal solution sets, and the coded space of solution sets, that is, SOS⊂WOS⊂SN.
In view of the aforementioned notions, there are four kinds of convergence related to a solution set updating sequence in the CIA model.
The CIA model is said to converge weakly in probability if its solution set updating sequence{X(t),t≥0} satisfies limt→∞P{X(t)∈WOS}=1, for all X(0)∈SN. The CIA model is said to converge strongly in probability if the sequence {X(t),t≥0} satisfies limt→∞P{X(t)∈SOS}=1, for all X(0)∈SN.
The CIA model is said to weakly converge almost surely if its solution set updating sequence{X(t),t≥0} satisfies P{limt→∞[X(t)∈WOS]}=1, forallX(0)∈SN. The CIA model is said to strongly converge almost surely if the sequence {X(t),t≥0} satisfies P{limt→∞[X(t)∈SOS]}=1, for all X(0)∈SN.Based on the definitions, the almost surely weak convergence of the CIA model can also be defined byP{limt→∞f^(X(t))=fmax}=1, and the almost surely strong convergence of the CIA model can also be defined by P{limt→∞f-(X(t))=fmax}=1.According to the above definitions, we can deduce the relationship among the four types of convergence.Theorem 5.
There are the following relations among the four types of convergence of the CIA model.(i)
Almost surely strong convergence⇒almost surely weak convergence ⇒weak convergence in probability.(ii)
Almost surely strong convergence⇒strong convergence in probability ⇒weak convergence in probability.Proof.
Based on the definition of the space of optimal solution set, we have(9)[X(t)∈SOS]⟹[X(t)∈WOS].
From (9) we can derive that
(10)P{[X(t)∈SOS]}≤P{[X(t)∈WOS]}.
Hence we have
(11)limt→∞P{[X(t)∈SOS]}⟹limt→∞P{[X(t)∈WOS]},P{limt→∞[X(t)∈SOS]}⟹P{limt→∞[X(t)∈WOS]}.
Owing to the fact that
(12)limt→∞[X(t)∈WOS]=⋃t=1∞⋂k=t∞[X(t)∈WOS],
according to the monotonicity of probability, we obtain
(13)P{limt→∞[X(t)∈WOS]}≤limt→∞P{⋂k=t∞[X(t)∈WOS]}≤limt→∞P{[X(t)∈WOS]}.
Thus, we get
(14)P{limt→∞[X(t)∈WOS]}⟹limt→∞P{[X(t)∈WOS]},P{limt→∞[X(t)∈SOS]}⟹limt→∞P{[X(t)∈SOS]}.Based on Theorem5, we know that almost surely strong convergence implies almost surely weak convergence and strong convergence in probability, and hence implies weak convergence in probability. However, the almost surely weak convergence and strong convergence in probability are not interdeducible.


## 4. Convergence Analysis of the CIA Model

In this section, the conditions under which the CIA model converges almost surely to the space of weakly optimal solution set are studied according to the Borel-Cantelli Lemma. And then the conditions under which the CIA model converges almost surely to the space of strongly optimal solution sets are deduced based on the submartingale convergence theorem.Lemma 6 (Borel-Cantelli Lemma [26]).
Let{ξi,i=1,2,…} be a sequence of events in a probability space and limsupξn the set of outcomes that occur infinitely many times within the infinite sequence of events (ξn), then
(15)limsupn→∞ξn=⋂n=1∞⋃k=n∞ξk.
The Borel-Cantelli Lemma states the facts that:(i)
if the sum of the probabilities of the eventsξi,  i=1,2,…, is finite, then the probability in which infinitely many of the events occur is zero. Namely, if ∑n=1∞P{ξn}<∞, then P{limsupn→∞ξn}=0;(ii)
if the eventsξi,  i=1,2,…, are independent and the sum of the probabilities of the events diverges to infinity, then the probability in which infinitely many of the events occur is one. Namely, if ∑n=1∞P{ξn}=∞ and the events ξi,  i=1,2,…, are independent, then P{limsupn→∞ξn}=1.Lemma 7.
Let{X(t),t≥0} be a solution set updating sequence generated by the CIA model and P{X(t+1)∣X(t)} the one-step transition probability of X(t). If the mutation rate of set components satisfies pj(t)>0, for all j∈{1,2,…,L}, then ∃c∈(0,1), satisfying(i)
P{X(t+1)∈WOS∣X(t)∈WOS}=1;(ii)
P{X(t+1)∈WOS∣X(t)∉WOS}≥c.Proof.
(1) Consider the case ofX(t)∈WOS. By the definition in Section 3, we know
(16)f^(X(t))=fmax.
Since an elite reserve strategy is adopted in the CIA model, from (16) we get
(17)f^(X(t+1))≥f^(X(t))=fmax.
Thus P{X(t+1)∈WOS∣X(t)∈WOS}=1. The proof of the first part of Lemma 7 is completed.
(2) Consider the case ofX(t)∉WOS. Also by the definition in Section 3, we know
(18)f^(X(t))<fmax.
If X(t+1)∈WOS, then ∃Xi(t+1)∈X(t+1),  i∈{1,2,…,N}, satisfying
(19)f^(X(t+1))=f(Xi(t+1))=fmax.
When f^(Xi(t+1))=fmax, we have
(20)P{Xi(t+1)∣X(t)∉WOS}≥∏j=1Lpj(t)>0.
Thus ∃c∈(0,1), where c=minP{Xi(t+1)∣X(t)∉WOS}, such that
(21)P{X(t+1)∈WOS∣X(t)∉WOS}=maxP{Xi(t+1)∈OC∣X(t)∉WOS}≥c.
The proof of the second part of Lemma 7 is completed.Theorem 8.
Let{X(t),t≥0} be a solution set updating sequence generated by the CIA model and X(0) an initial solution set. {X(t),t≥0} is weakly convergent almost surely if for all j∈{1,2,…,L} and t>0, the inequality pj(t)>0 holds.Proof.
Consider the case ofX(0)∈WOS. By the definition in Section 3, we know
(22)f^(X(0))=fmax.
Since the CIA model is assumed to adopt an elite reserve strategy, we get
(23)f^(X(t))≥f^(X(t-1))≥⋯≥f^(X(0)).
Combining (23) with (22) yields
(24)f^(X(t))=f^(X(t-1))=⋯=f^(X(0))=fmax.
Thus, the theorem is valid for X(0)∈WOS.
Consider the case ofX(0)∉WOS. Let pT=P{X(T)∉WOS}, then we have
(25)pT={0,if∃t∈{0,1,2,…T},X(t)∈WOS,pT′,if∀t∈{0,1,2,…T},X(t)∉WOS.
According to Lemma 7, we obtain
(26)pT′=P{X(t)∉WOS∣X(t-1)∉WOS,∀t=,1,2…T}=P{X(T)∉WOS∣X(T-1)∉WOS}⋯P{X(1)∉WOS∣X(0)∉WOS}≤(1-c)T.
From (25) and (26) and considering the fact that 0<c<1, we have
(27)∑T=1∞pT≤∑T=1∞(1-c)T=1-cc<∞.
Based on (27), the first part of Lemma 6 holds. Then we have
(28)P{⋂t=1∞⋃T=t∞X(T)∉WOS}=0.
Thus P{limt→∞f^(X(t))=fmax}=1.The sequence of the maximal evaluation values and the sequence of the average evaluation values of the solution sets generated by the CIA model will be used to describe the evolution process of the solution sets for further discussion. The martingale theory is introduced into the Markov chain analysis of the solution set updating sequence instead of the traditional ergodic theory. The conditions under which the CIA model converges almost surely to the space of strongly optimal solution sets are deduced based on the submartingale convergence theorem and the related conclusion in Section2.The concept of submartingale on a random sequence{β(k),γ(k),k≥0} can be found in [26] in the effort to construct the convergence criteria for random sequences; that is, a sequence {β(k),k≥0} is said to be a submartingale with respect to another sequence {γ(k),k≥0} if  for {β(k),γ(k),k≥0} the following conditions are satisfied: (i) E|β(k)|<∞; (ii) β(k) is the function of  γ(0),γ(1),…,γ(k); and (iii) E[β(k+1)∣γ(0),γ(1),…,γ(k)]≥β(k). In particular, a sequence {β(k),k≥0} is called the sequence of submartingale if for all k≥0,  β(k) is an integrable random variable satisfying E[β(k+1)∣β(0),β(1),…,β(k)]≥β(k).Based on the concept of submartingale and Doob’s upcrossing inequality, the following submartingale convergence theorem was deduced for random sequences.Lemma 9 (submartingale convergence theorem [26]).
If{β(k),k≥0} is a sequence of submartingale with supkE|β(k)|<∞, then β(∞)=limkβ(k) almost surely, and β(∞) is integrable; that is, P(limk→∞β(k)=β(∞))=1 and E|β(∞)|<∞.
The search process of the CIA model can be regarded as the progress of the maximal evaluation values of the solution sets generated in the process, expressed by the sequence{f^(X(t)),t≥0}; or the progress of the average evaluation values of the solution sets, expressed by the sequence {f-(X(t)),t≥0}. Both of the sequences are Markov chains. Thus, the convergence analysis of the CIA model can be firstly transferred to the submartingale analysis of the maximal evaluation value sequence {f^(X(t)),t≥0} and then be further transferred to the submartingale analysis of the average evaluation value sequence {f-(X(t)),t≥0}.Lemma 10.
W
O
S is a closed set.Proof.
Let{X(t),t≥0} be a solution set updating sequence generated by the CIA model. Since the elite reserve strategy is adopted in the CIA model, we have f^(X(t+1))≥f^(X(t)). On the other hand, according to the definition in Section 3, for all Y∈WOS and forallZ∉WOS, we have f^(Y)>f^(Z). Thus X(t+1)≠Z if X(t)=Y, which results in the conclusion that P(X(t+1)=Z∣X(t)=Y)=0. Then, for all Y∈WOS, we have
(29)∑Z∉WOSP(X(t+1)=Z∣X(t)=Y)=0,
or equivalently
(30)∑Z∈WOSP(X(t+1)=Z∣X(t)=Y)=1.
Therefore, WOS is a closed set.According to Lemma10, we can prove that the maximal evaluation value sequence of solution set is a submartingale with respect to the corresponding solution set updating sequence.Lemma 11.
The maximal evaluation value sequence{f^(X(t)),t≥0} generated by the CIA model is a submartingale with respect to the solution set updating sequence {X(t),t≥0}.Proof.
According to the non-after-effect property of Markov chain, we can conclude that(31)E[f^(X(t+1))∣X(0),X(1),…,X(t)]=E[f^(X(t+1))∣X(t)],
based on which we only need to prove that for all Y∈SN the following inequality is true:
(32)E[f^(X(t+1))∣X(t)=Y]≥f^(X(t)),∀t≥0.
According to the theory of random process [26], we have
(33)E[f^(X(t+1))∣X(t)=Y]===∑Z∈SNf^(Z)P(X(t+1)=Z∣X(t)=Y)===∑Z∈WOSf^(Z)P(X(t+1)=Z∣X(t)=Y)===+∑Z∉WOSf^(Z)P(X(t+1)=Z∣X(t)=Y)==≥∑Z∈WOSf^(Z)P(X(t+1)=Z∣X(t)=Y).
For the maximal evaluation value sequence {f^(X(t)),t≥0}, we have
(34)f^(X(t+1)=Z)≥f^(X(t)=Y),∀Z∈WOS.
Combining (34) with (33) yields
(35)∑Z∈WOSf^(Z)P(X(t+1)=Z∣X(t)=Y)≥=≥∑Z∈WOSf^(Y)P(X(t+1)=Z∣X(t)=Y)≥==f^(Y)∑Z∈WOSP(X(t+1)=Z∣X(t)=Y).
By Lemma 10, we obtain
(36)∑Z∈WOSP(X(t+1)=Z∣X(t)=Y)=1.
From (35) and (36) it results in
(37)∑Z∈WOSf^(Z)P(X(t+1)=Z∣X(t)=Y)≥f^(Y).
Equation (37) implies that E[f^(X(t+1))∣X(t)=Y]≥f^(X(t)).Based on Lemma11, we can associate the average evaluation value sequence of solution set with the progress rate of solution set defined in Section 2 to obtain the following corollary.Corollary 12.
The average evaluation value sequence{f-(X(t)),t≥0} is a submartingale with respect to the solution set updating sequence {X(t),t≥0} if the corresponding progress rate of the solution set satisfies α(t+1)≥α(t), for all t≥0.Proof.
Based on Lemma11, it can be obtained that
(38)E[f^(X(t+1))∣X(0),X(1),…,X(t)]≥f^(X(t)),∀t≥0.
It follows that if α(t+1)≥α(t)>0,  for all t≥0, we have
(39)α(t+1)E[f^(X(t+1))∣X(0),X(1),…,X(t)]≥α(t)f^(X(t)).
By Definition 2, (39) implies
(40)E[f-(X(t+1))∣X(0),X(1),…,X(t)]≥f-(X(t)).
Thus {f-(X(t)),t≥0} is a submartingale with respect to {X(t),t≥0}.Based on Lemma11 and its corollary, the sufficient conditions can be obtained for the strong convergence of the solution set updating sequence generated by the CIA model.Theorem 13.
Let{X(t),t≥0} be a solution set updating sequence generated by the CIA model and pj(t) the variation rate of set component Cj(t) in solution set X(t). {X(t),t≥0} is strongly convergent almost surely if Corollary 12 holds and ∑t=1∞∏j=1Lpj(t)=∞.Proof.
Let the complement of the set of the globally optimal solutions be denoted byOCC and {Mt,t≥0} a sequence of random events that at least a part of the candidate solutions in solution set X(t) belongs to OCC; that is, Mt={X(t)∩OCC≠∅}={f-(X(t))≠fmax}. Similarly, let MtC be the exclusive event sequence of Mt; that is, there is no any candidate solution in solution set X(t) belonging to OCC, expressed by MtC={X(t)∩OCC=∅}={f-(X(t))=fmax}. Let P{Mt} and P{MtC} be the probability measures on Mt and MtC, respectively.
From Corollary12, we know that {f-(X(t)),t≥0} is a submartingale with respect to {X(t),t≥0}. Then according to the properties of submartingale, it is known that
(41)fmax≥E(f-(X(t+1)))≥E(f-(X(t))).
According to (41) and the properties of expectation, we get
(42)∫MtCf-(X(t+1))dP=fmax·P{MtC}.
In addition, in view of the fact that 0≤f-(X(t))≤fmax and according to the properties of expectation, we have
(43)suptE(f-(X(t)))≤suptfmax<∞.
Then according to Lemma 9, (43) results in the conclusion that ∃X(∞)=limtX(t), P{limt→∞X(t)=X(∞)}=1. In other words, {X(t),t≥0} is almost surely convergent.
In the following we further prove that the average evaluation value sequence of{X(t),t≥0} converges to fmax almost surely. From (42) it can be seen that f-(X(t+1))=fmax if the event MtC occurs. Namely, MtC surely triggers off the event Mt+1C. Thus the following conclusion holds for the event sequence {MtC,t≥0}:
(44)MtC⊂Mt+1C.
On the other hand, for any solution setsY and Z, if Y∩OCC≠∅, then ∃Yk∈Y, f(Yk)<fmax; and if Z∩OCC=∅, then for all Zk∈Z, f(Zk)=fmax. Hence the following inequality holds:
(45)f-(Z)≥f-(Y)+δN,
where δ=min(fmax-f(Yk)) and N is the size of solution set.
In addition, by the properties of conditional expectation we have(46)E(f-(X(t+1)))-E(f-(X(t)))===E(E(f-(X(t+1))∣X(t)))-E(f-(X(t)))===∑YP{X(t)=Y}·∑ZP{Y,Z}·(f-(Z)-f-(Y))==≥∑Y∩OCC≠∅P{X(t)=Y}·∑ZP{Y,Z}·(f-(Z)-f-(Y))
and from the definition of  Mt, we have
(47)∑Y∩OCC≠∅P{X(t)=Y}=P{Mt}.
Moreover, by the definition in Section 3, we know that
(48)∑ZP{Y,Z}≥∏j=1Lpj(t).
Substituting (45), (47), and (48) into (46), we obtain
(49)E(f-(X(t+1)))-E(f-(X(t)))≥δNP{Mt}·∏j=1Lpj(t).
Now calculating the sum for both sides of the inequality in (49) from t=1 to t, it yields
(50)fmax≥E(f-(X(t+1)))-E(f-(X(1)))≥δN∑k=1tP{Mk}·∏j=1Lpj(k).
Note that (50) holds for any t. Then let t→∞ in (50); we have
(51)∑t=1∞P{Mt}·∏j=1Lpj(t)≤Nδfmax<∞.
It follows that P{Mt}→0 and P{MtC}→1 if ∑t=1∞∏j=1Lpj(t)=∞, which further leads to P{Mt+1C}→1 according to (44). Thus we have
(52)P{limt→∞MtC}=P{limt→∞f-(X(t))=fmax}=1.Remark 14.
The method shown in this paper has a certain similarity to methods reported in [11] for GA and in [17] for ACO. More specifically, the elitist strategy has the same benefits as the strategy of the parents population competing with their offsprings, and the condition of variation rates of set component satisfying ∑t=1∞∏j=1Lpj(t)=∞ in Theorem 13 is expected to act in a similar manner as the condition of minimum mutation probability of population space satisfying ∑n=1∞rn=∞ in [11]. However, the method reported in [11] only applies to GA rather than a class of CIAs. Furthermore, the variation rates of set component are measurable while minimum mutation probability of population space is not. Duan’s convergence proof of ant colony algorithm is also based on the Markov chain and the martingale theory, but they ignore important information [17]. Namely, the vector of pheromone values {τ_(n),n≥1}, without the best-found path ω^(n-1), is not a Markov process and cannot be defined in a self-contained way. However, the stochastic process with states {Xn=(τ_(n),ω^(n-1)),n≥1} is an inhomogeneous Markov process in discrete time [14].


## 5. Conclusions

CIAs is a relatively new interdisciplinary field of research, which has gained huge popularity in these days. One of the most important problems obsessing the researchers in the area of CIAs is the premature convergence or the stagnation of an algorithm. The solution to this problem is not only helpful to the setup of the parameters in an existing algorithm for fast convergence to global optima but also related to how to construct a more effective and efficient algorithm for complex problems optimization. In this paper, we first analyze the common characteristics shared by GA, ACO, and PSO, and based on that, a computational model is constructed for a class of CIAs. Two quantification indices, that is, the variation rate and the progress rate, are subsequently defined to estimate the evolution trend of the solution sets generated by CIAs. Secondly, we define four different notions of convergence of a solution set updating sequence generated by the CIA model, and their relations are discussed. Thirdly, a weak convergence criterion is presented by associating the almost surely weak convergence with the positive definiteness of the variation rate of set component. Finally, the conditions for strong convergence of the CIAs are derived based on submartingale convergence theorem. Two sufficient conditions are obtained for the almost surely strong convergence: (i) the progress rate of solution set does not diminish in the search process; and (ii) the summation of the Cartesian products of the variation rates of set component for all solution sets is infinite.It is obvious that the conditions described in Theorems8 and 13 are sufficient but not necessary; thus, there exists the possibility that these theorems are too conservative to be used in practice. Moreover, a fast convergence rate is absolutely critical for a wide range of applications of CIAs, but it cannot be estimated by using the results presented in this paper. Further research work will be conducted by the authors in an effort to solve these interesting and important problems.



---

*Source: 409606-2013-05-30.xml*