毕业设计（论文）基因表达式编程在数据压缩中的应用

1、本科毕业设计说明书（论文） （2011 届）届） 论文题目 基因表达式编程在数据压缩中的应用 作者姓名 指导教师 学科(专业) 所在学院 提交日期 浙江工业大学本科毕业设计说明书（论文） i 摘要摘要 各行各业的发展产生了大量的数据，如通话记录，股票数据，气象监测等 数据都可以看成数据流。为了挖掘蕴藏在这些数据流中信息的价值，需要一种 有效的数据流压缩技术对其进行压缩，以减少这些数据流对存储空间的需求， 而传统的压缩技术难以满足这些数据流的存储需求。 基因表达式编程(gene expression programming, gep)融合了遗传算法和遗传 程序设计的优点，编码简单，易于进行遗传修

2、饰操作，具有结构和功能的多样 性。在解决复杂的函数发现等问题上，gep 表现出优越的性能，在科学计算和 商业应用等领域取得了广泛的应用。 本文利用 gep 在函数发现上优越的性能，探索多数据流的压缩算法，提出 了一种基于 gep 的多数据流压缩算法。通过 gep 编码和遗传算子的设计，演化 出主、从存储数据流中数据元素之间的函数关系，使得在存储这些数据流时， 只需存储主存储数据流和对应的函数关系表达式，从而达到数据压缩的目的。 本文所采用算法在保证原数据和重构数据具有相同可用性的前提下，虽然数据 精度稍有损失，但获得了较高的压缩比。 通过实验验证，基于 gep 的多数据流压缩算法是可行的，当数

3、据流元素存 储于数据库时，该算法的压缩比接近，为数据流条数，而当数据流存储1nn 于文件时，经过该算法压缩的文件能用其他压缩软件进行二次压缩，从而达到 更高的压缩比。 关键词：关键词：基因表达式编程，数据流，数据压缩，压缩比 浙江工业大学本科毕业设计说明书（论文） i abstract the development of all walks of life gives birth to large amounts of data, such as call records, stock data, meteorological monitoring data and so on, and t

4、hey are regarded as data streams. in order to mining the valuable information in these data streams, an effective data stream compression technology is badly needed, and this compression technology must be able to reduce the storage space of these data streams significantly. but the traditional comp

5、ression technologies cant meet the demands of these data streams. gene expression programming(gep) incorporates both advantages of genetic algorithm and genetic programming. gep is simply coded, easy to run with genetic operators, and it also has the structural and functional diversities. in solving

6、 complex problems such as function discovery, gep shows excellent performance and be widely used in scientific computing and commercial application. taking advantage of the excellent performance of gep in function discovery, this paper explores the storage means of multiple data streams, proposes a

7、multiple data streams compression algorithm based on gep. by coding the gep and the design of genetic operators, the functional relation between the main data stream and the subordinate data stream is evolved, it makes that only the main data stream and subordinate data streams are needed when stori

8、ng these data streams, and thus reaches the goal of data compression. guaranteeing the original data and the reconstructed data have the same information value, this compression algorithm reaches a high compression ratio by sacrificing some accuracy of the data. verified by the experiment, the multi

9、ple data streams compression based on gep is feasible. when the data streams are stored in the data base, the compression ratio is close to , means the amount of the data streams, and when the data streams are 1nn stored in files, the files compressed by this algorithm also can be compressed the sec

10、ond time by other compression technology, thus reaches a higher compression ratio. 浙江工业大学本科毕业设计说明书（论文） ii keywords：gene expression programming, data streams, data compression, compression ratio 浙江工业大学本科毕业设计说明书（论文） i 目录目录 摘要摘要.i abstract.i 第一章第一章 绪论绪论.1 1.1选题的背景 .1 1.2选题的价值与意义 .2 1.3研究开发的主要内容 .2 1.4研

11、究开发的目标 .3 1.5本文的组织结构 .3 1.6本章小结 .3 第二章第二章 基因表达式编程基因表达式编程.4 2.1遗传算法类概述 .4 2.1.1遗传算法.4 2.1.2遗传程序设计.4 2.1.3基因表达式编程.5 2.2gep 算法流程 .5 2.3gep 的实体 .6 2.3.1染色体和基因型.6 2.3.2表达式树和表现型.7 2.3.3gep 的多基因染色体.8 2.4适应度函数 .10 2.5遗传算子 .11 2.5.1选择和复制.11 2.5.2变异.11 2.5.3转移.11 2.5.4重组.11 2.6本章小结 .12 第三章第三章 基于基于 gep 的多数据流压缩

12、算法的多数据流压缩算法.13 3.1数据压缩的相关概念 .13 3.1.1数据压缩定义.13 3.1.2数据压缩原理.13 3.1.3数据流基本概念.13 3.1.4数据流特点和存储需求.14 3.2算法设计 .14 3.2.1压缩算法设计.15 3.2.2重构算法设计.15 3.3本章小结 .16 第四章第四章 基于基于 gep 的多数据流压缩算法实现的多数据流压缩算法实现.17 4.1顶层框架 .17 浙江工业大学本科毕业设计说明书（论文） ii 4.2单基因机制的实现 .22 4.2.1单基因个体 monogenicindividual.22 4.2.2个体工厂.24 4.2.3个体适应

13、度评估.24 4.2.4选择策略.25 4.3扩展成多基因机制 .26 4.4算法整体类图 .28 4.5本章小结 .28 第五章第五章 实验与分析实验与分析.29 5.1实验平台 .29 5.2实验数据 .29 5.3算法配置 .29 5.4实验结果 .30 5.4.1压缩结果.30 5.4.2数据重构结果.30 5.5实验结果与分析 .32 5.5.1重构数据精度.32 5.5.2压缩比.33 5.6本章小结 .34 第六章第六章 总结与展望总结与展望.35 6.1总结 .35 6.2展望 .35 参考文献参考文献.36 致谢致谢.38 附录附录.39 附录 1 毕业设计文献综述.39 附

14、件 2 毕业设计开题报告.39 附件 3 毕业设计外文翻译（中文译文与外文原文）.39 浙江工业大学本科毕业设计说明书（论文） i 图目录图目录 图 2-1 gep 算法流程图.6 图 2-2 表达式树.8 图 2-3 三个子表达式树.9 图 2-4 多级表达式树.10 图 3-1 主存储数据流和从存储数据流中的数据关系图.14 图 4-1 gep 引擎图.17 图 4-2 nextevolutionstep()流程图.18 图 4-3 evolvepopulation()流程图.20 图 4-4 单基因机制类图.22 图 4-5 单基因个体工厂 monogenicindividualfact

15、ory.24 图 4-6 轮盘赌选择法.26 图 4-7 类 polygenicindividual.27 图 4-8 算法整体类图.28 图 5-1 易方达价值成长基金原数据和重构数据折线图.32 浙江工业大学本科毕业设计说明书（论文） i 表目录表目录 表 4-1 10 个个体的适应度、选择概率和累积概率.25 表 5-1 基于 gep 的多数据流压缩算法配置.29 表 5-2 易方达价值成长原数据和重构数据及误差比较.31 表 5-3 gep-mdsc 二次压缩的特性体现.33 浙江工业大学本科毕业设计说明书（论文） 1 第一章第一章 绪论绪论 1.11.1 选题的背景选题的背景 21

16、世纪是信息化的时代，计算机、网络技术的迅速发展使得越来越多的领 域应用数字技术或系统。采用数字技术或系统具有许多优越性，但也使数据量 大增。信息时代，带来了“信息爆炸”1,2。要解决“信息爆炸”带来的压力可 以从两方面入手：数据挖掘和数据压缩。数据挖掘是运用一定的技术从大量的 数据信息中挖掘出有价值的信息，这些有价值的信息被称为知识3。这样，用户 就可以丢弃大量的无价值的数据信息，而只需关注这些被提取出来的有价值的 信息，这在一定程度上缓解了“信息爆炸”带来的压力。另一方面，这些有价 值的信息需要被存储起来，供用户反复使用。如何有效地最大限度地存储这些 知识，就需要用到数据压缩技术。近几年来，

17、各行各业的发展催生了大量的数 据流4，如股票交易记录，地震检测数据，气象数据、网络流量监控等，这些数 据流被广泛地应用于许多领域，呈现出快速变化、海量无限和实时连续的特点 ，这使得传统的存储技术难以满足这些数据流的存储需求，寻求一种有效的 5 数据压缩技术来存储这些数据流迫在眉睫。 基因表达式编程(gene expression program, gep)6是一种新的遗传算法，它 是由葡萄牙科学家 candida ferreira 在 1999 年发明的，并在 2000 年首次被提出。 gep 融合了遗传算法(genetic algorithm, ga)7和遗传程序设计(genetic pro

18、gramming, gp)8的优点，编码简单，易于进行遗传操作，又具有结构和功能 的多样性。gep 的发明和提出引起了演化计算领域的广泛关注，因为 gep 在函 数挖掘9、规则挖掘10、时间序列预测11,12、分类聚类13,14和演化硬件15,16等多 方面都表现出了优良的特性。也因为 gep 的优良特性，许多改进的 gep 算法被 纷纷提出，这反过来也为 gep 自身注入了新鲜的血液，使得 gep 算法具有更好 的特性，被应用于更多的领域。 浙江工业大学本科毕业设计说明书（论文） 2 gep 凭借自身优良的特性，被应用于很多领域，取得了不小的成果，但在数 据压缩领域还未被广泛应用。但是可以预

19、见，性能优良的 gep 同样可以在数据 压缩领域中取得不错的研究进展。 1.21.2 选题的价值与意义选题的价值与意义 在信息时代，数据压缩的作用及其社会效益越来越明显，它能在一定程度上 缓解“信息爆炸”带来的压力。近几年，数据流在许多领域有着越来越广泛的 应用，而数据流不同于传统静态数据的特点，使得传统的数据压缩技术难以满 足这些数据流的存储需求。 为了掌握这些数据流的历史信息，需要一种有效的数据流压缩技术，能有效 地存储这些数据。本文利用了 gep 极强的函数发现能力，将 gep 运用于多数据 流压缩，探索多数据流的压缩方法，提出了一种基于 gep 的多数据流压缩算法 (multiple

20、data streams compression based on gep, gep-mdsc)，并用实验验证了 该算法的可行性和有效性。 通过不断完善该算法，将该算法运用到数据压缩技术中，定能成为数据压缩 技术领域的一位新成员。它能有效压缩多数据流，当数据流元素存储于数据库 时，该算法的压缩比接近，为数据流条数，当数据流存储于文件时，经1nn 过该算法压缩的文件能用其他压缩软件进行二次压缩，从而达到更高的压缩比。 1.31.3 研究开发的主要内容研究开发的主要内容 将基因表达式编程（gep）应用到多数据流压缩中，进行 gep 的编码和遗 传算子的设计，用 gep 算法演化出主存储数据流和从存

21、储数据流中数据元素之 间的函数表达式，挖掘出的函数表达式要保证：利用主存储数据流进行数据重 构后，重构数据要到达一定的数据精度。那么，将数据存入数据库的时候，就 只需存储主存储数据流和从存储数据流对应的函数表达式，使得所需存储的数 据量变为原来的（为数据流的条数） ，达到数据压缩的目的，而将数据存n1n 浙江工业大学本科毕业设计说明书（论文） 3 储于文件时，可以对经过该算法压缩的文件进行二次压缩，达到更高的压缩比。 1.41.4 研究开发的目标研究开发的目标 实现一种基于 gep 的多数据流压缩算法，要求重构后的数据要达到一定的 精度以保证原数据和重构数据具有相同的可用性，并具有较高的压缩比

22、。 1.51.5 本文的组织结构本文的组织结构 本文展开为六个章节，各章节主要内容如下： 第一章，介绍了选题的背景，价值与意义，以及研究开发的主要内容和目 标，并给出了本文的组织结构。 第二章，从理论上介绍了 gep 算法的原理。 第三章，首先先简单介绍了数据压缩的相关概念，接着分析了基于 gep 的 多数据流压缩算法的可行性，最后给出了该算法的简要设计 第四章，给出了基于 gep 的多数据流算法的完整实现。 第五章，用实验验证了基于 gep 的多数据流压缩算法的可行性。 第六章，对本文进行了总结，并提出了算法需要进一步研究和改进的地方。 1.61.6 本章小结本章小结 本章首先介绍了课题的研

23、究背景，以及选择该课题的所带来的价值与意义， 接着介绍了研究开发的主要内容和目标，最后给出了本文的组织结构，阐明每 章的主要内容。 浙江工业大学本科毕业设计说明书（论文） 4 第二章第二章 基因表达式编程基因表达式编程 遗传算法类(genetic, algorithms, gas) 将生物进化理论运用于计算机系统， 融入了自然界永恒不变的规律， “适者生存，不适者被淘汰”17。遗传算法类使 用个体种群，根据适应度选择个体，并通过一个或多个遗传算子引入遗传变异， 具有较好的性能。而 gep 与其它遗传算法相比所具有的的优良特性在于它完美 地结合了遗传算法(genetic algorithm, g

24、a)和遗传程序设计(genetic programming, gp)的优点，克服了两者的缺点。本章重点介绍了 gep 算法的原理，在介绍 gep 之前，也简单介绍了 ga 和 gp，这有助于更好的理解 gep 算法。 2.12.1 遗传算法类概述遗传算法类概述 2.1.1 遗传算法遗传算法 遗传算法，只使用一种实体：染色体。这些染色体由固定长度的线性符号 串构成，每个染色体都编码着问题的一个可能解。由于ga只使用一种实体，所 以它的染色体同时起着基因型和表现型的作用。的确，只使用一种实体在一定 程度上能简化算法的复杂性，但同时也大大限制了ga在功能结构上的多样性。 因为在这种情况下，ga的整个

25、染色体编码问题的一个可能解，染色体的整个结 构决定其功能。ga染色体固定长度的线性结构使得其容易进行遗传修饰操作， 但在编码问题的可能解上缺乏很大的可伸缩性。 2.1.2 遗传程序设计遗传程序设计 遗传程序设计，gp，同ga中的情况一样：只使用一种实体，语法分析树 (parse tree, pt)，并同时起着基因型和表现型的作用。语法分析树是一种不同大 小和形状的树结构，gp实体结构的多样性决定了其所具有的功能结构的多样性， 但限制了能够进行的遗传修饰操作。因为遗传修饰操作将直接作用于语法分析 树本身，程序必须保证经过遗传修饰后的语法分析树在结构上都是合法的。 浙江工业大学本科毕业设计说明书（

26、论文） 5 2.1.3 基因表达式编程基因表达式编程 gep 采用两种实体：染色体和表达式树（expression tree，et）6。前者是 由固定长度的线性符号串构成的，起着基因型的作用，后者是一种不同大小和 形状的树结构，起着表现型的作用。ga 的实体采用固定长度的线性字符串，这 种简单的编码方式，使得 ga 易于进行遗传修饰，但只能表示比较单一的功能结 构；gp 采用一种不同大小和形状的树结构作为实体，这种编码方式使 gp 具有 多样化的功能结构，但遗传修饰操作受到很大的限制；而 gep 采用两种实体， 将基因型和表现型分离，使得 gep 容易实现遗传修饰操作又能表示功能结构的 多样性

27、，gep 几乎可以编码任何简单和复杂的计算机程序。 2.22.2 gepgep 算法流程算法流程 在详细介绍 gep 的各基本要素之前，先来看一下 gep 算法的基本流程，如 图 2-1 所示： 浙江工业大学本科毕业设计说明书（论文） 6 创建初始种群 染色体编码 适应度评估 形成新一代种群 个体选择算法 遗传操作算法 选择最优个体 是否满足进 化结束条件 输出最优个体 是 否 图 2-1 gep 算法流程图 图 2-1 给出了 gep 算法的基本流程图，其中判别框“是否满足进化结束条 件”是生物进化理论“物竞天择，适者生存”的体现。gep 算法对每个种群个 体进行适应度评估，若有个体满足进化

28、结束的条件，则输出最优个体，进化结 束；若不满足，则用一种选择算法选取种群中的相对较优的个体，对它们进行 遗传修饰操作，形成新一代种群。至此，程序又返回到对每个种群个体进行适 应度评估，并重复进行接下来的步骤，直到发现满足进化结束条件的个体。 2.32.3 gepgep 的实体的实体 2.3.1 染色体和基因型染色体和基因型 gep 染色体是由固定长度的线性符号串构成的，这些线性符号串可以构成一 浙江工业大学本科毕业设计说明书（论文） 7 个或多个基因，这等价于，gep 染色体可以是多基因的染色体。gep 的多基因 染色体结构将在 2.3.2 节介绍，本小节先介绍 gep 的单基因染色体。 g

29、ep 基因是由一个头部和一个尾部组成的。头部由代表函数和终点的符号组 成，而尾部只能由代表终点的符号组成。在 gep 基因的头部和尾部之间有明显 的分界线，尾部的长度 是由头部长度决定的：th （2-1）1) 1(*nht 这里，是根据实际问题选定的，是具有最多参数的函数的参数个数。下面请hn 看公式（2-2）所表示的一个 gep 染色体： （2-2） acdabd 8765432 * 10 这里函数集 f=*, -, +，终点集 t=a, b, c, d, 取，则根据公式（2-1） ，可4h 以得到，染色体的长度等于 9。51) 12(4t gep 的染色体起着基因型的作用，而染色体固定长度

30、线性的结构使得遗传修 饰操作很容易在其上进行，并且被修饰的染色体总能被翻译成结构上合法的表 达式树。 2.3.2 表达式树和表现型表达式树和表现型 在gep中，染色体起着基因型的作用，它编码着遗传信息，根据不同的遗传 信息，这些染色体能表达成不同大小和形状的表达式树。读取并表达编码在gep 染色体中的遗传信息是通过一种karva语言18实现的。按照karva语言的规则， 染色体（2.2）所编码的遗传信息可以表达成如下图2-2的表达式树： 浙江工业大学本科毕业设计说明书（论文） 8 + - * d b ad 图 2-2 表达式树 这里，基因的位置 0 对应表达式树的根节点，接着在每个函数节点的下

31、面连接 与这个函数参数个数一样多的分支，直到叶节点都是终点。这样，一个 gep 染 色体的表达就完成了。 将图 2.1 的表达式树按 karva 语言规则读取，则可以得到如下染色体序 列： (2-3) dabd 65432 * 10 它是将图 2-2 按从上到下，从左到右的顺序读取的。但是从表达式树读取的序列 与原来的染色体序列相比，缩短了 2 个长度，位置 7 的c和位置 8 的a被 丢弃了。 式子（2-3）实际上是一个开放式阅读框（open reading frame，orf）18， 它类似于生物基因的编码区。每个 gep 染色体基因都对应着一个开放式阅读框， 那些在开放式阅读框之后的序列

32、就是非编码区域，这个例子中的非编码区域是 序列ca 。 gep 的表达式树起表现型的作用，它使得 gep 染色体能编码各种解，保证 了 gep 所表示的功能结构的多样性。 浙江工业大学本科毕业设计说明书（论文） 9 2.3.3 gepgep 的多基因染色体的多基因染色体 gep 染色体可以由多个基因构成，每个基因必须是等长的，因为染色体的总 长度是固定的。在染色体中的每个基因都对含有一个 orf，每个 orf 都将被翻 译成一个子表达式树。每个子表达式树都表示一个子功能结构，这些子表达式 树由连接函数连接，形成一个层次化的表达式树，表示一个更复杂的功能结构。 考虑下面这个 3-基因染色体： （

33、2-4） aaaaabbababababbqbqabababbbbq 2109876 * 5 / 4321 / 021098765432102109876 / 5 * 4321 * 0 它编码了如下三个子表达式树，如图 2-3： * + q b b */ - a a + q ab + * d b b q sub-et1sub-et2 sub-et3 图 2-3 三个子表达式树 将这三个子表达式树用连接函数连接，就得到一个多级表达式树，如图 2-4： 浙江工业大学本科毕业设计说明书（论文） 10 * + q b b */ - a a + q ab + * d b b q + + 图 2-4 多级

34、表达式树 在 gep 中引入了多基因机制后，对于复杂的问题，该算法也能表现出良好 的性能。 2.42.4 适应度函数适应度函数 在gep中，一般采用下面两种适应度函数对个体进行适应度评估： （2-5） t c j jjii tcmf 1 ),( （2-6） t c j j jji i t tc mf 1 ),( 100* 式子（2-5）是基于相对误差的，式子（2-6）基于绝对误差。这里，是选择m 范围，是染色体 对于适应度样本的返回值，而是适应度样本的目标 ),(ji cij j tj 值。 浙江工业大学本科毕业设计说明书（论文） 11 2.52.5 遗传算子遗传算子 遗传修饰是通过一个或多个

35、遗传算子引入的，它能带来种群的多样性，使 这些个体种群中存在满足进化条件的个体。对于不同的问题，可以设计部同的 遗传算子。 2.5.1 选择和复制选择和复制 选择和复制是gep的基本遗传算子。选择算子根据一定的选择策略选择个体 对其进行进一步的遗传修饰。复制简单地将上一代中的个体直接复制到下一代， 构成子代的一个个体。 2.5.2 变异变异 变异可以发生在染色体中的任何部位，但是尾部的元素只能变异成终点， 而头部的元素能变成函数或终点。经过变异修饰的基因，它所编码的表达式树 的节点可能增加，也可能减少，也可能保持不变。当变异点出现在基因的非编 码序列中时，这种变异算子产生的效果是中性的。 2.

36、5.3 转移转移 根据转移因子的不同，转移算子有三种类型。第一种是插入序列元素（is元 素）转移，它的转移因子是第一个位置是函数或终点的短序列，可以被转移到 基因头部除根以外的任何位置；第二种是根插入序列元素（ris元素）转移，它 的转移因子是第一个位置是函数的短序列，这种转移因子只能被转移到基因的 根部；第三种是基因转移，它的转移因子是整个基因，显然这种转移因子出现 在多基因染色体中。在基因转移中，被选中的基因成为转移因子，它被转移到 染色体的开头，成为染色体中的第一个基因。总的来说转移算子的效果没有变 异算子的效果好，但是在gep中也经常使用该算子。 2.5.4 重组重组 重组也存在着三种

37、不同的形式：单点重组，两点重组和基因重组。它们的本 质是一样的：随机选择两条配对的染色体，随机在染色体相同的位置选定重组 浙江工业大学本科毕业设计说明书（论文） 12 点，接着在这两条父代染色体之间交换序列。在单点重组中，随机选择一个重 组点并在染色体之间交换这个重组点以后的所有序列。两点重组随机在两条染 色体的相同位置选择两个重组点，它交换的是两个重组点之间的序列。在基因 重组中，两条父代染色体之间交换的是相同位置上的基因。而当基因之间相互 作用的函数是可交换的类型时，这种修饰是中性的。和转移算子一样，重组算 子的效果也没有变异算子的效果好。 2.62.6 本章小结本章小结 本章主要从理论上

38、介绍了 gep 算法，没有给出 gep 算法的具体实现，gep 的实现将在其它章节给出。在介绍 gep 算法原理之前，也简单介绍了遗传算法 家族的另两位成员，遗传算法和遗传程序设计。 浙江工业大学本科毕业设计说明书（论文） 13 第三章第三章 基于基于 gepgep 的多数据流压缩算法的多数据流压缩算法 前一章从理论上介绍了gep算法，本章将gep算法应用于多数据流的压缩算 法，提出了一种基于gep的多数据流压缩算法，分析了该压缩算法的可行性，并 给出了算法的简要设计。为了更好的理解基于gep的多数据流压缩算法，在本章 开头首先介绍了数据压缩的相关概念。 3.13.1数据压缩的相关概念数据压缩

39、的相关概念 3.1.1 数据压缩定义数据压缩定义 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高 其传输、存储和处理效率的一种技术方法4。或按照一定的算法对数据进行重新 组织，减少数据的冗余和存储的空间4。 3.1.2 数据压缩原理数据压缩原理 压缩得以进行的前提是数据存在冗余，压缩的理论基础是信息论。从信息 的角度来看，压缩就是去除掉信息中的冗余，即去除掉确定的或可推知的信息， 而保留不确定的信息，也就是用一种更接近信息本质的描述来代替原有的冗余 的描述，这个本质东西就是信息量。 3.1.3 数据流基本概念数据流基本概念 数据流即由连续的、近似无限的、时变的、有序的且快速流

40、动的数据元素 组成的无限序列1,2。 若令t表示任一时间戳，表示在t时刻到达的数据元素，则由无限集合 t s ，组成的序列成为数据流序列20。 1t s t s 1t s 设序列s由集合，组成，其中=， 0 s 1 s k s k s 1 ,k s 2,k s ，(k，n)为一个数据流序列，则称s为一个多数据流20。 nk s , n 浙江工业大学本科毕业设计说明书（论文） 14 对于多数据流s=，假定为主存储数据流，为 0 s 1 s k s 0 s k s 从存储数据流，等长的主存储数据流和从存储数据流中的数据元素之间的一一 对应关系称为多数据流映射8。如图3-1所示： 1 , 0 s 2

41、, 0 s n s , 0 1 ,k s 2,k s nk s , 图 3-1 主存储数据流和从存储数据流中的数据关系图 3.1.4 数据流特点和存储需求数据流特点和存储需求 由数据流定义可知，数据流具有海量、连续、近似无限、时变、有序且快 速流动的特点。传统的压缩技术难以满足数据流的存储需求，为了掌握这些历 史数据信息的价值，研究描述数据流压缩技术，减小数据存储容量具有重要意 义。 3.23.2算法设计算法设计 gep 能够在实验数据上，根据自变量和因变量之间的映射关系，提炼出数 学表达式，具有极强的函数发现能力，并且 gep 不需要给出函数模型。将 gep 应用到多数据流的压缩，寻找主存储

42、数据流和从存储数据流之间的函数关系， 则存储时只需存储主存储数据流和与各从存储数据流之间的函数关系，使得存 储容量变为原来的，代表数据流条数。例如假设，有 20 条数据流，选定n1n 其中一条为主存储数据流，其余的都为从存储数据流，那么经过基于 gep 的多 数据流压缩算法压缩后，所需存储的数据量变为原来的，从而达到数据压201 浙江工业大学本科毕业设计说明书（论文） 15 缩的目的，且数据流条数越多，压缩比越高。经过该算法压缩后的文件还能进 行二次压缩，进一步减少存储数据所需的空间。 压缩算法在达到较高压缩比的同时，也要保证重构后数据的精度。数据压 缩包括无损压缩和有损压缩，很明显，基于 g

43、ep 的多数据流压缩算法属于有损 压缩。因为分析决策者通常不关心这些数据流的具体精确值，所以在保证重构 后数据不影响分析决策的前提下，牺牲一定的数据精度来获得较高的压缩比是 可以被接受的。 3.2.1 压缩算法设计压缩算法设计 程序参数设置：gep 算法配置，从存储数据流条数 n 和所寻找的各个函数 关系表达式的可接受的误差范围。 输入：多数据流训练集 s 输出：主存储数据流、各个从存储数据流对应的序号和函数关系 1.用训练集 s 初始化 data，声明一个存储函数关系表达式的数组 inds 2.for(int i=0; in; i+) /循环次数为从存储数据流条数 n 3. 设置当前的多数据

44、流序号； 调用基于 gep 的多数据流压缩算法，找到主存储数据流和当前从存 储数据流之间的函数关系表达式； indsi = 当前的函数关系表达式； 4. 3.2.2 重构算法设计重构算法设计 输入：主存储数据流，存储有与各个从存储数据流对应的函数关系表达 0 s 式的数组 inds 输出：主存储数据流和各从存储数据流 1.初始化输出文件路径名； 浙江工业大学本科毕业设计说明书（论文） 16 2.for(int i=0; iinds.length; i+) 3. for(int j=0; j的长度; j+) 0 s 将函数表达式 indsi的自变量设为j； 0 s 计算 indsi的函数值并输出

45、到文件； 4. 3.33.3本章小结本章小结 本章先简单介绍了数据压缩的相关概念，接着分析了基于 gep 的多数据流 压缩算法的可行性，最后给出了该算法的简要设计。 浙江工业大学本科毕业设计说明书（论文） 17 第四章第四章 基于基于 gepgep 的多数据流压缩算法实现的多数据流压缩算法实现 gep 是唯一的多基因遗传算法，用多个基因构成的染色体能够编码更加复 杂的程序，使得 gep 能够在更短的时间内找到满足进化结束条件的个体。在基 于 gep 的多数据流压缩算法实现中，我们选择 gep 的多基因机制，用多基因染 色体表示种群个体。但实际上，多基因染色体可以看成是多个单基因染色体组 合而成

46、。所以在实现该基于 gep 的多数据流压缩算法时，我们按照这样的思路 进行：顶层框架单基因 gep 实现多基因 gep 实现。我们首先搭建算法最顶 层的框架，接着用 gep 的单基因机制实现了该算法，然后在单基因机制的基础 上，将该算法扩展成多基因机制的，实现基于 gep 的多数据流压缩算法时大量 运用了工厂模式。 4.14.1顶层框架顶层框架 启动一个 gep 程序，必须有一个 gep 引擎，这个 gep 引擎包含了启动所 需的各个部分，如图 4-1 所示： individualfactory operatorset evaluator observer selectstrategy ran

47、dom generationnumber stopcondition gep 引引 擎擎 nextevolutionstep() evolvepopulation() evolve() 图 4-1 gep 引擎图 浙江工业大学本科毕业设计说明书（论文） 18 由图 4-1 知，一个 gep 引擎(engine)包括：individualfactory (个体工厂)、 operatorset (遗传算子集)、evaluator (适应度函数)、observer (观察者)、 selectstrategy (选择策略)、stopcondition (停止条件)、random (随机数)、和 gen

48、erationnumber (当前种群代数)，还有操纵这些部分实现种群进化的方法： nextevolutionstep()，evolvepopulation()，evolve()， 左边一列都是抽象类或接口：individualfactory 用来产生初始种群个体，对 个体进行编码，selectestrategy 用来选择种群中的个体，operatorset 对选中的个 体进行遗传修饰，evaluator 对种群中的每个个体进行适应度评估，observer 观 察每代种群中最优个体的情况。右边一列，stopcondition 给出种群进化结束的 条件，generationnumber 是当前种

49、群代数，random 给出一个随机数。 engine 的方法 nextevolutionstep()返回下一代种群，它运用到了最佳个体复 制策略（精英策略6） 。最佳个体复制，即将上一代种群中的最佳个体，直接选 择复制到下一代，该策略保证整个种群是不断向前进化的。方法 nextevolutionstep()伪代码如下： 方法 nextevolutionstep()：返回下一代种群 1. 2. generationnumber+; /种群代数加 1 3. /精英策略，将上一代种群中的最优个体保留复制到下一代 4. list elites = new arraylist(); 5. for(0 到

50、 最佳个体数) 6. 7. elites.add(上一代种群中的最佳个体); 8. 9. 选择种群中的个体； 10. 对选中的个体进行遗传修饰； 11. 返回下一代种群 12. engine 的 evolvepopulation()方法返回含有满足进化结束条件个体的种群，且 浙江工业大学本科毕业设计说明书（论文） 19 返回的种群个体按适应能力从大到小排列。在该方法中，我们控制种群更新进 化代数为 600。即当种群进化到第 600 代时，还未得到满足进化条件的解，则保 留当前种群中的最佳个体，重置更新其余种群个体。该方法流程如图 4-2： 初始化进化停止条件 初始种群 适应度评估 种群个体排序

51、 获得最佳个体 最佳个体保留 是否满足进 化结束条件 返回种群 是 否 种群代数是 否大于 600 是 否 种群向前进化一代 图 4-2 evolvepopulation()流程图 evolvepopulation()伪代码如下： 方法 evolvepopulation()：返回含有满足进化结束条件个体的种群，种群中的 个体按适应能力从大到小排列。 1. 2. 初始化进化停止条件，当前种群代数置 0； 3. 获得初始种群； 4. 对种群个体进行适应度评估； 浙江工业大学本科毕业设计说明书（论文） 20 5. 根据适应度大小对种群个体进行排序； 6. 获得当前种群中的最佳个体，并调用 obser

52、ver 显示 7. while(stopcondition.continue(当前种群最佳个体) = true) 8. 9. if(generationnumber600) 10. 11. generationnumber=0; 12. 保留最佳个体，其余个体重置; /防止陷入局部最优解 13. 更新种群; 14. 15. nextpopulation = this.nextevolutionstep(); /获得下一代种群 16. 根据适应度大小对种群个体进行排序； 17. 获得当前种群中的最佳个体，并调用 observer 显示 18. 19. 返回当前种群； 20. engine 的 e

53、volve()方法返回种群中满足进化结束条件的个体，它在方法体内 调用 evolvepopulation()方法，实现比较简单，这里不给出该方法流程图和伪代码。 图 4-1 给出了算法最顶层的框架示意图，要实现一个 gep 算法，只需实现 图 4-1 中左边一列中的抽象类或接口，并给出具体怎样操纵种群进行进化的方法。 浙江工业大学本科毕业设计说明书（论文） 21 4.24.2单基因机制的实现单基因机制的实现 图 4-3 单基因机制类图 图 4-3 给出了基于单基因 gep 的多数据流压缩算法类图，下面将介绍图 4-3 中一些关键类的实现。 4.2.14.2.1 单基因个体单基因个体 monog

54、enicindividualmonogenicindividual gep 与 ga 和 gp 的不同在于，前者采用了两种实体，染色体和表达式树， 实现了将基因型和表现型分离。根据 gep 的这个特点，我们将类型为 inode的 字段 genotype 和类型为 expressiontree 的字段 phenotype 封装在类 monogenicindividual 里，分别表示种群个体的基因型和表现型，类 monogenicindividual 表示 gep 的单基因个体。这种封装法也符合自然界中的现 象，大多数生物个体都具有起着基因型作用的染色体和起着表现型作用的蛋白 质。 浙江工业大学

55、本科毕业设计说明书（论文） 22 monogenicindividual 的 expresset()方法将根据基因型 genotype 得到表现型 phenotype，该方法的伪代码如下： 方法 expresset()：根据基因型 genotype 得到表达式树 phenotype 1. 2. expressiontree et = new expressiontree(); /初始化一棵空的表达式树 3. /将 genotype 的第一个节点即根节点复制给表达式树的根 4. et.root = genotype0; 5. /调用方法 getallchildren()，将 genotype 中

56、剩下的节点表示成与根节 点相连的子树 6. getallchildren(new expressiontreeet, genotype, 1); 7. return et; 8. 方法 getallchildren()：将染色体中除根节点外的节点表示成与根节点相连的 子树，该方法用了递归，伪代码如下： 1.getallchildren(expressiontree parents, inode genotype, int currentinodeindex) 2. 3. 得到当前层所有节点的参数个数之和，复制给 length 4. if(length=0) /表示当前层的节点都是终节点，这是递

57、归停止条件 5. 6. return; 7. 8. /下一层的节点； 9. expressiontree allchildren = new expressiontreelength; 10. 将 genotype 中的节点与 allchildren 中的每个元素相关联，更新 currentnodeindex; 11. getallchildren(allchildren, genotype, currentinodeindex); /递归调用 12. 浙江工业大学本科毕业设计说明书（论文） 23 4.2.24.2.2 个体工厂个体工厂 种群个体是由个体工厂创造的，单基因 gep 的个体工厂如

58、图 4-4： 图 4-4 单基因个体工厂 monogenicindividualfactory 由图 4-4 知，monogenicindividualfactory 中有两个类型为 list的 字段 heads 和 tails，这两个字段分别产生头部和尾部的节点。字段 headlength、taillength 和 length 分别表示头部长度、尾部长度和基因的总长度 方法 generaterandomindividual(random)利用字段 heads 和 tails 产生随机的单 基因个体 monogenicindividual。该类中的方法 mutate()和 transfer(

59、)具体实现对种 群个体的遗传修饰，而类 mutationoperator 和 transferoperator 两个遗传算子只 是简单地调用 monogenicindividual 的 mutate()和 transfer()方法将遗传修饰作用于 种群个体，这样做也体现了面向对象编程中将实现与接口分离的思想。下面请 看 mutate()和 transfer()的伪代码： 方法 mutate()：实现对种群个体进行单点变异或两点变异 1. 2. 得到个体基因型 genotype; 3. n=1，进行一次单点变异，n=2，进行两次单点变异，即两点变异 浙江工业大学本科毕业设计说明书（论文） 24

60、4. int n = rnd.nextint(2) + 1; 5. for(int i=0; in; i+) 6. 7. 得到变异点位置 position; 8. if(positionheadlength) /变异点在头部 9. 10. 用头部节点替换变异点位置的节点; 11. 12. else /变异点在尾部 13. 用尾部节点替换变异点的节点; 14. 15. 方法 transfer()：对种群个体进行 ris 序列转移 1. 2. 得到个体基因型 nodes; 3. 得到转移序列 ris; 4. if(ris = null) 5. return; 6. vector head = ne