关于一类遗传算法收敛速度的研究

遗传算法收敛速度的研究是进化计算领域中一个复杂而重要的问题,但是有关收敛速度的研究结果还相对较少．目前有关遗传算法的收敛速度的结果可分为两类,一类是利用Doeblin条件来估计,但其结论中含有需要进一步估计的常量;另一类是利用状态转移矩阵的特征值来估计,然而同样需要进一步恰当地估计特征值的大小．本文首先给出一类遗传算法的框架,讨论了其全局收敛性,并且利用马尔可夫链的性质,估计了这类遗传算法的收敛速度．

A STUDY OF CONVERGENCE RATE IN A CLASS OF GENETIC ALGORITHMS

It is complicated and important to study the convergence rate of Genetic Algorithms in the field of Evolutionary Computation. However, there are few results about it. To the best of our knowledge, the results having been made on the convergence rate can be divided into two groups. In one group of works, Doeblin condition is made use of. Unfortunately, there exists one constant that needs the necessary estimation in its results. The other works are based on the eigenvalue of transition matrix that needs proper estimation too. In this paper, the frame of a class of genetic algorithms is firstly presented, and the global convergence analysis about this class of algorithms is given follow. Furthermore, the convergence rate of these algorithms is obtained by making use of the properties of Markov chain.