遗传进化理论及其在数据挖掘中的应用.pdf

自然杂志3 0 卷1 期科技进展遗传进化理论及其在数据挖掘中的应用万旺根崔滨E r i kD G o o d m a n 教授，博士，上海大学通信与信息工程学院，上海2 0 0 0 7 2；教授，美国密歇根州立大学电子与计算机工作工程系，兰辛U S A4 8 8 2 4关键词遗传算法数据挖掘分类规则挖掘关联规则挖掘遗传进化理论由美国密歇根大学J H o l l a n d 教授提出该理论借鉴生物遗传机制。以群体方法进行自适应搜索，受到广泛关注。并在科学研究中得到广泛应用。数据挖掘从大量数据中提取信息与知识。遗传算法具有群体搜索策略和简单的遗传算子。可以实现整个数据空间上的分布式信息搜索和采集。在数据挖掘领域得到广泛应用。本文综述了遗传算法的起源、基本原理和特点。介绍了数据挖掘的应用和发展，阐述了近年来遗传算法在分类规则挖掘和关联规则挖掘方面的应用。最后对遗传算法在数据挖掘中的应用前景和面临的挑战进行了分析和展望。遗传进化理论是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，由美国密歇根大学J H o l l a n d 教授于1 9 7-5 年首先提出。遗传进化理论的核心是遗传算法，该算法是搜索最优解的一种随机化方法，其主要特点是群体搜索策略和群体中个体之间的信息交换方法。遗传进化理论是近2 0 多年来备受关注的一种理论，并在数据挖掘、信号处理、工业设计等领域得到了广泛应用。1 遗传算法的起源和特点遗传算法(G e n e t i cA l g o r i t h m)廷一类借鉴生物界的进化规律，即适者生存，优胜劣汰遗传机制而提出的随机化搜索方法 1|。遗传算法最早起源于对人们生物系统进行的计算机模拟研究。构成生物基本单位的细胞中含有一种微小的化合物称之为染色体，生物的所有遗传信息都包含在这个复杂而又微小的染色体中。染色体主要是由一种叫脱氧核糖核酸(D N A)的物质所构成，D N A 在染色体中有规律地排列着，形成长长的链状结构，链状结构由于碱基间的氢键连接，所以有规律地扭合在一起，相互卷曲起来形成著名的双螺旋结构。基因就是D N A 长链结构中占有一定位置的基本遗传单位，基因结构中的分子按一定的模式排列，进行遗传编码。生物的各种性状由其相应的基因控制，细胞通过分裂进行自我复制，而在细胞分裂过程中，其遗传基因也被复制到下一代，其性状也被下一代继承。所以基因是遗传的基本单位。1 1 生物学基础早在2 0 世纪4 0 年代未，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。生命过程中的遗传是指生物从其亲代继承特性或性状，亲代的性状又在下一代表现，由于遗传的作用，使人们图1D N A 和基因可以“种瓜得瓜、种豆得豆”。例如，父亲是色盲，女儿视虽然遗传与进化的奥秘目前还未完全揭开，科学家觉正常，但她由父亲得到色盲基因，并有一半机会将此们没有完全掌握遗传、进化的机制，也不清楚染色体究基因传给她的儿子，使其显现色盲性状。故从性状来竟是如何编码和译码，更不完全理解遗传与进化的控制看，父亲有色盲性状，而女儿没有，但从基因的连续性来方式，但人们却总结出遗传进化的几个特点 2 ：看，代代相传，因而认为色盲是遗传的。遗传对于优生(1)生物的所有遗传信息都包含在其染色体中，染优育是非常重要的因素之一。色体决定生物的性状；3 9 万方数据P r o g r e s sC h i n e s eJ o u r n a lo fN a t u r eV 0 1 3 0N o 1(2)染色体是由基因及其规律排列所构成，遗传与进化过程发生在染色体上；(3)生物繁殖过程由其基因的复制过程来完成；(4)通过源染色体之间的交叉或染色体的变异产生新的物种，使生物呈现新的性状；(5)对环境适应性强的生物基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代。1 2 遗传算法的提出在2 0 世纪6 0 年代，人们开始对自然和人工自适应系统进行研究，该研究领域逐渐成为研究热点。美国密歇根大学H o l l a n d 教授认识到生物的遗传和自然进化现象与人工自适应系统的相似关系。他运用生物遗传和进化思想研究自然和人工自适应系统的生成、自适应系统与环境的关系。H o l l a n d 教授提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，同时充分认识到交叉、变异等运算策略在自适应系统中的重要性。1 9 7 5 年H o l l a n d 教授发表了第一本比较系统论述遗传算法的专著自然系统与人工系统中的适应性(A d a p t a t i o ni nN a t u r a la n dA r t i f i c i a lS y s t e m s)，从而奠定了遗传算法的基础，形成了遗传算法的基本框架。1 3 遗传算法的特点遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存”和“检测”迭代过程的搜索算法。遗传算法作为一种随机的优化与搜索方法，与其他搜索算法如回溯算法、模拟退火算法、禁忌搜索算法等相比具有鲜明特点：(1)遗传算法直接对需要研究目标的结构对象进行操作。遗传算法操作的对象不是参数本身，而是对参数进行编码的个体，这使得遗传算法可直接对结构对象如集合、序列、矩阵、树、图、链表等一维或多维对象进行处理。(2)遗传算法具有良好的全局寻优能力和鲁棒性。许多传统的搜索方法只是单点搜索算法，即通过一些变动规则，把问题的解从搜索空间中的当前解移动到另一个解。这样，对多峰分布的搜索空间常常会陷于局部极值点。遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多条。所以能自动获取和指导优化搜索空间，能够自适应调整搜索方向，因而遗传算法具有良好全局优化性和鲁棒性。(3)遗传算法没有求导可行性和函数连续性的限4 0 制。遗传算法只需要利用目标取值信息，而无需梯度等高阶信息，因而适用于任何大规模、非线性的不连续多峰函数的优化及无解析表达式的目标函数的优化，具有很强的通用性。(4)遗传算法具有潜在的并行计算能力。由于遗传算法采用概率化寻优方法，不需要确定规则，操作对象是一组可行解，搜索轨道有多条，所以具有良好的并行性。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，被人们广泛地应用于组合优化、机器学习、自适应控制和人工生命等领域，并取得了良好效果，它是现代智能计算中的关键技术，并逐渐成为重要的智能算法之一。1 4 遗传算法原理遗传算法求解优化问题的基本思想是：把优化的目标函数解释为生物种群对环境的适应性，把优化变量对应为生物种群的个体，由当前种群出发，利用合适的复制、交叉、变异与选择操作生成新一代种群，重复这个过程，直到求得合乎要求的种群为止。其中，选择、交叉和变异是遗传算法的核心操作。参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数等五要素构成了遗传算法的主要内容。图2 遗传算法迭代过程基本遗传算法是个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择、交叉、变异作用于群体，最终可得到问题的最优解或近似最优解。遗传算法提供了一种求解复杂系统优化问题的通用框架。它不依赖于问题的领域和种类。对一个需要进行优化计算的实际应用问题，可按下述步骤来构造求解该问题的遗传算法。(1)初始化。建立优化模型，确定求目标函数的最大值或最小值，同时设置数学描述形式或量化方法，确定适应度函数，用该函数对每一代的适应性进行评价。确定表示可行解的染色体编码方法，将解空间作为群 万方数据自然杂志3 0 卷1 期科技进展体，即确定出个体的基因型及遗传算法的搜索空间。设置最大进化代数和各控制参数。从群体中随机选择一定量的个体作为初始群体。初始群体如同生物的染色体，该种群被称为第一代，通过选择、交叉、变异等遗传操作，产生新一代染色体，然后代代繁衍下去，直到找到适应环境能力最强的染色体，达到期望结果。(2)个体评价。首先解码，将个体基因转换为表现一定性状的值，形成解集合，然后根据适应度函数计算群体中各个体的适应度。适应度函数对每一个解求出一个适应度值，解是可能的答案，而问题的答案则是其中最优的解或比较满意的解。如同生物学中一样，解相当于所有染色体，而问题的答案是适应环境性最好的染色体。(3)选择运算。将选择操作运用于群体，根据个体评价计算出的个体适应度，选择适应性强的染色体并赋予较大的繁衍概率。(4)交叉运算。两个相互配对的染色体交换其部分基因，形成新的个体。交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。(5)变异运算法。根据先前设定的变异概率对染色体进行变异计算，从而产生新的染色体，表现出新的性状。虽然发生变异的概率比较小，与交叉运算相比，只是产生新个体的辅助方法，但也是产生新物种的一个不可忽视的原因。经过选择、交叉、变异运算后得到下一代群体。(6)终止条件判断。若目前代数小于设定的最大进化代数，则转到(2)，再进行进化迭代。若已达到最大进化代数，则以进化过程中得到的具有最大适应度的个体作为最优解输出，终止计算。从遗传算法的基本原理可以看出，遗传算法作为一种自适应随机搜索方法，其搜索方式由当前群体所提供信息决定，而不是由数据结构决定，也不会按单一方向搜索。同时，遗传算法将多个体作为可能解，并考虑在搜索空间中全局范围内的抽样，因此能以更大的可能性收敛到全局最优解。由于这些特性，遗传算法能够成功地用于求解众多不同的复杂而困难的优化问题，包括数据挖掘问题。2 遗传算法在数据挖掘中的应用数据挖掘是对观测到的数据集进行分析以提取人们感兴趣的内容信息，而这些数据集往住是很庞大的 3 ，数据挖掘的目的是发现未知的关系，使人们可以理解数据信息，并利用一定方式来总结数据，在过去的经验基 i l t lI-_预言未来趋势等。从广义上讲，数据挖掘是从大量随机的、有噪声的、不完全的、模糊的实际数据中提取隐含在其中未知的、潜在有用的信息和知识的过程。由于工业生产、经营管理的实际需要，加上超大规模数据库的出现以及先进的计算机技术对这些数据的快速、深入的计算促使数据挖掘诞生，并快速发展和广泛应用。随着海量数据搜集、强大的多处理器计算机和数据挖掘算法这三种基础技术的发展成熟，数据挖掘技术开始得到广泛的重视，而遗传算法是众多数据挖掘技术中最重要的一种，它可以从数据仓库的大量数据中筛选信息，寻找可能出现的模式，挖掘人们所不知道的事实。2 1 数据挖掘的发展随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。人们希望将这些数据转换成有用的信息和知识，以便更好地利用这些数据，用于决策。虽然数据库系统可以高效地实现海量数据的录入、查询、统计等功能，但无法发现海量数据背后隐藏的具有决策意义的知识，如关系和模式，无法根据现有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据丰富但知识贫乏”的现象。面对“被数据淹没，却饥饿于知识”的挑战，数据挖掘技术应运而生。数据挖掘的概念在1 9 8 9 年8月于美国底特律市召开的第一届知识发现国际学术会议上正式形成。但数据挖掘在随后的研究中一直作为数据库和机器学习的一个分支，处于依附的地位。直到1 9 9 8 年6 月，A C MS I G K D D(美国计算机协会知识发现和数据挖掘特别互联网工作组)正式成立，标志着数据挖掘正式成为一个独立学科。2 2 遗传算法与数据挖掘数据挖掘的目的是要从数据库中提取信息与知识。为了达到这一目的，整个数据库可以被看作一个大的搜索空间，而数据挖掘方法则是一种搜索策略。显然，当数据库容量极其巨大时，进行穷举法是不可行的，必须采取一种有效的搜索策略。目前广泛采用的数据挖掘方法有多种，除遗传算法外，还包括：统计方法、机器学习方法、神经计算方法、决策树法、粗糙集算法等。与其他算法相比，遗传算法具有如下的优势。遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子 4 l。群体搜索使遗传算法得以突破邻域搜索的限制，可以实现整个界空间上的分布式信息搜索、采集和继承；遗传算子仅仅利用适应值度量作为运算指标进行染色体的随机操作，降低了一般算法在搜索4 1o 万方数据P r o g r e s sC h i n e s eJ o u r n a lo fN a t u r eV 0 1 3 0N o 1过程中对人机交互的依赖。这样就使得遗传算法获得了强大的全局最优解搜索能力 5 I、问题域的独立性、信息处理的隐并行性、应用的鲁棒性、操作的简明性，成为一种具有良好普遍适应性和可规模化的优化方法，其精度不亚于其他搜索算法。遗传算法的另一个优点是用户可以通过适应度函数的恰当设计得到不同性质的分类规则 6|。传统分类算法通常强调分类规则的准确性，如决策树算法、粗糙集算法在运行后都能得到高准确率的分类规则，但却不能或难以发现具有其他性质的分类规则，而遗传算法却可以通过对适应度函数的设计发现多种性质的分类规则，从而满足不同用户的需求。由于遗传算法能进行全局搜索，并能处理数据库中各种关联因素。同时与其他的搜索算法比较，遗传算法不仅具有很好的全局搜索能力，同时在处理数据库时，遗传算法能较好的处理数据库中不同属性之间的相互关系。正是因为遗传算法的这些特点，遗传算法被广泛用于数据库领域，实践证明利用遗传算法进行数据挖掘是可靠的，可以得到数据库中具有较强预测能力的规则 7|。2 3 分类规则挖掘目前基于遗传算法的数据挖掘方法研究主要集中在分类系统方面 8 。分类是数据挖掘的一种重要分析方法，即在已有数据的基础上构造一个分类函数或一个分类规则。该函数或模型能够把数据库中的数据映射到给定类别中的一个 9 ，从而可以应用于数据预测。其他常用的分类规则挖掘方法有统计方法、机器学习方法、粗糙集方法、神经网络方法。这些分类规则挖掘算法都有各自的内部缺陷。例如，统计方法中要求的先验概率在理论上令人难以信服；机器学习方法对噪声的容错性能差；粗糙集方法存在一个根本问题即无有效方法确定成员的隶属度；神经网络方法由于存在太多的节点和连接权，使得到的结果难以理解和验证。遗传算法在各种数据分类问题转化为遗传群体的迭代过程时也会遇到困难。尽管遗传算法存在缺点，但由于快速高效的搜索策略，使得其备受关注。其中重要的方法是基于小生境遗传算法D 0 l 的分类规则挖掘。小生境技术是将每一代个体划分成若干类，每个类中选出若干适应度值较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群。同时采用预选择机制将种群中的优秀代表保留下来，在子代中只有源于同一种群的适应度优于其父代的个体才有资格替代其父代中的个体。这样，在进化过程4 2，同时，由于不断地用优秀个体更新种群，使得种群不断地被优化。通过采用小生境技术，使得改进后的遗传算法保持了解的多样性，同时具有很高的全局寻优能力和收敛速度，特别是对复杂的多峰值函数的寻优问题显示出了明显的优越性 1 1|。2 4 关联规则挖掘近来年利用遗传算法进行关联规则提取逐渐成为研究热点。这是由于遗传算法具有全局寻优、并行处理的特点和优势，所以适合于进行关联规则挖掘。关联规则是指在数据库中具有这种形式的规则：由于某些事件的发生而引起另外一些事件的发生，它在决策支持系统、专家系统和智能信息系统等各个方面起着重要的作用。随着数据库应用的普及，数据挖掘的应用越来越广，在近几年内倍受人们的关注。例如，在学生资料数据库中可以发现“入学时是保送生的入学后学习成绩也是优良的可能性是6 0”，这就是一个关联规则。许多数据挖掘问题可以看成是搜索问题，数据库是搜索空间，发现算法是搜索策略。因此，遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能够被该组规则覆盖，从而挖掘出隐含在数据库中的规则。应用遗传算法进行数据挖掘，首先要对实际问题进行编码，然后，定义遗传算法的适应度函数，同时，随机产生一组规则，对每一个规则应用数据库中给定的例子进行判断，根据适应度函数计算其适应度。应用交叉、变异运算对该组规则进行进化，再利用选择运算产生下一代规则，这样经过若干次迭代后，遗传算法满足终止条件，从而得到一组理想规则。接下来，利用这些规则对数据库中的数据进行加工，删除规则覆盖的例子，对剩余的数据继续采用以上的遗传算法挖掘第二组规则。重复以上步骤，直至数据库中的所有例子都被覆盖或满足事先约定的终止条件。最后应用规则优化算法对所得规则进行优化，得到最简规则。现有的关联规则挖掘模型主要是R A g r a w a l 等人提出的A p r i o r i 算法 1 2 3，其中的核心问题是发现最大项目集。发现最大项目集的过程其实是全局搜索过程，遗传算法是一种全局优化算法，因此它避免了搜索过程中的局部最优。将遗传算法用在规则的发现和提取方面能够发现有价值的规则 1 3 1 4 1 。3 应用展望和挑战遗传算法作为一种数据挖掘技术，在各种问题的求解和应用中展现了它的特点和优势，随着数据挖掘领域 万方数据自然杂志3 0 卷1 期科技进展的不断扩展，遗传算法将会应用在提高数据挖掘的效率、解决挖掘数据失真、以及多媒体数据的挖掘等方面。遗传算法在数据挖掘的应用中也暴露了其在理论和应用上的许多不足。目前虽然有大量遗传算法新策略不断被提出，但是大部分都是对特定问题求解而言，评估也只限于基于对比试验，缺乏深刻而具有普遍意义的理论深化以及更通用的方法研究。在数据挖掘方面，遗传算法除了要迸一步改进基本理论和方法外，还需要采用与神经网络 1 5 t6 l、模拟退火等方法相结合的策略以提高挖掘能力。许多研究结果表明，采用混合模型 1 7,1 8 3 可以有效提高遗传算法的局部搜索能力，从而进一步改善其收敛速度和解的品质。随着相关问题的解决以及数据挖掘领域的不断拓展，遗传进化理论在数据挖掘方面的应用必将取得更大的发展。(2 0 0 7 年7 月1 2 日收到)1G O O D M A NED I n t r o d u c t i o nt og e n e t i ca l g o r i t h m s C G e n e t i c E v o l u t i o n a r yC o m p u t a t i o nC o n f e r e n c e-2 0 0 5(G E C C o 2 0 0 5)，s p o n s o r e db yA C MS l G E V 0。J u n e，2 0 0 5 2 周明，孙树栋遗传算法原理及应用E M l 北京：国防工业出版社，1 9 9 9 3H A N DD M A N N l L AH。S M Y T HP P r i n c i p l e so fd a t am i n i n g M M I TP r e s s，2 0 0 1 4R A Y M E RM。P U N C HW，G o o D M A NED，e ta 1 G e n e t i ep r o g r a m m i n gf o ri m p r o v e dd a t am i n i n g-a p p l i c a t i o nt ot h eb i o-c h e m i s t r yo fp r o t e i ni n t e r a c t i o n s c G e n e t i cP r o g r a m m i n g9 6，1 9 9 6：3 7 5 3 8 1 5J A N A K IG，e ta 1 E f f e c t i v ed a t am i n i n gb yi n t e g r a t i n gg e n e t i ca l g o r i t h mi n t ot h ed a t ap r e p r o e e s s i n gp h a s e e 1 P r o c e e d i n g so ft h eF o u r t hI n t e r n a t i o n a lC o n f e r e n c eo nM a c h i n eL e a r n i n ga n dA p p l i c a t i o n s(I C M L A 0 5)，2 0 0 5：3 3 1 3 3 6 6L A V A N G N A N A N D AK S e I f a d j u s t i n ga s s o c i a t i v er u l e sg e n e r a t o rf o rc l a s s i f i c a t i o n；a ne v o l u t i o n a r yc o m p u t a t i o nA p-p r o a c h C 7 2 0 0 6I E E EM o u n t a i nW o r k s h o po nA d a p t i v ea n dL e a r n i n gS y s t e m s 2 0 0 6：2 3 7 2 4 2 7H I s A oI，Y u S U K EN，I S A oK M u I t i-o b j e c t i v eg e n e t i cr u l es e l e c t i o na sad a t am i n i n gp o s t p r o c e s s i n gp r o c e d u r e -C P r o c e e d i n g so ft h e 8 t hA n n a a lC o n f e r e n c eo nG e n e t i ca n dE v o l u t i o n a r yC o m p u t a t i o n。2 0 0 6：1 5 9 1 1 5 9 2 8F O L I N OG，P I Z Z U T IC，S P E Z Z A N OG G Pe n s e m b l e sf o rl a r g e s c a l ed a t ac l a s s i f i c a t i o n J I E E ET r a n s a c t i o n so nE v o l u-t i o n a r yC o m p u t a t i o n，2 0 0 6。5(1 0)z6 0 4 6 1 6 9B o E T T l C H E RGD，K A M I N S K YK T h ea s s e s s m e n ta n da p p l i c a t i o no fl i n e a g ei n f o r m a t i o ni ng e n e t i cp r o g r a m sf o rp r o d u-c i n gb e t t e rm o d e l s C 2 0 0 6I E E EI n t e r n a t i o n a lC o n f e r e n c eo nI n f o r m a t i o nR e u s ea n dI n t e g r a t i o n 2 0 0 6：1 4 1 1 4 6 1 0 徐金梧，刘纪文基于小生境技术的遗传算法 J 模式识别与人工智能，1 9 9 9，(3)；1 0 4 1 0 6 1lL I UB，H S UW，C H E NS U s i n gg e n e r a li m p r e s s i o n st oa n a-l y z ed i s c o v e r e dc l a s s i f i c a t i o nr u l e s C T h e3 r dI n t lC o n f o nK D Da n dD a t aM i n i n g(K D D 9 7)，1 9 9 7 1 3 1 3 6 1 2A G R A W A LR，I M I E L N S K I T，S W A M IA M i n i n ga s s o c i a t i o nr u l e sb e t w e e ns e t so fi t e r ni nl a r g ed a t a b a s e C A C MS I G-M o Di n t Ic o n fo nM a n a g e m e n to fD a t a，1 9 9 3：2 0 7 2 1 6 1 3S U N I LC O nt h es u i t a b i l i t yo fg e n e t i c b a s e da l g o r i t h m sf o rd a t am i n i n g C A d v a n c e si nD a t a b a s eT e c h n o l o g i e s。S i n g a-p o t，1 9 9 8：5 5 6 7 1 4W UYT，Y O OJA，G E L L E RJ e ta 1 Ad a t am i n i n gb a s e dg e n e t i ca l g o r i t h m C P r o c e e d i n g so ft h eF o u r t hI E E EW o r k s h o po f fS o f t w a r eT e c h n o l o g i e sf o rF u t u r eE m b e d d e da n dU b i q u i t o u sS y s t e m s，a n dt h eS e c o n dI n t e r n a t i o n a lW o r k s h o po nC o l l a b o r a t i v eC o m p u t i n g，I n t e g r a t i o na n dA s s u r a n c e(S E U S W C C I A 0 6)，2 0 0 6：5 5 6 2 1 5C H I AHWK，T A NCL S U N GSY E n h a n c i n gk n o w l e d g ed i s c o v e r yv i aa s s o c i a t i o n b a s e de v o l u t i o no fn e u r a ll o g i cn e t w o r k s J I E E ET r a n s a c t i o n so nK n o w l e d g ea n dD a t aE n g i n e e r i n g，2 0 0 6，7(1 8)l8 8 9 9 0 1 1 6V A L D E SJJ，B A R T O NAJ V i r t u a lr e a l i t yv i s u a ld a t am i n i n gv i an e u r a ln e t w o r k so b t a i n e df r o mm u l t i o b j e c t i v ee v o l u t i o n a r yo p t i m i z a t i o na p p l i c a t i o nt og e o p h y s i c a lp r o s p e c t i n g C I n-t e r n a t i o n a lJ o i n tC o n f e r e n c eo nN e u r a lN e t w o r k s(U C N N 0 6)，2 0 0 6：4 8 6 2-4 8 6 9 17S H U MWH，L E U N GkS，W o N GML L e a r n i n ga c y c l i ed e-c i s t o nt r e e sw i t hf u n c t i o n a ld e p e n d e n c yn e t w o r ka n dM D Lg e-n e t i ep r o g r a m m i n g C C o m p u t i n gi nt h eG l o b a lI n f o r m a t i o nT e c h n o l o g y 2 0 0 6(I C C G I 0 6)，2 0 0 6：2 5 3 2 1 8 张应辉，曾庆华，王志伟遗传算法的混合算子策略 J 计算机科学，2 0 0 7，4(3 4)：2 2 2 2 2 4T h eT h e o r yo fG e n e t i cA l g o r i t h m sa n dI t sA p p l i c a-t i o n so nD a t aM i n i n g、6 州W a n g-g e n，C U IB i n。，E r i kD G o o d m a n。P r o f e s s o r。P h D，S c h o o lo fC o m m u n i c a t i o na n dI n f o r m a t i o nE n g i n e e r i n g，S h a n g h a iU n i v e r s i t y，S h a n g h a i2 0 0 0 7 2，C h i n a；P r o f e s s o r，D e p a r t m e n to fE l e c t r i c a la n dC o m p u t e rE n g i n e e r i n g，M i c h i g a nS t a t eU n i v e r s i t y，L a n s i n g4 8 8 2 4，U S A A b s t r a c tT h et h e o r yo fg e n e t i ca l g o r i t h m sw a se s t a b l i s h e db yP r o?f e s s o rJ H o l l a n do ft h eU n i v e r s i t yo fM i c h i g a nw h ow a si n s p i r e db yb i o l o g i c a lg e n em e c h a n i s m T h et h e o r yo fg e n e t i ca l g o r i t h m sw h i c ht a k e sa d v a n t a g eo fg r o u pa d a p t i v es e a r c hm e t h o dh a s r e c e i v e db r o a da t t e n t i o na n di sw i d e l yu s e di ns c i e n t i f i cr e s e a r c h M e a n w h i l e，d a t am i n i n gi sa l s ow i d e l yu s e dt oo b t a i ni n f o r m a t i o na n dk n o w l e d g ef r o mv o l u m ed a t a W i t has i m p l eg r o u ps e a r c hs t r a t e g ya n dag e n e t i co p e r a t o r，g e n e t i ca l g o r i t h m sc a nr e a l i z ed i s t r i b u t e ds e a r c h i n ga n di n f o r m a t i o ng a t h e r i n gf u n c t i o nf r o maw h o l ed a t as p a c e T h e r e f o r e，t h et h e o r yo fg e n e t i ca l g o r i t h m si sw i d e l yu s e di nt h ef i e l do fd a t am i n i n g I nt h i sp a p e r。t h ea p p l i c a t i o n so f t h eg e n e t i ce v o l u t i o nw e r ed i s c u s s e do nt h ec l a s s i f i c a t i o nr u l e sm i n i n ga n dt h ea s s o c i a t i o nr u l e sm i n i n g B e s i d e s，t h eo r i g i n，b a s i cp r i n c i p l e sa n df e a t u r e so ft h eg e n e t i ca l g o r i t h mw e r er e v i e w e d T h ed e v e l o p m e n to fd a t am i n i n ga n di t sa p p l i c a t i o n sw e r ea l s od i s c u s s e d F i n a l l y，t h ep r o s p e c t sa n dc h a l l e n g e so f t h ea p p l i c a t i o no f t h eg e n e t i ca l g o r i t h m so nd a t am i n i n gw e r ef o r e c a s t e d K e yw o r d sg e n e t i ca l g o r i t h m，d a t am i n i n g，c l a s s i f i c a t i o nr u l e sm i n i n g，a s s o c i a t i o nr u l e sm i n i n g(责任编辑：丁嘉羽)4 3 万方数据遗传进化理论及其在数据挖掘中的应用遗传进化理论及其在数据挖掘中的应用作者：万旺根，崔滨，Erik D.Goodman，WAN Wang-gen，CUI Bin，Erik D.Goodman作者单位：万旺根,崔滨,WAN Wang-gen,CUI Bin(上海大学通信与信息工程学院,上海,200072)，ErikD.Goodman,Erik D.Goodman(美国密歇根州立大学电子与计算机工作工程系,兰辛,USA,48824)刊名：自然杂志英文刊名：CHINESE JOURNAL OF NATURE年，卷(期)：2008，30(1)被引用次数：0次 参考文献(18条)参考文献(18条)1.GOODMAN E D Introduction to genetic algorithms 20052.周明.孙树栋 遗传算法原理及应用 19993.HAND D.MANNILA H.SMYTH P Principles of data mining 20014.RAYMER M.PUNCH W.GOODMAN E D Genetic programming for improved data mining-application to thebiochemistry of protein interactions 19965.JANAKI G Effective data mining by integrating genetic algorithm into the data preprocessing phase20056.LAV