分子遗传学中心法则范例(3篇)

分子遗传学中心法则范文

关键字：频率分配遗传算法GECP组合优化

1.通信网频率分配问题的背景

无线通信设备之间通过相互发射电磁波达成信息沟通。相互通信的设备之间使用特定的频率（信道）构成无线通信链路。由于电磁波的自然特性，无线通信设备发射的电磁波可能对位于附近、满足一定功率和频率条件的其它设备形成干扰。频率分配（FAP）的目的就是给工作在一定地域内的无线通信设备指定使用的工作频率(或信道)，使所有设备都以尽量小的概率扰，从而使整个网络的可用性得到优化。FAP可以描述为：对N个给定的待分配工作频率的链路，设G={S1,S2,…Sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，寻找最优解s*，使任意si∈G，C(s*)=minC（si）。因此FAP是一种组合优化问题。

具体设备频率分配方法虽然会随着设备的工作方式（单工、双工）、工作频段、天线类型、信号的调制解调方式的不同而有所区别，但是大部分频率分配算法都可以转换为等价的图的边着色问题。从图论算法理论上讲，图的广义边着色问题是NPC问题[7]，也就是说无法在多项式时间内求得问题的最优解。例如对于存在n条边的无向图，使用c种颜色对其着色，在没有其它约束条件下，其解空间是cn。即使在不考虑颜色重复使用（c>n）的情况下，其解空间也达到n!。这两者都是超越数，在c和n的值较大的情况下想利用穷举搜索的方法求得问题的最优解在时间上是不可行的。

在工程实践中许多NPC问题使用一些使用的近似算法得到问题的可行解。这些方法包括[]：只对问题的特殊实例求解；动态规划（DP）或者分支界限算法（BC）；概率算法；求近似解；启发式算法（HeufisticAlgorithms）等。这些方法的和核心是分割问题的解空间，按照特定规则搜索典型解作为次最优解。

对于FAP问题国内外许多学者进行了深入的研究，提出许多解决问题的方法。文献[4]在对FAP进行理论分析的基础上给出了几种常用算法的框架，这些算法包括：最小-最后次序查找算法，贪心T着色算法、模拟退火算法（SA）、列表寻优算法（TS）、遗传算法（GA）、神经网络（NN）多面体算法等，并指出各种算法有各自的适用范围；文献[2]提出了利用启发式的蚂蚁算法，并对解决CELAR、GRAPH、PHILADELPHIA上的几类问题同TS和SA算法进行了比较；文献[1]比较了SA、TS、GA、VDS（variable–depthsearch）、BC等算法的性能。文献[7]利用GECP理论对存在禁用频率的异频双工设备的频率分配给出工程上的实用算法；文献[9]则采用了BC方法频率分配的全排列算法进行了优化。本文将探讨如何遗传算法解决FAP问题。

2.遗传算法在频率分配问题中的适用性

2．1遗传算法的原理

遗传算法(GeneticAlgorithmsGA)是根据生物学上的染色体基因因子构成机制而产生的。1975年Holland教授首次提出了GA的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面。遗传算法是一种全局优化算法，其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决组合优化问题和复杂非线性问题[6]。

利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。

实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了模式定理。所谓模式，就是某些码位取相同值的编码的集合。模式定理说明在进化过程的各代码中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长[6]。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解[5]。

2．2遗传算法的基本结构

在遗传算法中，将问题的求解的过程，看成一个在候选解空间寻找满足问题要求的解或近似解的搜索过程。遗传算法的重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索，一般采用遗传算子(或称遗传操作)诸如(Crossover)和变异(Mutation)等，以及模拟自然过程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。

遗传算法求解问题的基本步骤可以描述如下：

1.首先生成一组初始的候选解群体(假设为N个候选解个体)，称为第0代；

2.计算群体中各个候选解的适应值；

3.如果有候选解满足算法终止条件，算法终止，否则继续4；

4.根据概率，将候选解群体中的个体随机两两配对，进行操作以生成新的候选解；

5.根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；

6.使用选择机制形成新一代候选解；转2。

GA算法具有下述特点：GA是对问题参数的编码组进行，而不是直接对参数本身；GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始；GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。

遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。

3.遗传算法用于频率分配

3．1算法的基本流程

采用遗传算法的FAP基本流程

3．2遗传算子的选择

3．2．1选择算子

选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在FAP中选择算子采用轮赌算法实现。

轮赌算法流程如下：

sum=0;i=0;

wheelpos=rand()*sumfitness;

for(sum<wheelpos&&i<pop-size)

｛

i++;

if(i≥pop-size)

｛

sum=0;i=0

wheelpos=rand()*sumfitness;

｝

j=rand()*pop-size;

sum+=fitness［j］;

｝

returnj;

3．2．2交叉算子

交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。

其基本流程如下：

//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0

if(flip(pc))

crossover1(mother,father);

elseif(flip(pc))

crossover2(mother,father);

else

copy(mother);

copy(father);

3．2．3变异算子

变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。

其基本流程如下：

while(allfrequentpoint)

{

if(flip(pm))mutate(frequentpoint)；}

4.工程上需要注意的问题

4．1初始候选种群

由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的GECP得到以各个顶点为主顶点的可行解作为初始候选种群。

4．2编码方案

编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。

4．3适配值函数

适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：

fitness=1000/Σ(pri×seperate(Freq))。

其中：

pri是节点的加权值；

函数seperate(Freq)是节点中各条链路发频率同其它链路的收频率间隔的和；

参考文献：

[1]RobertA.Murphey,PanosM.Pardalosetc,FrequencyAssignmentProblems,Handbookofcombinatorialoptimization,KluwerAcademicPublishers,1999

[2]VittorioM.,AntonellaC.,AnANTSHeuristicfortheFrequencyAssignmentProblem,csr.unibo.it

[3]JoeBater,PeterJeavons,DavidCohen,ArethereoptimalreusedistanceconstraintsforFAPswithrandomTxplacement?,CSD-TR-98-01,CSRoyalHollowayUni.OfLondon,1998

[4]K.IAardal,C.A.J.Hurkens,J.K.etc.AlgorithmsforFreequencyAssignmentProblems,CWIQuarterly,Vol9(1&2),1996

[5]王凌：《智能优化算法及其应用》清华大学出版社2001

[6]陈国良等：《遗传算法及其应用》人民邮电出版社1996

[7]孙俊柏：禁用频点、频段下野战通信网的频率分配中国科学技术大学硕士学位论文1998

分子遗传学中心法则范文篇2

关键词：思维进化算法遗传算法交叉变异

中图分类号：TP183文献标识码：A文章编号：1007-9416（2015）12-0000-00

Abstract：ThispaperdiscussedtheadvantageandweaknessoftheGeneticAlgorithmandMindEvolutionAlgorithmtentatively，expatiatethemainmindandteststep，pointouttheproblemandtheimprove，combinedgeneticoperatorwithMindEvolutionAlgorithm，andmadeMindEvolutionAlgorithmimproved，providedtheconcretingstep，usethecrossandvariation；Andusingthisalgorithmforsolvingtheextremevalueoffunction，itobtainedthesatisfiedexperimentalresult，applyforthecomputearea.

Keywords：MindEvolutionAlgorithm；GeneticAlgorithm；crossover；mutation

1引言

自然界是人类获得灵感的重要源泉，近几十年来，将生物界提供的答案用于实际问题的求解已经被证明是一个成功的方法。进化计算正是在这种背景下产生的，它主要包括：遗传算法、进化规划和进化策略。而在这中间应用最为广泛的是遗传算法。遗传算法是一种以达尔文的进化论和门德尔的遗传理论为基础的求解全局优化问题的仿生型算法。它是由Michigan大学的Holland教授提出的，它简单、通用、鲁棒性强。近年来，遗传算法的研究取得了长足的进步，并且在函数优化、组合优化、生产调度问题、人工生命及机器学习等众多领域里得到了广泛的应用。但是遗传算法的缺点也日益明显：交叉与变异两个重要算子都是在一定的概率条件下，随机、盲目的搜索，容易产生退化早熟现象；另外，它缺乏行之有效的强制记忆功能并且计算时间过长。正因为如此，有许多科学家试图从各个方面来改进遗传算法。而思维进化算法（MEA）就是针对遗传算法所出现的问题而提出的一种行之有效的解决方法。本文将遗传操作与思维进化算法有机的结合在一起，把变异与交叉算子融于思维进化中，对思维进化作了一定的改进。

2基本思维进化算法

2.1思维进化的主要思想

众所周知，自然界中的生物通过遗传和自然选择而进化了上亿年，这个过程非常缓慢。相比之下，人类思维进化的速度却远远高与生物的进化。其原因在于：向前人和优胜者学习；不断的进行探索和创新。人类在这两种思维方式的影响下使自身得到了快速的发展，推动了科技的进步。思维进化算法正是基于以上分析而得出的。其主要构成如下：

（1）群体和子群体。所有个体的集合称为一个群体。一个群体分为若干个子群体，子群体有两类：优胜子群体和临时子群体。（2）公告板。公告板为个体间和子群体间提供信息交流的机会。公告板上的信息包含了3部分：个体或子群体的序号、动作、得分。行为的表达是与区域相关的，即行为的表达因区域而异。得分是标量，取自于环境中的行为。个体关于环境的知识就是信息。（3）趋同和异化是思维进化中的重要概念。在学习初期，个体在解空间中随机散布，计算每个个体的得分。一些得分高的个体成为胜者，并以它们为中心形成子群体。

趋同：每个子群体的个体在子群体内向其胜者（子群体内得分最高的个体）学习，并相互竞争，直到一个新的胜者出现。胜者的得分就是子群体的得分。子群体的成熟：一个子群体诞生后，开始时，子群体的得分增长很快，以后得分增长逐步减慢，当子群体的得分不再增长时，称该子群体成熟。异化：一些个体在整个解空间中搜索，，产生若干个临时子群体。当临时子群体的得分高于任何一个成熟优胜子群体的得分时，用前者取代后者成为新的优胜子群体。从竞争的角度看，趋同进行局部竞争，异化进行全局竞争；从另一个角度看，异化进行探测，趋同进行开发利用。

2.2实现步骤

（1）群体初始化，根据得分产生优胜子群体和临时子群体。并将其得分记录到公告板中。（2）趋同学习发生在每个子群体（优胜和临时子群体）的内部，在局部竞争中寻找局部最优点。在每次趋同操作中都是以胜者为中心，按正态分布散布新一代的个体，其中得分最高的个体是该子群新的胜者。（3）异化是子群体为成为优胜子群体而与其它子群体所进行的一种全局竞争。若某一临时子群体的得分大于任一成熟优胜子群体的得分，则优胜子群体被临时子群体替代；同样，若某一成熟临时子群体得分小于任意优胜子群体的得分，则该临时子群体被放弃。（4）被替代与放弃的子群体中的个体在解空间重新均匀散布产生新的个体，以形成新的临时子群体，参加新一轮的趋同与异化。反复进行趋同与异化，当优胜子群体得分增长趋近于零时，认为算法收敛。此时优胜子群体的优胜者，即为全局最优解。

2.3存在的问题及改进措施

在实际使用中，思维进化算法也存在缺点。例如，对于单调函数或单峰函数，MEA在最优值附近收敛较慢；而对于多峰函数的优化问题，它往往会出现“早熟”，即收敛于局部最优。主要原因有：常规的趋同操作可能由于“学习”的作用，某些群体放弃了本身比较好的特征；再者是异化算子的设计是在已有的初始群体里重新组合以产生新的优胜子群体，并没有对初始群体中的每个个体进行实质上的变化。借鉴遗传算法中的交叉与变异操作，可以对思维进化算法作进一步的补充计算。交叉是把两个父个体的部分结构加以替换重组而生成新的个体，交叉的目的是为了能够在下一代产生新的个体，通过交叉操作，算法的搜索能力得到飞跃地提高，是获取新的优良个体的重要手段；变异是个体变量以很小的概率或步长产生转变，它本身是一种局部随机搜索，与交叉算子结合在一起，保证了算法的有效性，使种群也保持了多样性，防止了非成熟收敛。于是通过交叉与变异操作，思维进化算法的搜索性能会得到大幅度的提高。

3改进后的思维进化算法

3.1编码方式

从精度及使用方便的角度来看，在涉及多参数优化的问题中，通常采用浮点数编码。浮点数编码的变异操作可以任意小。采用浮点数编码，可以避免数制的转换、提高精度，其效率要比二进制编码高。在浮点数编码的思维进化算法中，必须保证个体的值在给定的区间限制范围内，而其中的交叉、变异等算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。

3.2算法的具体实现步骤

经过改进后的思维进化算法的的实现步骤如下：

（1）初始化。在解空间随机产生S个个体，并计算每一个体的得分，从中选择M+T个最好个体，即优胜者；（2）产生初始群体。以每一优胜者为中心，以δd=（Hd-Ld）/10为方差（其中Hd、Ld分别为第n维变量的上下限），以正态分布产生Nj个个体，构成M个一般子群体、T个临时子群体；（3）趋同操作。在每一子群体内，首先计算每一个体的得分，得分最高者为优胜者，其余个体以一定的方式向优胜者学习，产生新的子群体。重复上述步骤，直到子群体成熟，即新的优胜者的得分得到进一步改善。在此将优胜者的得分定义为子群体的得分；（4）异化操作。若某一临时子群体的得分高于任一成熟一般子群体的得分，则认为该一般子群体在全局竞争失败，用此临时子群体替代该一般子群体，该一般子群体被放弃，被放弃一般子群体的个数记Mr。当一个临时子群体成熟，且它的得分小于任意一般子群体的得分时，它将不可能对全局优化有所贡献因而被放弃，被放弃临时子群体的个数记为Tw；（5）在进行信息（即所抽取的特征和全局公告板信息）指导下，在解空间中重新产生Mr+Tw个临时子群体；（6）对于在步骤（5）产生的Mr+Tw个子群体的每一个群体进行如下操作：

交叉操作把其中的个体随机两两配对，按一指定概率Pc进行如下的交叉操作：

（1）

其中0

变异操作对每一个个体中的每一个参数，按一定概率Pm进行如下的的变异操作：

（2）

其中α为（0，1）之间的随机数，Cmin、Cmax分别为个体参数C的上下界；

（7）把上述步骤（6）中产生的新临时子群体重新参于趋同操作；（8）重复上面的步骤（3）至步骤（7），直到满足收敛条件为止，一般收敛性判据是，全局公告板记录着每一子群体的优胜者及得分，当优胜者的得分得不到进一步的改善时，则认为收敛。利用算法初始种群的集合构筑一个状态空间，将算法视为一个压缩映射，那么算法的每一次迭代相当于对由初始个体组成的状态空间实施一次压缩映射。利用Banach不动点原理，可以证明算法渐进收敛到全局最优点。

4实验结果及结论

为了测试算法的性能，分别用算法MEA，加入遗传算子的MEA对下面几种典型测试函数进行寻优：

，

该函数用于测试收敛速度，全局最小值为（0，0）。

，

该函数的极小值点（1，1）位于一狭长的抛物面形的平坦的处，较难找到，用于测试未成熟收敛。

，

该函数的极小值为（0，0）。在（0，0）附近范围内隆起部有无限多的次全局极大点，它的强烈震荡性质及它的全局最优点被次最优点所包围的特性，使得很难找到最优解。

在实验中，两种算法的种群规模设为100，每种算法各运行100次。每次运行过程中若得分值小于阈值（0.0001）则视为成功，否则视为失败。所有成功的迭代代数除以成功次数即位平均成功迭代代数，实验数据如表1所示。

表1实验结果

评价

函数算法阈值成功

次数失败

次数平均成功

迭代代数最优评价值

fit1基本MEA0.0001100020.245.252053e-5

加入遗传算子的MEA100019.272.225179e-14

fit2基本MEA841679.371.864154e-4

加入遗传算子的MEA10008.111.272805e-7

fit3基本MEA496779.172560e-5

加入遗传算子的MEA100011.862.947642e-14

从实验结果可以看出，加入遗传算子的MEA较基本MEA的搜索能力有明显的改善。特别是当极值点被局部次优的圈脊包围时，更能体现出加入遗传算子的MEA的优越性。从函数fit3的寻优结果可知，100次运算中基本MEA仅成功4次，但是改进后的MEA成功率为100%，而且其寻优结果比基本MEA更加精确。所以加入遗传算子的MEA的寻优的精度和速度是显而易见的。

参考文献

[1]Sunchen-yi，etal.Mind-Evolution-BasedMachineLearning：FrameworkandImplementationofOptimization[A].In：ProcIEEEIntConfonIntelligentEngineeringSystems[C].1998：355-359.

[2]HollandJH.Adaptationinnaturalandartificialsystems[M].MI：UniversityofMichiganPress，1975.

[3]戴晓晖，李敏强，寇纪淞.遗传算法理论研究综述[J].控制与决策，2000（3）：263-268.

[4]陈文清.遗传算法综述[J].沈阳工业高等专科学校学报，2003（1）：1-2.

[5]雷德明.多维实数编码遗传算法[J].控制与决策，2002（2）：239.

[6]孙承意，谢克明，程明琦.基于思维进化机器学习的框架及新发展[J].太原理工大学学报，1999（5）：453-457.

[7]曾建潮，孙承意.具有二进制编码的思维进化方法[J].航空计算技术，1999（4）：42-45.

[8]吉根林.遗传算法研究综述[J].计算机应用与软件，2004（2）：69-73.

[9]赵宗淦，李红俊.MEBML在优化排样中的趋同与异化策略[J].机械科学与技术，2002（2）：340-342.

[10]介靖，曾建潮.基于遗传算法与思维进化计算的一种广义进化模型[J].小型微型计算机系统，2004（3）：395-398.

[11]曾建潮，介靖.基于思维进化计算的一种广义进化模型[J].太原重型机械学院学报，2002（3）：181-186.

分子遗传学中心法则范文

[关键词]数据挖掘遗传算法关联规则

[中图分类号]TP18[文献标识码]A[文章编号]1007-9416(2010)02-0109-02

1引言

近年来,随着科技的进步,特别是信息产业的发展,把我们带入了一个崭新的信息时代。随着数据库技术的迅速发展以及数据库管理系统的广泛应用,同时条形码和信用卡的普及和使用,进一步加速了商业、金融、保险等领域的信息化进程。如此多领域的数据各自存放在相应的数据库中,致使数据库的规模日益扩大,已经达到数十兆字节,有的甚至更大。数据挖掘就是从大型数据库中的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在的有用的信息。提取的知识表示为概念(Concepts)、规则(Rule)、规律(Regularities)、模式(Patterns)等形式。

目前应用于数据挖掘的算法有很多种,如统计方法、机器学习方法、神经计算方法等。遗传算法由于其解决问题以混饨、随机和非线性为典型特征,它为其它科学技术无法解诀或难以解决的复杂问题提供了新的计算模型。这里,我们将遗传算法应用于数据挖掘领域,主要是因为:数据挖掘的目的就是要从大的数据库中提取信息与知识。为了达到这一目的,我们可以将整个数据库看作一个大搜索空间,而把挖掘算法看成一种搜索策略。显然,当数据库容量极其巨大时,进行穷举搜索是不可行的,必须采取一种有效的搜索策略。而与其它的启发式算法比较,遗传算法不仅具有很好的全局搜索能力,同时将其用于数据库领域时它能较好的处理数据库中不同属性之间的相互关系。正是因为遗传算法的这些特点,我们尝试将遗传算法用于数据库领域,实验证明算法是可靠的,可以得到数据库中具有较强预测能力的规则。本文提出用遗传算法挖掘关联规则,希望能在关联规则的提取方法上提出一种新的尝试。

2关联规则挖掘

关联规则挖掘就是从大量的数据中挖掘出有价值的、描述数据项之间相互关系的有关知识。有效的发现、理解、运用关联规则,是完成数据挖掘任务的一个重要手段。Agrawal等人于1993年首先提出了挖掘顾客事务数据库中项集间的关联规则问题,其核心方法是基于频繁项集理论的递推方法。目前,数据挖掘的关联规则方法有多种,其中Apriori算法是一种找频繁项集的典型算法。这种算法简单易理解,就是使用了不断通过连接产生候选集,并对侯选项集加以剪枝的方式来得到频繁集,再由频繁项集产生强关联规则的过程。关联规则是识别一组给定数据集的各特征值之间和各项之间的相互依赖及相互转化关系。关联规则是如下形式的一种规则:“在无力偿还贷款的人当中,60%的人的月收入在3000元以下。”关联规则的主要任务就是要挖掘出数据库D中所有的有用规则,在这个挖掘过程中,选择高效的关联规则算法进行数据挖掘是非常重要的。

设I={i1,i2,…im}为所有项目的集合,项目集,D为事务数据库,其中每个事务T是一个项目子集()。每一个事务具有惟一的事务标识Tid。我们说事务T包含项目集X,当且仅当。如果项集A中包含k个项目,则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是频繁项集(或大项集)。关联规则是形如X=>Y的逻辑蕴含式,其中,XT,YT,并且X∩Y=φ。X称作是前提,Y称作是结果。一般用两个参数描述关联规则的属性:

*支持度(support):如果事务数据库中有s%的事务包含XUY,那么我们就说关联规则X=>Y的支持度support为s,Support(X=>Y)=P(XUY)。

*信任度(support):如果事务数据库里包含X的事务中有c%的事务同时也包含Y,那么我们说关联规则X=>Y的信任度Confidence为c,Confidence(X=>Y)=P(Y|X)。

关联规则就是支持度和信任度分别满足用户给定阈值的规则。为了提高Apriori算法的有效性,可以使用基于散列的技术压缩侯选k-项集;而基于划分的方法是将大型事务数据库划分成多块数据,以便将每块数据放入内存求其频繁项集,这种方法只需要两次数据库的扫描;基于采样的方法,是在给定数据的一个子集上挖掘;通过事务压缩减少扫描的事务个数;基于hash的方法,可以提高找侯选项集的效率。另一种不需产生侯选项集的频繁模式增长算法,也是一种高效的关联挖掘算法。国内外在关联规则挖掘方面的研究已经取得了较大的进展,但关联规则挖掘技术在有些方面仍然存在着不足。需要进一步研究和提出更好的解决方案。

3遗传算法的基本思想

遗传算法是基于生物学进化原理的全局搜索算法,通过计算机模拟生物进化过程,对群体不断优化,最终找出最优解。到目前为止,遗传算法已经在模式识别、图象处理、人工智能、经济管理、商业和金融等多个领域中获得了较成功的应用。构成遗传算法的要素主要有:染色体编码,个体适应度评价,遗传算子(选择算子,交叉算子,变异算子)以及遗传参数设置等。基本遗传算法一般要包含以下几个处理步骤:

(1)选择编码策略,把参数集合X和域转换为位串结构空间S;

(2)定义适应值函数f(x);

(3)确定遗传策略,包括选择群体大小n,选择、交叉、变异方法;

(4)随机初始化生成群体P;

(5)计算群体中个串解码后的适应值f(x);

(6)按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;

(7)判断群体性能是否满足某一指标,或者已完成预定迭代次数,不满足返回步骤(6),或者修改遗传策略再返回步骤(6)。

4基于遗传算法的关联规则研究

遗传算法(GeneticAlgorithm-GA)是一种高效的启发式快速搜索算法,为了从海量数据中提取有用的信息与知识,我们可以将整个数据库看作一个大搜索空间,而把挖掘关联规则的算法看成一种搜索策略。当数据库容量极其巨大时,进行穷举搜索是不可行的,必须采取一种有效的搜索策略。针对传统的遗传算法容易导致算法的过早收敛而陷于局部最优困境,或收敛时间过长而消耗大量的搜索时间的缺陷,我们提出了一种改进的遗传算法,该算法采用一种自适应变异率和改进的个体选择方法,并且将这种改进遗传算法应用于web关联规则的挖掘,实验结果证明这种算法是有效的。

与其它的启发式算法比较,遗传算法不仅具有很好的全局搜索能力,同时将其用于数据库领域时它能较好的处理数据库中不同属性之间的相互关系。应用遗传算法进行关联规则发现,首先要对解决的实际问题进行编码,编码方法一般采用二进制编码,也可以采用十进制编码。关联规则挖掘的任务就是要发现能够反映记录属性之间的关系,通过遗传算法的适应度函数的定义,根据适应度函数的值进行搜索得到一组规则。利用交叉、变异运算对该组规则进行进化,再利用选择运算产生下一代规则,这样经过若干次迭代后,遗传算法满足终止条件,从而得到一组理想规则。接下来,利用这些规则对数据库中的数据进行加工,删除规则覆盖的例子,对剩余的数据继续采用以上遗传算法,去挖掘第二组规则。重复以上步骤,直至数据库中的所有例子都被覆盖或满足事先约定的终止条件。最后应用规则优化算法对所得规则进行优化,使之得到最简规则。基于遗传算法的关联规则挖掘技术可以应用在销售分析、金融信贷风险分析,物流货源分析等领域,具有较好的研究和应用价值。

[参考文献]

[1]叶传奇,张涛.遗传算法在数据挖掘中的应用研究[J].洛阳工业高等专科学校学报,2003.

[2]彭建.一种基于遗传算法的关联规则挖掘方法[J].计算技术与自动化,2005.

[3]张志立,张鹏,齐德昱:一种基于遗传算法的知识规则挖掘算法[J].郑州大学学报(理学版),2004.

[4]周涛,岳振才.基于改进遗传算法的关联规则挖掘[J].陕西工学院学报,2004.

[作者简介]

周大镯(1971-),女,河北文安人,河北经贸大学计算机中心副教授,天津大学管理学院在读博士研究生。研究方向:数据挖掘。