进化算法的收敛速度

Convergence Speed of Evolutionary Algorithm

遗传算法、进化规划和进化策略这三类进化算法都是基于对自然进化的模拟，其区别在于产生下一代群体的规则不同，但下一代群体的产生又都是仅依赖于其父代，因而进化算法的运行过程可以视为一个Ｍａｒｋｏｖ过程，其状态转移矩阵可以表示成一个统一的形式．利用矩阵范数的基本性质，得到了进化算法收敛速度的一个下界，同时也得到了进化算法收敛性的一个证明，并由此解释了遗传算法能很快地得到一个较好的解而要花费较长时间才能得到最优解的原因。

Genetic algorithm, evolutionary programming and evolution strategies are all based on the idea of natural evolution. Those algorithms are differentiated by the way of getting new generation. But the new one is related with the last generation only. So they are all Markov processes. A unified expression of the state transition matrix was proposed. A lower bound of the converge speed and the convergence of the evolution algorithm were derived. Finally, it was explained why the genetic algorithm can get a better solution quickly while it needs a long time to get the global solution.