J4 ›› 2012, Vol. 39 ›› Issue (6): 99-103.doi: 10.3969/j.issn.1001-2400.2012.06.016

• 研究论文 • 上一篇    下一篇

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

仁庆道尔吉1;王宇平2   

  1. (1. 西安电子科技大学 理学院,陕西 西安  710071;
    2. 西安电子科技大学 计算机学院,陕西 西安  710071)
  • 收稿日期:2011-07-04 出版日期:2012-12-20 发布日期:2013-01-17
  • 通讯作者: 仁庆道尔吉
  • 作者简介:仁庆道尔吉(1982-),男,西安电子科技大学博士研究生,E-mail: renqingln@sina.com.
  • 基金资助:

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

Schema theorem based on limited character set encoding and its proof

Renqingdaoerji1;WANG Yuping2   

  1. (1. School of Science, Xidian Univ., Xi'an  710071, China;
    2. School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China)
  • Received:2011-07-04 Online:2012-12-20 Published:2013-01-17
  • Contact: Renqingdaoerji

摘要:

基本遗传算法的核心理论是模式定理和收敛性理论.传统的模式定理使用了二进制编码方法并给予了证明,然而现实中用遗传算法求解很多问题时需要使用有限字符集的编码方法.首先给出了一些具有代表性的遗传算子,在此基础上证明了有限字符集编码下的模式定理.结果表明,基于有限字符集编码的遗传算法中阶次低、定义长度短且适应度值超过平均适应度值的模式的数目将以指数级增长.

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

Abstract:

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.

Key words: genetic algorithm, encoding method, schema theorem

中图分类号: 

  • TP301.6