演化算法的收敛速率与效率分析

The Convergence Rate and Efficiency of Evolutionary Algorithms

该文讨论了演化算法的收敛速度与效率问题 .引入了衡量演化算法收敛快慢的新标准———收敛阶和收敛因子等概念 ,使用顺序统计方法讨论了收敛阶和收敛因子的计算问题 .考虑到演化算法的收敛速度和每代群体的工作量 ,用收敛阶 (或收敛因子 )和函数评价次数定义了演化算法的效率 .对于常见的球函数模型 ,推导出 (μ ,λ)演化策略收敛因子和效率公式 ,从理论上分析了 (μ ,λ)演化策略中参数 μ ,λ的最佳比值 .

This paper investigates two important issues of evolutionary algorithms (EAs): The convergence rate and the efficiency. The convergence order and converging factor are presented to analyze the convergence rate of evolutionary algorithms. The theory of order statistics is utilized to compute convergence order and converging factor. Besides the convergence rate there remains the question how efficient an evolutionary algorithm performs the generational change. The convergence order and the number of fitness evaluation are used to assess the EAs’ efficiency. As an example, the convergence order and converging factor of (μ,λ)-ES on spherical model are derived. The optimal rate λμ of (μ,λ)-ES on spherical model is analyzed according to efficiency. This way, a step towards the theoretical foundation for the EAs’ efficiency is made.