精编制作基于遗传算法的特征选择PPT课件

基于遗传算法的特征选择 WhatWhyHow 回答什么是遗传算法 什么是特征选择 遗传算法是模拟进化论 搜索优化问题最优解的一种算法 它采用群体搜索策略 一代一代逐步进化 直到收敛到问题的最优解 群体是个体的集合 个体模拟一个问题的一个解 关键问题 个体如何表示 方法 问题编码如何产生下一代 方法 遗传操作如何评价种群的质量 方法 适应度函数 What 什么是特征选择 就是从一个特征集合中选择一个最优子集 遗传算法流程图 How 1 问题编码对于特征选择问题 问题编码很简单 采用0 1编码即可 任何一个n元0 1串 都表示问题的一个解 2 如何产生下一代通过选择 交叉 变异三种遗传操作产生下一代 前两种操作每一次都要用的 而第三种则不一定 但没有规则 选择是用来选择交叉的父本 交叉 模拟有性繁殖 产生新的个体 变异是某一位的变异 3 如何评价种群的质量适应度函数设计 对于特征选择问题可采用如下的类别可分离性准则 设计适应度函数 适应度函数为 需要注意的是这种适应度函数 只适用于连续值数据库的情况 下面如何计算 Iris数据库 选择的特征子集应使类内散度尽可能小 而使类间散度尽可能大 设xk i 和xl j 分别为 i类和 j类中的D维特征向量 xk i xk j 为这两个向量间的距离 则类间平均距离为 其中 Pi和Pj为先验概率 通常采用欧氏距离 JD称为各类之间的平均平方距离 定义类均值向量为和总均值向量分别为 和 定义类间散度矩阵Sb的估计为 定义类内散度矩阵Sw的估计为 其中 i为类协方差矩阵 其他需要说明的问题还有 Q1初始种群的产生主要涉及到 1 群体的规模N 2 初始化种群 种群的规模N越大 种群的多样性越好 GA陷入局部极小的可能性越小 但N太大 计算量会很大 收敛速度也会降低 N太小 GA搜索的空间被限制在一个较小的范围内 可能导致早熟 应根据问题的维数和难度来设定N 一般地 维数和难度越高 N应越大 建议N一般取为几十到几百之间 初始化种群一般用随机化方法产生 a 选择 Selection 算子依据每个染色体的适应值大小 适应值越大 被选中的概率就越大 其子孙在下一代产生的个数就越多 选择操作是建立在群体中个体的适应值评估基础上的 目前常用的选择算子有赌轮选择方法 保留最佳个体选择法 期望值选择方法等 a 1 赌轮方法 准备步 S1 按如下公式计算种群中每个个体xi被选择的概率 E3 选择步 根据选择概率 将圆盘形的赌轮分成N个扇形 第i个扇形的中心角为2 pi 在进行选择时 可以假想随机转到一下赌轮 若参照点落入第r个扇形内 则选择xr 这样重复选择N次即可 上述方法可用如下计算机方法模拟 将 0 1 区间分成长度为p1 p2 pN的小区间 按均匀分布在 0 1 中产生一个随机数 这个数属于哪个小区间 就选出对应的个体 如此重复N次即可 具体步骤如下 赌轮方法选择步骤STEP1 按公式 E4 计算累加概率 STEP2 重复以下两步N次STEP2 1 产生 0 1 中的一个随机数r STEP2 2 若r q1 则选择x1 否则 若qi 1 r qi 则选择xi a 2 保留最佳个体选择方法将到目前为止 得到的M个最佳个体直接保留到下一代种群中 其余N M个个体可按其他方法选择产生 a 3 期望值选择方法在赌轮选择方法中 当种群规模不大时 产生的随机数可能并不能代表其随机变量的真正分布情况 这样 在选择时 可能适应度值大的个体被淘汰 而适应度值小的个体反而被选上 为了克服这种缺点 提出了期望值方法 期望值方法选择步骤STEP1 按下式计算每个个体在下一代生存的期望个数 E5 STEP2 若某个个体被选择 则Mi Mi 0 5 否则 Mi Mi 1 STEP3 将第i个个体复制 Mi 份 小数部分作为选择的概率 再参加选择 看第i个个体是否能再次被选中 STEP4 一旦一个个体的生存期望个数降低到小于等于0 则该个体不再参加选择 被淘汰 b 交叉 Crossover 算子以概率pc选择参与交叉的个体 并将选出的个体两两配对 每一对用单点交叉或两点交叉产生两个后代 如有两个用二进制编码的个体A和B 交叉前后为 A a1a2a3 a4a5A a1a2a3 b4b5B b1b2b3 b4b5B b1b2b3 a4a5 父代 子代 c 变异 Mutation 算子变异增加了遗传算法找到接近最优解的能力 变异就是以很小的概率pm 随机地改变字符串某个位置上的值 把某一位的内容进行变异 在二进制编码中 就是将某位0变成1 1变成0 如 110010的第四位变异成110110 父代 子代 Q2控制参数的选择参数主要有个体编码长度m 群体大小N 选择率ps 交叉概率pc 变异概率pm 终止代数T等 这些参数对遗传算法的运行影响很大 需要认真选择 Theend