《基于遗传算法的属性选择》由会员分享，可在线阅读，更多相关《基于遗传算法的属性选择（7页珍藏版）》请在金锄头文库上搜索。
1、基于遗传算法的属性选择属性选择是数据挖掘领域非常重要的一个研究方向，属性选择的好坏对挖掘的性能和结果有着很大的影响。典型的基于算法的数据挖掘技术包括：或然性和最大可能性估计的贝叶斯理论 、衰退分析、最近邻、决策树、K-方法聚类、关联规则挖掘 、Web和搜索引擎、数据仓库和联机分析处理(Online Analytical Processing，OLAP) 、神经网络、遗传算法、模糊分类和聚类、粗糙分类和规则归纳等。这些技术都很成熟，这里主要介绍基于遗传算法的属性选择。一、遗传算法说明什么是遗传算法？遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机
2、制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。二、遗传算法与自然选择达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之
3、间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进
4、化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。三、遗传算法的基本步骤我们习惯上把Holland1975年提出的遗传算法（以下简
5、称GA）称为传统的GA。它的主要步骤如下：编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择(Selection)：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选
6、择实现了达尔文的适者生存原则。这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。交换(Crossover)：交换操作是遗传算法中最主要的遗传操作。这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。通过交换操作得到新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异(Mutation)：变异首先在群体中随机选择一个个体，对
7、于选中的个体以一定的概率随机地改变串结构数据中某个串的值。这是在选中的个体中，对个体中的某些基因执行异向转化。遗传算法的原理可以简要给出如下： choose an intial population determine the fitness of each individual perform selection repeat perform crossover perform mutation determine the fitness of each individual perform selection until some stopping criterion applies 这里
8、所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。同生物界一样，GA中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。全局最优收敛(Convergence to the global optimum) ：当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉
9、、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。图1遗传算法原理GA的计算过程为：选择编码方式 产生初始群体 计算初始群体的适应性值 如果不满足条件 选择 交换 变异 计算新一代群体的适应性值 （如图1所示）图2遗传算法计算过程示意图四、遗传算法的特点 遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点： （1）遗传算法从问题解的中集开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜
10、索，复盖面大，利于全局择优。 （2）遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。 （3）遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 （4）遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近
11、，交叉体现了最优解的产生，变异体现了全局最优解的复盖。 （5）遗传算法具有隐含的并行性 综合以上几点我们可以得出遗传算法搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。 遗传算法搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。 遗传算法采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。 遗传算法对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。 五、算法举例在了解和分析了遗
12、传算法之后，我们可以知道在我们面临大量待处理的数据面前，我们仅需要部分包含我们感兴趣的属性的数据，我们要将其从海量数据中依据其属性选择，若采用遗传算法则在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点，即完成编码。再随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。例如选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。通常以随机方法产生串或个体的集合bi，i1，2，.n。问题的最优解将通过这些初
13、始假设解进化而求出。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。以 （式1）为选中bi为下一代个体的次数。 显然从式1可知： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反之亦然。对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息
14、交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交叉概率P。的取值为0.250.75。根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，4位置的基因进行变异，则有 S=001111六、遗传算法的问题遗传算法虽然
15、可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最优解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。参考文献：1.基于遗传算法的文本分类及聚类研究.2008年.科学出版社. 作者: 戴文华2.遗传算法的数学基础. 2003年. 西安交通大学出版社. 作者: 张文修 梁怡3.数据仓库与数据挖掘教程. 2006年. 清华大学出版社. 作者: 陈文伟
