昆明理工大学短学期遗传算法.doc

程序设计及应用遗传算法在基因识别中的应用姓名： 学号： 学院： 班级： 指导老师： 昆明理工大学2013年7月一、 程序概述 1. Java。Java语言是纯粹的面向对象程序设计语言，它是基于Java平台的。可以Java用来开发可靠的、要求严格的应用程序。Java的风格很接近C语言，但是Java舍弃了C语言中容易引起错误的指针用引用取代。Java的优势：Java适合团队开发，软件工程可以相对做到规范。由于Java语言本身的极其严格语法的特点，Java语言无法写出结构混乱的程序。这将强迫程序员的代码软件结构的规范性。这是一个很难比拟的优势。Java的劣势：第一版软件可以做满意，但是很不适合互联网模式的持续不断修改。互联网软件工程管理上的不足，持续的修修补补导致架构的破坏。Java是一种单层继承的语言。这也导致了程序师在试图使用多重继承时候的不便，而很多语言都可以使用这个特性。但是Java可以使用接口类，把多重继承可能导致的风险减少到最小。Java不支持运算符重载，这是为了防止运算符重载使得代码的功能变得不清晰。但是用Java实现的语言Groovy可以进行运算符重载。过去Java对于文本的操作和其他语言，比如Perl和PHP相比差的较多，但Java在1.4版本时候引入了正则表达式。Java的设计目的主要是安全性和可携性，所以对于一些特性。比如对硬件架构和存储器地址访问的直接访问都被去除了，如果需要间接调用这些底层功能的话，就需要使用JNI（Java本地接口）来调用本地代码。而间接访问意味着频繁调用这些特性时性能损失会很大，微软的.NET平台也有这样的问题。Java发展中Android是第一个内置支持Java的操作系统，Android应用程序使用Java语言编写。Android开发水平的高低很大程度上取决于Java语言核心能力是否扎实。另外一方面，3G应用往往会和企业级应用相互结合。因此，在3GAndroid课程体系中将Android课程与Java EE课程紧密结合，以Android课程为主，以Java EE课程为辅，配合真实的企业级项目，不但可以深入掌握基于Android平台的智能手机开发技术，更重要的是还系统掌握了智能移动终端与Java EE服务器端相结合的诸多领域商业的应用。Java试图通过新的方式解决软件编写的复杂性。很多人认为Java语言做到了它承诺的一切。但是Java并不是一门完美的语言。不过Java相对其他语言较简单，功能也强大，所以在应用上很广泛，团队作业大多用Java语言2. 运行环境。2.1硬件要求：一般而言Java在现在计算机上都能工作，所以硬件要求不是很大32位和64位的操作系统都可以，在windowsxp、windows 7、windows8系统下都能用。我的电脑安装内存4GB，处理器CPU1.60GHZ，操作系统是64位。2.2软件要求：对于64位的系统要求装适合64位的jdk和eclipse，windows8的系统则安装myeclipse。jdk是Java 语言的软件开发工具包，jdk 有各种适合操作系统的版本，我们应该选择合适的版本安装，安装完成后还要进行环境变量的配置，否则Java不能在电脑上使用。安装和配置好环境变量后就可以编写Java程序了，通常我们用记事本来写代码，先把记事本的名字改为英文，后缀改为Java，写完代码再通过cmd控制台对代码进行编译，编译无误就可以运行了。eclipse是Java的集成开发环境。eclipse 是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，eclipse 附带了一个标准的插件集，包括Java开发工具（Java Development Kit，JDK）。虽然大多数用户很乐于将 Eclipse 当作 Java 集成开发环境（IDE）来使用，但 Eclipse 的目标却不仅限于此。Eclipse 还包括插件开发环境（Plug-in Development Environment，PDE），这个组件主要针对希望扩展 Eclipse 的软件开发人员，因为它允许他们构建与 Eclipse 环境无缝集成的工具。由于 Eclipse 中的每样东西都是插件，对于给 Eclipse 提供插件，以及给用户提供一致和统一的集成开发环境而言，所有工具开发人员都具有同等的发挥场所。这种平等和一致性并不仅限于Java开发工具。尽管 Eclipse 是使用Java语言开发的，但它的用途并不限于 Java 语言；例如，支持诸如C/C+、COBOL、PHP等编程语言的插件已经可用，或预计将会推出。Eclipse 框架还可用来作为与软件开发无关的其他应用程序类型的基础，比如内容管理系统。二、什么是遗传算法遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。遗传算法经过不断的发展和改进，又发展出许多新的进化算法，如模拟退火算法，免疫遗传算法，粒子群优化算法等等。1.遗传算法的步骤。初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成n个个体作为初始群体b（0)。个体评价：计算群体b（0)中各个个体的适应度。其中适应度方程为选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体b(i)经过选择、交叉、变异运算之后得到下一代群体b(i+1)。终止条件判断:若i=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。2. 遗传算法的关键遗传算法在应用中最关键的问题有如下3个：（1）串的编码方式它本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长及编码形式对算法收敛影响极大。（2）适应函数的确定适应函数也称对象函数，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模式函数作为对象函数；但有时需要另行构造。（3）遗传算法自身参数设定遗传算法自身参数有3个，即群体大小n，交叉概率和变异概率。群体大小n太小时难以求出最优解，太大则增长收敛时间。3.遗传算法程序设计遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适合环境的个体（Individual），求得问题的最优解。确定实际问题参数集对参数集进行编码初始化种群b(i)评价群体满足停止规则遗传操作利用适应度函数来评价，选出优质群体。三个基本算子：1. 选择2. 交叉3. 变异产生新一代群体结束YN图1 遗传算法流程图4.遗传算法编码问题（1）编码解空间中的解数据，作为遗传算法的表现型形式。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2）初始群体的生成随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数计数器t0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。（3）适应度值评价检测适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体中各个个体的适应度。（4）选择将选择算子作用于群体。（5）交叉将交叉算子作用于群体。（6）变异将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)（7）终止条件判断若tT，则t t+1，转到步骤（2）；若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。从遗传算法运算流程可以看出，进化操作过程简单，容易理解，它给其他各种遗传算法提供了一个基本框架。一个简单的遗传算法被Goldberg用来进行轮廓描述并用来举例说明遗传算法的基本组成。t代种群用变量P(t)表示，初始群体P(0)是随机设计的。三、基因识别1.基因及基因识别。基因（Gene）是遗传的基本单元，是产生一条多肽链或功能RNA所必需的DNA片段。基因通过复制把遗传信息传递给下一代，使后代出现与亲代相似的性状。也通过突变改变这自身的缔合特性，储存着生命孕育、生长、凋亡过程的全部信息，通过复制、转录、表达，完成生命繁衍、细胞分裂和蛋白质合成等重要生理过程。生物体的生、长、病、老、死等一切生命现象都与基因有关。它也是决定生命健康的内在因素。因此，基因具有双重属性：物质性（存在方式）和信息性（根本属性）。基因识别使用计算机手段识别DNA序列上的具有生物学特征的片段，其对象主要是蛋白质编码基因也就是外显子，也包括其他具有一定生物学功能的因子，如RNA、MicroRNA基因等一些非编码基因，基因识别是生物信息学领域里的一个重要研究内容。我们这里要做的就是找到启动子（ATG）和终止子（TAA、TAG、TGA），将外显子连在一起，组成一段基因。2.基因识别常用的算法及程序。基因识别的常用算法有遗传算法（在上文有详细说明）、DNA的4D表示法。DNA序列4D表示法不仅包含明确的生物学意义,而且有效避免了由DNA序列表示转化为几何表示法过程中造成的信息丢失。接着在DNA序列4D表示的基础上运用傅立叶变换,对编码区与非编码区序列进行频谱分析,从而实现编码区与非编码区的识别。还可以在NCBI网站上进行基因识别测试，用基因预测软件（GeneMark系列软件和Glimmer 2.02）也可以实现基因识别。3.基因识别本次的基因识别就是从一段基因序列中找出启动子和终止子的位置，并把他们之间的外显子打印出来。3.1代码package org.jenetics.example;import java.io.*;public class Truepublic static void main(String args) String filePath = F:java_codegene.txt; StringBuffer sb1=readTxtFile(filePath);printgene(sb1); static void printgene(StringBuffer sb)String gene=;int begin=-1, end,index;int len=sb.length();boolean next=true;while(next)boolean flag=true;begin=sb.indexOf(ATG,begin+1);if(begin=len-3 | begin0)next=false;flag=false;index=begin+3;end=index;while(flag & index=len-3) String coden=sb.substring(index,index+3);if( coden.equals(TAA) | coden.equals(TAG) | coden.equals(TGA)end=index+3;int genelen=end-begin;System.out.print(启动子:+begin+ ATG);System.out.println(, 终止子:+(end-3)+ +coden);System.out.println(编码长度:+genelen);gene=sb.substring(begin,end);System.out.println(编码序列: n+gene+n);flag=false;index += 3; static public StringBuffer readTxtFile(String filePath)StringBuffer sb=new StringBuffer(); try String encoding=GBK; File file=new File(filePath); if(file.isFile() & file.exists() InputStreamReader read = new InputStreamReader( new FileInputStream(file),encoding); BufferedReader bufferedReader = new BufferedReader(read); String lineTxt = null; while(lineTxt = bufferedReader.readLine() != null) sb.append(lineTxt); read.close(); else System.out.println(找不到