昆工短学期程序设计报告

程序设计及应用——遗传算法在基因识别中的应用小组：姓名：学号：学院：信息工程与自动化学院班级：指导教师:昆明理工大学2014年7月目录第一章程序概述……………………………………………1一、java…………………………………………………………1二、运行环境………………………………………………………11．硬件环境2．软件环境第二章遗传算法……………………………………………3一、遗传算法方程………………………………………………3二、程序流程图…………………………………………………4第三章基因识别……………………………………………5一、基因及基因识别……………………………………………51.基因2.基因识别二、常用算法及程序……………………………………………5三、程序代码……………………………………………………6四、运行结果……………………………………………………8五、分析…………………………………………………………91.程序分析……………………………………………………92.结果分析……………………………………………………113.心得体会……………………………………………………111第一章、程序概述一、JavaJava是一种程序设计语言，由SunMicrosystem公司于1995年推出；早在1991年，Sun公司的开始开发名为Oak的程序设计语言，希望用来控制嵌入在有线电视机顶盒和PDA等设备中的微处理器；1994年，Oak语言正式更名为Java；Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。Java是功能完善的通用程序设计语言，可以用来开发可靠的、要求严格的应用程序。Sun公司对Java编程语言的解释是：Java编程语言是个简单、面向对象、分布式、解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言。Java由四方面组成：Java编程语言、Java文件格式、Java虚拟机(JVM)、Java应用程序接口(JavaAPI)Java运行系统一般由类装载器、字节码校验器、解释器、代码生成器和运行支持库等几个部分组成。开发和运行Java程序，必须依赖和使用由SunMicrosystem公司提供的Java开发工具包（JavaDevelopmentKit）。开发java程序的步骤（1）创建Java源程序Java源程序使用任何文本编辑器创建与编辑，用.java作为扩展名，其实就是一个使用Java语言编写的文本文件；（2）编译源程序Java编译器读取Java源程序并翻译成Java虚拟机能够明白的指令集合，并以字节码的形式保存在文件中，通常，字节码文件以.class作为扩展名；（3）运行class（字节码）文件Java解释器读取字节码文件，取出指令并翻译成计算机能够执行的机器代码，完成运行过程。二、运行环境1．硬件环境处理器：Intel®Core(TM)i5，CPU：1.80GHz，硬盘容量：500G，系统：Windows7(32位)22．软件环境（1）Java语言的软件开发工具包jdk1.7.0，jdk是Java语言的软件开发工具包，jdk有各种适合操作系统的版本，我们应该选择合适的版本安装，安装完成后还要进行环境变量的配置，否则Java不能在电脑上使用。安装和配置好环境变量后就可以编写Java程序了，通常我们用记事本来写代码，先把记事本的名字改为英文，后缀改为Java，写完代码再通过cmd控制台对代码进行编译，编译无误就可以运行了。（2）运行Java程序所需的环境jre7，（3）基于Java的集成开发环境eclipse.eclipse是Java的集成开发环境。eclipse是一个开放源代码的、基于Java的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，eclipse附带了一个标准的插件集，包括Java开发工具JDK。尽管Eclipse是使用Java语言开发的，但它的用途并不限于Java语言；例如，支持诸如C/C++、COBOL、PHP等编程语言的插件已经可用，或预计将会推出。Eclipse框架还可用来作为与软件开发无关的其他应用程序类型的基础，比如内容管理系统。3niiiiFFP1/第二章、遗传算法一、遗传算法方程遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算最初是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。随着著作的出版，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。其中轮盘赌选择又称为比例选择算子，实现步骤如下（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。轮盘赌选择的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：4二、程序流程图初始化初始种群（编码成位串形式）计算每个个体的适应度是否满足优化准则Yes输出结果遗传算子No选择交叉变异产生新一代种群5第三章、基因识别一、基因及基因识别1.基因DNA是生物遗传信息的载体，其化学名称为脱氧核糖核酸。DNA分子是一种长链聚合物，DNA序列由腺嘌呤A、鸟嘌呤G、胞嘧啶C、胸腺嘧啶T这四种核苷酸符号按一定的顺序连接而成。其中带有遗传信息的DNA片段称为基因。在真核生物的DNA序列中，基因通常被划分为许多间隔的片段，其中编码蛋白质的部分，即编码序列片段，称为外显子，不编码的部分称为内含子。外显子在DNA序列剪接后仍然会被保存下来，并可在蛋白质合成过程中被转录、复制而合成为蛋白质。DNA序列通过遗传编码来储存信息，指导蛋白质的合成，把遗传信息准确无误地传递到蛋白质上去并实现各种生命功能。2.基因识别基因识别——使用计算机手段识别DNA序列上的具有生物学特征的片段，其对象主要是蛋白质编码基因，也包括其他具有一定生物学功能的因子，如RNA、mRNA基因等一些非编码基因，基因识别是生物信息学领域里的一个重要研究内容。二、常用算法及程序通常的计算机基因识别方法大致可以分为三类：序列相似性方法、从头预测方法、序列相似性和从头预测方法相结合的第三类方法。遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，6重复此过程，直到满足某种收敛指标为止。遗传算法的基本运算过程如下：(a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。(b)个体评价：计算群体P(t)中各个个体的适应度。(c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。(d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。(e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。(f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。三、程序代码：packageorg.jenetics.example;importjava.io.*;publicclassLi{publicstaticvoidmain(Stringargs[]){StringfilePath=D:\\gene.txt;StringBuffersb1=readTxtFile(filePath);printgene(sb1);}staticvoidprintgene(StringBuffersb){Stringgene=;intbegin=-1,end,index;intlen=sb.length();booleannext=true;while(next){booleanflag=true;7begin=sb.indexOf(ATG,begin+1);ifbegin=len-3||begin0){next=false;flag=false;}index=begin+3;end=index;while(flag&&index=len-3){Stringcoden=sb.substring(index,index+3);if(coden.equals(TAA)||coden.equals(TAG)||coden.equals(TGA)){end=index+3;intgenelen=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;}}}staticpublicStringBufferreadTxtFile(StringfilePath){StringBuffersb=newStringBuffer();try{Stringencoding=GBK;Filefile=newFile(filePath);if(file.isFile()&&file.exists()){InputStreamReaderread=newInputStreamReader(newFileInputStream(file),encoding);BufferedReaderbufferedReader=newBufferedReader(read);StringlineTxt=null;while((lineTxt=bufferedReader.readLine())!=null){sb.append(lineTxt);}read.close();}else{System.out.println(找不到指定的文件);}}8catch(Exceptione){System.out.println(读取文件内容出错);e.printStackTrace();}returnsb;}}四、运行结果图4.1运行结果1图4.2运行结果29五、分析1.程序分析（1）从文件读取基因序列读取待识别基因的或许可以考虑两种方法：直接在代码中输