遗传算法new.ppt
《遗传算法new.ppt》由会员分享,可在线阅读,更多相关《遗传算法new.ppt(57页珍藏版)》请在三一文库上搜索。
1、第三章 遗传算法,第三章 遗传算法,31 从生物进化到进化计算 32 标准遗传算法(SGA) 33 遗传算法的特点 34 遗传算法理论研究 35 遗传算法的应用 36 遗传算法的基本术语,一个人的战争,嗨呀嗨呀,人多力量大 吼吼吼,优化搜索问题简介单个体搜索,优化搜索问题简介单个体搜索,优化搜索问题简介单个体搜索,优化搜索问题简介群体搜索,优化搜索问题简介群体搜索,优化搜索问题简介群体搜索,优化搜索问题简介群体搜索,优化搜索问题简介群体搜索,如何实现高效的群体搜索呢?,初始群体的产生 新解的产生机制 新解的接受策略 个体间通信机制,生物界是一种自然进化(趋优)的系统。 生物为什么会进化?(生物
2、是如何进化的?) 只有生物界是自然进化的吗? 人工系统能否自然进化?如何实现?,3.1 从生物进化到进化计算,最早动物出现,最早真核细胞出现,兰细菌光合作用,大气中 O2 积累,最早原核生物出现,地球形成,澳州西海岸的垫藻岩,35亿年前的兰细菌化石,拟态,变色,自然进化的结果:环境生存能力强,冬天白色,夏天黑色,自然进化的结果:环境生存能力强,西番莲是热带藤本植物,展足蛾产卵于叶面,西番莲的蜜腺象卵,起到保护叶子的作用,达尔文的进化论: 自然选择,适者生存 孟德尔与摩根的遗传学理论: 基因是决定生物特征的最基本的物质单元,基因在染色体上以一定的顺序和结构排列,每个基因有特殊的位置并控制生物的某
3、些特性。 基因组合的特异性决定了生物体的多样性,基因结构的稳定性保证了生物物种的稳定性,而基因的杂交和变异使生物进化成为可能。,3.1 从生物进化到进化计算,22岁的达尔文开始贝格尔舰航行,孟 德 尔 (1822-1884),减数分裂时发生:染色体交叉/基因重组。,生物进化过程的发生需要四个基本条件: 1)存在由多个生物个体组成的种群; 2)生物个体之间存在着差异,或群体具有多样性; 3)生物能够自我繁殖; 4)不同个体具有不同的环境生存能力,具有优良基因结构的个体繁殖能力强,反之则弱。 5)存在竞争(优胜劣汰)。,3.1 从生物进化到进化计算,生物群体的进化机制包括三种基本形式: 1)自然选
4、择 2)杂交 3)突变 另外,外界对生物的评价反映了生物的生存价值和机会。,3.1 从生物进化到进化计算,生物进化过程本质上是一种优化过程。 进化计算(Evolutionary Computation, EC)包括四个重要分支: 1)遗传算法(Genetic Algorithm,GA),由John H. Holland教授等提出; 2)进化规划(Evolutionary Programming, EP),由Lawrence J. Fogel等人提出; 3)进化策略(Evolutionary Strategies, ES),由Ingo Rechenberg和Hans-Paul Schwefel提
5、出。 4)遗传规划(Genetic Programming,GP),由John R. Koza教授提出。,3.1 从生物进化到进化计算,3.2 标准遗传算法,产生背景: 模拟自然物种进化过程的人工系统 遗传算法的6个基本要素: 1)参数编码; 2)初始群体的设定; 3)适应度函数的设计; 4)遗传算子设计; 5)控制参数设定 6)迭代终止条件,3.2 标准遗传算法,标准遗传算法流程: 1编码(问题解在算法中的表示形式) 2产生初始群体 3评估每个个体的适应度 4WHILE DO 1. 选择 2. 交叉 3. 变异 4. 适应度评估检测 5END DO,Genetic Algorithm,3.2
6、 标准遗传算法(示例),问题: 求函数f(x) = x2的最大值, 1编码(定义问题参数空间到编码空间的映射) 13 = 0 1 1 0 1 24 = 1 1 0 0 0 8 = 0 1 0 0 0 19 = 1 0 0 1 1,3.2 标准遗传算法(示例),2初始群体的生成 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1,初始种群,3.2 标准遗传算法(示例),3适应度评估检测 f(x) = x2 0 1 1 0 1 = x=13 = f(x) = 169 1 1 0 0 0 = x=24 = f(x) = 576 0 1 0 0 0 = x=8 = f(x)
7、 = 64 1 0 0 1 1 = x=19 = f(x) = 361,3.2 标准遗传算法(示例)遗传算子,1)选择(复制),inter-mediate parent population :,01011,11010,10001,10001,probability of reproduction pi = fi / kfk,selection is a stochastic process,3.2 标准遗传算法(示例)遗传算子,2)交叉 0 1 1 0 | 1 0 1 1 0 0 1 1 0 0 | 0 1 1 0 0 1,3)变异 1 1 0 0 0 1 1 0 1 0,3.2 标准遗传算
8、法(示例)遗传算子,3.3 遗传算法的特点,基于群体的搜索。 直接处理的对象是参数的编码集而不是问题参数本身。 搜索过程中使用的是基于目标函数值的评价信息,搜索过程既不受优化函数连续性的约束,也没有优化函数必须可导的要求。 具有显著的隐并行性。(具有自学习能力) 形式上简单明了。 具有很强的鲁棒性。,3.4 遗传算法理论研究,遗传算法所追求的是当前群体产生比现有个体更好个体的能力,即遗传算法的可进化性或称群体可进化性。因此,遗传算法的理论和方法研究也就围绕着这一目标展开。,3.4 遗传算法理论研究,关于下面五个问题的回答,就成为GA理论研究的主要方向: 遗传算法为什么会具有很好的优化的能力?遗
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 new
链接地址:https://www.31doc.com/p-3773147.html