（计算机应用技术专业论文）基因表达式编程的早熟抑制策略研究.pdf

基因表达式编程的早熟抑制策略研究 计算机技术应用专业 研究生钟义啸指导老师唐常杰教授 9 9 3 7 7 0 数据挖掘已经成为当前数据库研究开发和应用的热点，函数挖掘是数据 挖掘技术的重要研究方向。进化计算常常被用于自动的函数关系发现，基因 表达式编程( g e p ) 具有编码简单，适应性强的优点，同时继承了遗传算法的简 单性和遗传编程求解复杂问题的能力，但传统g e p 有可能陷入局部最优的未 成熟收敛的“早熟”陷阱。为解决这一问题，本文做了如下主要工作： 1 ) 分析了g e p 早熟现象，用实验验证了早熟现象对函数挖掘的影响； 2 ) 借鉴生物界的“返祖现象”，引入回溯机制，提出基于回溯策略的g e p 算 法( g e p m t hb a c k t r a c k i n gs t r a t e g y ，g e p b s ) ；提出回溯检查点概念，设 计了等比递增捡查点序列和加速递增检查点序列用于约束回溯过程： 3 ) 扩充基于回溯的g e p 算法和四个抑制策略( a ) 退化因子( r f ) 策略。( b ) 比纸叵溯策略( g e pw i t h p r o p o m o n a lb a c k t r a c k a n gs t r a t e g y ，g e p p b s ) ：( c ) 自适应的画溯策略( g e pw t hs e l f - a d a p t i v eb a c k t r a c k i n gs t r a t e 9 3 g e p s b s ( d ) 疏剪策略借鉴植物人工培育的“疏剪方法”，在传统g e p 算法的进化过程 中引入疏剪镱略( g e p v a t h p r u n i n gs t r a l e k v , g e p p s ) 帮助种群进化活动； 4 ) 分析进化过程中种群构成特点，提出种群多样性度量标准( d i v e r s a y m e a s u r ec r i t e r i o n ) ，并结合前几和早熟抑制策略提出基医表达式编程的种 群多样性保持策略( g e pd i v e r s i t yr i f t a ms t r a t e g y ，g e t d r s ) ； 5 ) 通过若干实验验证了以上算法能有效地改善传统算法在进化过程c p 的早 熟现象。提高g e p 自动函数发现的成功率。 本文的组织如下：第一节介绍了数据挖掘的理论基础与应用范围，并介 绍了函数发现的目标、一般步骤和挑战；第二节介绍了本文研究的进化计算 背景，分析了遗传算法、遗传编程等典型模型的特点和应用范围；第三节介 绍了基医表达式编程的基本思想和概念，分析了其固有缺陷；第四节分析了 g e p 的早熟现象，并用实验验证了早熟现象对函数挖掘的影响；第五节给出 了几种针对早熟现象的抑制策略，其效果在第六节中分别用四个实验验证。 关键词早熟回溯策略画溯检查点退化因子部分叵溯策略自适应 叵溯策略疏剪策略多样性度量多样性保持策略 r e s e a r c ho fr e s t r a i n ts t r a t e g yf o r g e p p r e m a t u r i t y s p e c i a l t y ：c o m p u t e rs c i e n c e p o s t g r a d u a t e ：z h o n g y i x i a os u p e r v i s o r ：p r o ft a n gc h a n g j l e d a t an m u n gh a sa l r e a d yb e e nah o ti s s u ei nr e s e a r c ha n da p p h c a t i o no f d a n b a s er e a l ma m o n gv a r i o u sd a t an m n gt e c h n o l o g i e s ，f u n c t i o nm m m gi sa l l i m p o r t a n ta n dp r o n - a s m gb r a n c h e v o l u t i o n a r yc o m p u t i n gi so f t e nu s e d f o r f u n c t i o n n a n m ga m o n g v a r l o t l se v o l u t i o n m o d e l s ，g e n ee x p r e s s i o n p r o g r a m m i n g ，w l 1 l c hc o m b i n e st h es i m p l es t r u c t u r eo fg a a n dt h ea b l l qt os o l v e c o m p l e xp r o b l e t 惜o fg p , m a m t a i ns m a p l ee x p r e s m o na n dh l g ha d a p t a b i l i t y , h o w e v e r , t r a c h u o n a lg e pa l g o n t h mm a y f a l l ss h o r ti nal o c a lo p t i m u mp i t f a l l k n o w na sp r e m a t u r ec o n v e r g e n c ep r o b l e m i no r d e rt os o l v et h i sp r o b l e m , t t u sp a p e rh a sd o n et h ef o l l o w i n gw o r k ： ( 1 ) a n a l y z e st h ep r e m a u a t t yo f g e p a n dd e m o n s t r a t ei t sr o d e - e f f e c to ng e p f u n c t i o nm m m g 。 ( 2 ) p r o p o s e san o v e lg e pn z t h o db a s e d0 1 1b a d 啊a c k m gr e f e r r i n g t ot h e = a v m mmt h e b i o s p h e r e p r o p o s e s t h ec o n c e p to fb a c k t r a c k i n g c h e c k p o t n ta n dd e m g n m gg e o m e t n cp r o p o r t t o ni n c r e a s e dc h e c k p o i n t s e q u e n c 2a n da c c e l e r m e di n c r e a s e dc h e c k p o i n ts e q u e n c et or e s t n c tt h e 娥r a c k m gp r o c 嚣s ( 3 ) e x t e n d s t h eg e p b s a l g o n t h m a n df o re o r a r o l s t r m e g y ：( a ) r e t r o g r e s s i o nf a c t o r ( r f )s 仃m e g y ；( b ) g e p v a t hp r o p o m o n a l b a c k t r a c k m gs t r a t e g y ( g e p p b s ) ；( c ) s e l f - a d a p u v eb a c k t r a c k i n gs t r a t e g y ( g e p s b s ) ；( d ) p r m u n gs t r a t e g y t h t ss t r a t e g y i sb a s e do nt h ep r i m i n g m e t h o di n a r t l f i e t a lc u l t i v a t l o ni n t ot r a d i t i o n a lg e pa l g o n t h ma n dt o h e l pt h ee v o l u t i o no f g e pp o p u l a u o n ( 4 ) a n a l y s e st h es t r u c t u r eo fp o p u l a t l o nd u r i n ge v o l u t i o np r o c e s sa n d p r o p o s e sad i v e r s n ym e a s u r ec n l e n o r tp r o p o s e san e wg e pd i v e r s i t y r e t a i ns t r a t e g yb a s e do nt h ec o m b m a t l o no ft h ep r e c e d i n gp r e m a t u n w r e s t r a i n ts w a t e g l e s ( 5 ) d e m o n s t r a t e st h ee f f e c t i v e n e s so ft h en e wa l g o r i t h m sa n ds t r a t e g i e si n r e s t r a i n to f g e p p r e a n a t u n t yb ye ! 】( t e n s i v ea x p e r i m e n t s 佻p a p e r i s o r g a n i z e da sf o l l o w s ：s e c t a o n 1i n t r o d u c e st h et h e o r i e sa n d a p p l i c a t i o n so fd a t am m m ga sw e l la st h ep u r p o s e , p r o c e s sa n dc h a l l e t _ l g e so f f u n c t i o nn m a m g s e c u o n2j 1 】i r o d u c e st h eb a c k g r o u n do f e v o l u t i o nc o m p m i n ga n d a n a l y s e st h ec h a r a c t e r t s t t e sa n da p p l i c m l o n so fg e n e t i ca l g o r i t h ma n dg e n e u c p r o g m n m - a n g s e c n o n3i n t r o d u c e st h ef u n d a m e n t a li d e a 锄dc o n c e p t so fg e n e e x p r e s s i o np r o g r a m m i n ga n d i t si n t r i n s i cd e f e c t s s e c t i o n4a n a l y s e st h e p r e m m u n l yo f g e pa n dd e m o n s t r a t e si t ss i d e e f f e c to nf u n c t i o nm m m g s e c t i o n5 p r o p o s e saf e wp r e m a a m t yr e s t r a i n ts t r a t e g m sa n ds e c t i o n6d e m o n s t r a t e st h e i r e f f e e t i v e n e s sb ye x t e n s i v ee x p e r t r n e n t s k e yw o r d s ：p r e m a t u n t y , b a c k t r a c k i n gs t r a t e g y , b a c k t r a c k i n g ，c h e c k p o i n t r e t r o g r e s s i o nf a c t o r , p r o p o r t i o n a lb a c k t r a c k m gs t r a t e g y ,s e l f - a d a p t i v e b a c k t r a c k i n gs t r a t e g y , p r u n i n gs t r a t e g y , d i v e r s i t y m e a s u r ec r i t e r i o n , d i v e r s a yr e t a i ns t r a t e g y ， 稠川大学 硕士生毕业论文 弓l 言 数据库和数据挖掘技术己对人类世界产生了深刻的影响，并广泛渗透到 了现代科学的各个分支中。在现代数学、物理学、生物学、化学等自然科学 领域，数据库和数据挖掘技术日益广泛的使用极大地提高了科学研究和生产 的效率。 我们正处在一个信息爆炸的时代。统计表明，早在二十世纪八十年代， 全球信息量每隔2 0 个月就要增加近一倍。进入九十年代后，技术飞速发展使 各类机构所拥有的数据量更加急速地增长。2 0 0 3 年，加州大学伯克利分校的 研究人员称，仅过去3 年中，全球新生产出的信息量就翻了一番。在大量的 数据背后，隐藏着许多重要的信息。如何把这些信息抽取出来，形成可供人 们利用的知识和规律，成为一个重要的研究溧题，并且在过去的十余年中建 立了一个新的学科一数据挖掘( d a t a m i n i n g ) 。 数据挖掘的研究范围包括函数关系发现、分类、聚类、时间序列挖掘等 方面，其中函数关系发现是本文关注的重点。函数关系发现是数据挖掘领域 中的重要研究方向之一，并可应用于现代数学、生物学、经济学、人口学等 科学研究领域和公司客户数据分析、财务数据分析等商业应用领域。这些应 用又对函数关系发现的研究起到了积极的推动作用。 目前数据挖掘研究领域中己出现多种函数关系发现技术，包括最d , - 乘 法、泊松回归、对数回归等。在进化计算领域。自动函数发现成为一个研究 热点。近年来葡萄牙科学家c a n d i d af e r r e i r a 在进化计算领域开辟了个新的 分支基因表达式编程( g e n ee x p r e s s i o np r o g r a m m i n g ，g e p ) ，它使自动 函数发现技术产生了一个飞跃。 实践中发现，基因表达式编程也存在着一些固有的缺陷，在实际问题中 可能影响实验结果。本文关注基因表达式编程的早熟( p r e m a m d t y ) 现象， 借鉴自然界早熟现象的内在原因，提出了几种有针对性的改进算法。实验表 明，这些算法能够有效地抑制基因表达式编程的早熟现象，提高自动函数挖 掘和知识发现的成功率。 四j 大学 硕士生毕业论文 1 数据挖掘简介 知识获取是信息处理的关键问题之一。 在现代社会中，科研、企业机构的大多数工作滤程的核心部分是数据。 由于信息技术的飞速发展，全球信息总量呈几何级数增长。现代企业和科研 机构往往会积累大量的数据资料，如商业企业一般会收集大量有关市场、客 户、竞争对手的资料，科研机构、高等院校的实验数据、实验记录等也会随 时间的积累越来越多。随着数据量的急剧增加，如果不能有效地整理和利用 这些数据，不能对数据进行分析处理，我们就会迷失在数据的海洋里，拥有 了海量数据却缺乏有效的信息。不能作出正确的判断。因此，一种能从海量 数据中抽取知识和规律的技术成为急需。 数据挖掘的任务就是在海量数据中发现有用的规律，建立可靠的模型， 对未来趋势作出分析和预测。数据挖掘通过综合运用统计学、粗糙集、模糊 数学、机器学习和专家系统等多种学习手段和方法，从大量的数据中提炼出 抽象的知识，从而揭示出蕴涵在这些数据背后的客观世界的内在联系和本质 规律，实现知识的自动获取。按照j i a w e ih a n 的定义，数据挖掘是从大量数 据中提取或“挖掘”知识。具体地说，数据挖掘就是从大量的、不完全的、 有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、 潜在有用的信息和知识的过程1 1 i 。 数据挖掘技术是信息技术演化的必然结果。面对数据拥塞，知识贫乏的 挑战，数据挖掘和知识发现技术应运而生，蓬勃发展，并日益显示出了广阏 的应用空间和强大的生命力。 1 1 数据挖掘的产生及其实质 数据挖掘技术由信息爆炸推动而产生，是人们长期对数据库技术进行研 究和开发的结果。起初，各种数据是存储在计算机的数据库中的，然后发展 到可对数据库进行查询和访问，进而发展到对数据库的即时遍历。随着提供 四j 1 1 大学妒十牛毕业论文 高吞吐量查询衣事务处理的大型数据库系统大规模投入应用，自然产生了对 数据进行分析的要求。可见，数据信息化技术经历了从简单数据收集到数据 库的创建羊c 数据库管理，再到数据的分析和理解的过程，这恰恰可以看作数 据挖掘产生的历程。数据挖掘使数据库技术进入了一个更高级的阶段，它不 仅能对过去的数据进行查询和遍历，并且能够找出数据之间的潜在联系，得 到知识和规律供人们利用。 表1 ，l 可以简单说明数据挖掘的进化历程： 表11 数据挖掘的进化过程 原始数据可以看作是知识的“源泉”。原始数据可以是结构化的、半结构 化的、甚至可以是网络上的异构数据。它几乎可以在关系数据库，数据仓库、 w e b 数据、多媒体数据等所有常用的数据格式上进行。 数据挖掘是多个学科成果综合运用的结果。它可以从多个不同的视角观 察数据，提取有趣的知识和规律。这些知识和规律可以被用于数据管理、查 询优化、决策支持，过程控制等。因此，数据挖掘被认为是信息产业最重要， 最有前途的交叉学科之一。 数据挖掘从诞生开始，就是面向应用的。它不是生物学家实验室里的小 四川大学硕士生i 釜业论文 白鼠，不仅仅是面向狭窄的简单查询或管理，而且要对数据进行宏观的统计、 分析、综合和预测。而这些工作都是为了指导实际问题，利用已有的数据来 对未来的趋势和行为进行预测，从而支持决策行为。同时，由于数据挖掘承 担了大量消耗时间的任务，使人们能够从简单繁琐的工作中解放出来，以便 进行更有创造性的工作。 1 2 数据挖掘的功能 在数据挖掘作为一个学科而产生的历史上，曾经有过命名之争。有学者 指出，数据挖掘既然是指发掘隐藏在数据中的信息，如趋势、特征及相关性 的过程，即从数据中发掘知识，就应当更正确地命名为“从数据中挖掘知识”。 也有学者将数据挖掘视为另一个常用的术语数据库中“知识发现”或 “k d d ”( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) 的同义词。而另一些学者把数据 挖掘视为k d d 的一个基本步骤。k d d 由数据清理、数据集成、数据选择、 数据变换、数据挖掘( k d d 的基本步骤，使用智能方法提取数据模式) 、模 式评估和知识表示组成。 事实上，“数据挖掘”和“知识发现”讲的是同一件事情，但是是从两个 不同的角度来说明。“数据挖掘”主要从行为上界定了从数据中寻找知识和规 律的概念，而“知识发现”主要是定义了数据挖掘的功能。数据挖掘的功能 就是要从指定的数据中找出需要的模式类型。 知识可以分为很多种类。包括反映事物共同性质的知识、反映事物之间 关联的知识、反映事物特征的知识，反映事物差别的知识、反映事物异常的 知识、根据历史数据预测未来的知识。这些不同类型的知识隐藏在海量数据 中，可以在不同的概念层次上被发现，以满足不同层次、不同用户的决策需 要。其中，描述( d e s c r i p t i o n ) 和预测( p r e d i c t i o n ) 是最主要的两和知识发 现方式。 描述是对数据库中数据的种归纳，通过统计和抽象提取出数拐的一般 特性；预测是对数据的一和演绎，在当前数据上进行推断，并预言耒来的趋 势。一些经典的数据挖掘例子，如啤酒与纸尿布规律、证券交易所指数，都 四川大学 硕士生毕业论文 同时涉及了这两种方式。 通过数据挖掘，我们可以实现多种应用功能，包括： 关联规则 啤酒与纸尿布规律是典型的关联规则应用。关联规则是描述事物之间同 时出现的规律的知识模式。 分类 从数据中选出己分好类的训练集，在该训练集上分类技术能够挖掘分类 模型，把未分类的、无序的数据通过分类器分别映射到几个给定的类上，从 而可以应用于数据预测。分类器一般没计为一颗分类树，根据数据各个属性 的值从树根开始搜索比较，沿着属性值满足的分支向下走直到叶结点，即可 确定类别。 函数回归 函数回归和分类一样被认为是数据挖掘中被使用得最普遍的模式。所不 同的是函数回归是对数据进行函数拟合，其目标值是连续的，而分类的预测 臣标是离散点。 聚类 聚类的功能同样是要将数据映射到几个类型的集合中，但不同的是聚类 属于无监督学习，它不依赖于预先定义好的类，不需要训练集。进行聚类前 并不知道烤要把数据划分成几个类，或者划分成什么样的类。聚类所做的工 作是使类间的差男c 尽可能大而类陡差别尽可能小，对聚类结果给出类标号， 以此来实现无监督的分类。 时间序列预测 时间序列预测根据数据随时间变化的趋势预测将来的值。它通过对数据 进行汇总和分析找出时间序列观测值中的规律与变化趋势，然后通过这些规 律和趋势的外推来确定未来的预测值。 1 3 数据挖掘中的结果评价 并非所有数据挖掘产生的模式都是有趣的。对于特定用户，可毹只有一 四川大学硕士生毕业论文 小部分模式是他感兴趣的。这就对数据挖掘系统提出了一系列要求，如可理 解性、可重现性、有用性、新颖性。由于这些要求比较抽象，人们又定义了 一些衡量模式兴趣度的客观度量。这些度量是基于模式的结构氍统计。 一种广泛使用的客观性度量是支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 。 以关联规则x = y 为例，规则的支持度表示满足规则的样本的百分比，其值 为概率f ( x u y l ，其中( x u y ) 表示同时包含x 和y 的事务，睇项集x 和y 的并集；置信变表示的值为条件概率p ( x ，即包含x 的事务也包含y 的概 率。形式化的支持度和置信度定义如下： s u p p o n ( ) 【= y ) = p ( x u c o n f i d e n c e ( ) ( = = p ( y i ) ( ) 每个兴趣度度量都与一个阈值相关并可以由用户控制。一般支持度和置 信度均高于阈值的规则被认为是有趣的。支持度和置信度中任一者低于阈值 的规则反映的是异常、少数或噪声的情况，通常认为不太有价值1 。 当然，数据挖掘系统不可能产生所有的模式，应根据用户提供的限制和 兴趣度对搜索聚焦。对于某些数据挖掘任务，这通常能确保算泫的完全兰。 关联规则挖掘中支持度和置信度的限制就是一例。 数据挖掘的优化问题对用户也是至关重要的。对于数据挖掘系统，仅产 生有用的模式是非常期望的，因为这样就不需要搜索所有产生的模式柬识别 有趣模式。然而，这和优化至今仍是个挑战。 1 4 函数挖掘简介 本文关注的重点是函数挖掘。 函数挖掘是数据挖掘的重要分支，它的目的是发现描述数据或趋势的函 数，以便能够使用函数模型进行预测。 科研和工程中不仅需要对大量的数据定性分析，而且需要对它们进行定 1 并非所有人都认为支持度和置信度较低的规则没有价值。事实上，曾经有入研究利用低 支持度的规则进行孤立点检测。如u s i n ga s s o c i a t i o nr u l e sf o rf r a u dd e t e c t i o ni n w e ba d v e r t i s i n gn e t w o r k sv l d 8 0 5 四川大学 硕士生毕业论文 量分析。这些常常会用到函数挖掘。这类问题是根据得到的若干有关变量的 一组数据，寻找因变量与自变量之间的一个函数，使该函数对那组数据拟合 得最好。 函数挖掘通常包括下列步骤： c 1 ) 变量选择判断哪些自变量的影响是显著的，哪些自变量的影响是不 显著的，将影响显著的自变量选入模型中，而剔除影响不显著的变量； ( 2 ) 拟合从一组数据出发确定某些变量之间的定量关系式，郾建立函数 模型并估计其中的未知参数； ( 3 ) 估计与检验估计函数模型中的未知参数，并且对模型提出的各种假 设进行验证； ( 4 ) 预测利用所求的函数对一组输入数值进行预测。 目标函数可以用回归分析统计技术建模。许多问题可以用线性回归解决， 并且更多的可以对变量进行变换，使得非线性问题可以转换为线性的来加以 处理。 t 四川大学矽士生毕业论文 本文研究的进化计算背景 进化计算是目前数据挖掘和人工智能颁域的研究热点。人工智能的发展 有符号主义、连接主义和行为主义等不同的分支，近年来，在各个分支的研 究和应用上都取得了巨大的进展，也各有一些缺陷。为了克服这些缺陷，人 们开始男辟蹊径，转而向大自然学习，从而形成了模拟自然界生物进化的进 化计算。 本文主要关注的基因表达式编程，是进化计算的一个分支，由遗传算法 ( g a ) 和遗传编程( g e p ) 融合而成。 2 1 进化计算介绍 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) ，或称演化计算，其特点是群体搜 索策略和群体中个体之间的信息交换。进化计算以达尔文进化论为依据来设 计、控制和优化人工系统，它包括遗传算法( g e n e t i ca l g o r i t h m ) 、进化策略 ( e v o l u t i o n a r ys t r a t e g i e s ) 和进化规划( e v o l u t i o n a r yp r o g r a m m i n g ) 。尽管它们之 间很相似。但历史上这三和算法是彼此独立发展起来的。 遗传算法是由美国j h o l l a n d 创建，后由k d c j o n g ，j g r e f e n s t e t t e ， d g o l d b c r g _ 衽l d a v i s 等人进行了改进；进化规划最早由美国的l j g f o g e l , a j o w e n s 和m j w a l s h 提出：进化策略是由德国的i r e c h e n b e r g 和 h p s c h w e f e l 建立的。三种算法既有许多柜似之处，同时也有很大的不同。 进化规划和进化策略都把变异作为主要的搜索算子，而在标准遗传算法中， 变异只处于次要地位；交叉在标准遗传算法中起着重要作用，而在进化规划 中被完全省去，在进化策略中与自适应结合在一起使用非常重要；标准遗传 算法和进化规划都强调随机选择机制的重要性，而从进化策略的角度看，选 择是完全确定的，没有合理的根据表明随机选择原则的重要性；进化规划和 进化策略确定地把某些个体排除在被选择复制之外，而标准遗传算法一般对 每个个体都指定一个非零选择磺率。 四川大学母；士生毕业论文 进化计算能够饵决采用传统的方法不能解决的问题，通过输入问题及问 题应满足的条件、结果评价标准，就可以自动得到问题的解，不需要用户的 干预。因此遗传算法、进化策略和进化规划三种算法在工程的应用中各有各 的无可比拟的优势。 2 2 遗传算法g a 遗传算法( g e n e t i ca l g o r i t h m g a ) 是一种崭新的全局优化算法。遗传算法 来自于遗传学和达尔文学说，它模拟生物进化，借用了生物遗传学的观点， 通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这 点体现了自然界中”物竞天择、适者生存”进化过程。1 9 6 2 年h o l l a n d 教授 首次提出了g a 算法的思想，从而吸引了大批的研究者，迅速推广到优化、 搜索、机器学习等方面，并奠定了坚实的理论基础。用遗传算法解决问题时， 首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个 过程就将问题符号化、离散化了。也有在连续空间定义的g a ( g e n e t i c a l g o r i t h mi nc o n t i n u o u ss p a c e ，g a c s ) ，本文暂不讨论。 目前，遗传算法己成为进化计算研究的一个重要分支。与传统优化方法 相比，遗传算法的优点是：群体搜索，不需要目标函数的导数，概率转移准 则。 遗传算法主要用于组合优化问题和规则的自动提取。它具有简单通用、 并行运算、鲁棒性( r o b u s t n e s s ) 强等特点。遗传算法描述如下： ( 1 ) 确定编码方案； ( 2 ) 初始化群体( 确定遗传参数) ： ( 3 ) 计算个体适应度； ( 4 ) 进行遗传操作( 选择、交叉、变异) ，产生新一代个体； ( 5 ) 返回( 3 ) ，直到个体适应度达到要求。 遗传算法的最重要特征之一。是采用经过编码的符号串作为个体的遗传 编码。特别足，标准遗传算法采用了定长的二进制编码来表示染色体结构。 这种表示形式具有通用性好，遗传操作非常篱单等特点。针对不同问题，各种 四j i i 大学 硕士生毕业论文 改进的遗传算法编码方法能解决很多具体问题。 2 3 遗传编程g p 遗传编程( g e n e t i cp r o g r a m m i n gg p ) ，也称为遗传程序设计，或遗传规 划，是在遗传算法的基础上发展起来的，它采用了一种全新的个体描述方法， 其实质是采用层次结构来描述解决问题的计算机程序。因此，遗传编程是程 序自动生成技术的利器。 在遗传编程中，构成染色体结构的主要元素是函数集合和变量，常量集 合。染色体结构在初始化以及进化的过程中，根据问题的具体要求，在指定 的函数集合和变量常量集合中选定符号构成树形结构的程序。树形结构的遗 传编码是遗传编程的重要特征。 作为进化计算的成员，遗传编程中也有一系列的遗传算子，例如，重组 算子，变异算子等等。这些遗传算子直接作用在树形结构上，例如，常用的 重组算子随机选定两棵父代个体的程序树中的节点，然后交换以选定节点为 根节点的子树。 由于遗传编程能处理树形的程序结构，所以遗传编程已经被广泛应用于 优化控制，符号回归，公式发现等饭域。虽然遗传编程有很广阔的前景，但 它也存在很多不足。倪如，它直接处理树形结构，效率低下，代码膨胀影响 搜索效率等等。 2 4 其他进化算法 除了应用最广的遗传算法和遗传编程，进化规划和进化策略也各有特色。 他们各自强调的侧重点不同，应用起来都有自己的适合领域。 进化规划算法直接用问题空间的变量作为遗传编码，它的遗传编码的表 示方式根据问题的解的形式来确定，因此进化规划就不需要编码和译码过程。 进化规划不使用重组等遗传算子，仅采用变异算子，标准的进化规划采用高 斯变异算子。进化规划算法现在被广泛应用在组合优化，函数优化，自动控 1 2 四川大学硕士生毕业论文 制，游戏理论，路径规划等问题上。 进化策略最初用来解决工程上的一些无法用传统的数学线性方法求解的 非线性模型的数值问题。进化策略着重研究子代与父代行为特征之间的联系， 并且，进化策略不像遗传算法那样对变量的编码串进行操作，而是对变量本 身的操作。进化策略已经在非线性优化，系统识男r 等方面显示出比传统经典 方法更加强大的能力。 探究其本质，进化计算是一种随机搜索的优化算法，具有非确定性，并 且拥有强大的解决问题的能力，在很多复杂的非线性问题的求解上，进化算 法都是非常有效的分析工具。 四川大学硕士牛毕业论文 3 g e p 简介及局限性分析 基因表达式编程( g e n ee x p r e s s i o np r o 粤 a m m i n g ，g e p ) 是近年来出现的 新计算模型，结合了d a r w i n 的适者生存理论和随机交换理论，模仿生物进化 过程对问题进行优化求解。适者生存理论消除了解空间中的不适应因素，随 机交换理论利用了原有解中已有的知识，从而加速了对优化解的搜索过程。 g e p 作为进化计算家族中的一支，结合了遗传算法及遗传编程的思想， 融合了两者的优点，能通过简单紧凑的编码解决复杂的应用问题。参加进化 过程的定长线性编码使进化过程简单有效，解码为表达式树使进化结果清晰 明了，具有更强的解决实际问题的能力。葡萄牙科学家c a n d i d af e r r e i r a 于 2 0 0 1 年1 2 月正式发表g e p 的首批研究成果【8 】 9 后受到学术界的高度关注， 一批研究成果枢继闻世【l o 】 1 1 】【1 2 】【1 3 】【1 4 】。g e p 目前广泛应用于函数回归， 时间序列预测，分类问题等领域，并有一些软件相继成功开发面世。 在此基础上，新的g e p 研究成果也不断出现。【1 5 】将g e p 应用于数据挖 掘的典型任务一谓词关联规则挖掘上( p a g e p ) ，并从理论上证明了g e p 中基因编码的有效性： 1 7 】对函数发现这一知识发现形式的特点进行分析， 提出在任意维定义域上的一致表达式挖掘u e m 和分域表达式挖掘m e m ，并 从理论上给出m e m 成功率的证明：f 2 0 把函数挖掘的目标引申到函数集上， 提出箍述能力更强的函数挖掘对象频繁函数集，并提出更加灵活的可配 置频繁函数集挖掘算法c f f s d a 和用户制导的基于约束的可配置频繁函数集 挖掘算法。 2 2 提出g e p 的弱适应模型和带内集，带外集概念，设计了在弱 适应模型下基于相对误差计算适应度的算法r e f a 。 3 1g e p 的基本思想和概念 g e p 技术有两个重要概念：染色体( c h r o m o s o m e ) 和表达式树( e x p r e s s i o n t r e e ，e t ) 。染色体作为承载遗传信息的基因型实体，参与遗传操作；表达 式树作为信息的表现型，表达遗传实体中的信息编码。染色体和表j 左式瓣结 四川大学硕士生毕业论文 构麓草清晰，通过简单的编码和解码规则可以无二义地互相转化。g e p 将这 两者分别作为独立个体，侵遗传操作易于实施，操作结果方便表达，扬长避 短，对g a 和g p 的优点分别加以继承，而舍弃其不足之处。 g e p 的染色体为定长线性字符串，由一个或多个基因( g e n e ) 组成。各 基因以连接符( l i n k o p e r a t o r ) 作用成为整体。基因分为两个域：头部( h e a d ) 和尾部( 强1 ) ，头部包含函数( f u n c t i o n ) 和终结符( t e r m i n a l ) ，尾部只含 有终结符。按照定义，头部长度h e a d 和尾部的长度t r i l l 之间应遵循如下函数 关系： i t a l l i = i h e a c x ( n - 1 ) + l 其中n 为函数集合中所有运算符的最大目数。文献【1 5 】用数学归纳法证 明了在这个规则约束下，g e p 的任何遗传操作总能产生有效基因，有效地解 决了g p 中使用不同大小和形状的非线性实体作为遗传操作的载体所引起的 产生大量语义上不合法的表达式的问题。 g e p 中的实验数据类似于生物的进化环境，染色体在环境中随_ 杌进化， 进化的最终结果即问题的解。通过翻译可以唯一地解码为表达式树的形式。 对一个表达式树进行从上到下，由左至右的层次遍历编码可以得到一个符号 序列，称为k - 表达式( k - e x p r e s s i o n ) 8 】。对k - 表达式进行反方向的解码也 可以唯一得获得表达式树和相应的表达式。 g e p 的染色体和表达式树作为两个不同功能的实体，可以由简单的层次 遍历规则相互转化，这一规则较以往的对树的先根、中根等遍历方法简单， 更容易加以实施。些尾部结点可能不出现在表达式树中，这些冗余结点容 纳将来的遗传操作可能产生的结构变化留下了空f a 1 4 。 借鉴自然界“适者生存”的法则，每一代种群由适应度函数评价，考察 其是否适应进化环境，即数据集。常用的适应度函数有如下两种： n ， 。 = 乏：o f 一| c “，一r u ) 1 ) 乒l 扣兰阻一肾加0 f 1 _ ，= l l 1 j ) i 这两个适应度函数常常应用在函数回归和时间序列等领域，其中前者称 四i i 大学硬士生毕业论文 为基于绝对误差的适应度评价函数，后者称为基于相对误差的适应度评价函 数。基于绝对误差的适应度评价函数无法直接表示出待评价函数或预测值的 相对于理想值的近似程度，因此在实际应用中，基于相对误差的适应度评价 函数使用得更为普遍。这两种评价模型都其自身的缺点，因此，本文在评价 函数挖掘中比较拟合程度时使用了统计学上常用的相关系数( c o r r e l a t i o n c o e f f e i e n t ) ，将g e p 的适应度函数修改为复相关系数的平方值： f t t n e s s = r 2 = 1 一s 姬嚣t 其中： m 观= o ，一夕，) 2 肿= 艺 ，一夕) 2 其中多，表示乃的估计值，夕表示酌平均值，s s e 称为残差平方和，s s t 称为总离差平方和。 每一代的进化结果经适应度函数评价后，适应度高的个体被保留下来， 并有更高的机会繁殖后代，适应度相对较低的个体可能被抛弃。如此循环往， 直到出现满意解或达到预定进化代数，算法停止。 3 2 g e p 的遗传操作和进化方式 g e p 采用了线性等长编码，所以其遗传操作比较类似遗传算法，只要在 进行遗传操作的过程中保持基因长度不变，并符合3 1 中的头尾之间的约束 条件，就能保证后代基因的有效性。 g e p 的遗传操作主要有变异、插串、根插串、单点重组、两点重组、基 因重组等几种。 变异作用在单个染色体上，对染色体的每一位进行随机测试，当满足变 异概率时，则重新产生该位的编码。如果变异位在基因头部，可以重新选择 所有的符号，否则只能选择终结符。 插串是g e p 特有的遗传算子。它随机在基因中选择一段子串，然后将该 子串插入到头部的随机指定的一个位置( 除第一位外) ，将头部的其他符号向 后顺延，超过头部长度的编码将被截去。 四川大学 碗士生毕业论文 根插串是将选择的子串插入到第1 个位置。根插串算子从头部的随机选 择的一个位置开始向后扫描，找到第一个函数，然后以该位置为起始，选择 一段子串，将该子串插入到第1 个位置，头部编码依次后移，超过头部的部 分被截去。 单点重组作用在两个父代染色体上，它随机选择一个交叉位置，互换交 叉点之后的染色体部分，得到两个子代染色体。 双点重组也是作用在两个父代染色体上在染色体上随机选择两个交叉 点，然后互换交叉点之间的染色体部分，形成子代染色体。 基因重组只作用于多基因的染色体。随机选择一个基因，然后交换两个 父代染色体的相对应的基因，形成子代染色体。 g e p 的进化方式即是从上述遗传操作中按概率参数选择其一，作圉于种 群中的每个个体。首先产生一个初始种群，选择算子作用于种群，根据“适 者生存”原则，让适应度较高的个体有更高的机会生存。遗传算子作用于种 群，在种群的个体之间进行遗传操作，产生出新的子代个体。g e p 除了继承 了g a 中的变异、单点重组、两点重组外，还具有插串