遗传算法论文答辩ppt课件.ppt

遗传算法及其应用 姓名 车少帅专业 信息与计算科学指导教师 武斌 1 论文章节 结论 遗传算法求解函数优化问题 遗传算法的实现技术 遗传算法的基本概念与原理 研究目的与意义 2 论文主要工作 第1章 认识遗传算法的基本概念 个体与种群 适应度与适应度函数 染色体与基因 选择 交叉 变异等概念 掌握基本遗传算法基本原理与步骤 研究一些遗传算法的基本实现技术 如编码方法 适应度函数 选择算子 交叉算子 变异算子等 3 论文研究背景 目的与意义 研究背景 90年代 遗传算法迎来了兴盛发展时期 无论是理论研究还是应用研究都成了十分热门的课题 尤其是遗传算法的应用研究格外活跃 不但它的应用领域扩大 而且利用遗传算法进行优化和规则学习的能力也显著提高 同时产业应用方面的研究也在摸索之中 4 目的与意义 遗传算法提供了一种求解复杂系统问题的通用框架 它不依赖于问题的具体领域 对问题的种类有很强的鲁棒性 所以GA在函数优化 组合优化 生产调度问题 自动控制 机器人学 图象处理 人工生命 遗传编码和机器学习等方面获得了广泛的运用 从遗传算法的理论和技术两方面概述目前的研究现状 描述遗传算法的主要特点 基本原理 应用遗传算法来解决函数优化 组合优化等方面的案例 论文研究背景 目的与意义 5 主要内容 认识遗传算法的基本概念 掌握基本步骤 学习基本实现技术 应用遗传算法来解决函数优化问题 论文研究背景 目的与意义 6 遗传算法基本概念与原理 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型 它是由美国Michigan大学的J Holland教授于1975年首先提出的 遗传算法作为一种新的全局优化搜索算法 以其简单通用 鲁棒性强 适于并行处理及应用范围广等显著特点 奠定了它作为21世纪关键智能计算之一的地位 7 遗传算法基本概念与原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程 它把问题的参数用基因代表 把问题的解用染色体代表 在计算机里用二进制码表示 从而得到一个由具有不同染色体的个体组成的群体 这个群体在问题特定的环境里生存竞争 适者有最好的机会生存和产生后代 后代随机化地继承了父代的最好特征 并也在生存环境的控制支配下继续这一过程 8 遗传算法基本概念与原理 9 遗传算法基本概念与原理 1 个体与种群 个体就是模拟生物个体而对问题中的对象 一般就是问题的解 的一种称呼 一个个体也就是搜索空间中的一个点 种群 population 就是模拟生物种群而由若干个体组成的群体 它一般是整个搜索空间的一个很小的子集 10 遗传算法基本概念与原理 2 适应度与适应度函数 适应度 fitness 就是借鉴生物个体对环境的适应程度 而对问题中的个体对象所设计的表征其优劣的一种测度 适应度函数 fitnessfunction 就是问题中的全体个体与其适应度之间的一个对应关系该函数就是遗传算法中指导搜索的评价函数 11 遗传算法基本概念与原理 3 染色体与基因 染色体 chromosome 就是问题中个体的某种字符串形式的编码表示 字符串中的字符也就称为基因 gene 例如 个体染色体9 1001 2 5 6 010101110 12 遗传算法基本概念与原理 4 遗传操作 亦称遗传算子 geneticoperator 就是关于染色体的运算 遗传算法中有三种遗传操作 选择 复制 交叉 亦称交换 交配或杂交 变异 亦称突变 13 选择 复制通常做法是 对于一个规模为N的种群S 按每个染色体xi S的选择概率P xi 所决定的选中机会 分N次从S中随机选定N个染色体 并进行复制 遗传算法基本概念与原理 14 交叉就是互换两个染色体某些位上的基因 s1 01000101 s2 10011011可以看做是原染色体s1和s2的子代染色体 例如 设染色体s1 01001011 s2 10010101 交换其后4位基因 即 遗传算法基本概念与原理 15 变异就是改变染色体某个 些 位上的基因 例如 设染色体s 11001101将其第三位上的0变为1 即s 11001101 11101101 s s 也可以看做是原染色体s的子代染色体 遗传算法基本概念与原理 16 遗传算法基本概念与原理 17 基本遗传算法步骤步1在搜索空间U上定义一个适应度函数f x 给定种群规模N 交叉率Pc和变异率Pm 代数T 步2随机产生U中的N个个体s1 s2 sN 组成初始种群S s1 s2 sN 置代数计数器t 1 步3计算S中每个个体的适应度f x 步4若终止条件满足 则取S中适应度最大的个体作为所求结果 算法结束 遗传算法基本概念与原理 18 步5按选择概率P xi 所决定的选中机会 每次从S中随机选定1个个体并将其染色体复制 共做N次 然后将复制所得的N个染色体组成群体S1 步6按交叉率Pc所决定的参加交叉的染色体数c 从S1中随机确定c个染色体 配对进行交叉操作 并用产生的新染色体代替原染色体 得群体S2 遗传算法基本概念与原理 19 遗传算法的实现技术 编码方法 二进制编码方法是遗传算法中最常用的一种编码方法 它使用的编码符号集是由二进制符号0和1组成的二值符号集 它所构成的个体基因型是一个二进制编码符号串 格雷码 连续的两个整数所对应的编码值之间只有一个码位不相同 格雷码有这样一个特点 任意两个整数的差是这两个整数所对应的海明距离 这个特点是遗传算法中使用格雷码进行个体编码的主要原因 20 遗传算法的实现技术 符点数编码方法 指个体的每个基因值用某一范围内的一个浮点数来表示个体的编码长度等于其决策变量的个数 个体变量的长度等于去决策变量的真实值 所以也叫真值编码方法 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义 而只有代码含义的符号集 这个符号集可以是一个字母表 如 A B C D 也可以是一个数宇序号表 如 1 2 3 4 5 还可以是一个代码表 如 Al A2 A3 A4 A5 等等 21 遗传算法的实现技术 适应度函数 适应度较高的个体遗传到下一代的概率就相对大一些 而适应度较低的个体遗传到下一代的概率就相对较小一些 度量个体适应度的函数就称为适应度函数 根据个体的适应值 就可决定在此环境下的生存能力 个体适应度大小决定该个体被遗传到下一代群体中的概率 遗传算法仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息 目标函数值的使用是通过评价个体适应度来体现的 22 遗传算法的实现技术 选择算子 选择算子 也叫复制算子ReproductionOperator 来对群体中的个体进行优胜劣汰操作 适应度较高的个体被遗传到下一代的概率较大 适应度较低的个体被遗传到下一代的概率较小 选择操作建立在对个体的适应度进行评价的基础上 选择的主要目的为了避免基因缺失 提高全局收敛性和计算效率 23 遗传算法的实现技术 轮盘赌选择方法的实现步骤 1 计算群体中所有个体的适应度函数值 需要解码 2 利用比例选择算子的公式 计算每个个体被选中遗传到下一代群体的概率 3 采用模拟赌盘操作 即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配 来确定各个个体是否遗传到下一代群体中 24 遗传算法的实现技术 最优保存策略选择 在遗传算法的运行过程中 通过对个体进行交叉 变异等遗传操作而不断产生新的个体 虽然随着群体的进化过程会产生出越来越多的优良个体 但由于遗传操作的随机性 它们也有可能破坏掉当前群体中适应度最好的个体 我们希望适应度最好的个体要尽可能的保存到下一代群体中 为达到这个目的我们使用最优保存策略进化模型 25 遗传算法的实现技术 具体操作过程 1 找出当前群体中适应度最高的个体和适应度最低的个体 2 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还高 则以当前种群中的最佳个体作为新的迄今为止的最好个体 3 用迄今为止的最好个体替换掉当前群体中的最差个体 26 遗传算法的实现技术 交叉算子 所谓交叉运算 是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因 从而形成两个新的个体 交叉运算是遗传算法区别于其他进化算法的重要特征 它在遗传算法中起关键作用 是产生新个体的主要方法 SGA中交叉算子采用单点交叉算子 27 遗传算法的实现技术 单点交叉运算交叉前 00000 01000011100 000101交叉后 00000 00010111100 010000 28 遗传算法的实现技术 变异算子 所谓变异运算 是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换 从而形成一个新的个体 遗传算法中的变异运算是产生新个体的辅助方法 它决定了遗传算法的局部搜索能力 同时保持种群的多样性 交叉运算和变异运算的相互配合 共同完成对搜索空间的全局搜索和局部搜索 SGA中变异算子采用基本位变异算子 29 Matlab遗传算法GUI求函数最大值 函数 30 Matlab遗传算法GUI求函数最大值 步骤 首先编写目标函数的M文件并以文件名myfun存盘 functiony myfun x ifx 1 1y x sin 10 pi x 2 0 elsey 0end然后 在MATLAB工作窗口 gatool打开遗传算法的GUI 在 fitnessfunction 窗口输入 myfun 在 numberofvariables 窗口输入变量数目1 然后 单击 start 运行遗传算法 得到如下图结果 31 32 结论 遗传算法的特点 1 群体搜索 易于并行化处理 2 不是盲目穷举 而是启发式搜索 3 适应度函数不受连续 可微等条件的约束 适用范围很广 33 结论 遗传算法的应用领域 1 组合优化 2 函数优化 3 自动控制 4 生产调度 5 图像处理 6 机器学习 7 人工生命 8 数据挖掘 34 结论 先从遗传算法的基本概念入手 对个体与种群 适应度与适应度函数 染色体与基因 选择 交叉 变异等概念充分理解 通过