《遗传算法-讲稿》由会员分享，可在线阅读，更多相关《遗传算法-讲稿（34页珍藏版）》请在金锄头文库上搜索。
1、现代智能优化算法 遗传算法 遗传算法 GeneticAlgorithms 简称GA 是一种模拟生物遗传和进化过程的计算方法 进化学说的三个方面 遗传 生物从其父代继承特性或性状的生命现象 即种瓜得瓜 种豆得豆 遗传保持了物种的稳定 变异 一母生九子 九子各不同 变异的选择和积累是生物多样性的根源 适者生存 生物之间存在竞争 根据对环境的适应能力 适者生存 遗传算法 概述 GA四个基本条件 1 存在由多个生物个体組成的种群2 生物个体之间存在着差异 或全体具有多样性3 生物能够自我繁殖4 不同个体具有不同的环境生存能力 具有优良基因结构的个体繁殖能力強 反之則弱 GA 特点 遗传算法以决策变量的
2、编码作为运算对象 从而可以很方便地引入和应用遗传操作算子 传统的优化算法往往直接利用决策变量的实际值本身进行优化计算 遗传算法直接以目标函数值作为搜索信息 实现比较方便 传统的优化算法往往不只需要目标函数值 还需要目标函数的导数等其它信息 这样对许多目标函数无法求导或很难求导的函数 实现困难 GA 特点 遗传算法同时进行解空间的多点搜索 传统的优化算法往往从解空间的一个初始点开始搜索 这样容易陷入局部极值点 遗传算法进行群体搜索 而且在搜索的过程中引入遗传运算 使群体又可以不断进化 这些是遗传算法所特有的一种隐含并行性 遗传算法使用概率搜索技术 遗传算法属于一种自适应概率搜索技术 其选择 交叉
3、 变异等运算都是以一种概率的方式来进行的 从而增加了其搜索过程的灵活性 GA的基础术语 染色体 Chromosome 生物细胞中含有的一种微小的丝状化合物 是遗传物质的主要载体 由多个遗传基因组成 基因 gene 也称遗传因子 DNA链中占有一定位置的基本单位 生物的基因数量根据物种不同多少不一 从几个 病毒 到几万个 动物 个体 individual 指带有染色体特征的实体 种群 population 一定数量的个体的集合 GA的基础术语 适应度 fitness 个体对环境的适应程度进化 evolution 生物逐渐适应其生存环境 使得其品质不断提高选择 selection 指决定以一定概率
4、从种群中选择若干个体的操作 一般而言 选择的过程是一种基于适应度的优胜劣汰的过程复制 reproduction 细胞分裂时 遗传物质DNA通过复制转移到新的细胞中 新的细胞就继承了旧细胞的基因 GA的基础术语 交叉 crossover 两个染色体的某一相同位置处DNA被切断 其前后两串分别交叉组合形成两个新的染色体变异 mutation 在细胞复制时 基因的某个位发生某种突变 产生新的染色体编码 coding DNA中遗传信息按一定的方式排列 也可看作从表现型到遗传型的映射解码 decoding 从遗传型到表现型的映射 GA的三个基本算子 复制 选择 Reproduction Selectio
5、n 依据每一物种的适应程度来决定其在下一代中应被复制或淘汰个数的多少轮盘式选择竞争式选择 GA三个基本算子 交叉 交叉式一种提供个体间彼此交换信息的机制 交叉过程主要是母代中较优良的染色体作某些基因的交换 预期产生更优良的后代 一般常见的交叉方式有 1 单点交叉 One pointcrossover 2 双点交叉 Tail tailcrossover 3 均匀交叉 GA三个基本算子 变异 通过突变的方式 使得解可以跳脱单纯的交叉产生的区域 进而产生新的染色体 变异的过程主要以随机的方式 将染色体的基因位由0变成1或由1变成0 主要的变异方式有 1 等位基因突变 SimpleMutation 2
6、 均匀突变 UniformMutation 3 非均匀突变 Non UniformMutation GA的基本流程 算例说明 编码 求解问题maxf x x2 0 31 x取正整数第一步 编码采用二进制形式我们把变量x编码为5位长的二进制无符号整数表示形式00000031111117001111201100 算例说明 种群生成 第二步初始种群的生成由于遗传算法的群体型操作需要 所以为遗传操作准备了一个由若干初始解组成的初始群体 这里我们取群体大小为4 即群体由4个个体组成 每个个体通过随机初始化产生初始群体也称为进化的初始代 即第一代 firstgeneration 初始化后 群体为01101
7、110000100010011 算例说明 适应度评价 遗传算法用评价函数 适应度函数值 来评估个体 解 的优劣 并作为以后遗传操作的依据 这里我们根据f x x2在评价个体适应度值大小时 首先要解码 即把基因型个体变成表现型个体 即搜索空间的解 这里就是二进制到十进制的转换基因型01101110000100010011表现型x1324819f x x216957664361 适应值 算例说明 选择 选择概率适应度总和1170 平均值293运用轮盘赌选择结果1201 计算结果为0 140 490 060 31 算例说明 选择 算例说明 交叉 单点交叉为例两个染色体1011100111001100
8、假设交叉点在位置41011 10011100 11001011110011001001 算例说明 交叉 选择后的结果 配对情况1和2配对3和4配对01110110001100010001交叉点选择第一对位置3 第二对位置1交叉前01 1101100 011 0001000 1交叉后01000110011111010000 算例说明 交叉 f 1845平均适应度值f 461 算例说明 变异 变异基因数的决定基因总数 变异概率 4 5 0 1 2有兩個基因將被突变随机选取染色体进行变异随机选取要变异染色体的基因位变异目的在避免陷入局部最优解 算例说明 变异 01000110011111010000
9、假设变异基因发生在第一个染色体的第3位和第四个染色体的第二位上变异就是把二进制的0变成1把1变成0变异前01000110011111010000变异后01100110011111010010 算例说明 变异 f 1949平均适应度值f 487 算例说明 进化过程 算例说明 终止准则 一般而言 遗传算法终止条件有以下几种 1 达到最大的进化代数 2 所求的解达到可接受的范围 3 连续几代最佳解无变化或变化非常微小 4 达到最大的运算时间 遗传算法 参数配置 种群数量视具体问题和解空间的维数 问题越复杂 维数越高 种群数量要求越大 一般取遗传运算的终止进化代数根据问题的复杂程度 一般取为100 5
10、00交叉率一般选取范围在0 4 0 99之间变异率一般选取范围在0 001 0 1之间现代一般采用自适应变化的交叉率和变异率 遗传算法 应用 遗传算法提供了一种求解复杂系统优化问题的通用框架 它不依赖于问题的具体领域 对问题的种类有很强的鲁棒性 所以广泛应用于很多学科 下面列举一些遗传算法的主要应用领域 遗传算法 应用 组合优化 遗传算法是寻求组合优化问题满意解的最佳工具之一 实践证明 遗传算法对于组合优化问题中的NP完全问题非常有效 遗传算法 应用 生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解 即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太
11、远 现在遗传算法已经成为解决复杂调度问题的有效工具 遗传算法 应用 自动控制 遗传算法已经在自动控制领域中得到了很好的应用 例如基于遗传算法的模糊控制器的优化设计 基于遗传算法的参数辨识 基于遗传算法的模糊控制规则的学习 利用遗传算法进行人工神经网络的结构优化设计和权值学习等 遗传算法 应用 机器人学 机器人是一类复杂的难以精确建模的人工系统 而遗传算法的起源就来自于对人工自适应系统的研究 所以机器人学自然成为遗传算法的一个重要应用领域 机器学习 基于遗传算法的机器学习 在很多领域中都得到了应用 例如基于遗传算法的机器学习可用来调整人工神经网络的连接权 也可以用于人工神经网络的网络结构优化设计 遗传算法 应用 图象处理 图像处理是计算机视觉中的一个重要研究领域 在图像处理过程中 如扫描 特征提取 图像分割等不可避免地存在一些误差 这些误差会影响图像处理的效果 如何使这些误差最小是使计算机视觉达到实用化的重要要求 遗传算法在这些图像处理中的优化计算方面得到了很好的应用 遗传算法 应用 人工生命 人工生命是用计算机 机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统 自组织能力和自学习能力是人工生命的两大重要特征 人工生命与遗传算法有着密切的关系 基于遗传算法的进化模型是研究人工生命现象的重要理论基础 Thanksforyourattention
