Semenov Mikhail A, Terkel Dmitri A
Rothamsted Research, Harpenden, Herts, AL5 2JQ, United Kingdom.
Evol Comput. 2003 Winter;11(4):363-79. doi: 10.1162/106365603322519279.
This paper analyses the convergence of evolutionary algorithms using a technique which is based on a stochastic Lyapunov function and developed within the martingale theory. This technique is used to investigate the convergence of a simple evolutionary algorithm with self-adaptation, which contains two types of parameters: fitness parameters, belonging to the domain of the objective function; and control parameters, responsible for the variation of fitness parameters. Although both parameters mutate randomly and independently, they converge to the "optimum" due to the direct (for fitness parameters) and indirect (for control parameters) selection. We show that the convergence velocity of the evolutionary algorithm with self-adaptation is asymptotically exponential, similar to the velocity of the optimal deterministic algorithm on the class of unimodal functions. Although some martingale inequalities have not be proved analytically, they have been numerically validated with 0.999 confidence using Monte-Carlo simulations.
本文使用一种基于随机李雅普诺夫函数并在鞅理论框架下发展起来的技术，分析了进化算法的收敛性。该技术用于研究一种具有自适应能力的简单进化算法的收敛性，该算法包含两类参数：适应度参数，属于目标函数的定义域；以及控制参数，负责适应度参数的变化。尽管这两类参数随机且独立地变异，但由于直接（针对适应度参数）和间接（针对控制参数）选择，它们会收敛到“最优值”。我们表明，具有自适应能力的进化算法的收敛速度是渐近指数型的，类似于单峰函数类上最优确定性算法的速度。尽管一些鞅不等式尚未得到解析证明，但已通过蒙特卡罗模拟以0.999的置信度进行了数值验证。
