遗传算法在数据挖掘中的应用实例分析

无

第２７卷第６期增刊

２００６年６月

仪器仪表学报

ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＳｃｉｅｎｔｉｆｉｃＩｎｓｔｒｕｍｅｎｔ

Ｖ０１．２７ＮＯ．６Ｊｕｎ．２００６

遗传算法在数据挖掘中的应用实例分析

刘长良

赵建英

曲晓平

刘廉隅

（华北电力大学河北保定０７１００３）

摘要该文主要分析了数据挖掘的有关概念及其数据挖掘的过程，详细阐述了遗传算法的基本思想、步骤及其在数据挖掘中的应用，以遗传算法在旅行商问题中的应用为例，全面分析了遗传算法在数据挖掘中的应用过程及其实现的计算效果，同时对简单的遗传算法在数据挖掘应用中存在的问题进行了讨论。关键词

遗传算法数据挖掘

Ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍａｐｐｌｉｅｄｆｏｒｄａｔａｍｉｎｉｎｇ

Ｌｉｕ

Ｃｈａｎｇｌｉａｎｇ

ＺｈａｏＪｉａｎｙｉｎｇ

ＱｕＸｉａｏｐｉｎｇ

Ｌｉｕ

Ｌｉａｎｙｕ

（ＮｏｒｔｈＣｈｉｎａＥｌｅｃｔｒｉｃＰｏｗｅｒＵｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ０７１００３，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ

Ｔｈｅｐａｐｅｒａｎａｌｙｓｅｓｔｈｅｃｏｎｃｅｐｔａｎｄｐｒｏｃｅｓｓｏｆｔｈｅｄａｔａｍｉｎｉｎｇ，ｅｘｐｌａｉｎｔｈｅｂａｓｉｃｔｈｏｕｇｈｔ，ｔｈｅｐｒｏｃｅｄｕｒｅ

ａｎｄａｐｐｌｉｃａｔｉｏｎｉｎｄａｔａｍｉｎｉｎｇｏｆｔｈｅｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍ．Ｔａｋｅｔｈｅｐｒｏｂｌｅｍｏｆｓｈｏｒｔｅｓｔｔｒａｖｅｌｐａｔｈｆｏｒｅｘａｍｐｌｅ，

ａｎａｌｙｓｅｓｔｈｅａｐｐｌｉｃａｔｉｏｎａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍｉｎｄａｔａｍｉｎｉｎｇ．Ａｎｄｄｉｓｃｕｓｓｅｓｔｈｅｄｒａｗｂａｃｋｏｆ

ｔｈｅ

ｓｉｍｐｌｅａｐｐｌｉｃａｔｉｏｎｅｘｉｓｔｉｎｇｐｒｏｂｌｅｍｉｎｄａｔａｍｉｎｉｎｇｏｆｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍ．

ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍ

ｄａｔａ

Ｋｅｙｗｏｒｄｓｍｉｎｉｎｇ

在生成初期群体后，对各个个体进行适应度评价，

１

引言

并按适者生存的原则，从中选择出较适应环境的个体进行交叉变异，个体Ｇｉ被选择的概率ｐ（Ｇｉ）和适应度

数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人们事先未知的，但又是潜在有用的并且最终可理解的信息和知识的非平凡过程。

遗传算法是基于进化理论，并采用遗传结合、遗传变异及自然选择等涉及方法的优化技术。遗传算法模拟进化／适者生存的过程，以随机的形式将最适合于特定目标函数的种群通过重组产生新的一代，在进化过程中通过选择、重组和突变逐渐产生优化的问题解决方案。

ｆ（Ｇｉ）间成正比关系。即使适应度高的个体能留下更多的后代，然后再通过交叉、变异过程产生更适应环境的新一代染色体群。本代总适应度比上一代的要高，然后再重新进行自然选择。这样，一代一代地进化，各代群体的优良基因成分逐渐积累，群体的平均适合度和最优个体适合度不断上升。直到迭代过程趋于收敛，达到问题的最优解。２．２遗传算法的编码方法

将一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。目前，主要的编码方法有二进制编码方法、浮点数编码方法、

２基本遗传算法

２．１

符号编码方法、格雷码编码方法、多参数编码方法等。２．３适应度函数和适应度

基本遗传算法的处理步骤

遗传算法首先生成初始群体。通常随机地决定初

适应度是用来度量群体中各个个体在优化计算在中有可能达到或接近于或有助于找到最优解的优良程度，适应度总是非负的。适应度函数是用来评估个体的适应度，即区分群体中个体好坏的标准，是进行自然

始群体的个体染色体，群体数目Ｎ影响遗传算法的有效性。

无

２３３４

仪器仪表学报第２７卷

选择的唯一依据。适应度函数是根据目标函数确定代。该例子采用了染色体编码的方法决定了采用普通的，任何情况下总是希望越大越好。

的交叉算子将无法保证基因码在编码串中仅仅出现一次，即不能保证每个城市在一个路径中只出现一次。

３遗传算法在数据挖据中应用举例

为了满足在子代中不出现重复基因码的条件，这里我们采用循环交叉法。

现有城市Ａ（１）、Ａ（２）、……、Ａ（ｎ），一旅行商，欲由于我们应用了染色体编码方式，使得编码串中选择一条最短的路线环游所有城市各一次后回到原出的异位发生突变的常规的变异算法不再适用，这时我发地。如何选择这一路径？

们可以采用倒位变异、基于次序的变异或基于位置的定义：简单遗传算法ＳＧＡ的一个８元组如下：

变异。这里我们采用了倒位变异。ＳＧＡ一（Ｃ，Ｅ，ＰＯ，Ｍ，Ｆ，Ｇ，Ｙ，Ｔ）

（１）

３．４终止条件分析

其中：Ｃ为个体的编码方法；Ｅ为个体的适应度评价函迭代次数的选择对计算结果至关重要，固定迭代数；Ｐ０为初始群体；Ｍ为群体大小；Ｆ为选择因子；Ｇ次数有利于遗传算法的处理，但设置选择困难而且不为交叉因子；Ｙ为变异因子；Ｔ为算法终止条件。利于产生最优解；不固定迭代次数通过对个体解得判３．１参数选择和编码方法

断自动进行迭代，有利于产生最优解，并且解决了参数初始群体随机产生，其个体个数取５００个。这里选择的困难，但容易增加遗传算法的斥力时间。这里采用染色体编码方法，即将每个城市表示为一个基因，我们采用固定的迭代次数Ｎ＝４００。

城市数即为染色体的基因数，城市编号用十进制数表示，使用０～（ｎ一１）这ｎ个数码来表示以上ｎ个城市，一４结束语

条路径ｔ（ｉ）就是由这ｎ个数码组成的编码串，其中单个数码对应为基因，编码串对应于染色体。其中编码遗传算法在数据挖掘中已经得到了很广泛的应串中的每个数码只能出现一次。用，并取得了很好的计算结果。简单遗传算法在数据３．２适应度及适应度函数

挖掘中的应用在大部分情况下可达到较好的计算结设问题的目标函数为ｌｅｎｇｔｈ（ｔ），问题的目标是求果，但有时候也产生一些问题，例如缺乏广泛而完整的取最小路径，所以属于最小值优化问题，所以可以取适遗传算法收敛性理论，有时产生早熟现象和欺骗问题，应度函数Ｆ（ｔ）为路线ｔ所对应的路线长度ｌｅｎｇｔｈ（ｔ）的搜索效率及其时间复杂性问题等。

倒数，其中有：

卅２

参考文献

ｌｅｎｇｔｈ（ｔ）一≥：ｄ（ｖｉ，ｖ斗１）＋ｄ（ｖｏ，Ｖｗ－１）

（２）

‘互石

［１］陈文伟，黄金才．数据仓库与数据挖掘［Ｍ］．北京：人民

（ｖｏ，ｖｌ，．．．’ｖ＋。）表示路线ｔ所经过的ｎ个城市的顺序，邮电出版社，２００４。８：８－２００．

ｄ（ｖ。，ｖ…）表示两个城市之间的距离。Ｅ２］张云涛，龚玲．数据挖掘原理与技术ＥＭ］．电子工业出

３．３遗传因子的确定方法

版社，２００４，４：４０—３００．

根据适应度比例法选择进行交叉的父代，生成子

（上接第２３２８页）

ｉｎ

Ｉｌｌｉｎｏｉｓ

ＳｃａｎＡｒｅｈｉｔｅｃｔｕｒｅＢａｓｅｄＤｅｓｉｇｎｓ［Ｃ］．

Ｓｙｍｐｏｓｉｕｍ．Ｐｒｏｃｅｅｄｉｎｇｓ．１０ｈ．２００１：２５９—２６４．

Ａｕｔｏｍａｔｉｏｎ

ａｎｄ

Ｔｅｓｔ

ｉｎ

Ｅｕｒｏｐｅ

Ｃｏｎｆｅｒｅｎｃｅ

ａｎｄ

［３］

ＳｉｌｖｉａＣＡＴＡＬＤＯ，ＳｉｌｖｉａＣＨＩＵＳＡＮＯ，ＰａｏｌｏＥｘｈｉｂｉｔｉｏｎ，２００２ＩＥＥＥ．

ＰＲＩＮＥＴＴ０．ＯｐｔｉｍａｌＨａｒｄｗａｒｅＰａｔｔｅｒｎＧｅｎｅｒａｔｉｏｎ［２］Ｅ．Ｌａｒｓｓｏｎ，ＺＰｅｎｇ．Ｔｅｓｔｓｃｈｅｄｕｌｉｎｇａｎｄｓｃａｎ－ｃｈａｉｎｆｏｒ

Ｆｕｎｃｔｉｏｎａｌ

ＢＩＳＴ［Ｃ］．

ＩＥＥＥ

Ｉｎｔｅｒｎａｔｉｏｎａｌ

ｄｉｖｉｓｉｏｎ

ｕｎｄｅｒ

ｐｏｗｅｒ

ｃｏｎｓｔｒａｉｎｔ［Ｃ］．Ａｓｉａｎ

Ｔｅｓｔ

Ｃｏｎｆｅｒｅｎｃｅ

ｏｎ

Ｃｏｍｐｕｔｅｒ－ＡｉｄｅｄＤｅｓｉｇｎ，２００３：１１７—１２．