基于遗传算法的特征选择知识讲解.ppt

基于遗传算法的特征选择知识讲解.ppt

ID:57220762

大小:387.50 KB

页数:22页

时间:2020-08-04

基于遗传算法的特征选择知识讲解.ppt_第1页
基于遗传算法的特征选择知识讲解.ppt_第2页
基于遗传算法的特征选择知识讲解.ppt_第3页
基于遗传算法的特征选择知识讲解.ppt_第4页
基于遗传算法的特征选择知识讲解.ppt_第5页
资源描述:

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

1、基于遗传算法的特征选择WhatWhyHow什么是特征选择?就是从一个特征集合中选择一个最优子集。遗传算法流程图How1.问题编码对于特征选择问题,问题编码很简单,采用0-1编码即可。任何一个n元0-1串,都表示问题的一个解。2.如何产生下一代通过选择、交叉、变异三种遗传操作产生下一代,前两种操作每一次都要用的,而第三种则不一定,但没有规则。选择是用来选择交叉的父本,交叉(模拟有性繁殖)产生新的个体,变异是某一位的变异。3.如何评价种群的质量适应度函数设计,对于特征选择问题可采用如下的类别可分离性准则,设计适应度函数。适应度函数为需要注意的是这种适应度

2、函数,只适用于连续值数据库的情况。下面如何计算?Iris数据库选择的特征子集应使类内散度尽可能小,而使类间散度尽可能大.设xk(i)和xl(j)分别为i类和j类中的D维特征向量,(xk(i),xk(j))为这两个向量间的距离,则类间平均距离为:其中,Pi和Pj为先验概率。通常采用欧氏距离:JD称为各类之间的平均平方距离。定义类均值向量为和总均值向量分别为:和定义类间散度矩阵Sb的估计为:定义类内散度矩阵Sw的估计为:其中,i为类协方差矩阵。其他需要说明的问题还有:Q1初始种群的产生主要涉及到:(1)群体的规模N;(2)初始化种群。种群的规模N

3、越大,种群的多样性越好,GA陷入局部极小的可能性越小。但N太大,计算量会很大,收敛速度也会降低。N太小,GA搜索的空间被限制在一个较小的范围内,可能导致早熟。应根据问题的维数和难度来设定N,一般地,维数和难度越高,N应越大。建议N一般取为几十到几百之间。初始化种群一般用随机化方法产生。(a)选择(Selection)算子依据每个染色体的适应值大小,适应值越大,被选中的概率就越大,其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应值评估基础上的,目前常用的选择算子有赌轮选择方法、保留最佳个体选择法、期望值选择方法等。(a.1)赌轮方法(准

4、备步)(S1)按如下公式计算种群中每个个体xi被选择的概率。(E3)(S2)按如下公式计算种群中每个个体xi的累加概率。(E4)(选择步)根据选择概率,将圆盘形的赌轮分成N个扇形,第i个扇形的中心角为2pi。在进行选择时,可以假想随机转到一下赌轮,若参照点落入第r个扇形内,则选择xr,这样重复选择N次即可。上述方法可用如下计算机方法模拟。将[0,1]区间分成长度为p1,p2,…,pN的小区间。按均匀分布在[0,1]中产生一个随机数,这个数属于哪个小区间,就选出对应的个体。如此重复N次即可。具体步骤如下:赌轮方法选择步骤STEP1:按公式(E4)计算

5、累加概率。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:按下式计算每个

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

7、a4a5A'=a1a2a3

8、b4b5B=b1b2b3

9、b4

10、b5B'=b1b2b3

11、a4a5(父代)(子代)。(c)变异(Mutation)算子变异增加了遗传算法找到接近最优解的能力。变异就是以很小的概率pm,随机地改变字符串某个位置上的值。把某一位的内容进行变异。在二进制编码中,就是将某位0变成1,1变成0。如:110010的第四位变异成110110(父代)(子代)Q2控制参数的选择参数主要有个体编码长度m、群体大小N、选择率ps、交叉概率pc、变异概率pm、终止代数T等。这些参数对遗传算法的运行影响很大,需要认真选择。Theend

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。