《毕业设计（论文）基因表达式编程在数据压缩中的应用》由会员分享，可在线阅读，更多相关《毕业设计（论文）基因表达式编程在数据压缩中的应用（48页珍藏版）》请在金锄头文库上搜索。
1、浙江工业大学本科毕业设计说明书（论文）本科毕业设计说明书（论文） （2011届）论文题目 基因表达式编程在数据压缩中的应用作者姓名 指导教师 学科(专业) 所在学院 提交日期 I摘要各行各业的发展产生了大量的数据，如通话记录，股票数据，气象监测等数据都可以看成数据流。为了挖掘蕴藏在这些数据流中信息的价值，需要一种有效的数据流压缩技术对其进行压缩，以减少这些数据流对存储空间的需求，而传统的压缩技术难以满足这些数据流的存储需求。基因表达式编程(Gene Expression Programming, GEP)融合了遗传算法和遗传程序设计的优点，编码简单，易于进行遗传修饰操作，具有结构和功能的多样性
2、。在解决复杂的函数发现等问题上，GEP表现出优越的性能，在科学计算和商业应用等领域取得了广泛的应用。本文利用GEP在函数发现上优越的性能，探索多数据流的压缩算法，提出了一种基于GEP的多数据流压缩算法。通过GEP编码和遗传算子的设计，演化出主、从存储数据流中数据元素之间的函数关系，使得在存储这些数据流时，只需存储主存储数据流和对应的函数关系表达式，从而达到数据压缩的目的。本文所采用算法在保证原数据和重构数据具有相同可用性的前提下，虽然数据精度稍有损失，但获得了较高的压缩比。通过实验验证，基于GEP的多数据流压缩算法是可行的，当数据流元素存储于数据库时，该算法的压缩比接近，为数据流条数，而当数据
3、流存储于文件时，经过该算法压缩的文件能用其他压缩软件进行二次压缩，从而达到更高的压缩比。关键词：基因表达式编程，数据流，数据压缩，压缩比IAbstractThe 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 they are regarded as data streams. In order to mining the valuable i
4、nformation 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 compression technologies cant meet the demands of these data streams. G
5、ene 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 complex problems such as function discovery, GEP shows excellent p
6、erformance 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 multiple data streams compression algorithm based on GEP. By coding
7、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 storing these data streams, and thus reaches the goal of data compression
8、. 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 multiple data streams compression based on GEP is feasible. When the data
9、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 stored in files, the files compressed by this algorithm also can be compressed the second time by other compression technology, thus reaches a higher compressi
10、on ratio.Keywords：gene expression programming, data streams, data compression, compression ratio目录摘要IABSTRACTI第一章 绪论11.1选题的背景11.2选题的价值与意义21.3研究开发的主要内容21.4研究开发的目标31.5本文的组织结构31.6本章小结3第二章 基因表达式编程42.1遗传算法类概述42.1.1遗传算法42.1.2遗传程序设计42.1.3基因表达式编程52.2GEP算法流程52.3GEP的实体62.3.1染色体和基因型62.3.2表达式树和表现型72.3.3GEP的多基因染
11、色体82.4适应度函数102.5遗传算子112.5.1选择和复制112.5.2变异112.5.3转移112.5.4重组112.6本章小结12第三章 基于GEP的多数据流压缩算法133.1数据压缩的相关概念133.1.1数据压缩定义133.1.2数据压缩原理133.1.3数据流基本概念133.1.4数据流特点和存储需求143.2算法设计143.2.1压缩算法设计153.2.2重构算法设计153.3本章小结16第四章 基于GEP的多数据流压缩算法实现174.1顶层框架174.2单基因机制的实现224.2.1单基因个体MonogenicIndividual224.2.2个体工厂244.2.3个体适应
12、度评估244.2.4选择策略254.3扩展成多基因机制264.4算法整体类图284.5本章小结28第五章 实验与分析295.1实验平台295.2实验数据295.3算法配置295.4实验结果305.4.1压缩结果305.4.2数据重构结果305.5实验结果与分析325.5.1重构数据精度325.5.2压缩比335.6本章小结34第六章 总结与展望356.1总结356.2展望35参考文献36致谢38附录39附录1 毕业设计文献综述39附件2 毕业设计开题报告39附件3 毕业设计外文翻译（中文译文与外文原文）39图目录图 21 GEP算法流程图6图 22表达式树8图 23三个子表达式树9图 24多级
13、表达式树10图 31主存储数据流和从存储数据流中的数据关系图14图 41 GEP引擎图17图 42 nextEvolutionStep()流程图18图 43 evolvePopulation()流程图20图 44单基因机制类图22图 45单基因个体工厂MonogenicIndividualFactory24图 46轮盘赌选择法26图 47类PolygenicIndividual27图 48算法整体类图28图 51易方达价值成长基金原数据和重构数据折线图32表目录表 41 10个个体的适应度、选择概率和累积概率25表 51基于GEP的多数据流压缩算法配置29表 52易方达价值成长原数据和重构数据
14、及误差比较31表 53 GEP-MDSC二次压缩的特性体现33浙江工业大学本科毕业设计说明书（论文）第一章 绪论1.1 选题的背景21世纪是信息化的时代，计算机、网络技术的迅速发展使得越来越多的领域应用数字技术或系统。采用数字技术或系统具有许多优越性，但也使数据量大增。信息时代，带来了“信息爆炸”1,2。要解决“信息爆炸”带来的压力可以从两方面入手：数据挖掘和数据压缩。数据挖掘是运用一定的技术从大量的数据信息中挖掘出有价值的信息，这些有价值的信息被称为知识3。这样，用户就可以丢弃大量的无价值的数据信息，而只需关注这些被提取出来的有价值的信息，这在一定程度上缓解了“信息爆炸”带来的压力。另一方面，这些有价值的信息需要被存储起来，供用户反复使用。如何有效地最大限度地存储这些知识，就需要用到数据压缩技术。近几年来，各行各业的发展催生了大量的数据流4，如股票交易记录，地震检测数据，气象数据、网络流量监控等，这些数据流被广泛地应用于许多领域，呈现出快速变化、海量无限和实时连续的特点，这使得传统的存储技术难以满足这些数据流的存储需求，寻求一种有效的数据压缩技术来存储这些数据流迫在眉睫。基因表达式编程(Gene Expression Program, GEP)6是一种新的遗传算法，它是由葡萄牙科学家Candida F
