遗传算法(2) 遗传算法具有以下的共同结构: 算法迭代更新一个假设池,这个假设池称为 群体 在每一次迭代中,根据适应度评估群体中的 所有成员,然后用概率方法选取适应度最高 的个体产生新一代群体 在被选中的个体中,一部分保持原样地进入 下一代群体,其他被用作产生后代个体的基 础,其中应用交叉和变异这样的遗传方法 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 6 遗传算法（2） • 遗传算法具有以下的共同结构： – 算法迭代更新一个假设池，这个假设池称为 群体 – 在每一次迭代中，根据适应度评估群体中的 所有成员，然后用概率方法选取适应度最高 的个体产生新一代群体 – 在被选中的个体中，一部分保持原样地进入 下一代群体，其他被用作产生后代个体的基 础，其中应用交叉和变异这样的遗传方法
表9-1遗传算法原型 GA(Fitness, Fitness threshold, p, r, m) Fitness:适应度评分函数 Fitness threshold:指定终止判据的阈值 p:群体中包含的假设数量 r:每一步中通过交叉取代群体成员的比例 m:变异率 初始化群体:P<随机产生的p个假设 评估:对于P中每个假设h,计算 Fitness(h 当 Imax fimess(< Fitness threshold,产生新一代Ps,做: ·选择:用概率方法选择P的(1-η)个成员加入PS,概率公式是 P(h1)= Fitness(h,) ·交叉:按概率从P中选择rp/2对假设,对于每对假设<h,h2>,应用交叉算 子产生两个后代,把所有的后代加入PS 变异:使用均匀的概率从PS中选择m%的成员,应用变异算子 更新:P<PS 评估:对于P中每个h计算 Fitness(h) 从P中返回适应度最高的假设 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 7 表9-1 遗传算法原型 • GA(Fitness, Fitness_threshold, p, r, m) Fitness：适应度评分函数 Fitness_threshold：指定终止判据的阈值 p：群体中包含的假设数量 r：每一步中通过交叉取代群体成员的比例 m：变异率 – 初始化群体：P随机产生的p个假设 – 评估：对于P中每个假设h，计算Fitness(h) – 当 <Fitness_threshold，产生新一代PS，做： • 选择：用概率方法选择P的(1-r)p个成员加入PS，概率公式是 • 交叉：按概率从P中选择rp/2对假设，对于每对假设<h1,h2>，应用交叉算 子产生两个后代，把所有的后代加入PS • 变异：使用均匀的概率从PS中选择m%的成员，应用变异算子 • 更新：PPS • 评估：对于P中每个h计算Fitness(h) – 从P中返回适应度最高的假设 = = p j j i i Fitness h Fitness h h 1 ( ) ( ) Pr( ) max Fitness(h) h
遗传算法(3) 算法的每一次迭代以3种方式产生新一代 群体 直接从当前群体中选择 在选中的个体中进行交叉操作 在新群体上进行变异操作 遗传算法执行一种随机的、并行柱状的 搜索,根据适应度函数发现好的假设 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 8 遗传算法（3） • 算法的每一次迭代以3种方式产生新一代 群体 – 直接从当前群体中选择 – 在选中的个体中进行交叉操作 – 在新群体上进行变异操作 • 遗传算法执行一种随机的、并行柱状的 搜索，根据适应度函数发现好的假设
表示假设 遗传算法中的假设常常被表示成二进制位串,这便于 用变异和交叉遗传算子来操作 把 if-then规则编码成位串 首先使用位串描述单个属性的值约束 比如考虑属性 Outlook,它的值可以取以下3个中的任一个 Sunny、 Overcast、Rain,因此一个明显的方法是使用一个长度为 3的位串,每位对应一个可能值,若某位为1,表示这个属性可以 取对应的值 多个属性约束的合取可以很容易地表示为对应位串的连接 整个规则表示可以通过把描述规则前件和后件的位串连接起 来 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 9 表示假设 • 遗传算法中的假设常常被表示成二进制位串，这便于 用变异和交叉遗传算子来操作 • 把if-then规则编码成位串 – 首先使用位串描述单个属性的值约束 • 比如考虑属性Outlook，它的值可以取以下3个中的任一个： Sunny、Overcast、Rain，因此一个明显的方法是使用一个长度为 3的位串，每位对应一个可能值，若某位为1，表示这个属性可以 取对应的值 – 多个属性约束的合取可以很容易地表示为对应位串的连接 – 整个规则表示可以通过把描述规则前件和后件的位串连接起 来
表示假设(2) ·位串的特点 表示规则的位串对假设空间中的每个属性有一个子 串,即使该属性不被规则的前件约束。 得到一个固定长度的规则位串表示,其中特定位置 的子串描述对应特定属性的约東 规则集的表示:单个规则的位串表示连接起来 有必要让每个句法合法的位串表示一个有意义 的假设 假设也可以用符号描述来表示,而不是位串, 匕如计算机程序 2003.12.18 机器学习-遗传算法作者: Mitchell译者:曾华军等讲者:陶晓鹏
2003.12.18 机器学习-遗传算法作者：Mitchell 译者：曾华军等讲者：陶晓鹏 10 表示假设（2） • 位串的特点 – 表示规则的位串对假设空间中的每个属性有一个子 串，即使该属性不被规则的前件约束。 – 得到一个固定长度的规则位串表示，其中特定位置 的子串描述对应特定属性的约束 • 规则集的表示：单个规则的位串表示连接起来 • 有必要让每个句法合法的位串表示一个有意义 的假设 • 假设也可以用符号描述来表示，而不是位串， 比如计算机程序