Research On Asymptotic Behaviors Of A Class Of Adaptive Genetic Algorithms

Adaptive genetic algorithm is a very popular technique to prevent the prematureor random searching phenomena which is an inherited drawback of the standardgenetic algorithm. It is concerned with how to use the genetic algorithm to addressproblems in different processes with different parameter vales, such as geneticoperation, operator’s probability, and so on. Thus, this leads to a best trade offbetween exploration and exploitation. Now, it has become a powerful tool in the fieldof automatic programming, and has aroused the interests of many researchers at homeand abroad. However, most of the works on adaptive genetic algorithms focus on theimprovements and realizations, such as merging with other intelligent algorithms, orcombining with statistic study methods in order to enhance its learning ability.Comparing with the improvement and realization, although there are somedevelopments (including the convergence, convergence rate and time complexity) inthe theory research of adaptive genetic algorithm, the fundamental theory results arestill not enough, which has seriously restricted the development of adaptive geneticalgorithm to some extent, and provided less convenience to choose algorithms.Therefore, this dissertation studies the asymptotic behavior of some adaptive geneticalgorithms, including the convergence of genetic algorithm with varying populationsize, the asymptotic behavior of genetic algorithm with the adaptive selectionprobability, and the asymptotic behavior of genetic algorithm with adaptive mutationprobability. The main contents and innovations of this dissertation are summarized asfollows:(1) We summarize some relevant researches and methods about the convergence,convergence rate estimation and time complexity analysis of adaptive geneticalgorithm, and analyze their drawbacks, which can provide reference for researcherson the fundamental theories.(2) An adaptive genetic algorithm with varying population size is proposed. Weexplain the evolutionary process in detail, analyze the change of state transition matrixin those processes, and build the algorithm’s mathematic model using Markov chaintheory. Finally, we show the convergence of this algorithm through martingaleconvergence theory. The population consequence is not only convergence to theoptimal population with the probability one, but also convergence to the uniform optimal population in probability. The comparison results from the simulateexperiment and theory analysis show that the genetic algorithm with varyingpopulation size is better than simple genetic algorithm.(3) An adaptive genetic algorithm with varying selection probability is proposed.We discuss the evolutionary process exhaustively, analyze the change of statetransition matrix in those processes, and build the algorithm’s mathematical modelusing Markov chain theory. Introduce the general frame for the analysis on the theoryof adaptive genetic algorithm. The frame includes three steps: the weakly ergodic, thestronge ergodic, and the convergence of Markov chain to the optimal population.Then, the convergence and geometric convergence rate are estimated by the ergodictheorem in Markov chain theory. Finally, the comparison results from the simulateexperiment and theory analysis show that the genetic algorithm with varying selectionprobability is better than simple genetic algorithm.(4) A typical adaptive genetic algorithm with varying mutation probability isshown. We analyze the change of state transition matrix by Markov chain theory. Withthe introduction of the operators’ characteristic parameters, we obtain both theconvergence and the convergence rate of this algorithm. The upper and lower boundsof expected first hitting time of this algorithm are estimated. Furthermore, we showthat the bounds are determined by the algorithm parameters. Finally, the comparisonresults from the simulate experiment and theory analysis show that the geneticalgorithm with varying mutation probability is better than simple genetic algorithm.The theoretical results deduced by some special methods on the adaptive geneticalgorithms are not a direct extension of the results of simple genetic algorithms. Theyare general theoretical results on asymptotic behavior theory, which can be used todesign and realize the adaptive genetic algorithm. Meanwhile, they strengthen thetheoretical foundation of adaptive genetic algorithm. Moreover, the analyticaltechniques and methods introduced in this dissertation are applicable to the moregeneral situation and they can provide reference to relevant researchers on adaptivegenetic algorithm.