基于遗传算法的特征选择

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