遗传算法的几乎必然强收敛性——鞅方法  

Almost Sure Convergence of Genetic Algorithms:A Martingale Approach

作　　者：徐宗本[1] 聂赞坎[1] 张文修[1] 

机构地区：[1]西安交通大学信息科学与系统科学研究所,西安710049

出　　处：《计算机学报》2002年第8期785-793,共9页Chinese Journal of Computers

基　　金：国家自然科学基金 ( 6 9975 0 16 );国家"八六三"高技术研究发展计划项目 ( 2 0 0 1AA113182 )资助

摘　　要：遗传算法已有的收敛性分析大都是在概率收敛意义下考虑的且基于算法的遍历性分析 .这种收敛性分析不确保算法在有限步内收敛到问题的全局最优解且所获结果仅对带“杰出者记录策略”的算法有效 .该文首次尝试运用鞅论研究遗传算法的几乎必然强收敛性 ,证明一大类不带“杰出者记录策略”的遗传算法能以概率 1确保在有限步内达到全局最优解 .所获结果为遗传算法的实际应用奠定了理论基础 ,且所使用的鞅论分析方法为遗传算法研究提供了全新的分析工具 .The most convergence analysis on genetic algorithms (GAs) is conducted currently in the sense of probabilistic convergence and based on ergodicity analysis on the GA Markovian chain. Such analysis can not infer in general that the GA would be convergent to a global optimum in a finite number of evolution steps, and it validates normally only for the GAs with the elitist record strategy. In the paper, a martingale analysis approach is proposed to study the almost sure convergence of GAs. It is shown that without using the elitist record strategy, a large class of GAs, including the elitist selection GAs, the global annealing GAs, the canonical GAs with time-varying power gauge transformation, can guaranteedly converge to a global optimum in a finite number of steps, provided the involved crossover rate {PC(t)} and mutation rate {PM(t)} satisfy certain delay conditions. The obtained results underlies application of the GAs, and the suggested martingale analysis approach provides a new methodology for convergence analysis of genetic algorithms.

关 键 词：遗传算法 几乎必然强收敛性 鞅方法 马氏链 依概率收敛 计算机 算法分析 

分 类 号：O242.23[理学—计算数学] TP301.6[理学—数学]