遗传算法 ppt课件

1.3 遗传算法与传统方法的比较
传统算法 起始于单个点 遗传算法 起始于群体
改善 （问题特有的）
否
改善 （独立于问题的） 否
终止？
终止？ 是 结束
是
结束
1.3.1遗传算法与启发式算法的比较
启发式算法是通过寻求一种能产生可行解的启发式规则，找到问 题的一个最优解或近似最优解。该方法求解问题的效率较高，但是具有 唯一性，不具有通用性，对每个所求问题必须找出其规则。但遗传算法 采用的是不是确定性规则，而是强调利用概率转换规则来引导搜索过程。
1.2 遗传算法的特点
遗传算法是一种借鉴生物界自然选择和自然遗传机制 的随机搜索法。它与传统的算法不同，大多数古典的优化算 法是基于一个单一的度量函数的梯度或较高次统计，以产生 一个确定性的试验解序列；遗传算法不依赖于梯度信息，而 是通过模拟自然进化过程来搜索最优解，它利用某种编码技 术，作用于称为染色体的数字串，模拟由这些串组成的群体 的进化过程。
1.2.2 遗传算法的缺点
（1）编码不规范及编码存在表示的不准确性。 （2）单一的遗传算法编码不能全面地将优化问题的约束表示 出来。考虑约束的一个方法就是对不可行解采用阈值，这样， 计算的时间必然增加。 （3）遗传算法通常的效率比其他传统的优化方法低。 （4）遗传算法容易出现过早收敛。 （5）遗传算法对算法的精度、可信度、计算复杂性等方面， 还没有有效的定量分析方法。
上述遗传算法的计算过程可用下图表示。
遗传算法流程图
目前，遗传算法的终止条件的主要判据有 以下几种：
• 1） 判别遗传算法进化代数是否达到预定的最大代数； • 2） 判别遗传搜索是否已找到某个较优的染色体； • 3） 判别各染色体的适应度函数值是否已趋于稳定、再上升 否等。

以变异概率Pm改变染色体的某一个基因,当以二进制 编码时，变异的基因由0变成1，或者由1变成0。 平均约1-2%。
1
1
0
1
0
0
0
1
变异基因
变异基因
0
1
0
1
0
1
0
1
比起选择和交叉操作，变异操作是GA中的次要操作，但 它在恢复群体中失去的多样性方面具有潜在的作用
停止准则(Termination Criteria)
如何编码？
选 择
交 叉
变 异
遗传算法的基本操作
选择(selection):
根据各个个体的适应值，按照一定的规则或方法，从第t代群体 P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。
交叉(crossover):
将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个 概率Pc (称为交叉概率，crossover rate)交换它们之间的部分染色体。
在完全图中寻找 一个最小圈
旅行商问题的应用
例5. 碎纸片的拼接复原 破碎文件的拼接在司法物证复原、历史文献修复以及军 事情报获取等领域都有着重要的应用。传统上，拼接复 原工作需由人工完成，准确率较高，但效率很低。特别 是当碎片数量巨大，人工拼接很难在短时间内完成任务。 随着计算机技术的发展，人们试图开发碎纸片的自动拼 接技术，以提高拼接复原效率。请讨论以下问题： 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片 （仅纵切），建立碎纸片拼接复原模型和算法，并针对 附件1、附件2给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干预，请写出干预 方式及干预的时间节点。复原结果以图片形式及表格形 式表达（见【结果表达格式说明】）。

5.3.3 多交配位法
单交配位方法只能交换一个片段的基 因序列，但多交配位方法能够交换多 个片段的基因序列 1101001 1100010 1100000 1101011
交配前
交配后
5.3.4 双亲单子法
两个染色体交配后，只产生一个子染 色体。通常是从一般的交配法得到的 两个子染色体中随机地选择一个，或 者选择适应值较大的那一个子染色体
6.1.4 基于共享函数的小生境实现方 法
6.1.1 小生境遗传算法的生物 学背景
•小生境是特定环境下的生存环境
•相同的物种生活在一起，共同繁 衍后代 •在某一特定的地理区域内，但也 能进化出优秀的个体 •能够帮助寻找全部全局最优解和 局部最优解（峰顶）
6.1.2 基于选择的小生境实现 方法
•只有当新产生的子代适应度超过 其父代个体的适应度时，才进行 替换，否则父代保存在群体中 •这种选择方式有利于保持群体的 多样性 •这种方法有利于使得某些个体成 为它所在区域中的最优个体
5.1.3 实数编码的实现方法(续)
•适合于精度要求较高的问题 •便于较大空间的遗传搜索 •改善了遗传算法的计算复杂性， 提高了效率 •便于遗传算法与经典优化算法混 合使用 •便于设计针对问题的专门知识型 算子 •便于处理复杂的决策约束条件
5.2 选择算子
5.2.1 概率选择算子
5.2.2 适应值变换选择算子
•pm: 变异概率，一般取0.0001—0.1
4.1 问题描述 4.2 问题转换和参数设定 4.3 第0代情况 4.4 第0代交配情况 4.5 第1代情况 4.6 第1代交配情况 4.7 第1代变异情况 4.8 第2代情况 4.9 第2代交配情况
4. 基本遗传算法举例
4.1 问题描述

意义
• 近年来，遗传算法已被成功地应用于下业、经 济答理、交通运输、工业设计等不同领域.解决 了许多问题。例如，可靠性优化、流水车间调 度、作业车间调度、机器调度、设备布局设计、 图像处理以及数据挖掘等。本文将从遗传算法 的理论和技术两方而概述目前的研究现状。描 述遗传算法的主要特点、基木原理以及各种改 进算法，介绍遗传算法的程序设计。 • 遗传程序设计是借鉴生物界的自然选择和遗传 机制，在遗传算法的基础上发展起来的搜索算 法，它己成为进化计算的一个新分支。
问题的初始（侯 选）解 编码为染色体 （向量） 种群P（t） 计算各染色体适 应度 通过遗传运算存 优去劣 种群P（t+1） N 种群满足预定 指标 Y 解码染色体 问题解答空间 图1 遗传算法工作原 理示意图
复 制 交 换 变 异
种群P（t）种群P （t+1）
简单遗传算法（SGA）
选择
• 选择运算又称为繁殖、再生，或复制运算，用于模拟生物 界去劣存优的自然选择现象。它从旧种群中选择出适应性 强的某些染色体，放入匹配集（缓冲区），为染色体交换 和变异运算产生新种群做准备。适应度越高的染色体被选 择的可能性越大，其遗传基因在下一代群体中的分布就越 广，其子孙在下一代出现的数量就越多。
• 式中x为决策变量，式2-1为目标函数式，式2-2、2-3为约束条件， U是基本空间，R是U的子集。满足约束条件的解X称为可行解， 集合R表示所有满足约束条件的解所组成的集合，称为可行解集 合。 遗传算法的基本运算过程如下： a)初始化:设置进 化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为 初始群体P(0)。 b)个体评价：计算群体P(t)中各个个体的适 应度。 c)选择运算:将选择算子作用于群体。选择的目的是 把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再 遗传到下一代。选择操作是建立在群体中个体的适应度评估基础 上的。 d)交叉运算；将交叉算子作用于群体。所谓交叉是 指把两个父代个体的部分结构加以替换重组而生成新个体的操作。 遗传算法中起核心作用的就是交叉算子。 e)变异运算：将 变异算子作用于群体。即是对群体中的个体串的某些基因座上的 基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得 到下一代群体P(t 1)。 f)终止条件判断:若t=T,则以进化过程 中所得到的具有最大适应度个体作为最优解输出，终止计算。