In recent years, progress has been made in the analysis of global convergence of clonal selection algorithms (CSA), but most analyses are based on the theory of Markov chain, which depend on the description of the transition matrix and eigenvalues. However, such analyses are very complicated, especially when the population size is large, and are presented for particular implementations of CSA. In this paper, instead of the traditional Markov chain theory, we introduce martingale theory to prove the convergence of a class of CSA, called elitist clonal selection algorithm (ECSA). Using the submartingale convergence theorem, the best individual affinity evolutionary sequence is described as a submartingale, and the almost everywhere convergence of ECSA is derived. Particularly, the algorithm is proved convergent with probability 1 in finite steps when the state space of population is finite. This new proof of global convergence analysis of ECSA is more simplified and effective, and not implementation specific.
|Number of pages||4|
|Publication status||Published - 29 Nov 2013|
- Almost everywhere convergence
- Clonal selection algorithm
- Elitist strategy
- Martingale theory