《基于3D引擎的生物基因的三维重构技术 课程设计(初模版).doc》由会员分享，可在线阅读，更多相关《基于3D引擎的生物基因的三维重构技术 课程设计(初模版).doc（24页珍藏版）》请在三一办公上搜索。
1、本科课程设计论文 基于3D引擎的生物基因的三维重构技术专业名称：自动化学生姓名：许庆丰指导教师：杨宁设计论文 课程 任务书一、 题目 基于3D引擎的生物基因的三维重构技术二、 指导思想和目的要求 熟悉3D引擎、生物基因的基本原理；对基于3D引擎的3D重构方法进行综述；阅读最新国内外参考文献8篇以上。 两周完成设计任务，提交5000字以上的小论文。附参考文献并在论文上相应位置进行标注三、 主要技术指标1.3D引擎技术2.ChIA-PET技术3.遗传算法原理学生 _ 指导教师 _ 系主任 _摘要 通过查找资料文献，了解3D引擎技术的基本含义及内容，了解生物基因的结构及原理。了解了通过ChIA-PE
2、T技术可以探知基因的相互作用及结构。了解了遗传算法的原理及基本应用 配对末端标签测序分析染色质相互作用(ChIA-PET)技术是一项在全基因组范围内分析远程染色质相互作用的新技术。它把染色质免疫沉淀(ChIP)技术、染色质邻近式连接技术、配对末端标签( PET)技术和新一代测序技术融为一体，在基因组三维折叠和套环状态下分析基因表达和调控。ChIA-PET技术已用于确定人乳腺腺癌细胞内雌激素受体a 的结合位点之间的相互作用。随着更多蛋白质因子的发现及其抗体的应用，该技术可实时捕获全基因组范围内参与复制、转录过程的蛋白质因子结合位点以及结合位点间的相互作用，这对于阐明基因调控和疾病发生机制具有重大
3、意义。 关键词：染色体，基因，三维结构，ChIA-PET技术Abstract By looking up information literature, understand the basic meaning and content of 3 d engine technology, understand the structure and principle of the biological gene. Learned by ChIA PET technology can detect gene interactions and structure.Understanding the p
4、rinciple of genetic algorithm and the basic application Chromatin interaction analysis by paired-end tag sequencing (ChIA-PET) is a whole-genome approach for long-distance chromatin interaction analysis. It is a technique that incorporates chromatin immunoprecipitation, chromatin prox-imity ligation
5、, paired-end tag, and next-generation sequencing to study gene expression and regulation in the genomes three-dimensional folding and looping state. ChIA-PET has been applied to the identification of the estrogen-receptor-a-binding sitesand the interactions among the binding sites in human breast ad
6、enocarcinoma cells. With more protein factors being found andtheir antibodies being used, it will allow real-time and whole-genome identification of the DNA replication and transcription-involved protein factor-binding sites and the interactions among the binding sites, which has a great significanc
7、e to reveal themechanisms of gene regulation and the pathogenesis of diseases.Key words：hromosomes；genes；three-dimensional structure；ChIA-PET 目 录第一章 基本概念介绍.6 1.1 3D引擎简介.6 1.2 生物基因简介.7第二章 相关技术算法介绍.10 2.1 前言.10 2.2 ChIA-PET技术.112.2.1 ChIA-PET技术的原理与方法.12 2.2.2 ChIA-PET技术的优、缺点.15 2.2.3 总结.16 2.3 遗传算法.16
8、 2.3.1 引言.16 2.3.2 遗传算法的原理及特点.17 2.3.3 结束语.21参考文献.22课程设计小结及致谢.23第1章 基本概念介绍1.1 3d引擎简介1.1.1定义 3D引擎是将现实中的物质抽象为多边形或者各种曲线等表现形式，在计算机中进行相关计算并输出最终图像的算法实现的集合。 3D引擎就像是在计算机内建立一个“真实的世界” 3D引擎作为一个名词已经存在了很多年，但即使是一些专业的引擎设计师，也很难就它的定义达成一个共识。通常来说，3D引擎作为一种底层工具支持着高层的图形软件开发。你可以把它看成是对3D API的封装，对一些图形通用算法的封装，对一些底层工具的封装。我无法准
9、确的定义3D引擎的含义和作用，因为针对不同的用户和开发项目，3D引擎完成的功能可能都有不同。因此，我将从功能的角度来定义3D引擎，这种定义法也许能更确切的表达出一个3D引擎的真实含义。1.1.2功能3D引擎最基本的功能应该包括：数据管理：包括场景管理，对象系统，序列化，数据与外部工具的交互，底层3维数据的组织和表示。渲染器是：3D引擎的核心部分，它完成将3D物体绘制到屏幕上的任务。渲染器分为硬件渲染器和软件渲染器。之所以要说是合理的渲染器，是因为一个引擎的渲染能力是由多方面决定的。比如一款以实时游戏作为目标的游戏，会选择基于光栅化的渲染算法。在这种设计前提下，几何体一级的数据不会过于详细，例如
10、物体表面的BRDF，折射率，纹理坐标空间的变化率，切线空间的变化率（当然随着硬件能力的提升和Shader能力的发展，这些数据也会出现在一些比较高级的游戏引擎中），这时候即使你在设计初期就考虑到这些数据需求，并将它们表现在了Render中，最后也不会有任何意义。交互能力：简单的说，就是开发工具。任何一款3D引擎如果没有开发工具都不能称为是完整的。这些开发工具可能是一些文件转换器，场景编辑器，脚本编辑器，粒子编辑器.有了上面3种功能，就可以称为3D引擎了。3d引擎1.2 生物基因简介DNA的三级结构与功能（一）DNA超螺旋双螺旋DNA进一步扭曲盘绕则形成其三级结构，超螺旋是DNA三级结构的主要形式
11、。自从1965年Vinograd等人发现多瘤病毒的环形DNA的超螺旋以来，现已知道绝大多数原核生物都是共价封闭环分子，这种双螺旋环状分子再度螺旋化成为超螺旋结构。有些单链环形染色体（如174）或双链线形染色体（如噬菌体入），在其生活周期的某一阶段，也必将其染色体变为超螺旋形式。对于真核生物来说，虽然其染色体多为线形分子但其DNA均与蛋白质相结合，两个结合点之间的DNA形成一个突环结构，类似于CCC分子，同样具有超螺旋形式。超螺旋按其方向分为正超螺旋和负超螺旋两种。真核生物中，DNA与组蛋白八聚体形成核小体结构时，存在着负超螺旋。研究发现，所有的DNA超螺旋都是由DNA拓扑异构酶产生的。（二）染
12、色质和核小体1.染色质真核生物的染色体在细胞生活周期的大部分时间里都是以染色质的形式存在的。染色质是一种纤维状结构，叫做染色质丝，它是由最基本的单位棗核小体成串排列而成的。DNA是染色体的主要化学成分，也是遗传信息的载体，约占染色体全部成分的27%，另外组蛋白和非组蛋白占66%，RNA占6%.组蛋白是一种碱性蛋白质，等电点一般在PH10.0以上，其特点是富含二种碱性氨基酸（赖氨酸和精氨酸），根据这两种氨基酸在蛋白质分子中的相对比例，将组蛋白分为五种类型（表1）。表1五种组蛋白分子的基本参数种类类型碱性氨基酸酸性 氨基酸碱性氨基酸/酸性氨基酸氨基酸 残基数分子量核小体 上位置LysArgLys/
13、ArgH1极度富含Lys29%1%295%5.421523 000连接H2A11%9%1.215%1.412914 500核心H2B16%6%2.713%1.712513 774H3极度富含Lys+富含Arg10%13%0.7813%1.813515 324H411%14%0.7910%2.510211 282*现已证明：H1是与核小体的核心颗粒相当靠近的，认为它位于连接DNA上，只是一种习惯说法。五种组蛋白在同一生物的不同组织中完全一样，在不同的真核生物中也很相似。组蛋白对染色体中DNA的包装有十分重要的作用。2.核小体核小体是构成染色质的基本结构单位，使得染色质中DNA、RNA和蛋白质组织
14、成为一种致密的结构形式。核小体由核心颗粒和连接区DNA二部分组成，在电镜下可见其成捻珠状，前者包括组蛋白H2A，H2B，H3和H4各两分子构成的致密八聚体（又称核心组蛋白），以及缠绕其上一又四分之三圈长度为146bp的DNA链；后者包括两相邻核心颗粒间约60bp的连接DNA和位于连接区DNA上的组蛋白H1，连接区使染色质纤维获得弹性。核小体是DNA紧缩的第一阶段，在此基础上，DNA链进一步折叠成每圈六个核小体，直径30nm的纤维状结构，这种30nm纤维再扭曲成襻，许多襻环绕染色体骨架形成棒状的染色体，最终压缩将近一万倍。这样，才使每个染色体中几厘米长（如人染色体的DNA分子平均长度为4cm）的
15、DNA分子容纳在直径数微米（如人细胞核的直径为67m）的细胞核中。核小体的形成以及DNA超螺旋结构与功能的关系还不十分清楚，可能与基因的转录调节控制有关。 第2章 相关技术算法介绍2.1 前言 如果将人的所有染色体相连并充分伸展的话，其长度可达2米左右，如此庞大的DNA链要全部储存在直径约10微米的细胞核中。此外，基因及其调控元件需要交流，染色质必须打开，允许转录和复制。因此，人们常常提出这样的疑问：“基因的线性顺序与空间排布如何关联?”“基因如何被遥远的元件所调控?”。 阐明染色质复杂结构的技术有染色质构象捕获及更高通量的衍生技术4C、5C，这些提供了长距离的染色质相互作用，但不能扩展到整个
16、染色质相互反应组。在2009年末，两种新方法的迸发，有望绘出全基因组范围的相互作用图谱。 马萨诸塞大学的Job Dekker和Broad研究院的Eric Lander开发出了Hi-C技术，能捕获全基因组范围的相互作用1。Hi-C是一种3C衍生技术，基于交联DNA与生物素linker的邻近连接，能够拉下(pull down)片段，接着进行高通量测序。从800万个读取对中，研究人员产生了基因组范围的接触模型，分辨率在1 MB。Dekker认为Hi-C的难度不在染色质捕获本身，而在于数据的阐释。“数据中存在明显的聚合物特征，它们确定了背景。”他推测，如果想以1 KB的分辨率查看染色体的三维结构，还需
17、要数亿个读取。研究人员还发现了出人意料的结果：染色质并非类似于紧凑、多节的结构，而是一种无节的紧密压缩构象，有活性和无活性的染色质结构域折叠成两个空间各异的区室。一个月后，新加坡基因组研究院的Yijun Ruan和Edwin Cheung在nature上发表了另一项重要技术CHIA-PET 2。它是对读双标签(PET)测序与染色质免疫沉淀(ChIP)的结合，在碱基对的分辨率解析了蛋白介导的功能相互作用。研究人员用II型限制性内切酶将免疫沉淀的DNA片段与条形码linker连接，产生了PET，然后对染色质相互作用(ChIA)的PET进行高通量测序，生成了转录因子依赖的相互作用图谱。对于Ruan而
18、言，数据阐释中的最大问题在于如何处理噪音。“噪音来自两个水平，生物和技术。”生物噪音是由染色质的动态性质引起的，因为它一直在移动，在任一指定时间点许多相互作用都是无意义的。Ruan的理论是有意义的相互作用更强，因此能承受更剧烈的片段化方法。技术上的噪音则来自邻近连接步骤。为了控制这种嵌合体的形成，研究小组将染色质材料均分成两等份，随后加入带有不同条形码的linker，在连接之前再次混匀。嵌合体将在同一个PET上带有不同的linker，随后被排除。Hi-C和ChIA-PET从两个不同的方向靠近染色质相互作用组，一个提供了染色质如何在核中折叠的鸟瞰，另一个观察了特定蛋白对基因组结构的影响。为了增加
19、它们的影响力，提供更为精细的染色质相互作用组图谱，两种方法都将向中心靠拢。更高的测序能力以及新的分析方法将增加Hi-C的分辨率，最终达到1 KB的分辨率。ChIA-PET在更多蛋白如聚合酶上的应用，将鉴定出参与转录等过程的所有染色质相互作用。叠加Hi-C图谱和ChIA-PET图谱，以及现有的注释，将有助于了解三维空间的基因调控。下面重点讲解ChIA-PET技术。2.2 ChIA-PET技术染色质相互作用在基因组功能中的重要性一直备受关注。目前，研究染色质相互作用的技术主要有两大类：分子探针技术和分子相互作用图谱技术。分子探针技术包括电子显微镜技术、原子力显微镜技术和荧光原位杂交技术等，它们能够
20、提供直观的图像，为染色质相互作用的研究提供依据，但其图像的分辨率低，而且不能同时研究多个位点。分子相互作用图谱技术包括染色质构象捕获技术和基于3C技术的ChIP-3C、4C、5C技术等，利用这些技术能够捕获染色质点与点之间或多点之间的相互作用，但它们无法在全基因组范围内研究染色质的相互作用。总之，染色质相互作用的研究一直处于分辨率低和范围局限的状态。Fullwood等2009年11月在Nature上发表文章中提出了一项能够分析全基因组染色质相互作用的新技术配对末端标签测序分析染色质相互作用(chromatin interaction analysis by paired-end tagsequ
21、encing, ChIA-PET)技术。ChIA-PET技术是利用PET测序技术研究免疫沉淀后邻近式连接的DNA片段，以得到染色质相互作用的技术。它灵敏，准确，对在全基因组范围内研究染色质相互作用具有重大意义，现简介如下。2.2.1. ChIA-PET技术的原理与方法ChIA-PET技术应用了PET测序技术的基本原理。PET测序技术的独特之处在于构建配对末端测序模板。从目的DNA片段两个末端提取短标签并将它们配对构成一个PET，对PET进行高通量测序，利用标签序列定位目的DNA片段在基因组中的位置。为了获得短标签，将目的DNA片段两个末端分别与设计好的半连接子(linker)相连。半连接子为具
22、有MmeI限制性内切酶识别位点的寡聚核苷酸序列，而MmeI限制性内切酶能够水解其识别位点下游18/20个碱基对。连接子连接后将DNA片段两个末端配对，随后加入MmeI限制性内切酶，便可得到“标签-连接子-标签(tag-linker-tag)”结构，即PET(图1)。ChIA-PET技术中，借助ChIP技术甲醛固定细胞、超声断裂染色质图2(A)、免疫沉淀图2(B)，以获得与目的蛋白质因子结合的染色质片段。该染色质片段又被称为ChIP DNA片段，即PET测序技术中所需的目的DNA片段。然后进行连接子连接图2(C)。为了在确定蛋白质因子结合位点的同时捕获结合位点间的相互作用，将同一蛋白质因子结合的
23、DNA片段末端先配对图2(D)再进行逆转交联图2(E)。随后进行MmeI限制性内切酶水解图2(F)和高通量测序。这样将产生两种类型的PET：自连接PET(self-ligation PET)和间连接PET(inter-ligationPET)。1.自连接PET 如果一个PET的两个标签来自同一条染色质，基因组跨度在ChIP DNA片段范围(小于3 kb)内，方向相同且为相应单链连接，便被认为是一个ChIPDNA片段中两个标签的自连接，称为自连接PET。自连接PET是确定蛋白质因子结合位点的基础。通过构成自连接PET的两个标签可以确定其代表的ChIPDNA片段，而该ChIP DNA片段包含蛋白质
24、因子结合位点。利用峰检出程序(peak-finding algorithm)，把所有自连接PET两个标签代表的ChIP DNA片段映射(map)到参照基因组上，再将参照基因组每一区域被映射的次数转化为不同高度的峰，每一区域被映射的次数越多，峰越高。其每一高峰，都是大量的包含蛋白质因子结合位点的ChIP DNA片段重叠的区域，被认为是蛋白质因子结合位点。除高峰外，其它峰为弱的蛋白质因子结合位点或实验噪音(experi-mental noise)。2.间连接PET如果一个PET不符合自连接PET的标准，其便为两个ChIP DNA片段间的连接，被称作间连接PET。间连接PET又分为三类：染色质内的间
25、连接PET(intrachromosomal inter-ligation PET)、染色质间的间连接PET(interchromosomal inter-ligation PET)和不同方向的间连接PET(different orientation inter-ligation PET)。其中，染色质内的间连接PET所占比例最大，是用于确定结合位点间相互作用的重要依据。它是两个标签来自同一条染色质但是基因组跨度大于3 kb的间连接PET。相距较远的两个标签之所以能够构成染色质内的间连接PET，是因为这两个标签代表的两个ChIP DNA片段由同一个蛋白质因子结合着，即这两个DNA片段间存在相互
26、作用。故染色质内的间连接PET可以用来确定结合位点间的相互作用。由于间连接PET的两个标签分别来自两个ChIP DNA片段，需先依据参照基因组，分别延长两个标签远离连接子的序列，从20 bp延长至1500 bp(大多数ChIPDNA片段小于1500 bp)，将其延长为相应的ChIPDNA片段。再利用峰检出程序，将所有延长后的ChIP DNA片段在参照基因组不同区域的映射次数用峰的高度表示。出现高峰的区域，为蛋白质因子结合位点，其应与自连接PET确定的蛋白质因子结合位点一致。若一个间连接PET群，同时满足以下两个条件：(1)每一间连接PET的两个标签所代表的两个ChIP DNA片段，均包含一个高
27、峰所对应的区域；(2)每一间连接PET映射的两个高峰区域是相同的，则为重叠的间连接PET群(图3)。重叠的间连接PET群可被用来确定结合位点间的相互作用。其映射的两个高峰区域，即蛋白质因子结合位点，存在相互作用。此外，染色质内的间连接PET的存在还可以表明，蛋白质因子通过使染色质成环形成空间邻位结构以发挥其在复制、转录过程中的调节作用，从而推断结合位点间的相互作用是调节复制、转录的一个最基本的机制。染色质间的间连接PET数量较少，表明染色质间存在弱的相互作用或为实验噪音；不同方向的间连接PET数量甚少，在正常情况下不应存在，被认为是实验噪音。此二者对于正确判定染色质相互作用缺乏价值。 为了评估
28、非特异性嵌合连接对实验结果的影响，设计了具有标识作用的两种核苷酸序列半连接子：半连接子A(CG)和半连接子B(AT)。连接子连接时将染色质均分成两份，一份加入半连接子A，另一份加入半连接子B，除去多余的半连接子后，混匀，依次进行其后操作。由于结果中同时带有半连接子A和半连接子B的PET是极少的，即非特异性嵌合连接是偶然的、互不重叠的，因此不会被误认为是相互作用。综上所述，重叠的PET群被认为是蛋白质因子结合位点和结合位点间的相互作用，而甚少的PET则被认为是实验噪音。2.2.2. ChIA-PET技术的优、缺点ChIA-PET是全基因组范围内，无偏差的(unbiased)，从头(de novo
29、)分析染色质相互作用的技术。其具有以下优点：(1) ChIA-PET技术在全基因组范围内确定蛋白质因子结合位点的同时，能够确定结合位点间的相互作用。这也是其与仅能确定蛋白质因子结合位点，而不能确定结合位点间相互作用的ChIP-PET(ChIP analysis by paired-end tag sequencing)技术的唯一区别。能否捕获结合位点间的相互作用，关键在于末端配对和逆转交联的顺序。ChIA-PET技术先末端配对，再逆转交联，故能捕获由同一蛋白质因子结合的DNA片段间的相互作用。而ChIP-PET技术先逆转交联，使原本被蛋白质因子结合的DNA片段分散，只能产生自连接PET而不能产
30、生间连接PET，所以无法捕获结合位点间的相互作用(图4)。(2) ChIA-PET技术利用超声打断DNA-蛋白质复合体，避免了利用限制性内切酶水解DNA-蛋白质复合体引入的染色质随机连接, 因而有效减少了相互作用的噪音。(3) ChIA-PET技术借鉴了ChIP技术的优点棗利用特异性的抗体捕获与蛋白质因子结合的染色质，进而得到蛋白质因子结合位点和结合位点间的相互作用，避免了全基因组分析的复杂性。ChIA-PET技术的发明，对于确定单一的功能性的转录因子结合位点是一个重大突破，然而要想确定蛋白质因子中每一种相互作用的蛋白质，尚需其他技术的介入。对于不依赖蛋白质因子的染色质相互作用，ChIA-PE
31、T技术不能检测。此外，ChIA-PET技术受众多因素影响，如：(1)所用抗体的质量，纯度和特异性。(2)ChIA-PET技术需要依赖峰检出程序将PET映射到参照基因组并检出高峰，不同峰检出程序定义高峰的标准等不同，故不同峰检出程序的使用会影响实验结果。2.2.3. 结语ChIA-PET技术已成为分析染色质相互作用的重要方法，同时它标志着人类基因组通过折叠进行基因表达调控这一全新研究领域的开始。随着参与DNA复制、转录和染色质构象的蛋白质因子的发现及其抗体的使用，ChIA-PET技术将能确定更多染色质的相互作用。ChIA-PET技术对于揭示细胞增殖、分化等过程基因调控机制是至关重要的。2010年
32、，基于ChIA-PET技术原理，用于分析染色质相互作用的一整套软件已经研发并成为共享资源。通过相互作用图谱的绘制，可以更好地确定干预的特定目标，从而更好地了解和控制疾病。2.3 遗传算法2.3.1 引言 遗传算法是模拟遗传选择和自然淘汰的生物进化过程的计算模型，由美国Michigan大学的Holland教授于1969年提出，后经DeJong、Goldberg等人归纳总结，形成一种新的全局优化搜索算法。 所谓遗传算法来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。遗传算法是模拟自然界生物进化过程与机制求解极值问题的一类自组织、自适应人工智能技术，其基本思想是模拟自然界遗传机制和
33、生物进化论，引用了随机统计理论而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代式算法，是一种过程搜索最优解的算法，具有坚实的生物学基础。 遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学等领域，适用于解决复杂的非线性和多维空间寻优问题。 2.3.2 遗传算法的基本原理及特点 （一）遗传算法的基本原理 遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。在利用遗传算法求解问题时，问题的每个可能的解都被编码成
34、一个“染色体”，即个体，若干个个体构成了群体（所有可能解），通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，这些个体经过交叉和变异算子进行再组合生成下一代新的种群。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化。因此，遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。遗传算法的基本流程描述如图5所示。图5 （二）遗传算法的特点 遗传算法利用了生物进化和遗传的思想，不同于枚举法、启发式算法、搜索算法等传统的优化方法，具有如下特点： （1）自组织、自适应和智能性。遗传算法消除了算法设计中最大的障碍，
35、即需要事先描述问题的全部特点，并说明针对问题的不同特点，算法应采取的措施。直接处理的对象是参数编码集，而不是问题参数本身。它可用来解决复杂的非结构化问题，具有很强的鲁棒性。 （2）搜索过程中使用的是基于目标函数值的评价信息，搜索过程既不受优化函数连续性的约束，也没有优化函数必须可导的要求。 （3）易于并行化，可降低由于使用超强计算机硬件所带来的昂贵费用。 （4） 算法基本思想简单，运行方式和实现步骤规范，便于具体使用。 （三）遗传操作 遗传操作的任务是根据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言遗传操作可使问题的解逐代地优化，逼近最优解。 遗传操作包括以
36、下选择、交叉和变异三个基本遗传算子。选择和交叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到接近最优解的能力。（1）选择 选择是在适应度评估的基础上，从群体中选择优良的个体，并淘汰劣质个体的操作。适应度越大的个体，被选择的可能性就越大。 常用的选择方法有： a）轮盘赌选择法 又称为适应度比例法，是目前遗传算法中最基本也是最常用的选择方法。个体的适应度值越大，它被选中的概率就越高，体现了“适者生存”这一自然选择原理。被选中的个体被放入配对库中，随机地进行配对，以进行下面的交叉操作。 b) 局部选择法 在局部选择法中，每个个体处于一个约束环境中，称为局部邻集（而其它选择方法中视整个种
37、群为个体之邻集），个体仅与其临近个体产生交叉，该邻集的定义由种群的分布结构给出，邻集可被当作潜在的交配伙伴。 c) 最佳个体保存法 把群体中适应度最高的个体不进行配对交叉而直接复制到下一代。这样做的好处是保证了进化过程中某一代的最优解不被交叉和变异操作所破坏。但会使局部最优的遗传基因急速增加，而使进化停滞于局部最优解，即这种方法影响了遗传算法的全局搜索能力。因此，最佳个体保存法通常不单独使用。d) 竞争法 个体的选择公式为f m = maxf i， f j，即随机地选取两个个体，对其适应值进行比较，大的被选中，小的被自然淘汰；如果两个个体的适应值相同，则任意选取其中的一个。被选中的个体放入配对
38、库中。重复此过程，直至配对库中包含N 个个体为止。这种方法既保证了配对库中的个体在解空间中有较好的分散性，同时又保证了加入配对库中的个体具有较大的适应值。 e) 排序选择法 首先根据各个体的适应度大小进行排序，然后基于所排序号进行选择。（2）交叉/基因重组 交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉的目的是为了能够在下一代产生新的个体，就象人类社会的婚姻过程。通过交叉操作，遗传算法的搜索能力得以飞跃性的提高。交叉是遗传算法获取新优良个体的最重要手段。 交叉操作是按照一定的交叉概率（也称交叉率）在配对库中随机地选取两个个体进行的。交叉的位置也是随机确定的。交叉算子分为以
39、下几种： a)单点交叉 又简称为简单交叉，即在个体串中随机地选定一个交叉点，两个个体在该点前或后进行部分互换，以产生新的个体。 b)多点交叉 多个个体无重复随机地选择，在交叉点之间的变量间续地相互交换，产生两个新的后代。 c)均匀交叉 是通过设置屏蔽字来决定新个体的基因如何继承父代个体中相应的基因。 根据研究对象不同，还有多种可选择的交叉方法，如顺序交叉、循环交叉、洗牌交叉、缩小代理交叉等。、（3）变异 变异就是以很小的变异概率Pm随机地改变群体中个体的某些基因的值。变异操作的基本过程是：对于交叉操作中产生的后代个体的每一基因值，产生一个 0， 1 之间的伪随机数rand，如果rand Pm，
40、就进行变异操作。 变异本身是一种局部随机搜索，与选择、交叉算子结合在一起，就能避免由于选择和交叉算子而引起的某些信息的永久性丢失，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持群体的多样性，以防止出现未成熟收敛。因此，变异操作是一种防止算法早熟的措施。 几种常用的变异操作如下： a)基本位变异 对个体编码串以变异概率Pm随机指定某一位或某几位基因进行变异操作。 b)均匀变异 也叫一致变异，分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中原有基因值。均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动
41、，从而可以增加群体的多样性，使算法能够处理更多的模式。 c)二元变异 需要两条染色体参与，通过二元变异操作后生成两条新个体中的各个基因分别取原染色体对应基因值的同或/异或。它改变了传统的变异方式，有效地克服了早熟收敛，提高了遗传算法的优化速度。d)高斯变异 在进行变异时用一个均值为、方差为2的正态分布的一个随机数来替换原有基因值。其操作过程与均匀变异类似。 2.3.3 结束语 遗传算法的理论与技术研究主要包括编码、交叉运算、变异运算、选择运算等遗传操作以及适应度评价等问题。本文就遗传算法的理论与技术研究的诸方面进行了探讨。 遗传算法是一个十分活跃的研究领域，遗传算法的研究正在从理论的深度、技术的多样化以及应用的广度不断地探索，朝着计算机拥有甚至超过人类智能的方向努力。参考文献1 Nan Gao, Ning Yang, Jijun Tang, et al.Ancestral Genome Inference using a Genetic AlgorithmApproach2 Nan Gao, Fei Hu JiJun, Tang ,e
