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

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

作　　者：陈明[1,2] 丁立新[2] 余建平[1] 

机构地区：[1]湖南师范大学数学与计算机科学学院,长沙410081 [2]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《小型微型计算机系统》2013年第3期606-610,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60975050,60903168,61165004)资助;湖南省教育厅资助科研项目(10B062)资助;福建省自然科学基金项目(2011J05146)资助;湖南师范大学青年项目(11001)资助

摘　　要：基因表达式编程算法(或称基因表达式程序设计)的基因型/表现型双实体为之带来许多不同于传统演化算法的优势,但建立其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.

关 键 词：基因表达式程序设计 完全收敛 几乎必然收敛 依均值收敛 依概率收敛 有限Markov链 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]