下载文档原格式
20世纪50年代末，国外就有人开始进行课程编排问题研究，Judit Csima & C.C. Gotlieb[16]曾形象化描述并提出一个求解课表问题的数学模型，上世纪70年代，Even和Cooper[17]等人证明了排课问题就是一个NP-Hard问题。
而NP 问题除了穷举法没有绝对的求解方法，这有效地回答了排课在应用中遇到困难的原因，同时认识到了课表编排的复杂性，从理论上证明了要解决大规模的排课问题单纯依靠数学方法是行不通的。
印度Vastapur 大学管理学院的Arabinda Tripathy 在1992年进行了课表编排研究，他在进行课表编制过程中，充分地考“人”的因素，并以“人”为单位进行课表编排，但是效果却差强人意[18]。
有学者指出，可以通过适当地减少变量的个数，从而使得在排课时，最大程度地减少计算量，但是，这种思想无疑是不可取的，因为排课属于一个多目标的优化问题，减少变量的个数，人为地造成课程之间的矛盾[19]。
有学者设计了多重课组进行排课，具体是根据学生自主选课的冲突情况，如果选课学生人数过多，教学与教室之间冲突情况严重，则可以在一周内开设一定数量的重复课程，来解决选课学生人数多的矛盾，但是这种方法的随机性较大，无法从根本上解决排课过程中多目标问题。
加拿大Montreal 大学的Jacques A．Ferland 等人通过研究，认为可以将排课问题分解成两个关联程度较高的子问题：即分成时间表和课程分组，并构造相应的启发函数和惩罚因子，来试图解决排课问题[20]。
在排课过程中，Jacques A．Ferland 等人将SAPHIR 课程调度决策支持系统分成多个功能模块，如数据处理、自动优化、交互优化等模块，利用多重课组来协调解决排课过程中出现的主要矛盾[21]。
Colomi 等人将具有自适应寻优能力的遗传算法用于课程编排问题求解，首先与高校教学过程相关的因素进行编码，然后采用遗传算法模拟自然界的选择、交叉、变异算子寻找最优排课方案，并应用到当前一所高中的排课系统中。
收稿日期:2008-01-12;修回日期:2008-03-26 基金项目:西南大学研究生科技创新基金资助项目(2006011)作者简介:葛继科(1977-),男,河南濮阳人,博士研究生,主要研究方向为人工智能、语义网格(g j k i d@s .cn);邱玉辉(1938-),男,教授,博导,主要研究方向为人工智能、语义网格;吴春明(1972-),男,博士研究生,主要研究方向为网络技术;蒲国林(1971-),男,博士研究生,主要研究方向为人工智能.遗传算法研究综述*葛继科1,邱玉辉1,吴春明1,蒲国林2(1.西南大学计算机与信息科学学院,重庆400715;2.四川文理学院计算机科学系,四川达州635000)摘 要:介绍了遗传算法的基本工作原理和主要特点,讨论了遗传算法的理论、技术、存在问题及改进方法,概述了遗传算法的常见应用领域,分析了近五年国内对遗传算法的研究现状。
最后,进一步探讨了遗传算法的未来研究方向。
关键词:遗传算法;算子;优化;收敛性中图分类号:TP301.6 文献标志码:A 文章编号:1001-3695(2008)10-2911-06Sum m ary of geneti c a l gorithm s researchG E J-i ke 1,Q IU Y u -hu i 1,W U Chun -m i ng 1,PU G uo -li n 2(1.S c h ool of Compu ter&Infor m ation S cie n c e ,S outhw estUniversity ,Ch ong qi ng 400715,C hina;2.D e pt .o f Co m pu ter S cie nce ,S ic huan Uni -versit y of Arts&S cie n c e ,Dazhou S ic huan 635000,Ch i na )Abstract :Th is paper i ntroduced the h i story ,basic pri nciple and m ai n characters of genetic al gorith m s ,d i scussed t he theory ,technology ,lm i itati on and m i provi ngm easures about geneti c al gorith m.Then s u mm arized the m i p l e m entati on techni ques and app licati ons of genetic algorith m s ,anal yzed the research state of genetic al gorith m s i n Chi na duri ng t he past five years ,and poi nted out the genetic algorit h m s .research directi ons i n the fut u re .Key words :geneti c al gorith m (GA );operator ;optm i i zati on ;convergence 遗传算法是由美国M ich i gan 大学的H o lland 教授于1969年提出,后经D eJong 、G o ldberg 等人归纳总结所形成的一类模拟进化算法[1~3]。
经典人工智能算法综述一、专家系统专家系统是人工智能领域最早的知识工程技术之一，该技术首次在20世纪70年代末提出。
专家系统利用专家知识来解决特定问题，主要包括知识表示、知识推理和知识获取等方面。
专家系统常常包括知识库、推理机、用户接口等组成部分，通过模拟专家的经验和知识，来完成推理和决策。
专家系统在医疗、金融、制造等领域得到了广泛的应用，例如Dendral系统是一个专家系统，用于分析气相色谱质谱仪的输出数据以确定化合物的结构。
二、遗传算法遗传算法是一种模仿自然进化过程的搜索优化算法，它通过模拟自然选择、交叉和变异等进化过程来搜索问题的最优解。
遗传算法最早是由美国的约翰·霍兰德于20世纪60年代提出的。
遗传算法主要包括编码、选择、交叉、变异等操作，通过不断进化生成适应度更高的解，从而找到问题的最优解。
遗传算法在优化问题、机器学习、数据挖掘等领域得到了广泛的应用，例如在大规模旅行商问题、神经网络权值优化等问题上展现出了优势。
三、模糊逻辑模糊逻辑是一种用于表示不确定性、模糊性信息的逻辑系统，它在20世纪70年代被提出。
模糊逻辑将传统的逻辑二元关系扩展到了模糊的多值逻辑关系，使得不确定性、模糊性信息能够得到有效的处理。
模糊逻辑主要包括模糊集合理论、模糊关系、模糊推理等内容，被广泛应用于人工智能、控制系统、信息检索等领域。
例如在智能控制系统中，模糊逻辑被用于建模、推理，实现了对复杂系统的精确控制。
四、人工神经网络人工神经网络是一种模仿生物神经网络结构和功能的计算模型，它借鉴了大脑中的神经元和突触结构。
人工神经网络可以通过学习来自动地调整网络的连接权值，从而实现对信息的处理和识别。
人工神经网络于20世纪50年代被提出，并在之后得到了不断的改进和发展。
人工神经网络在模式识别、控制系统、金融预测等领域展现出了优势，例如AlphaGo就是基于深度神经网络的围棋程序，击败了世界冠军。
五、规则学习规则学习是指利用训练数据自动学习出数据中的规则并进行预测和决策的技术。
数据分析知识：数据挖掘中的遗传算法作为一种数据挖掘技术，遗传算法广泛应用于各个领域，如优化问题、机器学习、控制系统等。
它通过模拟自然选择的过程，不断迭代寻找最优解，具有灵活性、鲁棒性和高效性等优点，成为一种有效的数学工具。
本文将从遗传算法的概念、原理、基本过程及应用等方面进行介绍和探讨，希望对读者对遗传算法有一个全面的认识。
一、遗传算法的概念遗传算法是模拟生物进化过程中的自然选择、交叉、突变等规律，对经过编码后的个体进行迭代计算和优化，以寻找最优解的一种计算方法。
它将问题的求解转化为个体编码、适应度评价和遗传操作的过程，并通过重复执行演化过程，逐步优化目标函数的值。
遗传算法是一种鲁棒性强的优化方法，适用于各种类型的优化问题，如多维非线性优化、组合优化、约束优化等。
二、遗传算法的原理生物进化过程中存在自然选择、遗传变异和适应度评价等过程，遗传算法就是模拟这些过程进行计算和优化的。
其基本原理如下：1.个体表示：将问题中的候选解编码为某种形式的个体，如二进制编码、实数编码、字母编码等。
2.评价函数：评价函数用于度量每个个体的适应性或优越性，以便进行选择操作。
3.选择操作：选择操作根据评价函数的结果，选择具有高适应度的个体作为进化的基础，通常采用轮盘赌选择、锦标赛选择等方式。
4.交叉操作：交叉操作是将两个个体的编码进行配对交换，以获得新的个体，实现基因的交换和组合，通常采用单点交叉、多点交叉、均匀交叉等方式。
5.变异操作：变异操作是对个体编码中的某些基因随机改变，以增加搜索空间的多样性和可达性，避免进化陷入局部最优解。
通过选择、交叉和变异操作，遗传算法不断迭代，逐步搜索到最优解，达到优化目标函数的目的。
三、遗传算法的基本过程遗传算法的基本过程如下：1.初始化种群：将问题中所有可能的解编码为某种形式的个体，构成一个初始种群。
2.适应度评价：对每个个体进行评价函数计算，并根据适应度大小排序。
3.选择操作：根据某种选择操作方式（如轮盘赌选择、锦标赛选择等）选择具有较高适应度的个体作为进化的基础。
遗传算法与评价方法综述摘要:一直以来，由于遗传算法的优异性，被广泛应用在各个领域；本文通过遗传的各个步骤和方法的介绍，便于学者理解，并指出算法的评价指标，为广大学者提供验算标准。
关键词：编码；初始化；交叉1遗传算法研究综述遗传算法是模拟达尔文生物进化论的计算模型，它通过模拟物种长期繁衍进化的过程，对要求解的问题进行全局自适应搜索，以搜索问题[1]。
1994 年，Aderson使用遗传算法研究了装配线平衡问题[2]。
2000年， Kim 等率先使用遗传算法求解双边装配线平衡问题[3]。
2009年，吴尔飞提出一种基于“序列组合”编码的遗传算法用于求解双边装配线的平衡问题[4]。
2014年，Arunkumar等以最小化生产节拍为优化目标，提出一种改进的遗传算法[5]。
2020年，李尚函提出一种双层结构的混合超启发式遗传算法求解模糊柔性作业车间调度问题[6]。
一直以来，由于遗传算法的优异性，被广泛应用在各个领域，然而，由于自身的缺点，使得广大学者根据各自的领域的特性进行优化，以达到最优解求解的结果。
2遗传算法概述2.1编码编码方式通常是根据问题的特性，将求解问题的可行解转化成遗传算法可以处理的搜索解。
常用的编码方式如下[7]：二进制编码、浮点数编码、实数编码、十进制编码。
2.2初始化种群初始种群是一个种群集合，是通过某种方式产生初始种群的过程，让算法能够对种群中的个体进行操作。
初始种群的产生方法一般有两种：（1）一种是在对问题的解无任何理论或实际研究经验的情况下，依靠随机性生成多组染色体，组成初始种群。
这种方法相对简单易行，能够实现初始种群中染色体的多样性，便于扩大搜索空间。
然而，随机选择可能会产生比较多的无效解，可能会增大搜索的难度；（2）将已经实验经验或者研究的方法转化为约束条件，然后根据这些条件进行随机选择，并生成一定数量的染色体，组成初始种群。
这种方法，能够避免无效的搜索，有助于遗传算法快速收敛。
基于遗传算法与神经网络混合算法的数据挖掘技术综述摘要：数据挖掘是对大型数据库的数据进行统计分析、提取信息的方法，其基础是人工智能技术。
遗传算法和神经网络是人工智能技术中最重要的技术。
通过对遗传算法和神经网络的特征分析，阐述了遗传算法与神经网络混合算法在数据挖掘中的应用，指出了数据挖掘技术未来发展的方向。
关键词：数据挖掘；数据库；遗传算法；神经网络1遗传算法基本特征遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种具有广泛适用性的通用优化搜索方法。
遗传算法主要借用了生物遗传学的观点，通过自然选择、遗传和变异等作用机制来产生下一代种群，如此逐代进化，直至得到满足要求的后代即问题的解，是一种公认的全局搜索能力较强的算法。
遗传算法有良好智能性，易于并行，减少了陷于局部最优解的风险。
遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体，可以直接对集合、队列、矩阵、图表等结构进行操作。
同时，在标准的遗传算法中，基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传操作；遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜寻方向。
正是这些特征和优点，使得遗传算法在数据挖掘技术中占有很重要的地位，既可以用来挖掘分类模式、聚类模式、依赖模式、层次模式，也可用于评估其它算法的适合度。
2神经网络基本特征神经网络是人脑或自然神经网络若干基本特征的抽象和模拟，是以大量的、同时也是很简单的处理单元（神经元）广泛地互相连接形成的复杂非线性系统。
人工神经网络本质上是一个分布式矩阵结构，它根据样本的输入输出对加权法进行自我调整，从而近似模拟出输入、输出内在隐含的映射关系。
建模时，不必考虑各个因素之间的相互作用及各个因素对输出结果的影响机制，这恰好弥补了人们对各个因素及对输出结果的机制不清楚的缺陷，从而解决众多用以往方法很难解决的问题。
神经网络具有大规模的并行处理和分布式的信息存储，有良好的自适应、自组织性，学习能力很强，有较强的联想功能和容错功能，在解决机理比较复杂、无法用数学模型来刻画的问题，甚至对其机理一无所知的问题等，神经网络方法特别适用，是一种用于预测、评价、分类、模式识别、过程控制等各种数据处理场合的计算方法，其应用已经渗透到多个领域，在计算机视觉、模式识别、智能控制、非线性优化、信号处理、经济和机器人等方面取得了可喜的进展。
数据挖掘中的软计算方法及应用综述1在过去的数十年中,随着计算机软件和硬件的发展,我们产生和收集数据的能力已经迅速提高。
许多领域的大量数据集中或分布的存储在数据库中[1][2],这些领域包括商业、金融投资业、生产制造业、医疗卫生、科学研究,以及全球信息系统的万维网。
数据存储量的增长速度是惊人的。
大量的、未加工的数据很难直接产生效益。
这些数据的真正价值在于从中找出有用的信息以供决策支持。
在许多领域,数据分析都采用传统的手工处理方法。
一些分析软件在统计技术的帮助下可将数据汇总,并生成报表。
随着数据量和多维数据的进一步增加,高达109的数据库和103的多维数据库已越来越普遍。
没有强有力的工具,理解它们已经远远超出了人的能力。
所有这些显示我们需要智能的数据分析工具,从大量的数据中发现有用的知识。
数据挖掘技术应运而生。
数据挖掘就是指从数据库中发现知识的过程。
包括存储和处理数据,选择处理大量数据集的算法、解释结果、使结果可视化。
整个过程中支持人机交互的模式[3]。
数据挖掘从许多交叉学科中得到发展,并有很好的前景。
这些学科包括数据库技术、机器学习、人工智能、模式识别、统计学、模糊推理、专家系统、数据可视化、空间数据分析和高性能计算等。
数据挖掘综合以上领域的理论、算法和方法,已成功应用在超市、金融、银行[4]、生产企业[5]和电信,并有很好的表现。
软计算是能够处理现实环境中一种或多种复杂信息的方法集合。
软计算的指导原则是开发利用那些不精确性、不确定性和部分真实数据的容忍技术,以获得易处理、鲁棒性好、低求解成本和更好地与实际融合的性能。
通常,软计算试图寻找对精确的或不精确表述问题的近似解[6]。
它是创建计算智能系统的有效工具。
软计算包括模糊集、神经网络、遗传算法和粗集理论。
2数据挖掘中的软计算方法目前,已有多种软计算方法被应用于数据挖掘系统中,来处理一些具有挑战性的问题。
软计算方法主要包括模糊逻辑、神经网络、遗传算法和粗糙集等。
遗传算法在信息科学中的应用研究遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和遗传机制的计算方法，是通过模拟自然界的进化过程来不断优化问题的解。
遗传算法的基本思想来自于达尔文的进化论，通过遗传、交叉和变异等操作，逐步优化解空间，最终找到最优解。
在信息科学领域，遗传算法被广泛应用于解决复杂优化问题。
它具有全局搜索能力、并行搜索能力和自适应搜索能力，能够有效地寻找到复杂问题的最优解。
下面就具体介绍一些遗传算法在信息科学中的应用研究。
一、遗传算法在机器学习中的应用机器学习是信息科学中一个重要的领域，目的是让计算机通过学习数据和模式，自动提高性能。
遗传算法可以用来优化神经网络的参数，通过不断迭代调整权重和偏置，使神经网络的性能得到提升。
而且在强化学习中，遗传算法还可以用于优化智能体的策略，实现更高效的决策。
二、遗传算法在数据挖掘中的应用数据挖掘是从大量数据中挖掘出有用信息和模式的过程。
遗传算法可以用来发现数据之间的联系、规律和趋势，从而帮助人们做出更准确的决策。
例如，可以利用遗传算法来优化聚类算法的参数，提高聚类的准确度和效率。
三、遗传算法在图像处理中的应用图像处理是一项重要的信息科学技术，涉及图像数据的获取、分析和处理。
遗传算法可以用来优化图像处理算法的参数，改善图像的质量和清晰度。
例如，在图像压缩领域，可以利用遗传算法来找到最优的压缩方案，使图像在保持清晰度的同时减少存储空间。
四、遗传算法在智能优化中的应用智能优化是利用计算机算法来解决复杂优化问题的方法。
遗传算法作为一种智能优化算法，在解决各种复杂问题上表现出色。
例如，在城市规划中，可以使用遗传算法来优化城市交通网络的设计，提高交通效率和减少拥堵。
五、遗传算法在生物信息学中的应用生物信息学是通过生物学、计算机科学和数学手段来研究生物信息的跨学科领域。
遗传算法可以用来模拟生物进化过程，帮助科学家研究基因组序列、蛋白质结构等生物信息学问题。
遗传算法综述尘本是心摘要：遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度有效的随机搜索算法。
近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注。
本文介绍了遗传算法的基本原理和特点，以及在各个领域的应用情况。
关键词：遗传算法，综述，最优化。
A Review of Genetic AlgorithmsChen BenshixinAbstract:Genetic algorithms are considered as a search used in computing to find exact or a approximate solution for optimization and search problems.This article has a review of the genetic algorithm basic principle and the characteristic and its applications.Keywords:genetic algorithm,review,Optimization0前言在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准最优解。
在计算此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。
因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到最优解的通用搜索算法一直是令人瞩目的课题。
遗传算是这类特别有效的算法之一，它(GeneticAlgorithm,GA)是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机搜索算法。
是由美国Michigan大学的J.Holland教授1975年首先提出，它尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。
如著名的TSP、背包问题、排课问题等1遗传算法基本原理遗传算法是建立在自然选择和群众遗传学机理基础上的，具有广泛适应性的搜索方法。
目录摘要 (1)Abstract(英文摘要) (2)第一章绪论§1.1 引言 (3)§1.2 国内外研究现状 (3)第二章数据挖掘概述§2.1 数据挖掘的发展历史 (5)§2.2 数据挖掘的定义 (5)§2.3 数据挖掘的目的、任务和对象 (6)2.3.1 数据挖掘的目的 (6)2.3.2 数据挖掘的任务 (6)2.3.3 数据挖掘的对象 (7)§2.4 数据挖掘的特点 (8)§2.5 数据挖掘的常用方法 (8)2.5.1 归纳学习方法 (8)2.5.2 公式发现 (9)2.5.3 统计分析方法 (9)2.5.4仿生物技术 (9)2.5.5可视化技术 (10)§2.6 数据挖掘的基本步骤 (10)第三章关联规则基本理论§3.1 关联规则的定义及性质 (12)§3.2 关联规则的挖掘过程 (13)§3.3 衡量规则的价值 (14)第四章遗传算法概述§4.1 遗传算法的发展历史 (15)§4.2 遗传算法的特点 (15)§4.3 基本遗传算法的主要思想及术语 (16)§4.4 基本遗传算法的描述与形式化定义 (17)§4.5 遗传算法的基本实现技术及设计步骤 (17)4.5.1 编码方法的选取 (17)4.5.2 适应度函数的设计 (18)4.5.3 遗传算法的设计步骤 (18)第五章基于遗传算法的关联规则挖掘模型 (19)参考文献 (21)致谢 (22)摘要随着人们对数据库技术逐步深入的研究, 数据挖掘技术应运而生. 最初, 商业活动中的各种数据仅仅是存储在计算机的数据库中, 然而为了人们对数据库管理的需求, 我们开始能够查询并访问计算机的数据库, 从而实现了数据库的即时遍历. 数据挖掘技术甚至将数据库技术推动到了一个更为高级的阶段, 自此这项技术不仅能够查询和遍历过去的数据, 并且能够识别数据之间潜在的联系, 从而对信息的传递起到相当的促进作用. 作为一门典型交叉学科, 数据挖掘具有计算机科学、统计学的学术背景,其为当下数据库系统研究及应用领域的热门研究方向, 吸引了学术界和业界的广泛关注.首先，本文对数据挖掘技术做了概述, 以明确其定义、目的、任务、对象及主要过程、基本方法. 其次, 我们对关联规则的定义、性质及种类等概念作初步介绍. 再次, 重点介绍著名的优化搜索算法——遗传算法, 在回顾遗传算法的发展历史以及主要理论之后, 给出了基本遗传算法和算法描述以及算法的基本实现技术. 基于以上本文提出一种基于遗传算法的关联规则提取方法, 并从编码方法及适应度函数等方面详细讨论. 最后，本文给出遗传算法在关联规则挖掘中的应用模型.关键词：数据挖掘；遗传算法；关联规则；适应度函数AbstractData mining is a result of long-term research on database technology. Initially the data used on the business occasions were only stored incomputer’s database,whose inquiries and visits is later on developed then real-time database inquiries is further on so developed. Data mining pushed database technology to an even more advanced stage. It can not only inquire old data butalso identify the potential relationship between them, thusbenefit the information spreading. As a typical cross-discipline,data mining is a popular area for the current research on database system and its applications,ithas a double academic backgrounds on computer science and statistics, and it hasalsocaught the attentions from industrial fields.Firstly in this paper we give data mining an overview, as well as clarify its definition, purpose, mission andobjects, further we shall talk about the main processand techniques involved in data mining. Secondly weintroduce its definition, nature, typesof the associated rules. Witha huge significance weintroducegenetic algorithm,which is widely applied in data mining practices. We make a briefing on history and main theory of genetic algorithm, then give the basic genetic algorithms and its descriptionsalong with several basic implementation technologies. Last but not least, webring forward a mining method for association rules which is mainly based on genetic algorithms. At the same time, we would like to discussthe genetic algorithms fromthe aspects such as coding method, fitness function andgenetic operators.As the ending of the paper, we give the application model of the association rules mining based on genetic.Key Words: Data Mining;Genetic Algorithm; Fitness Function; Association Rules第一章绪论§1.1引言计算机科学及现代通信技术的迅猛发展已将人类带入了信息时代, 近几十年应由社会与经济发展的需求, 计算机的数据库存储的数据剧增, 人们掌握有大量的数据得以提取所需要的信息, 而这些数据所提供的信息在给人们带来方便的同时也对原有数据库技术提出了新的挑战. 现代社会的信息爆炸程度已远远超出了人们掌握和理解数据的能力, 这为正确地利用数据带来了困难. 人们开始逐渐意识到, 那些能够描述事物整体特征、预测未来发展趋势的信息往往是隐藏在大规模的数据背后更深层次的内容, 这些潜在信息对于人们做出决策具有重要的参考价值.那么如何透过巨量的数据信息获取这些有用的“知识”呢？计算机科学与统计学的最新研究给出回答：数据挖掘. 数据挖掘汇集了数据库、数理统计、人工智能、并行计算、可视化等诸多领域的研究者及业界的工程师,通过对数据库进行从微观到宏观的统计分析与综合推理, 以发现数据之间的相互关联, 乃至利用已有数据对未来进行预测, 从而针对实际问题为人们提供决策支持.§1.2国内外研究现状数据挖掘技术在诸多方面已得到广泛之应用, 但就其目前的研究状况来看, 这一技术还未能称得上成熟, 故在应用上有很大局限. 局限其一, 即挖掘对象之局限, 面对维数更高、各属性之间更为复杂的超大型数据库, 现有数据挖掘技术处理如此巨量数据不免捉襟见肘；局限其二, 大部分数据库在知识发现的过程中可能存在数据或属性丢失的问题；局限其三, 目前数据挖掘工具一般仅能处理特定数值型的结构化数据. 反而思之, 正是由于这些局限的存在, 方才能不断推动数据挖掘技术有着更为长足的发展.遗传算法作为全局并行优化搜索算法的有效性为人称道, 其在解决具有混沌、随机和非线性等典型特性的复杂问题中提供一种新的计算模型, 克服了由大量数据嘈杂无序造成的难题. 这一模拟自然界进化过程的通用全局搜索算法, 有效避免搜索过程中出现的局部最优, 有望在规则发掘中大施拳脚. 遗传算法自诞生至今虽已经过历次改进, 但仍有待进一步深入研究的必要. 其一, 算法的理论研究相对滞后, 遗传算法提出之灵感源于一种仿生的思想, 故其尽管在实践中被证明极为有用, 然而在理论证明上却遇到瓶颈；其二, 算法的参数设置仍无明确标准, 之前的应用中采用的均为过往的经验数值, 而不同编码与遗传技术将对遗传参数的选取产生影响, 这无疑制约了算法的通用性；其三, 算法对于约束化问题的处理缺乏足够的有效性.近年对关联规则挖掘的研究主要可分为四个方面. 一是改进由R. A g rawal等提出的Apriori算法, 这些工作主要集中在有效地生成最大项目集并改善该算法效率；二是对关联规则的阈值进行调整, 增强所挖掘规则的关联性与有效性使之更为符合人们的需求；三是提出用于关联规则发掘的并行算法；四是扩展关联规则发掘中的二级问题, 诸如多层/广义关联规则、循环关联规则、定量关联规则等.因遗传算法简单通用且适于并行处理之特性, 使其在数据挖掘技术占用举足轻重的地位. 目前, 对以遗传算法为基础的数据挖掘研究主要在分类系统方面, 而在关联规则提取方面的应用仍未常见. 本文提出用遗传算法辅助对关联规则进行挖掘, 便是希望能在这方面进行新的尝试.第二章数据挖掘概述§2.1数据挖掘的发展历史1989年8月, 于底特律召开的第十一届国际人工智能联合会议的专题讨论中首次提出KDD(Knowledge Discovery in Database)这一术语. 随后, 首届知识发现和数据挖掘国际学术会议于1995年在加拿大蒙特利尔召开. 亚太地区则于1997年在新加坡召开了第一届亚太知识发现和数据挖掘国际会议, 欧洲也于1998年召开了第一届欧洲知识发现和数据挖掘学术会议.知识发现和数据挖掘长期作为数据库和机器学习的分支, 直到1998年6月ACM(AssociationofComputingMachinery)成立SIGKDD(SpecialInternetGrouponKnowledgeDiscoveryandDataMining), 才使其正式脱身为一门独立学科.METAGroup有评论如下, “全球重要的企业及各类组织将会发现, 在二十一世纪, 数据挖掘技术将在决定其在商业经营中成功与否产生至关重要的影响”. IBM在之后几年随即发布IBMDB2智能挖掘器积分服务, 这一服务基于标准的数据挖掘技术, 提供个性化解决方案. 统计软件SPSS与SAS亦分别推出数据挖掘工具Clementine和EnterpriseMiner.§2.2数据挖掘的定义数据挖掘, 即从大量不完全并且模糊有噪声的随机数据中提取隐含其中事先未知却潜在有用的信息和知识的过程. 这一表述具有若干层次含义, 其一, 数据挖掘中原始数据真实、大量且含噪声；其二, 数据挖掘专注于发现人们感兴趣、有价值的知识；其三, 数据挖掘着力于发现直觉无法发现乃至有悖直觉的知识, 其越是出人意料, 便可能越有价值；其四, 潜在有用性是指数据挖掘发现的知识对于所讨论的业务或研究领域具有实用价值, 诸如常识性的结论、已掌握的事实及无法实现的推论均视作无意义；其五, 数据挖掘发现的知识须可为人们所接受、理解并运用于解决实际问题；其六, 数据挖掘并非要发现那些放之四海皆准的真理抑或全新的自然科学定理, 所有被发现的知识都具有特定约束条件或面向特定领域.目前来说, 学术界对数据挖掘仍未形成统一的精确定义, 在不同的文献中, 不同的应用领域里有着不同侧重的定义表述. 常见的如Ferruzza定义数据挖掘为于知识发现过程用以辨识存在数据间未知关系和模式的方法；Zekulin定义数据挖掘为从大型数据库中提取未知的、可理解的、可执行的信息并利用其辅助商业决策的过程；Parsaye 则认为数据挖掘是为获取未知的信息模式而研究大型数据集合的决策支持过程.§2.3数据挖掘的目的、任务和对象2.3.1数据挖掘的目的随着数据库及信息系统技术逐步深入的应用, 面对长时间积累所形成的海量数据人们常无所适从, 以至淹没在数据的海洋中却缺少“知识”. 我们开始考虑尝试发现数据中存在的关系和规则并根据已有数据预测未来发展趋势, 从而做到不被信息淹没, 提高信息利用率. 现在, 数据挖掘分析海量数据并发现其中的潜在联系.2.3.2数据挖掘的任务数据挖掘有关联分析、时间序列模式、聚类、分类、偏差检测及预测六项基本任务.我们先讨论关联分析. 当若干数据项取值出现重复, 这之间即有某种关联, 从而可建立关联规则. 我们常用“可信度”与“支持度”对其进行筛选.时间序列模式即根据时间序列搜索重复发生概率较高的模式. 我们需要在时序模式中找出在某个最小时间段内出现概率高于阈值的规则, 当然, 随着形式的变化我们将对规则做出适当的调整.聚类, 即根据意义之不同对数据库中的数据划分一系列子集, 即类. 人们通过聚类以建立宏观概念,统计分析、机器学习和神经网络均是常见方法.分类作为数据挖掘中应用最多的任务, 描述一个类别的概念以代表这类数据的整体信息, 称为其内涵描述, 一般用规则或决策树表示. 分类可将数据库中元组影射到给定类别的某一个中. 分类通常是基于训练样本集（已知数据库元组及类别所组成的样本）通过相关算法求得.然后是偏差检测. 数据库中数据往往存在诸多异常, 偏差检测便是寻找观察结果与参照之间的差别. 观察结果一般为一个或多个域的值的汇总, 参照则通常是给定模型的预测结果、外界提供的标准或另一个观察结果.最后我们讨论预测. 预测, 顾名思义, 从历史数据中寻找变化规律以建立模型, 并基于此预测未来. 主流的预测方法有回归分析和神经网络, 回归分析用于预测连续数值, 而神经网络预测则连续、离散皆适用.2.3.3数据挖掘的对象理论上, 在任何类型的数据存储上均可进行数据挖掘, 包括关系数据库、事务数据库、数据仓库等. 这里我们对主要的数据挖掘对象予以介绍.首先是关系数据库. 关系数据库是表的集合, 每个表命名唯一, 其中包含一组属性用于存放大量元组. 关系中每一元组代表一个被唯一关键字标识的对象, 并由一组属性值所描述. 关系数据库可通过数据库的结构化查询语言访问. 关系数据库拥有完备的数学理论基础且具有相当高的普及度, 是当下数据挖掘最为丰富的数据源之一.其次, 我们讨论事务数据库. 一般地, 事务数据库由一个文件组成, 每一个事物由其中一个记录所代表. 通常, 一个事务有唯一的事务标识号和一个组成项列表（部分包含事务的处理时间）. 事务数据库常应用于“购物篮数据分析”, 其对关联规则的数据挖掘十分有效.再次, 我们介绍数据仓库. 数据仓库的创始人WilliamH.Inmon对数据仓库定义如下：数据仓库是面向主题的(Subject-Oriented)、集成的(Integrated)、随时间而变化的(Time-Variant)、稳定的(Non-V olatile)数据集合. 从辨证的角度来看, 从关系数据模型到数据仓库的诞生, 数据仓库的出现与广泛为人们所接受实质上是数据管理螺旋式的上升.数据仓库技术的逐步成熟很大程度上推动了数据挖掘技术的繁荣.近年来, 数据库技术发生了翻天覆地的变化, 其已由最初单一的关系数据库逐步发展为面向对象数据库、事物数据库、空间数据库、对象-关系数据库、多媒体数据库等新的数据库系统, 与此同时, 数据挖掘的数据来源也更多地取自于新型的高级数据库系统.§2.4数据挖掘的特点数据挖掘的特点可初步归纳为五个方面. 其一, 数据挖掘所处理的数据规模十分庞大；其二, 数据库查询一般是即时的随机查询, 因不能有精确查询要求, 数据挖掘技术则可辅助寻找用户感兴趣的知识；其三, 在一些应用中数据在很短时间内即有较大变化, 数据挖掘技术能够在这种情况下快速反应以提供决策支持；其四, 数据挖掘不仅要发现潜在规则, 而且要管理、维护规则, 规则往往不是一成不变的, 随着数据的不断更新, 规则亦需随之而变；其五, 数据挖掘是基于大样本统计规律发现规则, 这未必适用于全部数据, 当达到某一阈值时即可认为此规则成立.§2.5数据挖掘的常用方法2.5.1归纳学习方法归纳学习方法从技术上分为两类：信息论方法与集合论方法.我们先讨论前者. 信息论方法主要基于信息论原理建立决策树, 由于最终将以决策树的形式表示知识, 故文献中经常称其为决策树方法. 这里我们介绍两种较有特色的信息论方法. 一是ID3等系列方法, 其利用信息增益寻找包含最大信息量的字段以建立树的结点, 由不同字段取值建立分枝, 再对数据子集重复以上过程, 最终建立决策树. 对愈为庞大的数据库, 这一方法愈为有效；还有一种方法我们称为IBLE(Information-BasedLearningfromExamples)方法, 其根据信息量大小寻找各字段取值建立树的结点, 并将结点中指定字段值的权值和与阈值比较, 建立三个分枝, 再对各分枝子集重复以上过程, 最终建立决策树.再说集合论方法.这类方法广为人知的有覆盖正例排斥反例的方法、概念树方法和粗糙集(RoughSet)方法.概念树方法则是将数据库中的属性字段根据归类方式进行合并, 以此建立的层次结构称为概念树；最后介绍粗糙集方法, 我们将数据库中的行元素看作对象, 列元素看作属性（分为条件属性与决策属性）. 定义等价关系R为不同对象某一个或多个属性具有相同取值, 称满足同一等价关系的对象所组成的集合为该等价关系的等价类. 条件属性上等价类E与决策属性上等价类Y之间有三种关系, 分别是下近似(Y包含E)、上近似(Y和E的交非空)和无关(Y和E的交为空). 我们对下近似建立确定性规则, 对上近似建立不确定性规则, 而无关情况下则不存在规则.2.5.2公式发现公式发现的含义即是对工程或科学数据库中的若干数据项进行数学运算并求相应的数学公式. 这里举两个典型的例子. 一是经验公式发现系统FDD, 其基本思想是对两个数据项交替取初等函数后再与另一数据项进行线性组合, 若组合结果为直线, 就得到由数据项的初等函数表示的线性组合公式；二是物理定律发现系统BACON, 其基本思想很简单, 就是对数据项进行初等数学运算以形成组合数据项, 若值为常数, 就得到组合数据项等于常数的公式.2.5.3统计分析方法统计分析利用统计学原理分析数据库中数据从而得到其中的统计信息与知识, 已发展成一门独立的学科. 下面简要介绍六种统计分析中的基本方法. 一是常用统计, 即求最简单的统计量；二是相关分析, 即计算变量间的相关系数；三是回归分析, 即以回归方程表示变量间数量关系；四是差异分析, 即从样本统计量的出发进行假设检验；五是聚类分析, 即直接计算样本数据间的距离, 将距离小于某一阈值的归为一类；六是判别分析, 即确立一个判别标准以建立一个或多个判别函数, 据此将未知对象划归到某一类别.2.5.4仿生物技术典型的仿生物技术方法有遗传算法和神经网络方法.我们先讨论遗传算法. 遗传算法的基本思路是模拟生物进化过程, 有选择、交叉和变异三个基本遗传算子. 选择算子描述从旧种群选择出具有更强竞争力的个体产生新种群的过程；交叉算子描述两个不同个体（染色体）的部分（基因序列）进行交换并产生新个体的过程；变异算子描述个体的某些基因进行变异（1变0, 0变1）的现象. 在优化计算和分类机器学习方面遗传算法已广泛应用并证实了其显著的效果. 后文将对遗传算法做进一步介绍.再讨论神经网络方法. 神经网络方法基于MP模型与Hebb学习规则, 模拟人脑神经元结构建立三类多种神经网络模型. 一是前馈式网络, 其代表为感知机、BP反向传播模型及函数型网络. 此类网络在预测和模式识别方面有广泛应用；二是反馈式网络, 其代表是Hopfield的连续及离散模型, 分别应用于优化计算和联想记忆；三是自组织网络, 其代表为Kohonen模型和ART模型, 常用于聚类.2.5.5可视化技术可视化技术, 顾名思义, 是一种图形显示技术. 以图形显示多维数据, 可深刻揭示数据的分布规律及内在本质. 同样, 对数据挖掘过程进行可视化与人机交互可显著提高挖掘效果. D.A.Keim定义数据挖掘可视化为寻找并分析数据库以找到隐藏的有用信息的过程. 常见的可视化方法有三种, 一是提取几何图元, 在构造、仿真和分析数据分布模型上极为有效；二是绘制, 主要基于计算机图形学近年的发展成果来进行图像生成、消隐、光照效应及部件绘制；三是显示和演放, 为取得更佳显示效果, 图片组合、文件标准、着色、旋转、放大和存储等诸多功能在这一部件中均有提供.§2.6数据挖掘的基本步骤以下我们将以顺序方式列出数据挖掘的各步骤, 但数据挖掘过程并不是线性的, 需不断重复以下步骤以得到最优的结果.步骤一：确定业务对象. 首先, 对业务问题要有清晰的定义, 数据挖掘的第一步也是最为重要的一步即是认清数据挖掘的目的；步骤二：数据准备.包含数据选择、预处理与转换；步骤三：数据挖掘. 挖掘已经过转换之数据, 只需选择适当的挖掘算法, 剩下的工作可交由计算机自动完成.步骤四：结果分析. 即解释并评估结果, 用到的分析方法由数据挖掘的具体操作决定, 可视化技术通常会被应用于此.步骤五：知识的同化. 即在业务信息系统的组织结构中集成数据挖掘所得知识.第三章关联规则基本理论§3.1关联规则的定义及性质定义3.1 设{}12=, , , m I i i i 为m 个不同项目之集合, D 为事务数据库, 其中每一事务T 为一项目子集, 即T I ⊆. 称事务T 包含项目集X , 表示为XT ⊆. 关联规则为形如X Y ⇒的逻辑蕴含式, 其中X T ⊂, Y T ⊂且X Y ⋂=∅. X 称作前提, Y称作结果.定义3.2 若事务数据库中有%s 的事务包含XY ⋃, 则称规则X Y ⇒的支持度为s ；若事务数据库中包含X 的事务中有%c 也包含Y , 则称规则X Y ⇒的置信度为c .可信度表示的是一条规则可信赖的程度. 我们发现关联规则是为了找到可信赖且具有代表性的规则, 因而我们需要事先对支持度和可信度分别给定最小阈值, 所谓发现关联规则, 即是发现可信度与支持度均高于阈值的规则.性质4.1 若关联规则XZ ⇒与Y Z ⇒在D 中均成立, 规则X Y Z ⋃⇒不一定在D 中成立.性质4.2 若X Y ⋂=∅, 且D 中支持Z 的都只支持X 或Y , 则X Y Z ⋃⋃的支持度为零, 故规则XY Z ⋃⇒的可信度为零. 性质4.1-2描述了关联规则的非结合性, 因其据定义显然, 故此不复证之. 类似地, 若X Y ⇒与X Z ⇒成立, XY Z ⇒⋃不一定成立. 性质4.3 若XY Z ⋃⇒在D 中成立, X Z ⇒与Y Z ⇒不一定在D 中成立. 证 由su p p ()su p p ()X Y X Y Z ⋃≥⋃⋃与su p p ()su p p ()X Z X Y Z ⋃≥⋃⋃, 若X Y Z ⇒⋃成立, 则X Y ⇒与X Z ⇒均成立, 矛盾, 故得证.性质4.3描述的是关联规则的不可分解性.性质4.4 由XY ⇒及Y Z ⇒不能推出X Z ⇒. 证 设()()()T X T Y T Z ⊂⊂最小可信度为m in co n f , 即()()m in co n f X Y co n f Y Z co n f ⇒=⇒=由()()T X T Y ⊂, ()()/()()/()m in co n f X Y S X Y S Y S X S Y co n f⇒=⋃==由()()T Y T Z ⊂, ()()/()()/()m in co n f Y Z S Y Z S Z S Y S Z co n f ⇒=⋃== 由()()T XT Z ⊂, ()()/()()/()co n f X Y S X Z S Z S X S Z ⇒=⋃=, 又m in co n f 1<, 故2m in m in c o n f X Z c o n f c o n f ⇒=<（）, 故规则X Z ⇒不成立.证毕.性质4.4描述的是关联规则的不可传递性.性质4.5 设项目集, , L A B 满足BA L ⊆⊂, 若()A L A ⇒-不满足最小可信度条件, 则()B L B ⇒-也不满足最小可信度条件.证 由子集支持性质, 设A 和B 是两个不同的项目集, 若A B ⊆, 则su p p ()su p p ()A B ≥. 又因D 中支持B 的交易一定支持A , 故su p p ()su p p ()B A ≥, 再由可信度定义有(())su p p ()/su p p ()su p p ()/su p p ()m in co n f B L B L B L A co n f -=≤<,同理, 对满足, D C L D ⊆⊂=∅的项目集, , L D C , 若()L C C -⇒成立, 则()L D D -⇒亦成立.性质4.5描述的是关联规则的可扩展性, 当项目集及支持度已确定, 可用这一性质加速规则发现的过程.§3.2关联规则的挖掘过程关联规则的挖掘一般有两个过程, 一是找出所有频繁项集,二是由频繁项集产生关联规则, 这些规则须满足可信度和支持度条件.第二个过程须在前一个的基础上进行, 工作量较小, 而过程一则决定了关联规则挖掘总体性能. 关联规则的可信度较之期望要高方才表明A 的出现对B 的出现产生促进作用, 即表明其之间在某种程度上相关. 对于给定交易集, 挖掘关联规则便是发现可信度与支持度均大于预先给定阈值的关联规则.§3.3衡量规则的价值在用数据挖掘方法发现了一些关联规则后, 系统如何得知哪些规则对于用户来说是有价值的？对这个问题常分为两个层面来考虑, 即系统客观层面与用户主观层面.我们先讨论系统客观层面. 首先, 我们需明确一点：使用前文所述的“支持度和信任度”框架可能发掘出“不正确”的规则, 即若我们人为地将阈值设置得过低, 则可能得到互相矛盾的规则, 而反之,若阈值被设置得过高, 则所得到的规则又可能不合实际. 因此只依靠可信度与支持度的阈值设定不一定能得出我们需要的规则. 于是, “兴趣度”这一概念被引入用来筛掉我们不感兴趣的规则. 在统计独立性假设下, 定义一条规则的兴趣度为真实强度与期望强度之比值.再是用户主观层面的考虑, 之前的讨论仅仅是基于系统方面, 但规则的价值判定最终仍应取决于用户, 因为有能力分辨所挖掘规则有效性与可行性的只有用户. 这里我们提出可以采用一种基于约束(Constraint-Based)的挖掘方式, 包括数据约束、维度/层次的约束乃至规则约束, 这其中的约束条件能够和算法紧密结合, 从而可以做到既提高效率, 又更加明确挖掘的目的.第四章遗传算法概述。
数据挖掘算法之遗传算法遗传算法（GA，Genertic Algorithm）是一种基于生物进化过程中自然选择与遗传机制的模拟算法，它广泛应用于机器学习、模式识别、控制系统优化及数据挖掘等领域中，在数据挖掘中它不公可以用于聚类分析，也可用于分类分析。
遗传算法的基本流程如下图：遗传编码由问题空间向GA编码空间的映射称为编码，反之则称为解码。
遗传编码是遗传算法的基础，一般要体现两个原则：✓编码方案应与问题本身相关性大，而与其它编码方案相关性小✓编码方案应采用最小字符集，以使问题得到自然、简单的表示和描述二进制编码是最基础的编码方式，应用范围非常广泛，其它编码方式有大字符集编码、序列编码、实数编码、树编码、自适应编码、乱序编码等。
适应值函数（评价函数）是评估染色体的主要工具，其设置分为三个步骤：1.确定目标函数：遗传算法中有一个求解问题的目标，而这个目标可以用一个函数来表示，这个函数就叫目标函数。
目标函数应预先设定。
2.从目标函数到适应值函数的转换：由于目标函数的值范围不定，而适应值函数的值一般是非负数为主，以表示染色体的适应程度，因此需要建立一个由目标函数到适应值函数间的转换。
3.适应值调整：适应值函数计算出来的适应值需作适当调整，使其控制在一定数值区间内，以避免不同染色体间的适应值差距过大而引起的不一致性。
遗传算子遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。
1.选择：按照某种策略从父代种群中选择一些染色体（不作任何改动）进入下一代种群，常用的选择算法有适应值比例选择、Boltzmann选择、排序选择、联赛选择、精英选择、稳态选择等。
2.交叉：随机从种群中抽取两个染色体，根据染色体位串长度L，随机选取[1, L-1]中的一个或多个的整数k作为交叉位置，然后根据交叉概率p c，实施交叉操作，即两个染色体在交叉位置处，相互交换各自的部分内容，从而形成新的一对染色体。
遗传算法综述遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。
进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
在阅读了一些相关资料后，我整理出这篇综述，将通过五个部分来介绍遗传算法以及其在计算机科学领域的相关应用、一、起源和发展分支尝试性地将生物进化过程在计算机中模拟并用于优化问题求解开始于20世纪50年代末，其目的是将生物进化的思想引入许多工程问题中而成为一种优化工具，这些开拓性的研究工作形成了遗传算法的雏形。
但当时的研究进展缓慢，收效甚微。
原因是由于缺少一种通用的编码方式，人们只有通过变异才能改变基因结构，而无法使用交叉，因而增加了迭代次数。
同时算法本身需要较大的计算量，当时的计算机速度便无法满足要求，因而限制了这一仿生过程技术的迅速发展。
20世纪60年代中期，Holland在Fraser和Bremermann等人研究成果的基础上提出了位串编码技术，这种编码技术同时适用于变异操作和交叉操作。
遗传算法的真正产生源于20世纪60年代末到70年代初，美国Michigan大学的Holland教授在设计人工适应系统中开创性地使用了一种基于自然演化原理的搜索机制，并于1975年出版了著名的专著“Adaptation in Natural andArtificial Systems”，这些有关遗传算法的基础理论为遗传算法的发展和完善奠定了的基础。
同时，Holland教授的学生De Jong首次将遗传算法应用于函数优化中，设计了遗传算法执行策略和性能评价指标，他挑选的5个专门用于遗传算法数值实验的函数至今仍被频繁使用，而他提出的在线(on-line)和离线(off-line)指标则仍是目前衡量遗传算法优化性能的主要手段。
在Holland教授和他的学生与同事De Jong进行大量有关遗传算法的开创性工作的同时，德国柏林工业大学的Rechenberg和Schwefel等在进行风洞实验时，为了对描述物体形状的参数进行优化以获得更好的实验数据，将变异操作引入计算模型中，获得了意外的优良效果。
基于遗传算法的数据挖掘综述朱玲(江西理工大学信息工程学院，赣州市中国 341000)摘要：本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。
关键词：数据挖掘;遗传算法Data Mining Based on Genetic AlgorithmZhu Ling(College of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, China 341000) Abstract:This paper defines the concept of genetic algorithm and the source of the theory, introduces the research direction and application field of genetic algorithm, explains the related concepts, coding rules, three main operators and fitness functions of genetic algorithm, describes the genetic algorithm calculation process and Parameter selection criteria, and in the given genetic algorithm based on the combination of practical applications to be explained.Key words: data mining; genetic algorithm前言遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。
遗传算法于20世界六七十年代由John Holland[1] 发展而成。
它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。
在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。
在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。
遗传算法借助了大量的基因术语。
遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。
生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。
受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。
通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。
现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。
[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。
例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。
遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。
1.遗传算法的应用领域和研究方向1.1遗传算法的特点遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结构对象的优化过程中显示出比传统优化方法更为独特的优势和良好的性能。
它利用其生物进化和遗传的思想，所以它有许多传统算法不具有的特点[3]：※搜索过程不直接作用在变量上，而是作用于由参数集进行了编码的个体上。
此编码操作使遗传算法可以直接对结构对象进行操作。
※搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，易于并行化。
※采用概率的变迁规则来指导搜索方向，不采用确定性搜索规则。
※对搜索空间没有任何的特殊要求，只利用适应度信息，不需要其它辅助信息，适应范围广。
※对于给定的问题，可以产生许多的潜在解，最总选择可以由使用者确定。
遗传算法的优越性只要表现在：首先他在搜索过程中不容易陷入局部最优，即使在定义的适应值函数是不连续的、非规则的或是有噪声的情况下，它也能以很大的概率找到整体最优解；其次由于它固定的并行性，遗传算法非常适合于大规模的并行计算机。
※遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，广泛适用于很多科学。
1.2遗传算法的应用领域1．函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评估的常用算例。
很多人构造出的各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有但峰值函数也有多峰值函数等。
用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。
而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法比较难求解，而遗传算法却是可以方便的得到较好的结果。
2．组合优化随着问题规模增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或不可能求解精确最优解。
对这类复杂问题，人们已经意识到应把主要精力放在求其满意解上，而遗传算法是寻求这种满意解定的最佳工具之一。
实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP难度的问题得到成功应用。
3．自动控制在自动控制领域中有很多优化相关的问题需要求解，遗传算法已在其中得到初步的应用，并显示出良好的效果。
例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交回控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习，都显示出遗传算法在这些领域的应用可行性。
4．图像处理图像处理是计算机视觉中的一个重要研究领域。
在图像处理过程中，如扫描、特征提取、图像分割等不可避免的存在一些误差，从而会影响图像的效果。
如何使这些误差最小是使计算机视觉达到实用化的重要要求。
遗传算法在这些图像处理中优化计算方面找用武之地。
目前已在模式识别、图像恢复、图像边缘特征提取等方面取得了应用。
5．数据挖掘数据挖掘是近几年出现的数据库技术，它能够从大型的数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。
许多数据挖掘问题可视为搜索问题，数据库视为搜索空间，挖掘算法视为搜索策略。
因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。
遗传算法已经成为数据挖掘的重要有效方法之一。
6．复杂性科学在复杂性问题的研究中，遗传算法也崭露头角。
什么叫复杂性问题，各家看法不一。
共同认识还是有的，即是复杂性问题应用是多层次、多因素、其相互作用是非线性、不确定和不稳定的，这样的学习问题自然属复杂性研究的范畴。
事实上，在复杂系统例如适应性系统学习策略的研究中，遗传算法占有重要位置。
由于介质参数的模型非常大，同时观测数据不完备、噪音的存在、源的情况复杂未知。
很难用传统的方法求得目标函数的全局最优值，而只能求一定意义下的“满意解”。
这时，可供选择的方法之一自然是遗传算法。
1.3遗传算法的研究方向遗传算法是多学科结合与渗透的产物，已经发展成为一种自组织、自适应的综合技术，广泛应用在计算机科学、工程技术和社会学领域。
[4]遗传算法的基础理论、数学模型主要集中在对于算法的收敛性、复杂性、收敛速度的研究上。
遗传算法在操作上突出特点是具有高度的并行性。
还有在与神经网络方向相结合，成功的用于从时间序列分析来进行财政预算。
开发遗传算法的的商业软件、开拓更广泛的遗传算法应用领域也是今后的主要任务。
遗传算法是21世纪有关智能计算术中的关键之一。
是十分活跃的研究领域，正在从理论深度、技术的多样化以及应用的广度不断探索。
2.遗传算法的编码规则编码机制是GA（遗传算法）的基础，编码是遗传算法主要解决的首要问题。
GA不是对研究对象直接进行讨论，而是通过某种编码机制把对象统一赋予有特定符号按一定顺序排成的串。
将问题的解转换成基因序列的过程称为编码。
反之，将基因转换成问题的解的过程成为解码。
对GA的码可以有十分广泛的的理解。
在优化问题方面，一个串对应于一个可能解；在分类问题的方面，串可以解释为一个规则。
即串的前半部为输入或前件，后半部分为输出或后件、结论等。
对于任何应用遗传算法解决实际问题，都要必须将解的表达方法和相关问题领域的特点结合起来分析考虑。
图一：编码空间与解空间从图一中可见，遗传算法的一个显著特点是它交替地在编码空间和解码空间中工作，它在编码空间对染色体进行遗传运算，而在解空间对解进行评估和选择。
自然选择联结了染色体和它所表达的解的性能当用遗传算法算法解问题，必须在问题空间对遗传算法的个体基因结构之间建立联系，即确定编码和解码方案。
一般来说，由于遗传算法计算过程的鲁棒性，他对编码的要求并不苛刻，但是编码的策略对于遗传算子，尤其是对交叉和变异算子的功能和设计有很大影响。
评估编码机制的一般采用一下三种规范：（1）完备性：问题空间中的所有点都能作为GA 空间中的点表现；（2）健全性：GA空间中的染色体能对应所有问题空间中的候选解；（3）非冗余性：染色体和候选解一一对应。
2.1几种常见的编码机制1.二进制编码二进制编码采用得到了Holland早期理论结果的支持，它是遗传算法中最常用的一种编码方法。
优点为（1）编码、解码操作简单易行；（2）交叉、变异操作便于实现；（3）符合最小字节符集编码原则；（4）便于利用模式定理对算法进行理论分析。
2.格雷码编码对于一些连续优化问题，二进制编码由于遗传算法的随机特性而使其局部搜索功能力较差。
为改进这一特点，人们提出了格雷码。
它的方法是二进制编码方法的一种变形。
它是这样的一种编码方法，其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的，其余位都是完全相同。
3．实数编码对于一些多维、高精度要求1的连续函数优化问题，使用二进制编码来表示个体将会带来一些不利。
例如，二进制编码存在着连续函数离散化的映射误差，同时不便于反映所求问题的特定知识。
为了克服这些缺点，人们提出了实数编码方法，即个体的每个基因值用实数表示。
3.遗传算法的主要算子遗传算子最重要的算子有三种：选择、交叉、变异。
选择体现“适者生存”原理，通过适应值选择优质个体而抛弃劣质个体。
