多维关联规则数据挖掘在税务数据分析中的研究与应用(4)

斗争中，具有有利变异的个体容易存活，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生的后代也少很多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。这被达尔文称为自然选择。

这也就是遗传算法的核心思想，它模拟了达尔文“优胜劣汰、适者生存”的进化原理激励好的结构，也模拟孟德尔等人的遗传变异理论在优化过程中保持已有结构，同时寻找更好的结构的理论。下面将详细介绍遗传算法的功过过程以及基本原理。

2.4.2 遗传算法的工作过程

开始编码初始种群生成遗传操作结束?否交叉是译码变异适应度计算输出结果个体选择结束 图2.1 遗传算法的基本流程

1、编码

编码是GA解决问题的先决条件，也是设计的关键。由于遗传算法不能直接处理解空间的问题数据，因此我们需要通过编码将它们表示成GA空间的基因型串结构数据。问题空间是指由GA个体（有效的侯选解）集所组成的空间。

定义2.8 （遗传编码）一个具有性质（2.5）的有限长字符串a1a2…aL称为是优化变量X的一个遗传编码（或染色体编码）

16

A=a1a2…aL => X?(x1,x2,...xn)T (2.10)

L称为X的编码长度，A=a1a2…aL称为X的编码，记为e(X)，而X称为字符串A的解码，记为X=e-1(A)

依照生物学术语，每一个ai看作是一个遗传基因，它的所有取值称为等位基因，则A=E(X)可以认为是由L个基因所组成的一个染色体，或者说是一个个体。如果编码和交叉处理不当，在GA空间生成的个体逆映射到问题空间时，将有可能成为无用解。因此，恰当的设计编码和交叉策略或方法，对于充分发挥遗传算法的功能是十分重要的。作为指导思想，DeJong提出了两条编码规则： (1) 意义积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块。

(2) 最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然的表示和描述。

规则(1)是基于模式定理和积木块假设。本章稍后将对这两个概念进行解释。一般采用的有2进制编码、十进制编码、树结构和符号编码方式等。 2、初始种群生成

一般遗传算法的初始种群的生成都是通过随机方式，以应对遗传算法的群体型操作的需要。

3、适应度计算

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数值来评估个体或解的优劣，并作为以后遗传操作的依据。评估函数值又称为适应度（fitness）。遗传算法的评估函数不受连续可微的约束且定义域可以为任意集合。对评估函数的唯一要求是针对输入可计算出能加以比较的非负结果。正是这一特点使得遗传算法的应用范围很广。在具体应用中需要结合解问题本身的要求而定 4、选择

依据选择算子从种群中选择优胜的个体，淘汰劣质的个体操作被称为选择。一般有赌轮或蒙特卡罗（Monte Carlo）、最佳个体保留、期望值、联赛选择方法等。

5、交叉

在生物进化过程中起核心作用的是生物遗传基因的重组，同样，遗传算法中起核心作用的是交叉。所谓交叉是依据交叉算子Pc指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉使遗传算法的搜索能力得以飞跃提高。一般采用的方法有一点交叉、两点交叉、多点交叉、一致交叉等。 6、变异

变异的基本内容是对群体中的个体串的某些基因座上的基因作变动。基本步骤是：在群体中所有的个体的码串范围内随机地确定基因座；以事先设定的变异概率Pm来对这些基因座的基因值进行变异。 7、判断是否结束

一般有判断是否达到了进化代数或者是是否已经收敛，如果达到要求就终止算法。

2.4.3 遗传算法的基本原理

遗传算法依赖基本遗传操作，既选择、交叉和变异算子来实现一代一代的得

17

以优化并逐渐逼近最优解的，模拟了自然界生物的优胜劣汰进化过程，但是作为一个智能搜索算法，其体现出的比其他算法优越的性能的内涵又是什么呢？本节的以下将详细介绍其一些基础理论来解释这个问题。 (1) 模式定理（schemata theorem）[15]

模式是一个描述字符串集的模板。不失一般性以二值字符集{0，1}为考虑对象。 定义2.8 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0，1字符串集的字符串称为模式。记为H。

以长度为5的串为例，模式*0001描述了位置在2到5具有“0001”的所有字符串，它表示了一个字符串的集合。它为我们提供了一个描述结构相似性的集合的方法。

定义2.9 模式H中确定位置的个数称为该模式的模式阶(schema order)，记为O(H)。

比如模式011***的阶数为3，显然一个模式的阶数越高，其样本数就越少，确定性越高。

定义2.10 模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距(defining length),记为?(H)。

比如模式011*1**的定义距为4

其中的字符串既是遗传操作中所指的染色体，模式阶和定义距描述了模式的基本性质。其是遗传算法的一大理论基础，在有了这个概念以后就可以讨论遗传操作了。

令A（t）表示第t代中串的群体，以Aj(j=1,2,…,n)表示一代中的第j个个体串。下面就遗传操作中的各个操作步骤对模式的作用。

? 选择

假设在第t代，群体A(t)中模式H所能匹配的样本数为m，记为m(H,t)，则一个串以概率Pi=fi/∑fj进行选择，fi 为个体Aj(t)的适应度。假设一代中群体规模为n,且个体两两互不相同，则模式H在t+1代中的样本数m(H,t+1)为

m(H,t+1)= m(H,t) ·n·f(H)/ ∑fj (2.11) f(H)为模式H的平均适应度，令群体的平均适应度为f??fi/n，则有

m(H,t+1)= m(H,t) ·f(H)/ f?? (2.12)

可见下一代模式H的数量依赖于模式的平均适应度与群体的平均适应度之比。那些平均适应度高于群体平均适应度的模式将在下一代中得以增长。

如果我们假定模式H的平均适应度始终高于群体平均适应度，并有以下关系： f(H)?(1?c)?f (2.13) C为一个常数，则式(2.7)可以改写成

m(H,t+1) = m(H,t)·(1+C) (2.14) m(H,t+1)= = m(H,0)·(1+C)t+1 (2.15)

从以上的可知，平均适应度大于群体平均适应度的模式将呈指数级增长，而低于群体平均适应度的模式将呈指数级减少。

? 交叉

交叉能产生新的个体，也就是能对搜索空间中的新区域进行搜索。它也将对模式

18

?产生影响。这里只讨论单点交叉。对于模式H，只有当交叉点落在模式定义距之外，才能不破坏模式，模式H的定义距越大，则其被破坏的可能性越大。则可知模式H在交叉操作下的生存概率为：

Ps≥1-Pc﹒?(H)/(l-1) (2.16)

Pc为交叉概率，l为串的长度。

? 变异

最后，看看变异操作对模式H的影响，假定串某一位发生变异的概率为Pm,如果模式H要生存下来，则其中的所有确定位置都必须保持不变，则模式H在变异时的生存概率为：

Ps=(1-Pm)O(H) （2.17）

通常Pm《1 ，所以

Ps=1-PmO(H) （2.18）

综上所述，在选择、交叉和变异的共同作用下，模式H子代的样本数为：

m(H,t?1)?m(H,t)?(f(H)/f)?[1?pc??(H)/(l?1)?O(H)?pm] (2.19)

?忽略极小项pc??(H)/(l?1)?O(H)?pm。则通过式(2.14)我们可以得出模式定理 定理2.11 （模式定理）在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体适应度的模式在子代中将得以指数级增长。 而在统计确定理论中的双角子机问题表明：要获得最优的可行解，则必须保证较优解的样本数呈指数级增长。而模式定理保证了较优模式的指数级增长，从而这一性质有利于找到全局最优解。为算法奠定了理论基础。 (2) 积木块假设

假设2.1 [积木块假设（building block hypothesis）] 具有低阶、短定义距以及平均适应度高于群体适应度的模式”（积木块）在遗传算子作用下，相互结合，能生成高阶、长距以、高平均适应度模式，可最终生成全局最优解。 之所以有这个假设是人们认为：遗传算法的求解过程并不是在搜索空间中逐一测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐构造出适应度高的个体。 (3) 隐并行性分析

从以上的模式定理我们知道了较好的模式能以指数级增长，那它的下界是多少呢？Holland和Goldberg指出遗传算法对于一个规模为n的群体，有效处理的模式个数为O(n3)，这以为着，尽管遗传算法实际上只对n个串个体进行运算，但却隐含地处理了O(n3)个模式。Holland命名这个性质为隐并行性[16]。

2.4.4 遗传算法特点

以上我们详细介绍了遗传算法所拥有的一些理论知识和基本原理，基于遗传算法的理论基础和遗传算法在实践应用中的效果研究，我们可以总结出遗传算法具有如下特点。

? 优点

(1)以优化变量的遗传编码为运算、搜索对象。遗传算法不是以实际的值来进行优化，而是以优化变量的某种形式的遗传编码为运算对象进行

19

优化计算，这样可以方面的进行遗传、进化等操作算子。这种特性使得它在对一些非数值概念或者是很难用数值概念只能用代码的优化问题显示了其独特的优越性[30]。

(2)应用范围广泛，使用简单。因为，首先标准的遗传算法基本不需要搜索空间的知识或其他辅助信息，而仅依靠适应度函数来评估个体进行遗传操作，并且只需要把问题空间转化为解空间就可以，转化过程简单。其次，适应度函数不仅不受连续可微的约束，而且定义域可以任意设定，特别是组合优化与非光滑优化问题。

(3)鲁棒性强。许多其他的搜索方法都是单点搜索，这种点到点的搜索对于多峰分布的搜索空间容易陷入局部的某个单峰的优解。而遗传算法采用了同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，这个特点使得遗传算法具有较好的全局搜索性能。并且，其选择、交叉、变异都是以一种概率的方式进行，这种方式提高了算法跳出局部极值陷阱的能力，保证了算法的稳健性。

(4)并行性。首先，由于遗传算法的的多个个体同时搜索的特性，使得其 易于并行处理。其次，由于其拥有的隐并行性特征，能同时对群体中多个个体进行处理，使得算法在对n个个体搜索的同时隐含了对n3极大的缩短了算法的运行时间。从而适宜在以分布、并行为特征的智能计算机上发挥潜能。

基于以上的特点，遗传算法在对处理大规模的、非线性的复杂问题时体现出了良好的性能。目前已被成功应用在了机器学习、模糊系统、人工神经网络训练、数据挖掘、组合优化、多目标规划等领域。 ? 缺点

作为一种搜索算法，遗传算法的基本框架已经形成，在各种问题的求解和应用中都展现了它的魅力和特点，但同时也暴露了理论和应用技术上的缺陷。 (1) 理论分析仍许加强。对许多特定问题都提出了许多基于遗传算法的新策略，但是对于其比较都是基于对比实验，其中缺乏深刻而具有普遍意义的理论分析。因此，还需要对遗传算法的基本理论进行开拓和深化。

(2) 局部搜索能力差。遗传算法采用的是群体的搜索，并基于全局统计处理的基础，所以其全局搜索能力强，但是其局部的搜索能力相对较弱。如在初始种群的确认和变异操作的进行方面，没有利用任何有用的信息来指导操作的进行。从而在不降低解解的品质的前提下来加快收敛速度。

2.5 蚁群算法

象蚂蚁、蜜蜂等昆虫虽然单个个体行为简单，但是它们却可以凭借集体的力量进行觅食等复杂活动。比如蚂群能找到从巢穴到食物源的最短路径，这种群体所表现出来的“智能”被称为群集智能（Swarm Intelligence -SI）。人们通过模拟蚁群寻找最短路径的行为提出了蚁群算法。并在应用在了许多组合优化问题（如旅行商问题）的研究，电信路由，道路交通管理等方面都有了许多成功的应用。

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库多维关联规则数据挖掘在税务数据分析中的研究与应用(4)在线全文阅读。