遗传算法收敛性分析的统一方法(英文)

The Unified Method Analyzing Convergence of Genetic Algorithms

建立了种群中最佳个体的马尔可夫链模型 ,定义了仅包含所有全局最优解的状态子集 ;根据从任意状态转移至该子集的概率的极限分布 ,给出了独立于搜索曲面拓扑结构的遗传算法全局收敛性的精确定义 ;提出并严格地证明了与编码方式和选择策略无关的、统一的全局收敛性判据定理 .对几种不同的遗传算法进行全局收敛性分析的结果表明 ,统一的判断方法具有普遍的适用性 .

This paper models the homogeneous finite Markov chain of the best individuals in the populations. Based on the limit distribution of transition probability that any state on the chain transfers into the state subset containing all global optima, a precise definition of the global convergence of genetic algorithms is presented regardless of the topologic structures of search landscapes. Two unified criterion theorems judging the global convergence are proposed and proved strictly, which are independent of encoding schemes and selection mechanisms. The results of analyzing the convergence of different genetic algorithms illustrate that the unified criterion theorems are generally practical and convenient.