基于重叠表达的多基因进化算法  

A Multi-Gene Evolutionary Algorithm Based on Overlapped Expression

作　　者：彭京[1] 唐常杰[2] 元昌安[2] 朱明放[2] 乔少杰[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]四川大学计算机学院,成都610065

出　　处：《计算机学报》2007年第5期775-785,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60473071;60473051;60503037);中国博士后科学基金(20060400002);四川省青年科技基金(07ZQ026-055);国家"八六三"高技术研究发展计划项目基金(2006AA01Z230);四川省重点科技计划项目(04SG1640)资助.

摘　　要：受生物基因片段重叠表达现象的启发，文中提出了一种新的基于重叠表达进化算法——MEOE（Multigene Evolutionary algorithm based on Overlapped Expression）．文章具体描述了MEOE的基因表达结构及相应的算法．不同于已有的工作，在MEOE中作为遗传物质的基因具有重复表达的概率，同时算法融合了免疫算法关于浓度的计算技术．文章对MEOE算法作了较为全面的分析，讨论了算法在表达空间、可表达性、性状遗传上的特点，并与传统算法作了相应比较．详尽的实验证明，MEOE算法在速度上是GEP的2．5～9．4倍．在高次函数发现问题上MEOE算法的成功率比GEP提高至少一个数量级．另外，通过实验证明了基于密度的概率选择函数在高次函数发现问题上具有一定优势．Inspired by the overlapped gene expression in the phenomena of biology, this paper proposes a novel evolutionary algorithm, MEOE （Multi-gene Evolutionary algorithm based on Overlapped Expression）, and describes the genetic expression structures and relevant algorithm of it. Different from existing works, MEOE suggests a new expression structure of genes with probabilities of overlapped expression for some segments and borrows some idea from artificial immunity algorithm. This paper systematically analyzes MEOE, discusses the features of expression space, capability of expression, and compares MEOE with traditional algorithms. The detailed experiments show that MEOE algorithm is 2.5-9.4 times faster than usual GEP method, and in higher-degree polynomial function finding problem, the success rate of MEOE is 10 times than usual GEP. The experiments results also show that the probability selection function based on density works well in higher-degree polynomial function finding problem.

关 键 词：基因表达式编程 进化算法 基因重叠 表达空间 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]