计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1571-1573.DOI: 10.3724/SP.J.1087.2013.01571

• 先进计算 • 上一篇    下一篇

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

彭复明1,姚敏2,白顺科1   

  1. 1. 南京工业职业技术学院 计算机与软件学院,南京 210046
    2. 浙江大学 计算机科学与技术学院,杭州 310027
  • 收稿日期:2013-01-04 修回日期:2013-02-22 出版日期:2013-06-01 发布日期:2013-06-05
  • 通讯作者: 彭复明
  • 作者简介:彭复明(1962-),男,江苏南京人,讲师,硕士,主要研究方向:进化计算;姚敏(1954-),男,安徽安庆人,教授,博士生导师,博士, 主要研究方向:计算智能、模糊信息处理、模式识别、图像处理;白顺科(1968-),男,湖北十堰人,讲师,博士, 主要研究方向:测试计量技术与仪器。

Convergence analysis of general evolutionary algorithms

PENG Fuming1,YAO Min2,BAI Shunke1   

  1. 1. College of Computer and Software, Nanjing Institute of Industry Technology, Nanjing Jiangsu 210046, China
    2. College of Computer Science and Technology, Zhejiang University, Hangzhou Zhejiang 310027,China
  • Received:2013-01-04 Revised:2013-02-22 Online:2013-06-05 Published:2013-06-01
  • Contact: PENG Fuming

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

关键词: 收敛, 概率空间, 通用进化算法, 定理, 证明

Abstract: 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 probability 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.

Key words: convergence, probability space, general evolutionary algorithm, theorem, prove

中图分类号: