高级检索

    选择的遗传漂移分析

    Genetic Drift Analysis of Selection

    • 摘要: 进化算法存在早熟收敛和丢失可选解的趋势 ,其原因可归咎于由选择压、采样噪声和交叉算子引起的遗传漂移 建立选择算子的马尔可夫链模型 ,通过吸收态和吸收概率分析证明遗传漂移的必然性和早熟收敛的可能性 ,分析早熟收敛与选择压和适应值函数峰值分布的关系 针对 2解问题 ,通过计算种群多样度期望值 ,分析漂移过程的动态特征 应用实验的方法比较不同采样方法对漂移速度和早熟收敛的影响 其结论为进化算法的实现和改进提供了理论依据和经验指导

       

      Abstract: Evolutionary algorithms tend to get stagnated on local optima and lose alternative solutions. It is due to genetic drift caused by selection pressure, sampling error and gene recombination of crossover. In this paper, homogeneous Markov chain of selection operator is modeled. By demonstrating the existence of absorption states and analyzing absorption probabilities, it is strictly proved that simple selection such as proportional reproduction and rank-based selection must cause uniform convergence of the population, and the makeup of the final population depends not only on selection pressure, but also on distribution of peaks of fitness function, thus planting the curse of premature convergence. In respect of the problems with two candidate solutions, the dynamic characteristics of drift from various selection methods are analyzed by calculating expected value of population diversity. By experimentally measuring the average drifting time and counting the number of premature convergence, the impacts of various sampling methods on genetic drift are compared and analyzed. The results of this paper provide theoretic references and empirical data for implementing and improving evolutionary algorithms.

       

    /

    返回文章
    返回