The unified method analyzing convergence of genetic algorithms (Q2745617)

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.