The unified method analyzing convergence of genetic algorithms

Publication date 19 August 2002

Published in Control Theory \& Applications (Search for Journal in Brave)

genetic algorithms global convergence homogeneous finite Markov chain optimization positive stochastic matrix probabilistic search reducible stochastic matrix

Mathematics Subject Classification ID

Stochastic matrices (15B51) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Review text

The homogeneous finite Markov chain of the best individuals in a population is modeled here. The genetic algorithms (GAs) as a class of probabilistic search and optimization algorithms based on the model of organic evolution are used. The interest of the authors is to give a definition of the global convergence of GAs and to analyze the global convergence by means of the Markov chain of the best individuals in the population.NEWLINENEWLINENEWLINEThe set \(P(t)= \{a_i(t)\mid i\in [1,n]\), \(t\in\mathbb{N}\), \(a_i(t)\in I\}\) denotes the population at generation \(t\), \(a_i(t)\) being an individual representing a solution of the feasible region \(I\) of a global optimization problem, \(a^*(t)\) is the best individual in \(P(t)\), \(P= (p_{ij})\) is the transition matrix of an \(a^*(t)\)-chain with state space \(S\), and \(S^*\) is the state subspace, each of which corresponds, respectively, to a solution in a subset \(I^*\) of \(I\).NEWLINENEWLINENEWLINETwo main criteria are presented. The first criterion states that if the transition matrix \(P= (p_{ij})\) of the \(a^*(t)\)-chain with state space \(S\) and the subspace \(S^*\) is a positive stochastic matrix, then the genetic algorithm does not converge to any one of the global optima. The second criterion states that if the transition matrix \(P= (p_{ij})\) of the \(a^*(t)\)-chain is a reducible stochastic matrix with the structure NEWLINE\[NEWLINEP= \begin{pmatrix} C & 0\\ R & T\end{pmatrix},NEWLINE\]NEWLINE where \(C\) is a positive stochastic matrix of order \(|S^*|\) (the cardinality of \(S^*\)) and \(R,T\neq 0\), then the genetic algorithm converges to one of the global optima. These criteria are independent of encoding schemes and selection mechanisms.NEWLINENEWLINENEWLINEFinally, the authors give some examples that aim at illustrating how to apply the above criteria to judge the global convergence of GAs.

Recommendations

Cited in

(16)

This page was built for publication: The unified method analyzing convergence of genetic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2745617)