遗传进化理论及其在数据挖掘中的应用VIP专享VIP免费

自然杂志30卷1期科技进展遗传进化理论及其在数据挖掘中的应用万旺根①崔滨②ErikD．Goodman③①教授，②博士，上海大学通信与信息工程学院，上海200072；③教授，美国密歇根州立大学电子与计算机工作工程系，兰辛USA48824关键词遗传算法数据挖掘分类规则挖掘关联规则挖掘遗传进化理论由美国密歇根大学J．Holland教授提出．该理论借鉴生物遗传机制。以群体方法进行自适应搜索，受到广泛关注。并在科学研究中得到广泛应用。数据挖掘从大量数据中提取信息与知识。遗传算法具有群体搜索策略和简单的遗传算子。可以实现整个数据空间上的分布式信息搜索和采集。在数据挖掘领域得到广泛应用。本文综述了遗传算法的起源、基本原理和特点。介绍了数据挖掘的应用和发展，阐述了近年来遗传算法在分类规则挖掘和关联规则挖掘方面的应用。最后对遗传算法在数据挖掘中的应用前景和面临的挑战进行了分析和展望。遗传进化理论是模拟达尔文的遗传选择和自然淘汰、适者生存的生物进化过程的计算模型，由美国密歇根大学J．Holland教授于197-5年首先提出。遗传进化理论的核心是遗传算法，该算法是搜索最优解的一种随机化方法，其主要特点是群体搜索策略和群体中个体之间的信息交换方法。遗传进化理论是近20多年来备受关注的一种理论，并在数据挖掘、信号处理、工业设计等领域得到了广泛应用。1遗传算法的起源和特点遗传算法(GeneticAlgorithm)廷一类借鉴生物界的进化规律，即适者生存，优胜劣汰遗传机制而提出的随机化搜索方法[1|。遗传算法最早起源于对人们生物系统进行的计算机模拟研究。构成生物基本单位的细胞中含有一种微小的化合物称之为染色体，生物的所有遗传信息都包含在这个复杂而又微小的染色体中。染色体主要是由一种叫脱氧核糖核酸(DNA)的物质所构成，DNA在染色体中有规律地排列着，形成长长的链状结构，链状结构由于碱基间的氢键连接，所以有规律地扭合在一起，相互卷曲起来形成著名的双螺旋结构。基因就是DNA长链结构中占有一定位置的基本遗传单位，基因结构中的分子按一定的模式排列，进行遗传编码。生物的各种性状由其相应的基因控制，细胞通过分裂进行自我复制，而在细胞分裂过程中，其遗传基因也被复制到下一代，其性状也被下一代继承。所以基因是遗传的基本单位。1．1生物学基础早在20世纪40年代未，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。生命过程中的遗传是指生物从其亲代继承特性或性状，亲代的性状又在下一代表现，由于遗传的作用，使人们图1DNA和基因可以“种瓜得瓜、种豆得豆”。例如，父亲是色盲，女儿视虽然遗传与进化的奥秘目前还未完全揭开，科学家觉正常，但她由父亲得到色盲基因，并有一半机会将此们没有完全掌握遗传、进化的机制，也不清楚染色体究基因传给她的儿子，使其显现色盲性状。故从性状来竟是如何编码和译码，更不完全理解遗传与进化的控制看，父亲有色盲性状，而女儿没有，但从基因的连续性来方式，但人们却总结出遗传进化的几个特点[2]：‘看，代代相传，因而认为色盲是遗传的。遗传对于优生(1)生物的所有遗传信息都包含在其染色体中，染优育是非常重要的因素之一。色体决定生物的性状；·39·万方数据ProgressChineseJournalofNatureV01．30No．1(2)染色体是由基因及其规律排列所构成，遗传与进化过程发生在染色体上；(3)生物繁殖过程由其基因的复制过程来完成；(4)通过源染色体之间的交叉或染色体的变异产生新的物种，使生物呈现新的性状；(5)对环境适应性强的生物基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代。1．2遗传算法的提出在20世纪60年代，人们开始对自然和人工自适应系统进行研究，该研究领域逐渐成为研究热点。美国密歇根大学Holland教授认识到生物的遗传和自然进化现象与人工自适应系统的相似关系。他运用生物遗传和进化思想研究自然和人工自适应系统的生成、自适应系统与环境的关系。Holland教授提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，同时充分认识到交叉、变异等运算策略在自适应...