遗传算法收敛率的下鞅分析

Submartingale Analysis of Convergence Rate Genetic Algorithm

通过鞅论分析来给出遗传算法的收敛率 ,这种分析方法的优势在于它不依赖于染色体的编码形式如常用的二进制形式 ,也不依赖于转移矩阵及其特征值的分析 ,它只以概率来给出遗传算法的收敛率 ,在形式上更加简单明了 ,这是鞅分析优于其它分析如马尔可夫链分析的独特优势 .本文分别对在一定条件下收敛的杰出遗传算法和整体退火遗传算法给出了收敛率的概率形式o( 1- mNn · sNn)和o 1N +N0+( 2 - cN0n - mN0n)e(Δ-δ) /Tn .

This paper analyzes the convergence rate of Genetic A lg orithms in terms of submartingale analysis,which is independent of the decoding method of the chromosome such as binary system,and needn't study the transition probability matrix and the corresponding eigenvalue.The results show that the co nvergence rate of Elitist Genetic Algorithm is o(1- N n)· N n,and the convergence rate of Global Annealing Genetic Algo rithm is o1N+N 0+(2- N 0 n- N 0 n)e (Δ-δ)/T n .