算法设计与分析W16-现代启发算法2

VIP免费

2025-01-13 0 0 4.16MB 95 页 5.9玖币

侵权投诉

现代启发式算法

（

Modern Heuristics

）

Part 2

：遗传、粒子群、蚁群

遗传算法

（Genetic Algorithm）

•模仿生物种群中优胜劣汰的选择机制，通过种群

中优势个体的繁衍进化来实现优化的功能

• 发展历史

– 由美国密歇根大学的John H. Holland教授及其学生于

20世纪60年代末到70年代初提出

– 在1975年出版的《自然与人工系统的自适应性》

(Adaptation in Natural and Artificial Systems)中,

Holland系统地阐述了遗传算法的基本理论和方法, 提

出了对遗传算法的理论发展极为重要的模板理论

(Schema Theory).

– 后来De Jong和Goldberg等人完善了遗传算法.

遗传算法的产生

生物的进化

•进化(Evolution)

– 生物在其延续生存的过程中, 逐渐适应其生存环境, 使

得其品质不断得到改良, 这种生命现象称为进化.

•群体(Population)

– 生物的进化是以团体的形式共同进行的, 这样的一个团

体称为群体,

– 组成群体的单个生物称为个体(Individual),

– 每个个体对其生存环境都有不同的适应能力, 这种适应

能力称为个体的适应度(Fitness).

生物进化——达尔文的进化论

•自然选择，适者生存

– 具有较强适应环境变化能力的生物个体具有更高的生存

能力, 容易存话下来, 并有较多的机会产生后代

– 具有较低生存能力的个体则被淘汰, 或者产生后代的机

会越来越少, 直至消亡

•通过这种自然的选择, 物种将逐渐地向适应于生存

环境的方向进化, 从而产生优良物种

生物的遗传与变异

•遗传( Heredity)：生物从其亲代继承特性或性状

的生命现象。

•基因(Gene)：控制生物遗传的物质单元，是有遗

传效应的DNA片段；生物的各种性状由其相应的

基因所控制。

•染色体(Chromosome)：细胞中含有的一种微小

的丝状化合物，包含了生物的所有遗传信息，由

蛋白质和脱氧核糖核酸(DNA)组成。

•细胞(Cell)：构成生物的基本结构和功能单位。

生物的遗传与变异

u同源染色体：在二倍体生物细胞中，形态、结

构基本相同的染色体。这一对染色体其中的一

条来自母方，另一条来自父方。

u等位基因：指位于一对同源染色体相同位置上

控制同一性状不同形态的基因。

生物的遗传与变异

u首先，在细胞间期进行染色体和DNA的复制，

数目分别变为一般细胞的两倍。

DNA复制出错的概率约十亿分之一，这是人类得癌症

的主因，也是生物进化（变异）根源

生物的遗传与变异

(1) 减数分裂前期：

开始时，细胞含有两

组染色体，每个染色

体各含有两个染色单

体。

(4) 第二次分裂：

每个染色体中的两个

染色单体被拉开，形

成4个新细胞，各含

一对单条染色题。

(2) 同源染色体按四

分体排列并进行部分

交换。使同源染色体

之间的基因产生部分

重新组合，即重组。

(3) 第一次分裂：

同源染色体互相分

离，形成两个新细

胞，各自拥有一对

染色体。

生物的遗传与变异

• 细胞在分裂时, 遗传物质DNA通过复制(Reproduction) 而

转移到新产生的细胞中, 新细胞就继承旧细胞的基因

• 有性生物在繁殖下一代时，两个同源染色体之间通过交

叉(Crossover)而重组, 即两个染色体的某一相同位置处的

DNA被切断, 其前后两串分别交叉组合而形成两个染色体

• 在进行复制时, 可能以很小的概率产生某些差错, 从而使

DNA发生某种变异(Mutation), 产生出新的染色体.

构成了遗传算法的生物学基础

复制、交叉、变异被称为遗传算子

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

现代启发式算法（ModernHeuristics）Part2：遗传、粒子群、蚁群遗传算法（GeneticAlgorithm）•模仿生物种群中优胜劣汰的选择机制，通过种群中优势个体的繁衍进化来实现优化的功能•发展历史–由美国密歇根大学的JohnH.Holland教授及其学生于20世纪60年代末到70年代初提出–在1975年出版的《自然与人工系统的自适应性》(AdaptationinNaturalandArtificialSystems)中,Holland系统地阐述了遗传算法的基本理论和方法,提出了对遗传算法的理论发展极为重要的模板理论(SchemaTheory).–后来DeJong和Goldbe...

展开>> 收起<<

算法设计与分析W16-现代启发算法2.pdf

共95页,预览19页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W16-现代启发算法2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: