基于遗传算法的特征选择

《基于遗传算法的特征选择》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于遗传算法的特征选择WhatWhyHow回答什么是遗传算法？什么是特征选择？遗传算法是模拟进化论，搜索优化问题最优解的一种算法。它采用群体搜索策略，一代一代逐步进化，直到收敛到问题的最优解。群体是个体的集合，个体模拟一个问题的一个解。关键问题：个体如何表示？方法：问题编码如何产生下一代？方法：遗传操作如何评价种群的质量？方法：适应度函数What什么是特征选择？就是从一个特征集合中选择一个最优子集。遗传算法流程图How1.问题编码对于特征选择问题，问题编码很简单，采用0-1编码即可。任何一个n元0-1串，都表示问题的一个解。2.

2、如何产生下一代通过选择、交叉、变异三种遗传操作产生下一代，前两种操作每一次都要用的，而第三种则不一定，但没有规则。选择是用来选择交叉的父本，交叉(模拟有性繁殖)产生新的个体，变异是某一位的变异。3.如何评价种群的质量适应度函数设计，对于特征选择问题可采用如下的类别可分离性准则，设计适应度函数。适应度函数为需要注意的是这种适应度函数，只适用于连续值数据库的情况。下面如何计算？Iris数据库选择的特征子集应使类内散度尽可能小，而使类间散度尽可能大.设xk(i)和xl(j)分别为i类和j类中的D维特征向量，(xk(i),xk(j

3、))为这两个向量间的距离，则类间平均距离为：其中，Pi和Pj为先验概率。通常采用欧氏距离：JD称为各类之间的平均平方距离。定义类均值向量为和总均值向量分别为：和定义类间散度矩阵Sb的估计为：定义类内散度矩阵Sw的估计为：其中，i为类协方差矩阵。其他需要说明的问题还有：Q1初始种群的产生主要涉及到：(1)群体的规模N；(2)初始化种群。种群的规模N越大，种群的多样性越好，GA陷入局部极小的可能性越小。但N太大，计算量会很大，收敛速度也会降低。N太小，GA搜索的空间被限制在一个较小的范围内，可能导致早熟。应根据问题的维数和难度来设

4、定N，一般地，维数和难度越高，N应越大。建议N一般取为几十到几百之间。初始化种群一般用随机化方法产生。(a)选择(Selection)算子依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应值评估基础上的，目前常用的选择算子有赌轮选择方法、保留最佳个体选择法、期望值选择方法等。(a.1)赌轮方法(准备步)(S1)按如下公式计算种群中每个个体xi被选择的概率。(E3)(S2)按如下公式计算种群中每个个体xi的累加概率。(E4)(选择步)根据选择概率，将圆盘形的

5、赌轮分成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-

6、1rqi，则选择xi。(a.2)保留最佳个体选择方法将到目前为止，得到的M个最佳个体直接保留到下一代种群中，其余N-M个个体可按其他方法选择产生。(a.3)期望值选择方法在赌轮选择方法中，当种群规模不大时，产生的随机数可能并不能代表其随机变量的真正分布情况。这样，在选择时，可能适应度值大的个体被淘汰，而适应度值小的个体反而被选上。为了克服这种缺点，提出了期望值方法。期望值方法选择步骤STEP1：按下式计算每个个体在下一代生存的期望个数。(E5)STEP2：若某个个体被选择，则Mi=Mi-0.5；否则，Mi=Mi-1。STEP

7、3：将第i个个体复制[Mi]份，小数部分作为选择的概率，再参加选择，看第i个个体是否能再次被选中。STEP4：一旦一个个体的生存期望个数降低到小于等于0，则该个体不再参加选择（被淘汰）。(b)交叉(Crossover)算子以概率pc选择参与交叉的个体，并将选出的个体两两配对。每一对用单点交叉或两点交叉产生两个后代。如有两个用二进制编码的个体A和B。交叉前后为：A=a1a2a3

8、a4a5A'=a1a2a3

9、b4b5B=b1b2b3

10、b4b5B'=b1b2b3

11、a4a5(父代)(子代)。(c)变异(Mutation)算子变异增加了遗

12、传算法找到接近最优解的能力。变异就是以很小的概率pm，随机地改变字符串某个位置上的值。把某一位的内容进行变异。在二进制编码中，就是将某位0变成1，1变成0。如：110010的第四位变异成110110（父代）（子代）Q2控制参数的选择参数主要有个体编码长度m、群体