基于3D引擎的生物基因的三维重构技术课程设计(初模版).docVIP

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