智能控制02遗传算法1.ppt

天津大学自动化学院 智能控制系统 天津大学电气与自动化工程学院 二 天津大学自动化学院 第二章 遗传算法 什么是遗传算法 1 遗传算法方法介绍 2 遗传算法的理论基础 3 遗传算法的计算机实现 4 天津大学自动化学院 1. 什么是遗传算法 1.1 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。遗传算法(Genetic Algorithms，GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。 遗传算法所借鉴的生物学基础就是生物的遗传和进化。 1.1.1 遗传与变异 遗传(Heredity)——生物从其父代继承特性或性状。 天津大学自动化学院 1. 什么是遗传算法 细胞(Ce11) ：生物的基本结构和功能的单位。 染色体(Chromosome) ：细胞核内有结构的线状体，是遗传信息的载体。 基因(Gene): DNA长链结构中占有一定位置的基本遗传单位。 在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。 天津大学自动化学院 1. 什么是遗传算法 生物的遗传方式： 复制：遗传过程中，父代的遗传物质DNA被复制到子代。 交叉：细胞进行有性繁殖时，两个同源染色体之间通过交叉而重组。 变异：细胞进行复制时，DNA发生某种变异，产生出新的染色体。 如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。 天津大学自动化学院 1. 什么是遗传算法 1.1.2 选择与进化 达尔文的自然选择学说：适者生存，优胜劣汰 “在繁殖过程中，大多数生物通过遗传，使物种保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。” “生物在生存竞争中，根据对环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜劣汰的原则，不断地进行进化。” 天津大学自动化学院 1. 什么是遗传算法 1.2 遗传算法简介 优化问题 max f(x) (1-1) s.t. x∈R (1-2) R∈U (1-3) x为决策变量， f(x)为目标函数，式(1-2)、(1-3)为约束 条件，U是基本空间，R是U的一个子集。 满足约束条件的解X称为可行解； 集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。 天津大学自动化学院 1. 什么是遗传算法 对于上述最优化问题，目标函数和约束条件种类繁多，求出其近似最优解或满意解是人们的主要着眼点之一。 总的来说，求最优解或近似最优解的方法主要有三种： 枚举法、解析法和随机有哪些信誉好的足球投注网站法。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化有哪些信誉好的足球投注网站算法。 天津大学自动化学院 1. 什么是遗传算法 遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率有哪些信誉好的足球投注网站方法。 最早由美国密西根大学的H.Holland教授提出； 1967年，Bagley在其论文中首次使用“遗传算法”； 70年代 De Jong在计算机上进行了大量的纯数值函数优化计算实验； 1975年，Holland出版了《Adaption in Natural Artificial System》 天津大学自动化学院 1. 什么是遗传算法 1.2.1遗传算法的基本思想 将优胜劣汰的思想引入待优化参数形成的编码串群体中，按照一定的适配值函数及一系列的遗传操作对个体进行筛选，从而使适配值高的个体被保留下来，组成新的群体。 Holland采用二进位串对解个体编码，每个串称为染色体，染色体上的每一位称为基因。 适应度较高的个体（最优）获得更大的生存和繁殖的机会 一对个体通过交换编码串来实现交叉 一个个体通过改变编码串中的某一位实现变异 天津大学自动化学院 1. 什么是遗传算法 1.2.2遗传算法步骤 群体初始化； 评价群体中每一个个体的性能（适配值）； 选择下一代个体； 执行简单的操作算子（复制，交叉，变异）； 评价下一代群体的性能； 判断终止条件满足否，若不满足，转第三步继续；若满足，退出