高级检索

    二元进化策略的全局收敛与早熟收敛

    Global Convergence and Premature Convergence of Two-Membered Evolution Strategy

    • 摘要: 离散状态马尔科夫链理论已经广泛应用于进化算法的收敛性和时间复杂度分析中,而连续状态马尔科夫过程理论由于需要用到比较高深的数学工具,应用还不多.引入连续状态马尔科夫过程理论,以测度论为工具,借助公理化的条件数学期望理论推导出关键的转移概率的计算公式,分析了以(1+1)ES为代表的连续型进化算法的收敛性,从理论上证明若采用常变异算子,包括正态分布、柯西分布在内的一大类常用变异分布可使(1+1)ES依概率收敛到全局最优解的ε-邻域;构造了一个带适应值平台的函数,从理论上证明某些自适应变异算子即使以正态分布、柯西分布为变异分布也会导致(1+1)ES陷入早熟收敛.通过仿真实验验证了理论分析.结果表明自适应调整机制并非总是有效的.

       

      Abstract: The theory of discrete state Markov chain has been applied widely to the analysis of convergence and time complexity of the evolutionary algorithms, and the application of the theory of continuous state Markov process is relatively few and not systematic due to the adoption of some profound mathematical tools. In this article, we introduce the theory of continuous state Markov process, use the measure theory and conditional mathematical expectation theory as tools to deduce a key calculation formula of the transition probability. We analyze the convergence property of the continuous evolutionary algorithms represented by (1+1)ES; prove theoretically that a wide class of common mutation distributions including normal distribution and Cauchy distribution, if satisfying some specified conditions which are not difficult to meet in practice, can cause (1+1)ES to converge in probability to the ε-vicinity of global optimum if the constant mutation operator is adopted; construct a function with fitness plateau and prove theoretically that some self-adaptive mutation operators can plunge (1+1)ES into premature convergence even if normal distribution and Cauchy distribution are adopted as mutation distribution. The theoretical analysis is validated by simulation experiment. The results show that self-adaptive mechanism is not always effective, and the scale factor should be selected properly.

       

    /

    返回文章
    返回