通用进化算法的收敛性分析

Convergence analysis of general evolutionary algorithms

传统进化算法的收敛性专注于具体算法,对应的研究成果也仅仅适用于具体算法。为了研究所有进化算法的收敛性问题,提出了一种包含所有操作类型算子的通用进化算法,建立了一套概率空间用于研究算法的收敛性,所有有关算法的术语都用严格的数学语言加以定义。在概率空间中,有七个算法收敛性定理被完整地证明,其中之一找到了算法依概率收敛的充分必要条件。更为重要的是,这些定理适用所有进化算法。它建立了一个体系,用来指导进化算法的设计,从理论上判断进化算法的收敛性。

Traditional Evolutionary Algorithm （EA） convergence research focuses on specific algorithm; consequently the conclusion is only suitable for some specific algorithm. In order to study the convergence of all EAs, this paper presented a general EA including EAs of all operator types. A probability space was set up for the purpose of studying the algorithm＇ s convergence, and all terms on the algorithm were strictly defined in mathematical language, and seven theorems related to the algorithm＇s convergence were completely proved in the probabihty space. One of the theorems found the sufficient and necessary conditions for the algorithm＇ s convergence in probability. More importantly, these theorems are suitable to all types of EAs. A system composed of these theorems was established, which could be used to guide the EA design and judge the correctness of an EA theoretically.