（计算机应用技术专业论文）基因表达式编程核心技术研究.pdf

l 删j i i 大学博l 学位沦义 基因表达式编程核心技术研究 计算机应用专、l k 研究生序劫指导教师唐常杰教授 迸化计算足当前人r 智能知识工程数据挖掘l ir 的研究热点。遗传算法 和遗传编程，足众多进化计算模型l i ，的两个最典型的模型。遗传算法采用线性 编码，求解普通的优化问题。遗传编程则采用树形编码，试图求出解决问题的 程序。fc a n d i d a 于2 0 0 1 年草创了新的进化计算模型基因表达式编程f g e n e e x p r e s s i o np r o g r a m m i n g ) 。同时具有遗传算法的简单性，也具有遗传编程的功 能。在对很多问题的求觯效率上、比普通的遗传编程高2 4 个数量级。f c a n d i d a 在草创的同时，留卜了大量的理论空白，技术缺陷和遗憾之处。本文在 前人l ：作的基础，卜- 对苯因表达式编程的核心技术进行了研究，丰要结果和贡献 如f ： ( 1 ) 对基因表达式编程的螭因编码进行，理沦分析。给山了k 一序列和表达 式树之间的关系，指出它 i l z 间的表达能力是致的。随后存给出的定邢中指 出，皋因表达式编程是可靠日完备的。满足t = ( a ( f ) 一1 ) + l 的g e p 皋因 定能够解码为棵完整的表达式树。这为皋园表达式编程的基因编码给出了 坪沦依据。 ( 2 ) 提出了更有坪沦背景的罐十复相关系数的适应度函数。升对采用复相 关系数作为评价雨数的龋因表达式编程进行了收敛性分析，指出，犟十犟凶表达 式编程的符号回归是俄概率收敛到伞局最优染色体的， t x , 1 符号同归中的常数 问题，提出了m c 常数方法，并进i i 了f h 沦分析，结果表明、m c 方式是简单但 是却非常有效的，为了达到指定的精度，m c 方法所付m 的代价是对数级的。 ( 3 ) 对基因表达式编程建寺了卜下文无关文法模犁。指出基因表达式编程 和仅含有单个非终结符的卜下文无关文法存描述能力卜是等价的。 ( 4 ) 根据基因表达j 编程的上下文无关文法模型，指出，k - n 表达，编程不 能处理包含多个非终结符的上下文无关文法。提山丁扩展f 门基因表达式编稗与 法解决了基因表达，编程的这一重大不足。在扩展的基因表达j 编程中给山 四j i 大学博上学位论义 r 堪冈构造力浊 等似k 表达，多段晕冈。仆明j 扩j k f 一捧因表达式编袖! 尽因编码的有效性同州指出堆别表达式编程就是扩展的綦因表达式编程的特 例。 ( 5 ) 提出了新的概念j 月词关联规则和趟十缺因表达式编程的挖掘系统。 分析挖掘系统的特性，孙明了传统关联舰则是谓词关联规则的特例。任何传统 关联规则司以表示为系列简单关联规则的与。提j i j 并实现了i 肖词关联规则挖 掘算法行r 根据启发。h 知识设计了特别的适应度函数。两绍实验表明，算法 是有效，的，能发现。监刖传统关联规则挖掘算法不能发现的规则。龋因表达 式编程应用十俐词关联规则挖掘是成功的。 ( 6 ) 提出了两种笨j ：g e p 的方法进行时间序列预测。滑动窗口预测法直 接发现日寸问序列中历史数据到未来数据的函数关系并以此进行预测。微分方 稗顶测法则利用训练数据建立关于t t , ? 1 1 司的高阶常微分力稗并在给定的初值条 件下进行颀测。为了减小数据中噪声的影响，提出了微分显微插值力法，有效 地过滤了数据中的噪声并且使得一阶导数更加精确，提高了方法的可靠性。 大量的实验，特别是在太阳黑子数据上的实验证明系统是有效的性能是良好 的。 关键词：基因表达式编稃，进化计算，遗传算法，遗传编稗上下文无关文法，谓 洲关联规则挖掘，时间序列预测 l l 四j i i 大学1 冉j j 学位论j 史 a b l s t r a c t e v o h l t i o n a r yc j o m l m t a t i o ni s ar i o tp o i n ti nt h er e s e a t e l la r e ao fa r t i f i c i a l i n t e l l i g e n c e ，k n o w l e d g ee n g i n e e r i n ga n dd a t am i n i n g g e n e t i ca l g o r i t h ma n d g e n e t i cp r o g r a m m i n ga tet i l em o s ti m l ) o r t a n tc o m p u t a t i o nm o d e l s i ne v o l u t i o n a r ye o m p u t a t i o n g e n e t i ca l g o r i t h mu s e sl i n e a rb i ts t r i n g3 sc h r o m o s o m ec o d e ， a n ds o l v e so r d i n a r 3 rp r o b l e m sg e n e t i cp r o g r a n m f i n gu s e st r e es t r u c t u r ea sc h r o - m o s e m ec o d e ，a n dw a n tf i n do u tt i l ep r o g r a i l l sf o rt i l ep r o b l e m s i n2 0 0 1 ，f c a n d i d ap r o p o s e san e we v o l u t i o n a r yc o m p u t a t i o nm e t h o dn a m e dg e n ee x - p r e s s i o np r o g r a n m f i n gf g e p ) g e p i sa ss i m p l ea sg e n e t i ca l g o r i t h m ，a n da s f u n c t i o n a la sg e n e t i cp r o g r a m m i n g b u tf o rm o s tp r o b l e m s ，g e pi sm u c hf a s t t h a ng e n e t i cp r o g r a m m i n gi n2 4m a g n i t u d e s w h i l ec r e a t i n gn e wc o n c e p t s a n da l g o r i t h m s ，f c a n d i d al e f ts o m et h e o r e t i ci s s u e sa so p e np r o b l e m s fc a n d i d aa l s o 、i s e sm a n yp r o p e r t i e sw i t h o u tp r o o fs o m ec o n j e c t u r e si ss t i l ll i s ti nt h e f i r s t , b o o ka b o u tg e pw r i t t e nb yf c a n d i d a t h i sp a p e rt r yt oa n s w e rt h e s e p r o b l e m sb a s e do no u rr e s e a r c ho ng e p t h em a i nr e s u l ta n dc o n t r i b u t i o na r e a sf o l l o w s ： ( 1 ) g i v e sr i g o r o u sa n a l y s i so ng e pe n c o d i n g t h i sw o r k r e v e a l st h er e l a t i o n b e t w e e nk e x p r e s s i o na n dt h ee x p r e s s i o nt r e ei tp o i n t so u tt h a tt h e yh a v et h e s a m ee x p r e s s i o np o w e rt h ed i s s e r t a t i o np r o o f sa ni m p o r t a n tt h e o r e ma b o u t s o u n d n e s sa n dc o m p l e t e n e s so fg e p g e n ee n c o d i n gi t , p o i n t so u tt h a tt h eg e n e s a t i s f i e dt = h ( a ( f ) 一1 ) 十1c a nb ed e c o d e di n t oav a l i df u n c t i o ne x p r e s s i o n t r e es y s t e m a t i c a l l y t h i si st h eb a s i ct h e o r yo fg e p ( 2 ) p r o p o s e sa i l e v vf i t n e s sf u n c t i o nv i ac o m p l e xc o r r e l a t i o nc o e f f i c i e n tw i t h s t r o n gs t a t i s t i c st h e o r e t i cb a , c k g r o u n d t h i sw o r ka n m y z e sc o n v e r g e n c eo fg e p u s i n gc o m p l e xc o r r e l a t i o nc o e f f i c i e n tf i t n e s sf u n c t i o n i ti sp r o v e dt h a ts y m b o l r e g r e s s i o nb a s e do ng e p w i l lc o n v e r g e n c eb yp r o b a b i l i t yt og l o b a lo p t i m i z a t i o n s t a i , u st h ed i s s e r t a t i o na l s op r o p o s e san e wc o n s t a n tm i n i n gm e t h o dn a m e d m e t a c o l l s , i d n t s ( m c ) t h et h e o r e t i c a la n a l y s i sa n de x p e r i m e n tr e s u l t ss h o wt h a t l l l 婴型查堂堕土堂垡堡塞 m c m e t h o di ss i m p l eb u tp o w e r f u le n o u g ht h a ti t , ( 、a ng e t , t h ep r e d e f i n e dp r e c i s i o n w i t , ho n l yl o a n r i t , h n f i cc o s l ( 3 ) p r o p o s e st h ec o n t e x t h e eg r a n l n ) a rm o d e lf o rg e pp r o v e st h a tt i l ep r e s e n t a t i o np o w e ro fg e pa n dt h ec o n i e x l f r e eg r a n u n s rw i t ho n en o n e t e r m i n a l a r ee q u i v a l e n t ( 4 ) a c c o r d i n gt ot h ec o n t e x t f r e eg r a m m a rm o d e lo fg e p ，t h ed i s s e r t a t i o n p o i n to u tt h a tc a n d i d a sg e pt e c h n i q u e sc a n n o tp r o c e s sc o n t e x t f r e eg r a m m a r w i t hm u l t i p l en o n e - t e r m i n a l s t h ep a p e rp r o p o s e st h ee x t e n d e dg e n ee x p r e s s i g np r o g r a m m i n g ( e g e p ) t os o l v et h i sw e a k n e s s i ta l s op r o p o s e sn e wc o n c e p t s a b o u ta l m i ek e x p r e s s i o na n dn m l t i s e g m e n tg e n e p r o v e st h a tt h ev a l i d i t yo f t h ee x t e n d e dg e p g e n ee n c o d i n g p r o v e st h a tg e pi sas p e c i a le a s eo fe g e p ( 5 ) p r o p o s e san e wc o n c e p tn a m e dp r e d i c a t ea s s o c i a t , i o nr u l ea n di m p l e m e n t sam i n i n gs y s t e mb a s e do ng e p p r o v e st h a tt h et r a d i t i o n s la s s o c i a t i o n r n l ei sas p e c i a lc a s eo fp r e d i c a t ea s s o c i a t i o nr u l e g i v e st h ea l g o r i t h m sa b o u t m i n i n gp r e d i c a t ea s s o c i a t i o nr i d e s d e s i g n san e wf i t n e s sf u n c t i o na c c o r d i n g t o t h eh e u r i s t i ck n o w l e d g e t w og r o u p so fe x p e r i m e n t ss h o wt h a tt h ea p p l i c a t i o n o fg e pi ss u c c e s s f u l ( 6 ) p r o p o s e st w ok i n d so ft i m es e r i a lp r e d i c t i o nm e t h o d sb a s e do ng e p ： ( a ) b ys l i d ew i n d o wm e t h o dd i s c o v e r st h ep r e d i c a d o nf u n c t i o nb e t w e e nh i s t o r y d a l ；aa n df u t u r ed a t a ( b ) b yo r d i n a r yd i f f e r e n t i a le q u a t i o nm e t h o dm i n e s8 , n o r d i n a r yd i f f e r e n t i a le q u a t i o nf r o mt i m es e r i a ld a t a ，a n dm a k e sp r e d i c t i o nb a s e d a ni n i t i a lc o n d i t i o n i no r d e rt or e d u c et h ea f f e e t i o no ft h en o i s e t h ed i s s e r t a t i o n p r o p o s e sd i f f e r e n t i a lb yi v l i c r o s c o p ei n t e r p o l a t i o nm e t h o d t h i sm e t h o di m p r o v e s t h ep r e c i s i o no ff i r s t , o r d e rd e r i v a t i r e ，a n di m p r o v e st h er e l i a b i l i t yo ft h es y s t e m e x t e n s i v ee x p e r i m e n t so nr e a ld a t as e t sf b rs u ns p o tp r e d i c t i o ns h o wt h a to u r n e wm e t h o di se f f e c t i v ea n dp o w e r f u l k e yw o r d s ：g e n ee x p r e s s i o np r o g r a m m i n g ，e v o l u t i o nc o m p u t a t i o n ，g e n e t i c a l g o r i t h m ，g e n e t i cp r o g r a m m i n g ，c o n t e x tf r e eg r a m m a r ，p r e d i c a t e a s s o c i a t i o n r u l e t i m es e r i a lp r e d i c t i o n 四川大学博上学位坨义 1 前言 1 1 基因表达式编程研究的毒义 智能的木质，内涵、和潜能的奥秘，一直足古今l l 外的哲学家，思想家和科学 家关注，探索和研究的重大问题。近年来，随着脑科学、神经科学的发展，人们 对人脑的结构和功能有了初步的认识，但对整个神经系统的内部结构和作用机 制，特别是脑的功能原理还没有完全搞清楚，还不可能从本质上给智能给出一个 精确的，可被公认的定义。人们还只能从智能的外在表现出发，从不同的角度、 不同的侧面，用不同的方法来对智能来进行研究。人们在对现有智能理解的基 础上采用人工的方式获得智能。目前人们把非生物生命方法产生的智能都称为 人工智能。人工智能总足和逻辑，规则，推理等名词联系在一起。 人工智能的发展经过了孕育，形成和发展三个阶段，提出了符号主义，网络 连接主义等方法，在很多方面都取得了非常巨大的成就。 为了克服上述传统方法存在的缺陷，人们从另外的方面解释智能现象，希望 能从l 得到启发，以发展新的人工智能方法。人们开始向自然界本身学习，大 自然的奥秘启迪了人类的思想家，科学家，最典型，最成功的范例是模仿生物 进化的进化计算这族强大的计算工具。 人们希单通过进化计算 _ 具解决采用以往方法不能解决的问题。希望仅仅 指定问题的输入，问题应该满足的条件，结果的好坏的评价标准，就能够通过计 算机自动过程得到结果。遗传算法，进化规划，进化策略等算法在定程度j 二 满足了人们的要求。 人类对知识的追求永不满足，得寸进尺。典犁的例子就是：希趣利用计算 机白动寻找计算机程序，使计算机程序能够解答相应的类问题。给定多组数 据，希颦发现这螳数据之间的关系，也就是说要找到个程序，更确切地，甬数 表达式，使得对指定的输入，输出相应的数据。或者利用计算机自动找到能够 指挥机器人安伞到达目的地的行走规则，等等。卜述需求催生了程序自动牛成 技术。而进化计算的另 个成员遗传编程( g e l l e t i cp r o g r a m m i n g ，g p ) 则为程 序臼动牛成技术提供了个承要的方法。尽管它的性能还不甚理想，但已经被 1 四川大学博上学位论义 迫切的人们广。泛心用到r 各种| j i 域中。 摧吲表达式编程( g e n ee x p l e s s i o np i o g r a m m i n g g e p ) 是- 葡萄牙学者c a 1 1 一 d i d a 十2 0 0 1 年首次提出的种新犁的进化计算算法。它的应用目标和遗传编 程样，但性能比遗传编程高2 4 个数黾级 1 9 。本文将对摧因表达式编程 的原理，核心技术和。系列新算法，新改进进行伞面的讨沦。 1 2 本文的组织 全文共分十章在第二章中，介绍了基冈表达式编程的研究背景。在第三 章中，给m 了基冈表达式编程的基本方法，洋细描述了基冈表达式编程算法从结 构，遗传编码定义到遗传算子的各个方面。第四章对基冈表达式编程进行了理 论分析，主要包括基因表达式编程原理，基因表达式编程的收敛性分析，基因表 达式编程相对于遗传编程的优势体现基囚表达式编程l i i 常数表达等方面。第 五章讨论，上下文无关文法制导的基因表达式编程，提出了基本基因表达式编 程的上下文无关模型讨论了基木基因表达式编程和上下文无关文法的关系，提 出了扩展的基因表达式编程，解决了基本基因表i 厶式编程的不足。第六，七章 分别介绍了基因表达式编程的应用，一个是将基囚表达式编程应用于关联规则 挖掘，另一个是将基因表达式编程应用于时问序列预测。第八章介绍了作者建 立的基于基因表达式编程的通用建模系统。第九章足本文的结论。 2 四川大学博上学位论义 2 研究背景 2 1 生物进化和遗传 在自然界l h 生命千姿百态，万物树互依存。务种不同的生物在这个自然 界繁衍生息数以万年计的进化，它们都找到了适应各自环境而生存，并繁衍后 代的方法。生物是如何进化的? 足如何适应环境，并进行繁衍的? 人们发现生 物的进化有一些共同的地方： f 1 ) 牛物的性状具有可遗传性。子代的牛物会继承父代个体的一些性状，但 是，后天对生物体性状的改造，不会遗传到下一代中，即获得性不能遗传。 ( 2 ) 成功适应环境的个体有更多的机会将自己的特性遗传给下一代。 f 3 ) 染色体能产生突变，使得子代个体和父代不同。发生这种现象的概率虽然 很低，但它为环境突变时产生新物种埋伏了物质基础。 f 4 ) 进化过程是没有记忆的。下一代的进化过程和上一代的进化过程是没有 关系的。 针对这些现象，在历史上曾经出现过多种不同的理论。经过长期实践的检 骑，目前人们大都认i 司达尔文( d a r w i n ) 的进化理论。达尔文在进化论中指出，地 球上的每一种生物从诞生丌始就进入了漫长的进化历程。生物进化的总趋势是 从低级，简单的类型向高级，复杂的类型进化。各种生物要生存下去，就必须耍 面临来自自然界其他物种以及同一物种的竞争。生存能力高，更适应环境的 个体有更高的机会存活f 来，并有较多的机会产生后代。而对环境的适应能力 较低的个体将更容易被淘汰，i 刊时，产生后代的机会也越米越少，直至灭绝。达 尔文将这一过程和现象称为“自然选择，适者生存”。这就是达尔文进化理论的 核心。根据这一理论，生物的发展和进化有三种主要形态：遗传，变异和选择。 本世纪初，m o r g a n 通过遗传学和细胞学的结合，奠定了基因理论。1 9 5 2 年，h e r s h e y 等通过实验、成功地证实d n a ( d e s o x y r i b o n u c l e i ca c i d ，脱氧核话核 酸) 是遗传物质。作为一种指令密码封装在每一个细胞中，并以基因的形式排 列在染色体1 - _ 。每个基因有特殊的位置、并摔制着生物的某些特性。生物在产 3 四川大学博上学位论义 牛后代的时候，后代染色体是从亲代复制过来的。对于有性牛物，还会对双亲 的染色体进行币组，综合，使得双亲的基因都有机会得到延续。 2 2 遗传算法 将生物现象应用列入工领域的仿生学己经越来越被人们看好。将生物进化 过程应用到人工智能领域，也是一个越来越被看好的方向。这方面的研究形成 厂进化计算这一广阔的分支。在数量众多的进化计算算法中，各种算法都以生 物进化作为算法的背景，但是，每一种算法都具有自己的特点，有的侧重于生物 个体的变异，有的侧重于个体之间的杂交，有的主要利用每一个个体自身进行搜 索，具有较强的局部搜索能力，而有的主要利用群体间个体之间的相互影响，具 有较强的全局搜索能力。在这些算法r h 目前使用最广泛，研究最彻底的是遗 传算法。 h o l l a n d 及其他的学生f ( b a g l e y 等) 于1 9 7 5 年提出了遗传算法( g e n e t i c a l g o r i t h m ) ，并给出了著名的模式定理f 4 ，5 1 。到了8 0 年代末，g o l d b e r g 对一系 列研究工作进行了归纳总结。逐渐认识到在机器学习的研究中，为了获得一个 好的学习算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候 选策略的群体的繁殖。研究结果最终形成了现代遗传算法的基本框架【6 】d 其 特色足高度并行，随机，自适应，健壮，特别适合于处理复杂问题f 如n p 问题的 近似觯) 和非线性问题。 最早的遗传算法称为标准遗传算法后来人们对标准遗传算法进行了大量 改进，使得遗传算法能够得到更加广泛的应用。这些改进的遗传算法不但提出 了很多有自己特色的特性，也大量融入了其他一些进化计算算法的特点。这使得 它们与别的进化计算算法的界限变得比较模糊了。比较有特色的非标准遗传算 法有w h i t l e y 的g e n i t o r 系统【9 ，g r e f e n s t e t t e 的s a m u e l 系统f 1 0 】，d a v i s 的遗 传算法i 1 1 】，m i c h a l e w i c z 的进化程序1 1 2 】，e s h e l m a n 的c h c 算法i 1 3 1 ，k o z a 的 遗传编程f 1 5 1 ，以及c a n d i d a 的趟因表达式编程f 1 9 1 。 实际卜，有螳非标准的遗传算法已经和标准遗传算法在实现，功能，及主 要应用范围等方面部发牛了重大变化，人们也把这些算法看成1 种新的算法来 进行研究。最典型的代表是遗传编程和摹因表达式编程。 4 四j i l 大学博j 一学位论义 标准遗传算法使用确定长度的_ 进制位串作为遗传编码，即个体的染色 体。通常为了解决雨数优化问题需要将位串按照定的长度进行划分，每。 段表示个分_ 晕= ，然后利用位段译码函数映射到每个分最的定义域卜。存其 他世应用中，则需要对_ 进制位串进行编码使其代表相应问题领域的特定意 义。 存标准遗传算法中，最丰要的遗传操作是重组算子，有些文献也称为杂交， 或者交叉算子。雨绍算子以定的概率，即重组概率，作用在两个父代染色体 ：，产牛两个新的子代染色体。承绢的概率般都选择得比较大，在f 0 6 ，1 0 1 之间。匝绢算予中最重要的是单点重组算子。当进行单点重组算子操作的时 候，随机产牛个交义点，然后，交换交义点后的染色体部分，形成两个子代染色 体。通过选择更多的交叉点，并变替地交换交义点之间的位段，可以将单点晕 组扩展到1 1 1 点重组算子。另外，也有人捉山一些其他的重组算子，比较有特色 的是一致重组算子1 4 1 。一致重组算子把两个父代的位串上的每一位都执行一 个随机判定来决定是否交换信息。标准遗传算法具有比种群规模大得多的隐性 并行搜索能力。这在很大稗度上都得益于重组算子。 变异算子也被标准遗传算法所采用、但它一般被看成是辅助算子。变异算 子作用在单个染色体上，以一 定的概率，即变异概率改变位串上每一位，变异概 率一般都选择得比较小，通常在o o o l ，o 叭1 之间，并且不依赖于目标变量的位 数和位串的总长。变异算子在标准遗传算法中被认为是次要的算子，这和其他 两个独立提山的进化计算算法进化规划( 见2 4 1 节) 进化策略( 见2 4 2 节) 都不 一样。标准遗传算法认为，变异算子的作用主要在于保持种群的多样性，防止 种群过早地收敛到同一个，或者相似的染色体上。( 这种现象称为早熟现象，是 遗传算法研究中的一个重耍问题) 而不承担主要的进化动力的作用。 标准遗传算法中采用的是一种依据概率复制的选择算子。每一个个体被选 择复制到下一代的概率由该个体的适应度值决定。适应度值高的个体被选择的 可能性高，适应度值低的个体被选择的可能性低。常用的选择算予有比例选择、 锦标赛选择等等。比例选择算了仆选择概率和适应度成正比，适应度值低于一 定的闽值的个体选择概牢为o 。通常认为，比例选择算了有较强的选择能力，容 易使标准遗传算法以太快的速度收敛到局部最优。另外一种使用较多的选择算 了是锦标赛选择算了。锦标赛选择算了指定一个联赛规模n ，然后每次随机从 5 四川大学1 尊学位论义 父代种群q | 选择 个个体进 j ：蛾懿、? 1 个个体c p 适应皮最大的个体被选择复制， 然后再进行下次联赛选择p个子代个体。由于锦标赛选择算于每次进行联 赛的时候，只比较个体之间的相对适应度、因此、这是种相对选择算子。联赛 规模越小，锦标赛选择算子的选择压力越弱适应度较低的个体越有机会被选择 复制到下代。总的来说，锦标赛选择算子对于防1 l ：标准遗传算法中常见的早 熟现象有很显著的作用，因此，存很多实际应用中，常常采用锦标赛选择算子。 遗传算法己绎得到了广泛应用。采用遗传算法解决旅行商问题是个非常 成功的例子。遗传算法所能解决的旅行商问题的规模已经远远超过普通确定性 算法所能解答的规模。存作、l k 调度、白动控制、机器学习等领域遗传算法也有 非凡表现。存实际丁程应用中，通用电器公司和r e n s s e l a e r 综合技术学院的研 究人员成功地将遗传算法应用到了种商、i k 客机等使用的高函道比喷气发动机 的涡轮设计之中【1 1 1 。作者所在的课题绸则成功地将遗传算法应用于低泄漏核 反应堆堆芯优化装载f 3 9 1 。在此之前，核反应堆专家利用一个可视化的工具对 反应堆堆芯装载进行人工分析、凭借专家的经验通常需要数周的时间才能找到 一。个相对比较满意的装载与+ 案。而采用遗传算法的自动优化装载稗序，则只需 要几十个小时的时间就能找到比专家手工得到的更好的方案。 2 3 遗传编程 遗传算法的最重要特女r 之一，足采用经过编码的符号串作为个体的遗传编 码。特别是，标准遗传算法采用了定长的二进制编码来表示染色体结构。这种 表示形式具有通用性好，遗传操作非常简甲等特点。针对不同问题，各种改进 的遗传算法编码方法能解决很多具体问题。 遗传编程( g e n e t i cp r o g r a n a m i n g g p ) ，也称为遗传程序设计，或遗传规划， 足在遗传算法的基础上发展起来的，它采用了一种全新的个体捕述方法，其实质 是采用层次结构来拙述解决问题的计算机程序。因此，遗传编程是程序白动牛 成技术的利嚣。 存遗传编程中，构成染色体结构的丰要元素是函数集合和变常最集合。染 色体结构存仞始化以及进化的过程中根据问题的具体要求，在指定的函数集合 和变常最集合中选定符号构成树形结构的程序。树形结构的遗传编码是遗传 6 四川大学博上学位论义 编程的重要特征。 作为进化计算的成员，遗传编程中也有系列的遗传算子，例如，重组算子， 变异算子等等。这螋遗传算子直接作用在树形结构卜，例如，常用的重组算子 随机选定两棵父代个体的程序树中的节点，然后交换以选定节点为根节点的子 树。 由于遗传编程能处理树形的程序结构，所以遗传编程已经被广泛应用十优 化控制，符号回归，公式发现等领域。虽然遗传编程有很广阔的前景，但它也存 存很多不足，例如，它亢接处理树彤结构、效率低下代码膨胀影响搜索效率等 等。 2 4 相关的其他算法 受到生物进化的启发的进化计算算法，除了遗传算法，遗传编程外，还有一 些也很有特色的算法，比如进化规划，进化策略等。这些算法和遗传算法或多 或少有一些相似之处，但各自强调的的侧重点又各不相同。这些算法都有一些 自己的优势应用领域，所以不易横肉比较。 2 4 1 进化规划 6 0 年代中期，p o g e l 等人为了解决有限自动机的演化预测问题，提出了进化 规划算法( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 【2 8 】。进化规划在原理司遗传算 法相似，也是仿真生物进化的过程，将生物界中“优胜劣汰”规律引入到实际中， 解决目标函数或约束条 ：不可微的复杂的非线性优化问题。但进化规划和遗传 算法还是有很多重要区别。在进化规划中，问题的解虽然仍用数字串表示，但 不像标准遗传算法那样要转换成二进制。进化规划一般采用一种比较直观的疔 ，直接用问题空间的变量作为遗传编码。它的遗传编码的表示方式根据问题 的解的形式来确定，于是，进化规划就不需要编码和译码过程。其次，进化规划 中不采用重组算子，而仪仪利用变异算子。这和遗传算法有本质的区别，遗传 算法认为重组算子是最重要的进化手段。进化规划则认为，仅仅通过变异就能 够维持种群的进化。这一点也使得进化规划采用问题空间的变量直接作为遗传 编码变得很容易，因为在很多情况下，如何定义非二进制编码的重组算子是一件 7 四川大学博上学位论义 很棘手的事情。 进化规划没有采用i 进制编码其变异算子也定义得比较有特色。标准进 化规划采用高斯变异算子。对个个体进行变异的时候，在其每一个分母卜加 r 个变异骨= 6 。变异鼋：6 是、r 均值为0 ，方筹为o - 2 的随机变：早= 。而j 的取 值则根据个体的适应度来确定。高斯分布的方著反映了分布分散的程度，对适 应度越大的个体，其变异晕有越小的趋势，而适应度越小的个体，其变异晕有越 大的趋势，这比较符合牛物进化过程。 存很长一段时间内，进化规划虽然在研究应用卜有些进展。但人t 智能学 界对于进化规划大多抱以怀疑的态度。现今的进化规划不再限定以有限状态机 作为单元结构。而是根据所对应的问题，来设定单元结构和变异操作。因此在 处理数值问题的进化规划，所采取的机制就和进化策略很类似。现在已被广泛 用在组合优化，函数优化，自动控制，游戏理论，路径规划等问题上。 2 4 2 进化策略 1 9 6 5 年，r e c h e n b e r g 为了解决流体力学中模型控制里实数参数最优化的问 题，提出了第一个实验性的进化策略( e v o l u t i o ns t r a t e g y ，e s ) 方法。因为工程 上的一些非线性模型的数值问题，无法用传统的数学线性方法求解。后来他 与s c h w e f e l 合作提出了一种新的方法运用计算机以求解决问题，这就是进化策 略。进化策略已经在非线性优化，系统识别等方面显示出比传统经典方法更加 强大的能力。在机器学习，自动控制等方面已经可以解决了用传统方法较难解 决的统汁优化问题。 进化策略源自于从这样一个简单的自然进化模型：一个群体由目标函数搜 索空间中的一个测试点集组成，群体中每个个体的适合度由其所对应的测试点 的目标函数值所确定。每个个体的繁殖率依赖于该个体在当前群体中的相对适 合度，根据繁殖率及选择算子在该群体中选择出双亲( 测试点) ，这些选出来的双 亲可以通过重组和变异产生后代。重组是随机地合并双亲的遗传信息的，而变 异是随机地改变遗传信息的。进化策略着重研究子代与父代行为特征之间的联 系，而遗传算法着重研究子代与父代基因之间的联系，即进化策略和遗传算法之 间的本质区别在于：遗传算法是对变量的编码串操作，而进化策略则是对变量本 身操作。 8 四川大学博上学位论义 每个进化策略个体由纲实数数值参数所构成，最早的进化策略非常简单， 类似随机搜寻、被称为1 + 1 进化策略，其中只有两个唯7 亡。并以机率的观点， 发展了关j ：突变的1 5 成功率规则。后来又发展了多无进化策略肛十。进化策 酶和儿“进化策略。更使控制进化的策略参数、也加入随着各单元同进化。 进化策略中的变异算子也采用高斯算子，商接存个体的各个分_ 晕= 卜加卜符 合高斯分布的随机变母。向蕈组算子则作用存两个个体卜，根据随机产牛的重 组率将两个个体的分冒进行融合。比较特别的是，进化策略采用的选择算子 是壳伞确定的算法。以确定选择指定数角= 的最优个体进入下代种群。这种 选择算子可以保自f 性能的单调提离，但电抛弃了具有良好潜力的个体，使锝算法 容易收敛到局部最优。 根据牛物进化的现象r e e h e n b e r g 归纳出以下的结沦：“进化会使牛物过程 达到最件化，而进化本身也是一种生物过稗，所以进化必然使本身也达到最传 化”这种探讨关于进化本身的进化，也就是考虑剑进化的策略。在进化策略的 机制中，单元染色体的重组是发生在表现型，而非在基因型。进化策略中所谓 的表现型就是各个体中的实数参数，而基因型是指在计算机中构成实数的位，其 中的重组是以实数参数为基本单位。而在遗传算法中一般以位为基本单位。 这种观点导致关于在实数参数中，突变强度的探讨，引出了进化窗( e v o l u t i o n w i n d o w ) 的观念。因此在进化策略的程序坐，不止是群体中各单元参数进化，也 将突变强度的策略加入进化调整使其趋入进化窗的区间。这种进化过程被称 为移变进化( m e t * e v o l u t i o n l 。 2 4 3 模拟退火算法 究其发展沿革，模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m 、s a ) 不属于 进化讣算模型。进化讣算的灵感米自于生物的进化，而模拟退火算法则米自于 晶体物质的退火这个物理过程。但是，模拟退火作为一种有效的随机性搜索算 法，和进化讣算算法有很多相似之处，这里稍做介绍。 物理学发现，晶体物质从高温熔化惫逐渐降低温度，粒子逐渐形成低能态的 晶格，当温度卜降速度很快的时候，物质将保持较高的能量状态，这叫做淬火，而 当温度卜降的速率足够缓慢刚，物质将形成最低能量的状态，这个过程叫做退 火。模拟退火算法就是模拟晶体物质的退火过程将问题的求解作为物质的能 9 四川大学博上学位论义 域进行退火。 模拟退火算法从合法的定义域中随机选取个点作为初始态，同时给出 个温度参数。然后慢慢降低温度，同时采用m e t r o p o l i s 算法确定下个状态， 以和状态能量相关的概率接受陔状态。承复进行定的次数，然后再按照。定 的策略降低温度，继续进行状态转移。直到温度下降到定的程度，所有的变 元存温度降低过程中被冰结，或者目标函数的降低速度已经很小，在统计意义卜 该值已经稳定。 值得 ! 辛意的是，模拟退火算法是个单线程的搜索算法，它仅仅依靠。个线 索进行随机化的搜索。所以它的全局搜索能力相对比较弱，搜索容易陷入局部 最优。 2 5 进化计算的本质 由数值分析的角度来看，进化计算可视为随机搜索的优化算法。因为其本 质是非确定性的，所以能搜寻问题空问里所有的可能解答。而在进化计算的 群体r 1 1 ，大量个体随着环境的变化，进行变化，选择，进而形成各种各样的个 体。不同个体也就代表了用以解决问题的不同途径与其信息，进化计算含有多 样性以觯决问题的能力。在很多复杂的非线性的问题上，没有现成的可利用解 析方法，进化计算便成为最有效的分析手段。 由自然进化的角度来看，进化足在动态变化的环境下的一种适应过程，而 并非在静态环境下的最优化过程。在进化过程r 1 的系统有趋向复杂的倾向。 因此进化可理解为适应性复杂系统的变化过程，同时也足在生命与智慧本质中 的必要的基本过程。由物理的观点来看，复杂是产生在非线性动力学里介于混 沌与秩序问的现象。复杂带来信息的产生与变化。经典物理学中描述运动的 动力学足确定性的，无法捕述进化过程。但热力学里，处于非平衡状态的耗散 性结构却可以描述进化过程。而动力学和热力学问的歧异，也就蕴含着关于进 化本质的最大奥秘。 存大自然罩的牛物并非由单简单的机能形成而是由大蜒的个体聚集的 复杂系统所构成。牛物形成的复杂系统会随着环境改变，适应环境，从而“寻 求”牛存。所以牛命现象以及由其衍牛的智慧行为，是适应性复杂系统的表 l o 四川i 大学博_ l 学位论义 现。由适应性复杂系统的观点，可以归纳出四项牛命智能的基本特质一复杂 进化，交感，适应。这四项特质彼此相依相存，只是牛命本质的不同方式早现。 2 6 基因表达的生物学背景 基因表达式编程的灵感来自于生物i i ，的瑟因表达过程。这里简要介绍基因 表达的生物学背景。 基因是遗传的生物学单位。基因决定了生物的显性特征。其t h # 常重要 的部分之一就是指导合成包含生物酶在内的各种蛋白质。基因如何指导蛋白质 的合成是我们所关心的。 简荦来说，在基因表达过程| _ i 有三种重要的物质：d n a ，r n a 以及蛋白 质。基因存在于d n ai hr n a 足i i i 问媒介，而蛋白质是壤终目的。 脱氧核糖核酸脱氧核糖核酸( d n a ，为英文d e o x y r i b o n u c l e i ca c i d 的缩写) ， 又称去氧核糖核酸是染色体的主要化学成分，同时也是组成基因的材料。有 时被称为“遗传微粒”，因为在繁殖过程中，父代把它们自己d n a 的一部分复制 传递到子代扎从而完成性状的传播。原核细胞( 无细胞核) 的d n a 存在于细 图2 l ：d n a 结构示意图 胞质中，而真核生物的d n a 存在于细胞核中，d n a 是由两条单链像葡萄藤那 样相互盘绕成双螺旋形。这种核酸高聚物是由核苷酸链接成的序列，每一个核 菅酸都由一分子脱氧核糖，一分子磷酸以及一分子碱基组成