机器学习 第9章遗传算法 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 1 机器学习 第9章 遗传算法
概述 遗传算法是一种大致基于模拟进化的学习方法 假设通常被描述为二进制位串,也可以是符号表达式或计算机程 序 搜索合适的假设从若干初始假设的群体或集合开始 当前群体的成员通过模拟生物进化的方式来产生下一代群体,比 如随机变异和交叉 每一步,根据给定的适应度评估当前群体中的假设,而后使用概 率方法选出适应度最高的假设作为产生下一代的种子 遗传算法已被成功用于多种学习任务和最优化问题中,比如学习 机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数 本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序 描述假设的遗传编程 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏 2
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 2 概述 • 遗传算法是一种大致基于模拟进化的学习方法 • 假设通常被描述为二进制位串，也可以是符号表达式或计算机程 序 • 搜索合适的假设从若干初始假设的群体或集合开始 • 当前群体的成员通过模拟生物进化的方式来产生下一代群体，比 如随机变异和交叉 • 每一步，根据给定的适应度评估当前群体中的假设，而后使用概 率方法选出适应度最高的假设作为产生下一代的种子 • 遗传算法已被成功用于多种学习任务和最优化问题中，比如学习 机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数 • 本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序 描述假设的遗传编程
动机 遗传算法(GA)是一种受生物进化启发的学 习方法,它不再是从一般到特殊或从简单到复 杂地搜索假设,而是通过变异和重组当前已知 的最好假设来生成后续的假设 每一步,更新被称为当前群体的一组假设,方 法是使用当前适应度最高的假设的后代替代群 体的某个部分 这个过程形成了假设的生成测试的柱状搜索, 其中若干个最佳当前假设的变体最有可能在下 步被考虑 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 3 动机 • 遗传算法（GA）是一种受生物进化启发的学 习方法，它不再是从一般到特殊或从简单到复 杂地搜索假设，而是通过变异和重组当前已知 的最好假设来生成后续的假设 • 每一步，更新被称为当前群体的一组假设，方 法是使用当前适应度最高的假设的后代替代群 体的某个部分 • 这个过程形成了假设的生成测试的柱状搜索， 其中若干个最佳当前假设的变体最有可能在下 一步被考虑
动机(2) 遗传算法的普及和发展得益于下面的因素 在生物系统中,进化被认为是一种成功的自适应方法,具有 很好的健壮性 遗传算法搜索的假设空间中,假设的各个部分相互作用,每 一部分对总的假设适应度的影响难以建模 遗传算法易于并行化 本章内容安排 描述了遗传算法,举例演示了它的用法,分析了它搜索的空 间的特性 描述了遗传算法的一个变体:遗传编程,这个方法中,整个 计算机程序向着某个适应度准则进化 介绍了一些有关生物进化的课题(遗传算法和遗传编程是进 化计算领域中的两种普遍方法),比如鲍德温效应,它描述 了个体的学习能力与整个群体进化速度之间的相互作用 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 4 动机（2） • 遗传算法的普及和发展得益于下面的因素 – 在生物系统中，进化被认为是一种成功的自适应方法，具有 很好的健壮性 – 遗传算法搜索的假设空间中，假设的各个部分相互作用，每 一部分对总的假设适应度的影响难以建模 – 遗传算法易于并行化 • 本章内容安排 – 描述了遗传算法，举例演示了它的用法，分析了它搜索的空 间的特性 – 描述了遗传算法的一个变体：遗传编程，这个方法中，整个 计算机程序向着某个适应度准则进化 – 介绍了一些有关生物进化的课题（遗传算法和遗传编程是进 化计算领域中的两种普遍方法），比如鲍德温效应，它描述 了个体的学习能力与整个群体进化速度之间的相互作用
遗传算法 遗传算法研究的问题是搜索候选假设空间并确 定最佳假设 最佳假设被定义为使适应度最优的假设 适应度是为当前问题预先定义的数字度量,比如 如果学习任务是在给定一个未知函数的输入输出训练样例 后逼近这个函数,适应度可被定义为假设在训练数据上的 精度 如果是学习下国际象棋的策略,适应度可被定义为该个体 在当前群体中与其他个体对弈的获胜率 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 5 遗传算法 • 遗传算法研究的问题是搜索候选假设空间并确 定最佳假设 • 最佳假设被定义为使适应度最优的假设 – 适应度是为当前问题预先定义的数字度量，比如： • 如果学习任务是在给定一个未知函数的输入输出训练样例 后逼近这个函数，适应度可被定义为假设在训练数据上的 精度 • 如果是学习下国际象棋的策略，适应度可被定义为该个体 在当前群体中与其他个体对弈的获胜率