《基于遗传算法的特征选择》.ppt

(a) 选择(Selection)算子 依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。 选择操作是建立在群体中个体的适应值评估基础上的，目前常用的选择算子有赌轮选择方法、保留最佳个体选择法、期望值选择方法等。 College of Mathematics and Computer Science 基于遗传算法的特征选择 What Why How 回答什么是遗传算法？什么是特征选择？ 遗传算法是模拟进化论，搜索优化问题最优解的一种算法。它采用群体搜索策略，一代一代逐步进化，直到收敛到问题的最优解。 群体是个体的集合，个体模拟一个问题的一个解。 关键问题： 个体如何表示？ 方法：问题编码 如何产生下一代？ 方法：遗传操作 如何评价种群的质量？ 方法：适应度函数 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.1) 赌轮方法 (准备步) (S1) 按如下公式计算种群中每个个体xi被选择的概率。 (E3) (S2) 按如下公式计算种群中每个个体xi的累加概率。 (E4) (选择步) 根据选择概率，将圆盘形的赌轮分成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|a4a5