遗传算法在数据挖掘中的应用研究

张骞 西安工程大学计算机科学学院

1 研究背景及其意义

遗传算法基于生物进化，完成了一系列设计，从而达到优化的目的，这些过程主要涉及到，交叉组合，自然选择。遗传算法从一组初始可行解，出发，从而在可行域全局搜索下得到全局最优解，该特性在优化函数与优化组合方面得到了很好的利用，同时也为计算机智能技术提供的技术提供了技术支撑。为了增强数据挖掘的准确性，很多学者纷纷在数据挖掘之中引入了遗传算法，并且取得了一定的成就。

2 遗传算法的基本原理

遗传算法主要来源于生物系统，钟中计算机模拟研究，该算法主要是用来模拟生物进化，是计算机与自然遗传学相结合的一种研究计算方法。遗传算法的基础是遗传理论与自然选择，该算法是将适者生存和群体内染设计随机交换相结合的搜索算法。在搜索前，先需要通过以某种方式把变量进行编码，产生的变量叫做染色体，不同的染色体形成一个群体，再以某种方法对这些染色体进行评估，从而得出适应值，产生群体的步骤总结如下：

第一，按照染色体的适应值完成染色体的选择和复制染色体的次数，第二，对染色体进行重组，变异从而生成新的染色体。

3 遗传算法的主要特点

为了处理优化计算等各种难题，学者纷纷提出了多种优化算法，比如分支定界法，梯度法，单纯形法。没有算法，有着各自的优点与缺点，以及各自的限制，已转算法作为一种应用于复杂系统优化计算的鲁棒搜索算法，相比于其他算法而言，特点总结如下：

遗传算法编码方式的选择。处理对象是参数的编码及并非是问题参数，搜索过程不会受到优化函数的约束。

遗传算法的处理模式规模庞大，具有高定型性，同时搜索效率较高。

遗传算法思想简单，实现步骤以及运行方式，简单易懂，形象生动，考虑到遗传算法这些特点，从而使得遗传算法在众多领域得到广泛应用。

4 遗传算法的步骤

遗传算法是生物进化模拟的一种优化搜索算法，主要通过计算机对生物进化过程进行模拟，怼不断优化各种种群，从而找到最优解遗传算法的要素，主要包括适应度函数，参数编码，遗传操作，群体设定，结束参数等。

4.1 编码方法

遗传算法中主要是通过编码的方式对问题的可行解进行描述，换言之，就是把问题可行解从空间向遗传算法的搜索空间进行转换，这种方法被称为编码十进制，编码波动小，准确度高，因此本文选择的编码方式是十进制编码。评估编码机制通常选择的规范总结如下：

(1）完备性（Completeness）

问题空间中的全部点都可以当作是GA空间里的点（染色体）表现。

(2）健全性（Soundness）

GA 空间里的染色体可以对应全部问题空间里候选解。

(3）非冗余性（Nonredundancy）

染色体和候选解一一对应。

现今常用的编码方式包括二进制编码，实数编码，符号编码。最常用的编码方式是二进制编码，二进制编码中的另一种变形就是格雷码编码，这是数字排序系统中的一种，十进制编码主要运用于高精度要求的连续函数优化问题中。

4.2 适应度函数

评价遗传算法的标准是适应度函数，在ga 中，主要是运用适应度函数来完成个体适宜程度的计算，所以适应度函数也能够叫做评价函数，该函数主要是用来完成，完整个体优劣标准的评判。适应度函数直接对遗传算法的性能起到决定性作用，适应度函数需要满足条件，总结如下：

第一，单值、连续、非负、适应度越大越好；

第二，设计的合理性、一致性；

第三，设计尽可能简单，计算量越小越好；

第四，具有较强的通用性。

5 基于模拟退火遗传算法的关联规则挖掘

模拟退火算法首次在1953 年由Metropolis 等人提出的，Kirkpatrick 于1983 年将其应用于组合优化。这个算法具体是针对NP 复杂性问题、克服初值依赖性、克服优化过程陷入局部极小。这个基本思想是对比统计热力学的热平衡问题与优化过程，物理背景是固体退火过程的物理图像和统计特性，Metropolis准则接受新的解，避免算法陷入局部最优，算法的合理应用还需要合理的冷却进度表。

5.1 编码

每个事物的每个属性的取值，用十进制数来标识，：每个十进制数就是一个，基因把事物的全部属性的实践次数连接，从而生成的十进制串就一条染色体，也就是说每个染色体的构成形式如：A1∧A2 ∧…∧An 构成，编码时字段顺序一定要保持不变。

5.2 适应度函数设计

适应度一般用来衡量群体中每个个体在优化计算的过程之中可能得到的最优解的优良程度，这是遗传算法优胜劣汰执行的重要依据，适应度函数主要是评价个体的适应度，区分群体中优胜劣汰的重要标准。本文取适应度函数是：

通过上面的公式知道当兴趣度大于1 的时候，表示正相关，也就是说在选择操作过程中，被选中的概率越高，假如兴趣度小于1，表示负相关，选择操作中被选中的概率就越小。

6 规则提取与评价

如果相邻几代的平均适应度差值小于某个阀值ε，或者达到了最大进化代数时，则结束，输出结果。由上文描述可得出改进的模拟退火遗传算法的关联规则算法流程图：

图2 模拟退火遗传算法关联规则流程图

7 结语

20 世纪90 年代初，数据挖掘技术应运而生，数据挖掘技术主要是将用户真正需要的隐藏、有效的信息提取出来，并且进行相应的处理，该技术涉及到多学科研究。有用信息提取出来之前，用户是完全不知情的，完全不知道大量的数据量之中，哪些是对自己有用的，哪些是对自己有价值的。

作为数据挖掘中重要算法之一，遗传算法在数据挖掘方面取得重大应用，另外遗传算法在模糊规则，分类器获取或者决策树等各方面都有着广泛的应用，作为数据挖掘领域中一个重要的研究方向，遗传算法模拟自然进化者通用全局搜索算法，从而避免了搜索过程中的局部最优解，用在规则发现方面有希望发现真正有用的规则。