数据挖掘之遗传算法
- 格式：doc
- 大小：22.50 KB
- 文档页数：5
华 北 水 利 水 电 大学
研 究 生 结 课 论 文
姓 名 童艳梅
学 号 201220959406
专 业 计算机技术
性 质 国家统招（√）单 考（
）
工程硕士（ ）同等学力（ ）
科 目 数据挖掘
任课老师 刘扬
成 绩
遗传算法
摘要：遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。
关键字：遗传算法；基因遗传；神经网络
一、遗传算法的基本概念
遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。
Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。
Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
二、遗传算法的原理
遗传算法GA （Genetic Algorithm）把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
长度为L的n个二进制串bi(i＝1，2，„，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。 2．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
3．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
三、遗传算法的特点
1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。
这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。
2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。
3．遗传算法有极强的容错能力
遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。
4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。
这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。
5．遗传算法具有隐含的并行性
遗传算法的基础理论是图式定理。它的有关内容如下：
(1)图式(Schema)概念
一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1xx
0 x x是一个图式。
(2)图式的阶和长度
图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。
(3)Holland图式定理 低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。
遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。
四、遗传算法的应用
遗传算法在很多领域都得到应用；在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。
1．遗传算法在网络学习中的应用
在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用
(1)学习规则的优化
用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。
(2)网络权系数的优化
用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。
2．遗传算法在网络设计中的应用
用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：
(1)直接编码法
这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。
(2)参数化编码法
参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。
(3)繁衍生长法
这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。
3．遗传算法在网络分析中的应用 遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
参考文献：
[1] 李嶶，李宛州.基于数据仓库技术的进销存系统的设计与实现.2001(10)：93-94
[2]Jiawei Han.数据挖掘概念与技术.机械工业出版社2001，8
[3]W.H.Inmon.数据仓库.机械工业出版社2000，5
[4]林字等编著.数据仓库原理与实践.人民邮电出版社，2003
[5]张春阳，周继恩，刘贵全，蔡庆生.基于数据仓库的决策支持系统的构建，计算机工程.2002(4)：249-252
