一类基因表达式程序设计的若干收敛定理及其推广

Convergence Theorems for a Class of Gene Expression Programming and the Generalization

基因表达式编程算法(或称基因表达式程序设计)的基因型/表现型双实体为之带来许多不同于传统演化算法的优势,但建立其Markov模型时,我们须在两者之间作出权衡.为简化遗传算子概率结构的分析,本文以基因型空间为搜索空间,研究一类GEP在宽松条件下的收敛性.首先,针对由基因型-表现型映射所致的多峰适应值函数,重构带精英保留策略的GEP的Markov链模型转移矩阵.然后,通过建立依概率收敛速度的精确表达式、估计其上界,证明了算法依均值收敛、几乎必然收敛甚至完全收敛至全局最优值.与之前的严格假设下的若干结论相比,本文的模型更匹配算法的特性,收敛性结论更强且最优状态子集更小.另外,上述精确表达式也可以推广至自适应演化算法.

The two entities called genotype/phenotype in gene expression programming algorithms(GEP) provide many advantages different from that of traditional evolutionary algorithms.However,they make trouble for establishing the Markov model.In order to simplify analyses on probability structure of genetic operators,with genotype searching space this study focuses on the convergence of a class of GEP under gentle conditions.At first,for multimodal fitness functions caused by the genotype and phenotype mapping,we reconstruct the transition matrix of the Markov model corresponding to GEP with elitist recording strategy is reconstructed.And then,we prove its convergence in mean,almost sure convergence and even complete convergence,through addressing and bounding an exact expression for the rate of probability convergence.Compared to old conclusions with rigorous assumptions,our model is more applicable to characteristics of the algorithms.Moreover,the convergence results are stronger and the optimal state set is less.In addition,the exact expression for convergence in probability can be generalized to adaptive evolutionary algorithms.