First passage times of genetic algorithms (Q2784223)

Let be given a set \(I\), finite but with extremely many elements, and a function \(f|I\rightarrow\mathbb{R}\). One possibility for searching the maximizers of \(f\) is the imitation of biological evolution, named genetic algorithm. A Markov chain \((X_n)\) with the population space \(I^p\) (\(p\) being the population size) as state space describes the evolution by means of the cyclically acting evolution mechanisms mutation, mixing, recombination and selection. Outgoing from a destination set \(S^*\) of the population and the first-entrance time \(\tau:=\inf\{n\geq 0:X_n\in S^*\}\), mainly the convergence principle \(\varlimsup_{n\rightarrow\infty}\sup_{\mu}P_{\mu}(\tau>n)=0\) (\(\mu\) being the initial distribution) has been investigated. In connection with the known algorithmic principle of simulated annealing, the transition kernel \(Q(\beta_n)\) of \((X_n)\) what can be represented as a product sum of the partial transition kernels of the separate evolution mechanisms, will be considered as dependent on a cooling schedule \((\beta_n)\). Now, by means of the Perron-Frobenius theory, the distribution of \(\tau\) and the (quasi-)stationary distribution of \((X_n)\) on dependence of the eigenvalues of \(Q(\beta_n)\) asymptotically has been investigated for the homogeneous as well as for the non-homogeneous case. The influence of the cooling schedule to the convergence of \(\tau\) and its speed is given. NEWLINENEWLINENEWLINEWith the paper, the author shows great competence in theoretical biology as well as in Markov chains. The paper is written in an exact mathematical style. Often it is commented which meanings mathematical properties have for biological evolution. The present material is very rich, nevertheless many questions remain open what will be named in the final chapter. The rich list of literature (58 items) and exact references within the text may stimulate the reader to more profound studies.