9.1 符号学习 9.2 神经网络学习 9.3 知识发现与数据挖掘 9.4 遗传算法 第9章 机器学习 9.1 符号学习 9.2 神经网络学习 9.3 知识发现与数据挖掘 9.4 遗传算法

9.1 符号学习 首先，我们指出，机器学习（这里指符号学习）是靠学习程序（或称为学习系统）实现的。学习程序的输入是数据、事实等各种各样的信息，输出则是知识，即概念、规则（规律）等。而且所学到的知识一般要存入知识库。

符号学习又可以分为不同的类型。通常是按学习策略、知识表示和应用领域等进行分类的。学习策略是学习中使用的推理方法。学习策略是按照学习程序对提供的信息所做的推理数量的多少来区分的。一种极端情况是没有任何推理功能，要增加系统知识时就得靠外界环境作大量的输入新知识的工作；另一种极端情况则是学习程序有相当数量的推理，可以根据试验和观察，推导出有组织的知识，这样系统就可能独立地发现新理论或发明新概念。介于这两者之间就是学习程序有一定的推理能力，能适应减轻外界环境负担的各种折衷情况。

遗传算法（Genetic Algorithm）是一种优化算法，它模拟了生物繁衍的遗传、变异和生物进化的自然选择过程。分类器系统是一种依靠信息传递的高度并行的规则库系统，它通过信任分配和规则发现进行学习。分类器系统运用遗传算法，把每一物种的个体对应于一个概念描述的变形，通过一个目标函数来确定哪些概念及其变化可保留在基因库中。

9.1.1 记忆学习 记忆学习也称死记硬背学习或机械学习。这种学习方法不要求系统具有对复杂问题求解的能力，也就是没有推理技能，系统的学习方法就是直接记录问题有关的信息，然后检索并利用这些存储的信息来解决问题。

机械学习是基于记忆和检索的办法，学习方法很简单，但学习系统需要几种能力。   (1) 能实现有组织的存储信息。 (2) 能进行信息综合。 (3) 能控制检索方向。

9.1.2 传授学习 传授学习即通过对计算机指点教授的学习方法。具体来讲就是通过人机对话，把用户一般性意见或建议具体化，或者协助用户补充和修改原有的知识库。例如FOO程序(1981年开发)是玩扑克牌的一种游戏，称为“红心牌游戏”，可以告诉系统游戏的规则以及若干取胜的建议，如“避免取点”，“如果某个对手已无某种花色的牌，则不要先出该花色的大牌”，“如某个对手有黑桃Q，就设法把它攻出来”等等。

9.1.3 演绎学习 演绎学习是基于演绎推理的一种学习。演绎推理是一种保真变换，即若前提真则推出的结论也为真。在演绎学习中，学习系统由给定的知识进行演绎的保真推理，并存储有用的结论。例如，当系统能证明A→B且B→C，则可得到规则A→C，那么以后再要求证C，就不必再通过规则A→B和B→C去证明，而直接应用规则A→C即可。演绎学习包括知识改造、知识编译、产生宏操作、保持等价的操作和其他保真变换。演绎学习近几年才作为独立的学习策略。

9.1.4 类比学习 这是基于类比推理的一种学习方法。例如，学生在做练习时，往往在例题和习题之间进行对比，企图发现相似之处，然后利用这种相似关系解决习题中的问题。类比学习就是寻找和利用事物间的可类比的关系，从已有的知识推导出未知的知识。类比学习的过程包括以下主要步骤： (1)回忆与联想 即当遇到新情况或新问题时，先通过回忆与联想，找出与之相似的已经解决了的有关问题，以获得有关知识；

(2)建立对应关系 即建立相似问题知识和求解问题之间的对应关系，以获得求解问题的知识； (3)验证与归纳 即检验所获知识的有效性，如发现有错，就重复上述步骤进行修正，直到获得正确的知识。

9.1.5 示例学习 示例学习也称实例学习，它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。 Winston的程序是在简单的积木世界领域中运行，其目的是要建立积木世界中物体概念定义的结构化表示，例如学习房子、帐篷和拱的概念，构造出这些概念定义的结构化描述。

系统的输入是积木世界某物体（或景象）的线条图，使用语义网络来表示该物体结构化的描述。例如系统要学习拱桥概念，就给学习程序输入第一个拱桥示例，得到的描述如图9―1所示，这个结构化的描述就是拱桥概念的定义。接着再向程序输入第二个拱桥示例，其描述如图9―2所示。这时学习程序可归纳出如图9―3所示的描述。

图9―1 第一个拱桥的语义网络

图9―2 第二个拱桥的语义网络

假定下一步向程序输入一个拱桥概念的近似样品，并告知程序这不是拱桥(即拱桥的反例)，则比较程序会发现当前的定义描述（图9―3）与近似样品的描述只是在B和D节点之间，“不接触”的链接弧有区别。由于近似样品不是拱桥，不是推广当前定义描述去概括它，而是要限制该定义描述适用的范围，因而就要把“不接触”链修改为“必须不接触”，这时拱桥概念的描述如图9―4所示。这就是机器最后学到的拱桥概念。

图9―3 学习程序归纳出的语义网络

图9―4 拱桥概念的语义网络

例9.1 假设示例空间中有桥牌中“同花”概念的两个示例： 示例1：花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)→同花(c1，c2，c3，c4) 示例2：花色(c1，红桃)∧花色(c2，红桃)∧花色(c3，红桃)∧花色(c4，红桃)→同花(c1，c2，c3，c4) 花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)→同花(c1，c2，c3，c4)

例9.2 假设示例空间存放有如下的三个示例： 示例1：(0，2，7) 示例2：(6，-1，10) 示例3：(-1，-5，-10) 这是三个3维向量，表示空间中的三个点。现要求求出过这三点的曲线。 对于这个问题可采用通常的曲线拟合技术，归纳出规则： (x，y，2x+3y+1) 即z＝2x＋3y＋1

9.1.6 发现学习 前面几节所讨论的几种学习方法，通常都认为所获取的都属其他实体（如书本、老师或专家）所拥有的知识。发现学习则是系统直接从（数据）环境中归纳总结出规律性知识的一种学习。即发现学习是指机器获取知识无须外部拥有该知识的实体的帮助，甚至蕴含在客观规律中的这类知识至今尚未被人所知，因此发现学习也是一种归纳学习，而且是一种高级的学习过程。它要求系统具有复杂的问题求解能力。下面仅就这方面的研究作一点简要介绍。

9.1.7 解释学习 解释学习是近年来出现的一种机器学习方法。这种方法只用一个实例，运用领域知识，经过对实例的详细分析，构造解释结构，然后对解释进行推广得到一般性描述。解释学习的一般框架是： 给定：领域知识、目标概念、训练实例和操作性准则。 找出：满足操作性准则的关于目标概念的充分条件。

为了具体地了解解释学习的学习过程，我们来看一个简单的例子。假设要学习的目标概念是：年青人总比年纪大的人更充满活力。并且已知如下事实： (1)一个实例：张三比他的父亲更充满活力。 (2)一组论域知识:假设这一组论域知识能证明给出的实例就是目标概念的例子。

下面我们再看一个用PROLOG描述的法律领域基于解释学习的例子。领域理论： /*如果一个人感到沮丧，他会恨自己*/ hate(X，X):-depressed(X). /*如果一个人买过某物，那么该物为他所拥有*/ posses(X，Y):-buy(X，Y). /*猎枪和手枪均为武器*/ weapon(X):-shotgun(X). weapon(X):-pistol(X).

目标概念： /*如果X恨Y，并且X拥有一件武器，那么Y可能被X所杀。*/ kill(X，Y):-hate(X，Y)，weapon(Z)，posses(X，Z). 训练实例： depressed(john). buy(john，objl). shotgun(objl). 操作准则： /*谓词depressed，buy，shotgun，pistol均为可操作性谓词*/ operational(depressed(X)). operational(buy(X，Y)). operational(shotgun(X)). operational(pistol(X)).

在这一例子中，任务是学习有关法律上自杀的判断法则，所使用的实例即john自杀事件中的三条事实。下面再分两步进行： (1)分析阶段：生成一棵证明树，它用于解释为什么实例是目标概念的一个实例。   (2)基于解释的泛化(ExplanationBased Generaliza tion，简称EBG)阶段：通过将实例证明树中的常量用变量进行替换，从而完成解释的泛化，形成一棵基于解释的泛化树(简称EBG树)，得到目标概念的一个充分条件。

图9―5 证明树

图9―6 EBG树

9.2 神经网络学习 9.2.1 生物神经元 这里的神经元指神经细胞，它是生物神经系统的最基本的单元，其基本结构如图9―7所示。可以看出，神经元由细胞体、树突和轴突组成。细胞体是神经元的主体，它由细胞核、细胞质和细胞膜三部分构成。从细胞体向外延伸出许多突起，其中大部分突起呈树状，称为树突。树突起感受作用，接受来自其他神经元的传递信号；

另外，由细胞体伸出的一条最长的突起，用来传出细胞体产生的输出信号，称之为轴突；轴突末端形成许多细的分枝，叫做神经末梢；每一条神经末梢可以与其他神经元形成功能性接触，该接触部位称为突触。所谓功能性接触是指并非永久性接触，它是神经元之间信息传递的奥秘之处。  

一个神经元把来自不同树突的兴奋性或抑制性输入信号(突触后膜电位)累加求和的过程，称为整合。考虑到输入信号的影响要持续一段时间(毫秒级)，因此，神经元的整合功能是一种时空整合。当神经元的时空整合产生的膜电位超过阈值电位时，神经元处于兴奋状态，产生兴奋性电脉冲，并经轴突输出；否则，无电脉冲产生，处于抑制状态。

图9―7 生物神经元基本结构

9.2.2 人工神经元 如果我们对生物神经元作以适当的结构简化和功能抽象，就得到所谓的人工神经元。 一般地，人工神经元的结构模型如图9―8所示。它是一个多输入单输出的非线性阈值器件。其中x1，x2，…xn表示神经元的n个输入信号量；w1，w2，…，wn表示对应输入的权值，它表示各信号源神经元与该神经元的连接强度；A表示神经元的输入总和，它相应于生物神经细胞的膜电位，称为激活函数；y为神经元的输出；θ表示神经元的阈值。

图9―8 人工神经元结构模型

于是，人工神经元的输入输出关系可描述为： 函数y=f(A)称为特性函数(亦称作用函数或传递函数)。特性函数可以看作是神经元的数学模型。常见的特性函数有以下几种:

1. 阈值型 2.S型 这类函数的输入－输出特性多采用指数、对数或双曲正切等S型函数表示。例如 S型特性函数反映了神经元的非线性输出特性。

3.分段线性型 神经元的输入－输出特性满足一定的区间线性关系， 其特性函数表达为 式中，K、Ak均表示常量。

以上三种特性函数的图像依次如图9―9中的(a)、(b)、(c)所示。由于特性函数的不同，神经元也就分为阈值型、S型和分段线性型三类。另外，还有一类概率型神经元,它是一类二值型神经元。与上述三类神经元模型不同，其输出状态为0或1是根据激励函数值的大小，按照一定的概率确定的。例如，一种称为波尔茨曼机神经元就属此类。本书后面所说的神经元及神经网络都是指人工神经元与人工神经网络。

图9―9 神经元特性函数

9.2.3 神经网络 如果将多个神经元按某种的拓扑结构连接起来，就构成了神经网络。根据连接的拓扑结构不同，神经网络可分为四大类：分层前向网络、反馈前向网络、互连前向网络、广泛互连网络。 1.分层前向网络 分层前向网络如图9―10(a)所示。这种网络的结构特征是，网络由若干层神经元组成，一般有输入层、中间层（又称隐层，可有一层或多层）和输出层，各层顺序连接；且信息严格地按照从输入层进，经过中间层，从输出层出的方向流动。

2.反馈前向网络 反馈前向网络如图9―10(b)所示。它也是一种分层前向网络，但它的输出层到输入层具有反馈连接。反馈的结果形成封闭环路，具有反馈的单元也称为隐单元，其输出称为内部输出。 3.互连前向网络 互连前向网络如图9―10(c)所示。它也是一种分层前向网络，但它的同层神经元之间有相互连接。同一层内单元的相互连接使它们之间有彼此牵制作用。

4. 广泛互连网络 所谓广泛互连是指网络中任意两个神经元之间都可以或可能是可达的，即存在连接路径，广泛互连网络如图9―10(d)所示。著名的Hopfield网络、波尔茨曼机模型结构均属此类。

图9―10 分层前向网络

具体来讲，神经网络至少可以实现如下功能： 数学上的映射逼近 通过一组映射样本(x1，y1)，(x2，y2)，…，(xn，yn)，网络以自组织方式寻找输入与输出之间的映射关系：yi=f(xi)。 数据聚类、压缩通过自组织方式对所选输入模式聚类。 联想记忆 实现模式完善、恢复，相关模式的相互回忆等。 优化计算和组合优化问题求解 利用神经网络的渐进稳定态，特别是反馈网络的稳定平衡态，进行优化计算或求解组合优化问题的近似最优解。

模式分类 现有的大多数神经网络模型都有这种分类能力。 概率密度函数的估计 根据给定的概率密度函数，通过自组织网络来响应在空间Rn中服从这一概率分布的一组向量样本X1，X2，…，Xk。

9.2.4 神经网络学习 学习（亦称训练）是神经网络的最重要特征之一。神经网络能够通过学习，改变其内部状态，使输入—输出呈现出某种规律性。网络学习一般是利用一组称为样本的数据，作为网络的输入（和输出），网络按照一定的训练规则(又称学习规则或学习算法)自动调节神经元之间的连接强度或拓扑结构，当网络的实际输出满足期望的要求，或者趋于稳定时，则认为学习成功。

1.学习规则 权值修正学派认为：神经网络的学习过程就是不断调整网络的连接权值，以获得期望的输出的过程。所以，学习规则就是权值修正规则。 2.学习方法分类 从不同角度考虑，神经网络的学习方法有不同的分类。表9.1列出了常见的几种分类情况。

表9.1 神经网络学习方法的常见分类

9.2.5 BP网络及其学习举例 BP(BackPropagation)网络即误差反向传播网络是应用最广泛的一种神经网络模型。  (1)BP网络的拓扑结构为分层前向网络； (2)神经元的特性函数为Sigmoid型(S型)函数，一般取为

(3)输入为连续信号量（实数）； (4)学习方式为有导师学习； (5)学习算法为推广的δ学习规则，称为误差反向传播算法，简称BP学习算法。  BP算法的一般步骤如下： 步1 初始化网络权值、阈值及有关参数(如学习因子η等)； 步2 计算总误差

其中ykj为输出层节点j对第k个样本的输入对应的输出（称为期望输出），yk′j为节点j的实际输出。 其中p为样本的个数， (9―1  ) 其中ykj为输出层节点j对第k个样本的输入对应的输出（称为期望输出），yk′j为节点j的实际输出。 如果总误差E能满足要求，则网络学习成功，算法结束。 步3 对样本集中各个样本依次重复以下过程，然后转步2。 首先，取一样本数据输入网络，然后按如下公式向前计算各层节点(记为j)的输出：

其次，从输出层节点到输入层节点以反向顺序，对各连接权值wij按下面的公式进行修正： (9―2) 对于输出节点 对于中间节点

l为与节点j在输出侧有连接的节点个数。 算法中的δj称为节点j的误差。它的来历如下: 于是，令

又当j为输出节点时

可以看出，(9―1)式中Ek是网络输出yk′j(j=1，2，…，n)的函数，而yk′j又是权值wij的函数，所以，Ek实际是wij的函数。网络学习的目的就是要使这个误差函数达到最小值。(9―2)式及δ的定义，就是用梯度下降法，在权值空间沿负梯度方向调整权值wij，以使(9―1)式所示的准则函数达到最小。所以，BP网络的学习过程就是一个非线性优化过程。

据进行学习，使学成的网络能解决类似的模式分类问题。设网络的输入层有三个节点，隐层四个节点，输出层三个节点，拓扑结构如图9-11所示。 例 9.3 设计一个BP网络，对表9.2所示的样本数 据进行学习，使学成的网络能解决类似的模式分类问题。设网络的输入层有三个节点，隐层四个节点，输出层三个节点，拓扑结构如图9-11所示。 表9.2 网络训练样本数据 输入 输出 X1 x2 x3 Y1 y2 y3 0.3 0.8 0.1 0.7 0.1 0.3 0.6 0.6 0.6 1 0 0 0 1 0 0 0 1

图9―11 BP网络举例

用样本数据按BP算法对该网络进行训练，训练结束后，网络就可作为一种模式分类器使用。因为网络的输出向量(1，0，0)、(0，1，0)、(0，0，1)可以表示多种模式或状态。如可以分别表示凸、凹和直三种曲线，或者三种笔划，也可以表示某公司的销售情况：高峰、低谷和持平等等。当然，要使网络有很好的模式分类能力，必须给以足够多的范例使其学习，本例仅是一个简单的示例。

9.2.6 神经网络模型 神经网络模型是一个在神经网络研究和应用中经常提到的概念。所谓神经网络模型，它是关于一个神经网络的综合描述和整体概念，包括网络的拓扑结构、输入输出信号类型、信息传递方式、神经元特性函数、学习方式、学习算法等等。截止目前，人们已经提出了上百种神经网络模型,表9.3简介了最著名的几种。

表9.3 一些著名的神经网络模型

神经网络模型也可按其功能、结构、学习方式等的不同进行分类。 1.按学习方式分类 神经网络的学习方式包括三种，有导师学习、强化学习和无导师学习。按学习方式进行神经网络模型分类时，可以分为相应的三种，即有导师学习网络、强化学习网络及无导师学习网络。

2. 按网络结构分类 神经网络的连接结构分为两大类，分层结构与互连结构，分层结构网络有明显的层次，信息的流向由输入层到输出层，因此，构成一大类网络，即前向网络。对于互连型结构网络，没有明显的层次，任意两处理单元之间都是可达的，具有输出单元到隐单元(或输入单元)的反馈连接，这样就形成另一类网络，称之为反馈网络。

3. 按网络的状态分类 在神经网络模型中，处理单元(即神经元)的状态有两种形式：连续时间变化状态、离散时间变化状态。如果神经网络模型的所有处理单元状态能在某一区间连续取值，这样的网络称为连续型网络；如果神经网络模型的所有处理单元状态只能取离散的二进制值0或1(或-1、+1)，那么称这种网络为离散型网络。典型的Hopfield网络同时具有这两类网络，分别称为连续型Hopfield网络和离散型Hopfield网络。另外，还有输出为二进制值0或1、输入为连续值的神经网络模型，如柯西机模型。

4. 按网络的活动方式分类 确定神经网络处理单元的状态取值有两种活动方式，一种是由确定性输入经确定性作用函数，产生确定性的输出状态；另一种是由随机输入或随机性作用函数，产生遵从一定概率分布的随机输出状态。具有前一种活动方式的神经网络，称为确定性网络。已有的大部分神经网络模型均属此类。而后一种活动方式的神经网络，称为随机性网络。随机性网络的典型例子有：波尔茨曼机、柯西机和高斯机等。

9.3 知识发现与数据挖掘 9.3.1 知识发现的一般过程 知识发现过程可粗略地划分为：数据准备、数据开采以及结果的解释评估等三步。 9.3 知识发现与数据挖掘 9.3.1 知识发现的一般过程 知识发现过程可粗略地划分为：数据准备、数据开采以及结果的解释评估等三步。 1.数据准备 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。数据选取就是确定目标数据，即操作对象，它是根据用户的需要从原始数据库中抽取的一组数据。

2. 数据挖掘 数据挖掘阶段首先要确定开采的任务或目的是什么，如数据总结、分类、聚类、关联规则或序列模式等。确定了开采任务后，就要决定使用什么样的开采算法。同样的任务可以用不同的算法来实现，选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关的算法来开采；二是用户或实际运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高的预测型知识。

3. 结果解释和评价 数据挖掘阶段发现出来的知识模式中可能存在冗余或无关的模式，所以还要经过用户或机器的评价。若发现所得模式不满足用户要求，则需要退回到发现阶段之前，如重新选取数据，采用新的数据变换方法，设定新的数据挖掘参数值，甚至换一种采掘算法。另外，KDD由于最终是面向人的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“ifthen...”规则。

9.3.2 知识发现的任务 所谓知识发现的任务，就是知识发现所要得到的具体结果。它至少可以是以下几种。  1.数据总结 数据总结的目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼状图等图形方式表示。

2. 概念描述 有两种典型的描述：特征描述和判别描述。特征描述是从与学习任务相关的一组数据中提取出关于这些数据的特征式，这些特征式表达了该数据集的总体特征；而判别描述则描述了两个或多个类之间的差异。

3. 分类 分类是数据挖掘中一项非常重要的任务，目前在商业上应用最多。分类的目的是提出一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。

4.聚类 聚类是根据数据的不同特征，将其划分为不同的类。它的目的是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法等。

5.相关性分析 相关性分析的目的是发现特征之间或数据之间的相互依赖关系。数据相关性关系代表一类重要的可发现的知识。一个依赖关系存在于两个元素之间。如果从一个元素A的值可以推出另一个元素B的值，则称B依赖于A。这里所谓元素可以是字段，也可以是字段间的关系。

6.偏差分析 偏差分析包括分类中的反常实例、例外模式、观测结果对期望值的偏离以及量值随时间的变化等，其基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常，可以引起人们对特殊情况加倍注意。 7.建模 建模就是通过数据挖掘，构造出能描述一种活动、状态或现象的数学模型。

9.3.3 知识发现的方法 知识发现主要有以下几种方法。 1.统计方法 事物的规律性，一般从其数量上会表现出来。而统计方法就是从事物的外在数量上的表现去推断事物可能的规律性。 2.粗糙集 粗糙集（roughset）理论由Zdziskew Pawlak在1982年提出，它是一种新的数学工具，用于处理含糊性和不确定性，粗糙集在数据挖掘中也可发挥重要作用。

3. 可视化 可视化(Visualization)就是把数据、信息和知识转化为图形的表现形式的过程。可视化可使抽象的数据信息形象化。 4.传统机器学习方法 包括符号学习和连接学习。

9.3.4 知识发现的对象 1.数据库 数据库是当然的知识发现对象。 2.数据仓库 随着计算机技术的迅猛发展，到20世纪80年代，许多企业的数据库中已积累了大量的数据。 3.Web信息 随着Web的迅速发展，分布在Internet上的Web网页已构成了一个巨大的信息空间。

4. 图像和视频数据 图像和视频数据中也存在有用的信息需要挖掘。比如，地球资源卫星每天都要拍摄大量的图像或录像，对同一个地区而言，这些图像存在着明显的规律性，白天和黑夜的图像不一样，当可能发生洪水时与正常情况下的图像又不一样。

9.4 遗传算法 遗传算法(GeneticAlgorithm)是一种优化算法。它是人们从生物的有性繁殖、遗传变异和按优胜劣汰法则进化的自然现象中得到启发，而设计出来的，因此称为遗传算法。我们知道，自然选择的原则是优胜劣汰、适者生存，有性繁殖则可以使基因不断地进行混合和重组。

遗传算法以生物细胞中的染色体作为生物个体，并设置了三个作用于染色体的操作：复制、交叉（亦称交换或杂交）和变异（亦称突变），它们被称为遗传操作或遗传算子。此外，还要定义染色体的适应度，即对环境的适应程度。适应度也就是表征一个染色体优劣的测度。在此基础上，遗传算法的步骤就是对一个染色体集合中的染色体，重复做：①三种遗传操作；②计算适应度；③按适应度大小进行取舍，直至达到预定目标。

复制：产生一个与字符串S相同的字符串； 交叉：取字符串S1和S2，互相交换其中的某些字符，得到两个新的字符串S′1和S′2；变异：改变字符串S中的某一个字符，得到一个新的字符串S′。 例如，设字符串S1 =10101001， S2 =10010011，那么， (1)对S1进行复制操作，得新串10101001；

(2)对S1和S2进行交叉操作，如交换两个字符串的后4位，则得S′=10100011，S′2=10011001； 有了以上准备，下面我们给出基本遗传算法的一般描述。

基本遗传算法： 步1 随机产生一个个体集合A={S1,S2, :,Sn}，将A作为一个初始种群，并在其上定义一个适应度函数f(x)； 步2 计算A中每个个体的适应度函数值； 步3 若满足停止条件，取A中适应度最大的个体作为所求结果，算法结束。 步4 以一定的概率选择A中若干适应度高的个体S1, S2, :,Sk(k<n)，进行复制操作，并删去A中适应度低的个体，这样得到集合A′(注：被复制个体和复制个体同时存在于A′中)；

步5 以一定的概率选取A′中的若干个体对，进行交叉操作，得到集合A″； 步7 将A作为新一代种群，用A代替A，转步2；

遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，解决困难的问题。遗传算法的适应性强，除需知适应度函数外，几乎不需要其它的先验知识。遗传算法长于全局搜索，它不受搜索空间的限制性假设的约束，不要求连续性，能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。