论文研究-基于自适应遗传算法的粗糙集知识约简算法.pdf

所需积分/C币:5 2019-09-12 20:34:00 612KB .PDF

为了获得有效的属性最小相对约简,提出了一种基于自适应遗传算法的粗糙集知识约简算法。该算法将核引入遗传算法的初始群体来提高算法的性能,依照决策属性对条件属性的依赖度,在加强局部搜索能力的同时保持了该算法全局寻优的特性,并且对交叉概率和变异概率进行了新的设计。设计中既考虑到进化代数对算法的影响,又考虑到每代中不同个体适应度对算法的作用。最后通过两个经典算例进行了验证,无论在约简的准确性上,还是平均运行代数上都取得了较好的结果。
潘伟,王云峰,伞冶:基于自适应遗传算法的粗糙集知识约简算法 2008,44(15)3 敛过程加长;而从产生新个体的角度来看,群体中的所有个体组点,选择、交叉和变异就是在空间中点集变换的某种运算,通 在交叉操作上应该具有同等地位,相同概率,从而使GA在搜过这些运算最后达到解空间中的最优点。 索空间具有各个方向的匀性。本文为此设计与进化代数相关的 (2)文中采用的适应值函数可以控制染色体朝着最小约简 交叉概率计公式 的方向进化:k越大,说明决策属性D依赖条件属性C越强;再 +6 (6)通过card(x)来控制染色体朝着最小约简的方向进化 本文算法保证了这两方面要求,所以该算法得到的R为 其中,G为进化代数,a、为定常系数,a代表交叉概率的变化问题的最优解 曲率,B代表交叉概率的收敛极限。 证毕。 (2)变异概率的自适应确定 变异算子在遗传操作中起辅助作用,主要用来维持群体多5算例 样性,防止出现未成熟收敛。在算法早期,群体中个体多样性丰 为考察本算法的有效性,使用本文算法分别对不同的信息 富,此时的变异概率应该小些,以提高算法的运行速度;而随着 进化的进行,个体越来越向适应度高的个体靠近,致使个体越系统做了多项实验。 来越单一,此时的变异概率就应该大些,以维持群体的多样性。 例1计算表1所示信息系统的最小约简。在这个信息系 同样的原因,同一代群体中个体的变异概率应该随个体的优劣统中,论域U包括18个对象,编号1-18,属性集A={a,b,c,d 而变化,即加大优质个体变异概率。为此设计了如下的与遗传文献[0证明多种基于核的启发式搜索算法无法正确的求得最 进化代数和个体适应度相关的自适应变异概率 小约简。这些策略得到的最小约简是{u,b,c}或者{a,b,d}。而实 际的最小约简是{c,l}。 k,f-f, ff 表1例1信息系统 (7) U123456789101112131415161718 f≤f a12345677991112131415161717 其中,G为进化代数,a、k1、k2为定常系数。a代表变异概率的 b12345678991112131415151718 c113355779101112131415161718 变化速度;k1与具体问题有关,是为保证遗传算法不退化为随12345678910111113131515 机搜索,Pn所能取到的最大值;k2为一个比较小的变异概率,一 般取0.001。 根据遗传约简算法,在无需其它先验知识的情况下,无需 引入其它概念的情况下,可以正确的求得信息系统的最小约简 4遗传算法约简过程 为{c,d}。经过与标准遗传算法的对比发现,自适应遗传算法在 属性约简算法,输入信息:一个决策表S=(U,A,V,F),A 第16代就岀现了最优个体,而标准遗传算法需要经过56代才能 C∪D,C是条件属性,D是决策属性。输出信息:此决策表的 找到最优个体,并且找到最优个体的概率也由99%降到87%。 个知识约简R。 例2表2是一个关于汽车数据的信息系统。其中论域U= (1)由式(3)计算出决策属性D对条件属性C的依赖度y(D)。 {1,2,…,2l},条件属性集为C={类型,气缸,涡轮式,燃料,排气 (2)令Core(C)=,逐个去掉一个属性c∈C,若yc≠yc 量,压缩率,功率,换档,重量}决策属性为D={里程}。 表2汽车数据表 则Core(C)=Core(C)Ue},即核为Core(C);若yc(D)=yc (D),则Core即为最小相对约简,否则执行(3) 类型气缸涡轮式燃料排气量压缩率功率换档重量里程 (3)随机产生n个长度为m(条件属性的个数)的二进制串 小型4¥1型中 高高自动中中 小型4 组成初始群体:对于核中的属性,其对应位取1:其它则对应位小 型中中高手动中中 N1型中高高手动中中 随机取0或1。 小型4Y1型中高高手动轻高 (4)由式(3)计算出决策属性对每个个体所含条件属性的 小型4N1型中中中手动中中 依赖度,由式(4)计算出每个个体的适应值,由式(5)计算出每小型4N2型中中中自动重低 个个体被选择的概率,最后使用模拟赌盘操作(即0~-1之间的 小型4N1型中中高手动重低 随机数)来选择个体。 微型4 型小高低手动轻高 (5)根据式(6)的自适应交叉概率P进行交叉操作,采用 小型4N2型小高低手动中中 小型4 小高中自动中中 点交叉方式。 微型4N1型小高低手动轻高 (6)根据式(7)的变异概率P进行变异操作,采用基本位微型4N1型小中中手动中高 变异方式,其中核中属性的对应位不发生变异。 小型4 N2型中 中中手动中中 (⑦)采用最优保存策略,将最优个体复制到下一代群体中。 微型4 1型小 高高手动中高 (8)如果连续keep代的最优个体的适应值不再提高,则终 微型4N2型小 中低手动中高 止计算,否则转(4)。 小型4Y1型中中高手动中中 小型4 N1型中 中高自动中中 证明该算法得到的R为问题的最优解。 小型4 N1型中 中高自动中中 证明 微型4N1型小高中手动中高 1)该算法是从一个初始群体出发,不断重复执行选择、交 小型4N1型小高中手动中高 叉和变异的过程,使群体进化越来越接近某一目标,如果把每 小型4N2型小高中手动中中 个个体看成是空间中的一个点,那么初始群体就是空间中的 (下转11页)

...展开详情
试读 3P 论文研究-基于自适应遗传算法的粗糙集知识约简算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于自适应遗传算法的粗糙集知识约简算法.pdf 5积分/C币 立即下载
    1/3
    论文研究-基于自适应遗传算法的粗糙集知识约简算法.pdf第1页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >