有限字符集编码下的模式定理及其证明  

Schema theorem based on limited character set encoding and its proof

作　　者：仁庆道尔吉[1] 王宇平[2] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071 [2]西安电子科技大学计算机学院,陕西西安710071

出　　处：《西安电子科技大学学报》2012年第6期99-103,共5页Journal of Xidian University

基　　金：国家自然科学基金资助项目(61272119)

摘　　要：基本遗传算法的核心理论是模式定理和收敛性理论.传统的模式定理使用了二进制编码方法并给予了证明,然而现实中用遗传算法求解很多问题时需要使用有限字符集的编码方法.首先给出了一些具有代表性的遗传算子,在此基础上证明了有限字符集编码下的模式定理.结果表明,基于有限字符集编码的遗传算法中阶次低、定义长度短且适应度值超过平均适应度值的模式的数目将以指数级增长.The core theory of the basic genetic algorithm is the schema theorem and the convergence theory.The traditional schema theorem uses binary representation and gets proved.However,in reality,solving many problems using the genetic algorithm needs to use a limited character set encoding method.In this paper,we give some typical genetic operators first,on the basis of which we prove the schema theorem using limited character set encoding.The result shows that the numbers of schema with a low order,a short defined length and a fitness value greater than the average fitness value grow exponentially.

关 键 词：遗传算法 编码方法 模式定理 

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