By 谢广明 , 2005~2006 学年度第一学期 1 Genetic Algorithm , GA 第二章 遗传算法 (II)

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
§3.4 空间直线的方程.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
一、能线性化的多元非线性回归 二、多元多项式回归(线性化)
第三章 函数逼近 — 最佳平方逼近.
第五章 遗传算法.
【主要内容】 介绍遗传算法的主要思想、关键步骤、如何实现以及在数学建模中的应用。
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
不确定度的传递与合成 间接测量结果不确定度的评估
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
第三章 多维随机变量及其分布 §2 边缘分布 边缘分布函数 边缘分布律 边缘概率密度.
第四章 遗传算法的实现技术 80年代以后,遗传算法得到了广泛的使用,在实践过程中,人们对遗传算法的实施提出了许多改进。本节分别予以介绍。
Hadoop I/O By ShiChaojie.
遗传算法原理与应用 Alex
第一讲: 基本流程(1).
计算机数学基础 主讲老师: 邓辉文.
第十章 方差分析.
遗传算法(Genetic Algorithm) Natural Computing
Artificial Neural Networks
使用矩阵表示 最小生成树算法.
工业机器人技术基础及应用 主讲人:顾老师
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
第一章 函数与极限.
习题 一、概率论 1.已知随机事件A,B,C满足 在下列三种情况下,计算 (1)A,B,C相互独立 (2)A,B独立,A,C互不相容
3.2 基于遗传算法的神经网络优化方法.
抽样和抽样分布 基本计算 Sampling & Sampling distribution
线段的有关计算.
顺序表的删除.
概 率 统 计 主讲教师 叶宏 山东大学数学院.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
5.2 常用统计分布 一、常见分布 二、概率分布的分位数 三、小结.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
iSIGHT 基本培训 使用 Excel的栅栏问题
3.1 变化率与导数   3.1.1 变化率问题 3.1.2 导数的概念.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
概 率 统 计 主讲教师 叶宏 山东大学数学院.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
第4课时 绝对值.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
空间平面与平面的 位置关系.
第一部分:概率 产生随机样本:对分布采样 均匀分布 其他分布 伪随机数 很多统计软件包中都有此工具 如在Matlab中:rand
第七、八次实验要求.
基于最大margin的决策树归纳 李 宁.
《工程制图基础》 第五讲 投影变换.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
难点:连续变量函数分布与二维连续变量分布
基因信息的传递.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
计算机问题求解—论题4.10 启发式算法的概念 陶先平 2017年6月5日.
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
线性规划 Linear Programming
遗传算法原理与应用 唐 慧 丰 2006 年 5 月.
插入排序的正确性证明 以及各种改进方法.
位似.
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
§4.5 最大公因式的矩阵求法( Ⅱ ).
第二次课后作业答案 函数式编程和逻辑式编程
最小生成树 最优二叉树.
Presentation transcript:

by 谢广明 , 2005~2006 学年度第一学期 1 Genetic Algorithm , GA 第二章 遗传算法 (II)

by 谢广明 , 2005~2006 学年度第一学期 2 内 容  简单演示  应用实例 1 : TSP  应用实例 2 :函数优化  策略设计  算法改进

by 谢广明 , 2005~2006 学年度第一学期 3 简单演示 问题:求 ( 1 )编码: 编码长度为 5 ( 2 )初始群体生成:群体大小设置为 4 ,随机产生四 个个体: 编码: , , , 解码: 适应度: ( 3 )适应度函数:

by 谢广明 , 2005~2006 学年度第一学期 4 ( 4 )轮盘赌选择:选择概率 个体: , , , 适应度: 选择概率: 选择 和 交配产生下一代 简单演示

by 谢广明 , 2005~2006 学年度第一学期 5 ( 5 )交叉操作:发生交叉的概率取大 交叉点位置的选取是随机的(单点交叉) 简单演示

by 谢广明 , 2005~2006 学年度第一学期 6 ( 6 )变异:发生变异的概率取小 改变某个字节  ( 7 )新群体的产生: 保留上一代最优个体, 1 个新个体取代旧个体 , , , ( 8 )重复上述操作 20 次, 或许就能够得到最优解! 简单演示

by 谢广明 , 2005~2006 学年度第一学期 7 应用实例 1 : TSP  问题回顾 – 给定 n 个城市以及两两城市之间的距离,求解 一条从某个城市出发、不重复地遍历所有其它 城市并最终又回到起始城市的最短路径。  数学描述 – 给定图 G=(V,E), V 为顶点集, E 为边集,确定 一条长度最短的 Hamilton 回路

by 谢广明 , 2005~2006 学年度第一学期 8 应用实例 1 : TSP  编码方案 – 路径表达:对一个旅行最自然的表达 – 一个旅行 5 — >1 — >7 — >8 — >9 — >4 — >6 — >2 — >3 的编码就是( ) – 编码空间和解空间一一对应,总量为 n! 个? – 其实一些解是相同的,因为  ( | ) = ( | )  二者是同一个解  (n -1)!/2

by 谢广明 , 2005~2006 学年度第一学期 9 应用实例 1 : TSP  适应度函数 – 就取为目标函数的倒数,即路径总长度的倒数  初始种群 – 随机生成 40 个  终止条件 –2000 次迭代  参数设置 – 自定

by 谢广明 , 2005~2006 学年度第一学期 10 应用实例 1 : TSP  选择操作算子 : 轮盘式选择  首先计算每个个体 i 被选中 的概率  然后根据概率的大小将将圆 盘分为 n 个扇形,每个扇形 的大小为 。选择时转 动轮盘,参考点 r 落到扇形 i 则 选择个体 i 。 p1p1 p2p2 pipi r

by 谢广明 , 2005~2006 学年度第一学期 11 应用实例 1 : TSP  交叉操作算子 –Davis 提出 OX 算子:通过从一个亲体中挑选一个子序列旅行 并保存另一个亲体的城市相对次序来构造后代 – 例如: p1= ( | | 8 9 ) p2= ( | | 9 3 ) 首先保持中间部分 o1= ( X X X | | X X ) o2= ( X X X | | X X )

by 谢广明 , 2005~2006 学年度第一学期 12 应用实例 1 : TSP  交叉操作算子 然后移走 p2 中已在 o1 中的城市 4 、 5 、 6 和 7 后,得到 2 — 1 — 8 — 9 — 3 该序列顺次放在 o1 中: o1= ( | | 9 3 ) 类似地,可以得到另一个后代: o2= ( | | 5 9 )

by 谢广明 , 2005~2006 学年度第一学期 13 应用实例 1 : TSP  变异操作算子 – 采用倒置变异:在染色体上随机地选择两点,将两 点间的子串反转 – 例如 原个体:( ) 随机选择两点:( 1 2 | | ) 倒置后的个体:( 1 2 | | )

by 谢广明 , 2005~2006 学年度第一学期 14 应用实例1:TSP应用实例1:TSP

by 谢广明 , 2005~2006 学年度第一学期 15 应用实例 1 : TSP  中国城市 TSP 的一个参考解

by 谢广明 , 2005~2006 学年度第一学期 16 应用实例 2 :函数优化  函数优化 – 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理, 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如; [0 , 1] ,计算精度 0.001, 则 0 , 0.001,0.002, …,0.998,0.999,1.000 , 个数为 1001 则用长度为 10 的二进制字符串一次表征所有离散点 , , …,

by 谢广明 , 2005~2006 学年度第一学期 17 应用实例 2 :函数优化  适应度函数 – 例如, f(x)=x 2 - x 5 ,取 C max =2, 即可得到满足要 求的 F(x)

by 谢广明 , 2005~2006 学年度第一学期 18 应用实例 2 :函数优化  其它的就类似于 TSP 的求解了

by 谢广明 , 2005~2006 学年度第一学期 19 策略调整  针对不同实际问题需要调整相应策略  同一个实际问题不同的人也有不同的做法  编码方案  适应度函数设计  选择算子  交叉算子  变异算子  初始种群

by 谢广明 , 2005~2006 学年度第一学期 20 策略调整  编码方案 – 本质:如何表示解 – 二进制:  自变量高维、大范围连续、高精度的时候很难处理  冗余问题,离散化后解的个数介于 2 (n-1) 和 2 n 之间 –D 进制, D=3,8,16, … – 实数编码:无需编码和解码 – 序列编码:例如 TSP 的路径表达 – 树编码:非定长 – 自适应编码 - 长度可调节

by 谢广明 , 2005~2006 学年度第一学期 21 策略调整  适应度函数 – 是进行自然选择的定量标准 – 直接采用目标函数 – 引入适应值调节  线性变换  乘幂变换  指数变换  自适应变换

by 谢广明 , 2005~2006 学年度第一学期 22 策略调整  选择算子 – 轮盘赌选择 (roulette wheel selection)  最基本、最常用的方式,又叫适应度比例选择算子 – 最佳个体保存 (elitist model)  把适应度最高的个体保留到下一代,又叫精英保留 – 排序模型 (rank - based model)  按适应度函数大小排序,根据事先设定的概率表分配选择概率 – 联赛选择模型 (tournament selection model)  随机选择几个进行比较,高的被选,又叫锦标赛模型

by 谢广明 , 2005~2006 学年度第一学期 23 策略调整  选择算子 – 期望值模型 (expected value model) – 排挤模型 (crowding model) – 浓度控制策略 – 共享机制 – 截断选择

by 谢广明 , 2005~2006 学年度第一学期 24 策略调整  交叉算子 – 简单交叉  最基本、最常用的方式,双亲互换子串 – 平坦交叉  二者之间均匀随机产生 – 算术交叉  双亲的凸组合 – 线性交叉  1 : 1 , 3 : 1 , 1 : 3 比较最好的两个留下

by 谢广明 , 2005~2006 学年度第一学期 25 策略调整  交叉算子 – 混合交叉 – 离散交叉 – 启发式交叉 – 模拟二进制交叉 – 单峰正态分布交叉 – 单纯形交叉 – 父体中心交叉 – 几何交叉 – 均匀交叉 – 基于模糊联接的交叉

by 谢广明 , 2005~2006 学年度第一学期 26 策略调整  变异算子 – 随机变异  区间内均匀随机取 – 非一致变异  某个区间内随机扰动 – 边界变异  取边界值 – 多项式变异 – 高斯变异 –Cauthy 变异 – 自适应变异 –Muhlenbein 变异

by 谢广明 , 2005~2006 学年度第一学期 27 策略调整  初始种群 – 对计算结果和计算效率有影响 – 全局性要求初始解尽量分散 – 设计一些生成方法

by 谢广明 , 2005~2006 学年度第一学期 28 求解 TSP 的策略调整  编码方案 – 二进制编码:交叉和变异很难处理 – 顺序表示: 1985 年 Grefenstette 提出,序表示是指所有 城市依次排列构成一个顺序表 (order list), 对于一条旅程, 可以依旅行经过顺序处理每个城市, 每个城市在顺序表 中的顺序就是一个遗传因子的表示, 每处理完一个城市, 从顺序表中去掉该城市. 处理完所有城市以后, 将每个城 市的遗传因子表示连接起来, 就是一条旅程的基因表示. 例如, 顺序表 C = (1,2,3,4,5,6,7,8,9), 一条旅程为 按照这种编码方法, 这条旅程的编 码为表 l = ( )

by 谢广明 , 2005~2006 学年度第一学期 29 求解 TSP 的策略调整  编码方案 – 路径表示:最自然、直接的表示方法 – 布尔矩阵表示:将一个旅程定义为一个优先权 布尔矩阵 M, 当且仅当城市 i 排在城市 j 之前时 矩阵元素 m ij = 1. 这种方法用 n × n 矩阵 M 代表一 条旅程, M 具有如下三个性质 :  1) 矩阵中 1 的数目为 n ( n - 1) / 2 ;  2) m ii = 0, i= 1,2,., n ;  3) 若 m ij = 1, 且 m jk = 1, 那么 m ik = 1.

by 谢广明 , 2005~2006 学年度第一学期 30 求解 TSP 的策略调整  选择算子 – 轮盘赌选择 (roulette wheel selection), – 最佳个体保存 (elitist model), – 期望值模型 (expected value model), – 排序模型 (rank - based model), – 联赛选择模型 (tournament selection model) – 排挤模型 (crowding model) – 浓度控制策略 – 上述机制混合

by 谢广明 , 2005~2006 学年度第一学期 31 求解 TSP 的策略调整  交叉算子 – 依赖于编码方式 – 基于路径表示的顺序交叉 – 基于路径表示的部分匹配交叉 – 贪心交叉法:在一个父个体中选择第一个城市作为子 个体的第一个城市, 然后在两个父个体中进行比较并找 到与已经选择的那个城市相邻且距离较近的城市作为 下一个城市扩展到旅程中 ; 如果与该城市相邻的两个城 市有一个已经在旅程中, 那么选择另外一个, 如果两个都 在旅程中, 那么就选择其它没有被选择的城市. – 循环交叉 – 边重组交叉

by 谢广明 , 2005~2006 学年度第一学期 32 求解 TSP 的策略调整  变异算子 – 全局意义 – 点位变异:变异仅以一定的概率 ( 通常很小 ) 对 串的某些位做值的变异 ; – 逆转变异:在串中, 随机选择两点, 再将这两点内 的子串按反序插入到原来的位置中 ; – 对换变异:随机选择串中的两点, 交换其值 ( 码 ) ; – 插入变异:从串中随机选择 1 个码, 将此码插入 随机选择的插入点中间.

by 谢广明 , 2005~2006 学年度第一学期 33 求解 TSP 的策略调整  变异算子 – 贪心对换变异:从一个染色体中随机的选择两 个城市 ( 即两个码值 ), 然后交换它们, 得到新的染 色体, 以旅程长度为依据比较交换后的染色体与 原来的染色体的大小, 保留旅程长度值小的染色 体. – 倒位变异算子:在个体编码串中随机选择两个 城市, 第一个城市的右城市与第二个城市之间的 编码倒序排列, 从而产生一个新个体. 如, 若有父 个体 P ( ), 假设随机选择的城市是 4,3, 那么产生的新个体为 Offspring ( ).

by 谢广明 , 2005~2006 学年度第一学期 34 算法改进  遗传算法本质上依赖于问题的编码以及遗 传操作算子. 要发展遗传算法也要以这几个 方面作为突破口  解决实际问题,经验往往要起到决定性作 用,不要期望能很快很好的解决问题  多亲和单亲遗传算法  多目标优化问题  和其他优化算法整合,取长补短