人工智能课件：第二讲(计算智能-遗传算法).pptx

1、遗传算法遗传算法提纲 动机 什么是遗传算法 生物学基础 遗传算法的基本过程 案例动机 解决传统方法无法解决的最优化问题。提纲 动机 遗传算法的定义 生物学基础 遗传算法的基本过程 案例 进化计算是一种模拟自然界生物进化过程与机制进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的它以达尔文进化论的“物竟天择、适者生存物竟天择、适者生存”作作为算法的进化规则，并结合孟德尔的遗传变异理为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的论，将生物进化过程中的 繁殖（繁殖（Reproducti

2、on） 变异（变异（Mutation） 竞争（竞争（Competition） 选择（选择（Selection）引入到了算法中。引入到了算法中。 w几个名词概念几个名词概念 进化计算：进化计算： 由于遗传算法、进化规划和进化策略是不同领由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到里相互之间没有正式沟通。直到90年代，才有所年代，才有所交流。交流。 他们发现彼此的基本思想具有惊人的相似之处，他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为于是提出将这类方法统称为“进化计算进

3、化计算” ( Evolutionary Computation ) 。 w几个名词概念几个名词概念 计算智能：计算智能： 计算智能主要包括神经计算、进化计算和模糊计算智能主要包括神经计算、进化计算和模糊计算等。它们分别从不同的角度模拟人类的智能计算等。它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能。活动，以使计算机具有智能。 通常将基于符号处理的传统人工智能称为符号通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能。智能，以区别于正在兴起的计算智能。 符号智能的特点是以知识为基础，偏重于逻辑符号智能的特点是以知识为基础，偏重于逻辑推理，而计算智能则是以数据为基

4、础，偏重于数推理，而计算智能则是以数据为基础，偏重于数值计算。值计算。提纲 动机 遗传算法的定义 生物学基础 遗传算法的基本过程 案例生物学基础生物学基础w达尔文的自然选择说达尔文的自然选择说遗传（遗传（heredity）：子代和父代具有相）：子代和父代具有相 同或相似的性状，保证物种的稳定性；同或相似的性状，保证物种的稳定性；变异（变异（variation）：子代与父代，子代不同个体之）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘

5、汰。留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。自然选择过程是长期的、缓慢的、连续的过程。生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语染色体（染色体（chromosome）：遗传物质的载体；）：遗传物质的载体；脱氧核糖核酸（脱氧核糖核酸（DNA）：大分子有机聚合物，双螺）：大分子有机聚合物，双螺旋结构；旋结构；遗传因子（遗传因子（gene）：）：DNA或或RNA长链结构中占有一长链结构中占有一定位置的基本遗传单位；定位置的基本遗传单位；生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语基因型（基因型（genotype）：遗传因子组合

6、的模型；）：遗传因子组合的模型；表现型（表现型（phenotype）：由染色体决定性状的外部表）：由染色体决定性状的外部表现；现；1 1 1 1 1 1 1 1 1 1 0 1 1 1 生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语基因座（基因座（locus）：遗传基因在染色体中所占据的位）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因置，同一基因座可能有的全部基因称为等位基因（allele）；）；个体（个体（individual）：指染色体带有特征的实体；）：指染色体带有特征的实体；种群（种群（population）：个体的集合，该集合内个体数）：个

7、体的集合，该集合内个体数称为种群的大小；称为种群的大小；生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语进化（进化（evolution）：生物在其延续生存的过程中，逐）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；生命现象称为进化；适应度（适应度（fitness）：度量某个物种对于生存环境的适应）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁繁殖机会，而对生存环境适

8、应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝殖机会就会相对较少，甚至逐渐灭绝;生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语选择（选择（selection）：指决定以一定的概率从种群中选）：指决定以一定的概率从种群中选择若干个体的操作择若干个体的操作 ；复制（复制（reproduction）：细胞在分裂时，遗传物质）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因就继承了旧细胞的基因;交叉（交叉（crossover）：在两个染色体的某一相同位置）：在两个染色体的某一相同位置处处DNA被切

9、断，其前后两串分别交叉组合形成两个被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称新的染色体。又称基因重组，俗称“杂交杂交”;生物学基础生物学基础w遗传学基本概念与术语遗传学基本概念与术语变异（变异（mutation）：在细胞进行复制时可能以很小的）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使概率产生某些复制差错，从而使DNA发生某种变异，发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状产生出新的染色体，这些新的染色体表现出新的性状;编码（编码（coding）：表现型到基因型的映射；）：表现型到基因型的映射；解码（解码（decoding）：从基因型

10、到表现型的映射。）：从基因型到表现型的映射。生物学基础生物学基础w生物进化生物进化与智能学的关系与智能学的关系 生物物种作为复杂系统，具有奇妙的自适应、自组生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。的智能，也是人工系统梦寐以求的功能。提纲 动机 遗传算法的定义 生物学基础 遗传算法 案例w遗传算法的基本思路遗传算法的基本思路 w自组织、自适应和自学习性自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法在编码方案、适应度函数及遗传算子确定后，算法将利用

11、进化过程中获得的信息自行组织搜索。将利用进化过程中获得的信息自行组织搜索。w本质并行性本质并行性 内在并行性与内含并行性内在并行性与内含并行性w不需求导不需求导 只需目标函数和适应度函数只需目标函数和适应度函数w概率转换规则概率转换规则 强调概率转换规则，而不是确定的转换规则强调概率转换规则，而不是确定的转换规则20 进化计算尽管有多个重要分支，但它们却有着共同的进化框架。进化计算尽管有多个重要分支，但它们却有着共同的进化框架。 若假设若假设P为种群为种群(Population，或称为群体，或称为群体)，t为进化代数，为进化代数， P(t)为第为第t代种群代种群 , 则进化计算的基本结构可粗略

12、描述如下：则进化计算的基本结构可粗略描述如下： 确定编码形式并生成搜索空间；确定编码形式并生成搜索空间； 初始化各个进化参数，并设置进化代数初始化各个进化参数，并设置进化代数t=0； 初始化种群初始化种群P(0); 对初始种群进行评价（即适应度计算）；对初始种群进行评价（即适应度计算）； while（不满足终止条件）（不满足终止条件）do t=t+1; 利用选择操作从利用选择操作从P(t-1)代中选出代中选出P(t)代群体；代群体； 对对P(t)代种群执行进化操作；代种群执行进化操作； 对执行完进化操作后的种群进行评价（即适应度计算）；对执行完进化操作后的种群进行评价（即适应度计算）； 可以看

13、出，上述基本结构包含了生物进化中所必需的选择操作、进化操作可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。和适应度评价等过程。进化计算的基本结构21 遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：满足目标为止。遗传算法所涉及到的基本概念主要有以下几个： 种群种群（Population）：种群是

14、指用遗传算法求解问题时，初始给定的多个）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。解的集合。遗传算法的求解过程是从这个子集开始的。 个体个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。其基本遗传结构的数据结构来表示。 染色体染色体（Chromos）：染色体是指对个体进行编码后所得到的编码串。其）：染色体是指对个体进行编码后所得到的编码串。其中的每中的每1位称为基因，若干个基因构成的一个有效信息段称为基因组。位称为基因，若干个基因构成的

15、一个有效信息段称为基因组。 适应度（适应度（Fitness）函数）函数：适应度函数是一种用来对种群中各个个体的环境：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。适应性进行度量的函数。 遗传操作遗传操作（Genetic Operator）：遗传操作是指作用于种群而产生新的种群）：遗传操作是指作用于种群而产生新的种群的操作。的操作。标准的遗传操作包括以下标准的遗传操作包括以下3种基本形式：种基本形式： 选择选择（Selection） 交叉交叉（Crosssover） 变异变异（Mutation） 遗传算法的基本概念22 遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗

16、传操作遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成，其算法主要内容和基本步骤可描述如下：设计等几大部分所组成，其算法主要内容和基本步骤可描述如下： (1) 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；出来，即形成染色体； (2) 定义遗传策略，包括种群规模定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率，交叉、变异方法，以及选择概率Pr、交叉概率交叉概率Pc、变异概率、变异概率Pm等遗传参数；等遗传参数； (3) 令令t=0，随机选择，随机选择N

17、个染色体初始化种群个染色体初始化种群P(0)； (4) 定义适应度函数定义适应度函数f（f0）；）； (5) 计算计算P(t)中每个染色体的适应值；中每个染色体的适应值； (6) t=t+1； (7) 运用选择算子，从运用选择算子，从P(t-1)中得到中得到P(t)； (8) 对对P(t)中的每个染色体，按概率中的每个染色体，按概率Pc参与交叉；参与交叉； (9) 对染色体中的基因，以概率对染色体中的基因，以概率Pm参与变异运算；参与变异运算； (10) 判断群体性能是否满足预先设定的终止标准，若不满足则返回判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。遗传算法的基本过程23计

18、算种群中各个个体的适应度，并进行评价计算种群中各个个体的适应度，并进行评价满足终止条件吗？满足终止条件吗？终止终止选择交叉交叉变异变异Y图图4-18 基本遗传算法的算法流程图基本遗传算法的算法流程图编码和生成初始种群编码和生成初始种群N选择选择 其算法流程如其算法流程如图图4-18所示。所示。 遗传算法的基本结构24 常用的遗传编码算法有霍兰德二进制码、格雷码（常用的遗传编码算法有霍兰德二进制码、格雷码（Gray Code）、实数编码）、实数编码和字符编码等。和字符编码等。(1)二进制编码（二进制编码（Binary encoding） 二进制编码是将原问题的结构变换为染色体的位串结构。在二进制

19、编码中，二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算，该长度与变量的定义域和所求问题的计算精度有关。精度有关。 例例5.5 假设变量假设变量x的定义域为的定义域为5，10，要求的计算精度为，要求的计算精度为10-5，则需要将，则需要将5，10至少分为至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于串长至少等于20，原因是：，原因是： 524288=219600000220=1048576这样，对

20、应于区间这样，对应于区间5，10内满足精度要求的每个值内满足精度要求的每个值x，都可用一个，都可用一个20位编码的位编码的二进制串二进制串来表示。来表示。 二进制编码存在的主要缺点二进制编码存在的主要缺点是汉明（是汉明（Hamming）悬崖。）悬崖。 例如，例如，7和和8的二进制数分别为的二进制数分别为0111和和1000，当算法从，当算法从7改进到改进到8时，就必须时，就必须改变所有的位。改变所有的位。 遗传编码(1/3)25(2) 格雷编码（格雷编码（Gray encoding） 格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方格雷编码是对二进制编码进行变换后所得到的一种编

21、码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题，其基本原理如下：同的。它有效地解决了汉明悬崖问题，其基本原理如下： 设有二进制串设有二进制串b1,b2,bn，对应的格雷串为，对应的格雷串为a1,a2,an，则从二进制编码到，则从二进制编码到格雷编码的变换为：格雷编码的变换为： (4.9)其中，其中， 表示模表示模2加法。而从一个格雷串到二进制串的变换为：加法。而从一个格雷串到二进制串的变换为： (4.10) 例例4.6 十进制数十进制数7和和8的二进制编码分别

22、为的二进制编码分别为0111和和1000，而其格雷编码分别为，而其格雷编码分别为0100和和1100。111ibbibaiiiiijiiab1)2(mod遗传编码(2/3)26(3) 实数编码（实数编码（Real encoding） 实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。来表示，其编码长度等于该问题变量的个数。 这种编码方法是将问题的解空间映射到实数空间上，然后在实数空这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实

23、值，因此这种间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。编码方法也叫做真值编码方法。 实数编码适应于那种多维、高精度要求的连续函数优化问题。实数编码适应于那种多维、高精度要求的连续函数优化问题。 遗传编码(3/3)27 适应度函数是一个用于对个体的适应性进行度量的函数。通常，一适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。(1) 常用的适应度函数常用的适应度函数 在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函

24、在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：数有以下两种： 原始适应度函数原始适应度函数 它是直接将待求解问题的目标函数它是直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函定义为遗传算法的适应度函数。例如，在求解极值问题数。例如，在求解极值问题时，时，f(x)即为即为x的原始适应度函数。的原始适应度函数。 采用原始适应度函数的采用原始适应度函数的优点优点是能够直接反映出待求解问题的最初求是能够直接反映出待求解问题的最初求解目标，其解目标，其缺点缺点是有可能出现适应度值为负的情况。是有可能出现适应度值为负的情况。 )(max,xfbax适应度函数(1/3)2

25、8 标准适应度函数标准适应度函数 在遗传算法中，在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好一般要求适应度函数非负，并其适应度值越大越好。这就。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。例如下面的极小化和极大化问题：例如下面的极小化和极大化问题： 极小化问题极小化问题 对极小化问题，其标准适应度函数可定义为对极小化问题，其标准适应度函数可定义为 (

26、4.11)其中，其中，fmax (x)是原始适应函数是原始适应函数f(x)的一个上界。如果的一个上界。如果fmax (x) 未知，则可用当前未知，则可用当前代或到目前为止各演化代中的代或到目前为止各演化代中的f(x)的最大值来代替。可见，的最大值来代替。可见， fmax (x) 是会随着进是会随着进化代数的增加而不断变化的。化代数的增加而不断变化的。 否则当0)()()()()(maxmaxxfxfxfxfxfnomal适应度函数(2/3)29 极大化问题极大化问题 对极大化问题，其标准适应度函数可定义为对极大化问题，其标准适应度函数可定义为 (4.12)其中，其中，fmin(x)是原始适应函

27、数是原始适应函数f(x)的一个下界。如果的一个下界。如果fmin(x) 未知，则可用当前未知，则可用当前代或到目前为止各演化代中的代或到目前为止各演化代中的f(x)的最小值来代替。的最小值来代替。 否则当0)()()()()(minminxfxfxfxfxfnomal适应度函数(3/3)30 遗传算法中的基本遗传操作包括选择、交叉和变异遗传算法中的基本遗传操作包括选择、交叉和变异3种，而每种操作种，而每种操作又包括多种不同的方法，下面分别对它们进行介绍。又包括多种不同的方法，下面分别对它们进行介绍。(1). 选择操作选择操作 选择（选择（Selection）操作是指根据选择概率按某种策略从当前

28、种群中）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。 常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。 比例选择比例选择 比例选择方法（比例选择方法（Proportional Model）的基本思想是：各个个体被选）的基本思想是：各个个体被选中的概率与其适应度大小成正比。中的概率与其适应度大小成正比。 常用的比例选择策略包括常用的比例选择策略包括 轮盘赌选择轮盘赌选择 繁殖池选择繁殖池选择基本遗传操作(1/

29、11)31 轮盘赌选择轮盘赌选择 轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：其中，其中，P(xi)是个体是个体xi的相对适应度，即个体的相对适应度，即个体xi被选中的概率；被选中的概率；f(xi)是个体是个体xi的原的原始适应度；是种群的累加适应度。始适应度；是种群的累加适应度。 轮盘赌选择算法的基本思想是：根据每个个体的选择概率轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将

30、一个圆盘将一个圆盘分成分成N个扇区，其中第个扇区，其中第i个扇区的中心角为：个扇区的中心角为：再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第静止时指针指向第i个扇区，则选择个体个扇区，则选择个体i。其物理意义如图。其物理意义如图5-19所示。所示。1()()()iiNjjf xP xf x1()22()()iiNijjf xp xfx基本遗传操作(2/11)32P(x1)P(x2)P(xN)P(xi)2p(xp(xi i) )图图4-19 轮盘赌选择轮盘赌选择 从统计角度看，个

31、从统计角度看，个体的适应度值越大，体的适应度值越大，其对应的扇区的面积其对应的扇区的面积越大，被选中的可能越大，被选中的可能性也越大。这种方法性也越大。这种方法有点类似于发放奖品有点类似于发放奖品使用的轮盘，并带有使用的轮盘，并带有某种赌博的意思，因某种赌博的意思，因此亦被称为轮盘赌选此亦被称为轮盘赌选择。择。基本遗传操作(3/11)33(2)交叉操作交叉操作 交叉（交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界体的部分基因进行交配重组，从而形成新的个体。交配重组是自然

32、界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型二进制交叉和实值交叉两种类型。 二进制交叉二进制交叉 二进制交叉（二进制交叉（Binary Valued Crossover）是指二进制编码情况下所）是指二进制编码情况下所采用的交叉操作，它主要包括采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀单点交叉、两点交叉、多点交叉和均匀交叉交叉等方法。等方法。基本遗传操作(

33、4/11)34 单点交叉单点交叉 单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：生成子代中的两个新的个体。假设两个父代的个体串分别是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn 随机选择第随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但位为交叉点，若采用对交叉点后面的基因进行交换

34、的方法，但点交叉是将点交叉是将X中的中的xk+1到到xn部分与部分与Y中的中的yk+1到到yn部分进行交叉，交叉后生成的部分进行交叉，交叉后生成的两个新的个体是：两个新的个体是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 例例4.7 设有两个父代的个体串设有两个父代的个体串A=0 0 1 1 0 1 和和B=1 1 0 0 1 0 ，若随机交叉点，若随机交叉点为为4，则交叉后生成的两个新的个体是：，则交叉后生成的两个新的个体是： A= 0 0 1 1 1 0 B= 1 1 0 0 0 1 基本遗传操作(5/11)35 两点交叉两点交叉 两点交叉是指先在两个

35、父代个体的编码串中随机设定两个交叉点，然后再两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。 假设两个父代的个体串分别是：假设两个父代的个体串分别是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn 随机设定第随机设定第i、j位为两个交叉点（其中位为两个交叉点（其中ijn），两点交叉是将），两点交叉是将X中的中的xi+1到到xj部分与部分与Y中的中的yi+1到到yj部分进行交换，交叉后生成的两个新的个体是：部分进行交换，交叉后生成的两个新的个

36、体是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi xi+1 xj yj+1 yn 例例4.8 设有两个父代的个体串设有两个父代的个体串A= 0 0 1 1 0 1 和和B= 1 1 0 0 1 0 ，若随机交叉点，若随机交叉点为为3和和5，则交叉后的两个新的个体是：，则交叉后的两个新的个体是： A= 0 0 1 0 1 1 B= 1 1 0 1 0 0 基本遗传操作(6/11)36 多点交叉多点交叉 多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个

37、新的个体。交换，生成子代中的两个新的个体。 假设交叉点个数为假设交叉点个数为m，则可将个体串划分为，则可将个体串划分为m+1个分段，其划分方法是：个分段，其划分方法是： 当当m为偶数时，对全部交叉点依次进行两两配对，构成为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。个交叉段。 当当m为奇数时，对前为奇数时，对前(m-1)个交叉点依次进行两两配对，构成个交叉点依次进行两两配对，构成(m-1)/2个交叉段，个交叉段，而第而第m个交叉点则按单点交叉方法构成一个交叉段。个交叉点则按单点交叉方法构成一个交叉段。 下面以下面以m=3为例进行讨论。假设两个父代的个体串分别是为例进行讨论。假设两

38、个父代的个体串分别是X=x1 x2 xi xj xk xn和和Y=y1 y2 yi yj yk yn，随机设定第随机设定第i、j、k位为三个交叉点（其位为三个交叉点（其中中ijkn），则将构成两个交叉段。交叉后生成的两个新的个体是：），则将构成两个交叉段。交叉后生成的两个新的个体是： X= x1 x2 xi yi+1 yj xj+1 xk yk+1 yn Y= y1 y2 yi xi+1 xj yj+1 yk xk+1 xn 例例4.9 设有两个父代的个体串设有两个父代的个体串A= 0 0 1 1 0 1 和和B= 1 1 0 0 1 0 ，若随机交叉点为，若随机交叉点为1、3和和5，则交叉后

39、的两个新的个体是：，则交叉后的两个新的个体是： A= 0 1 0 1 0 0 B= 1 0 1 0 1 1 基本遗传操作(7/11)37 均匀交叉均匀交叉 均匀交叉（均匀交叉（Uniform Crossover）是先随机生成一个与父串具有相同）是先随机生成一个与父串具有相同长度，并被称为交叉模版（或交叉掩码）的二进制串，然后再利用该长度，并被称为交叉模版（或交叉掩码）的二进制串，然后再利用该模版对两个父串进行交叉，即将模版中模版对两个父串进行交叉，即将模版中1对应的位进行交换对应的位进行交换，而，而0对应对应的位不交换，依此生成子代中的两个新的个体。事实上，这种方法对的位不交换，依此生成子代中

40、的两个新的个体。事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。父串中的每一位都是以相同的概率随机进行交叉的。 例例4.10 设有两个父代的个体串设有两个父代的个体串A=001101和和B=110010，若随机生成的，若随机生成的模版模版T=010011，则交叉后的两个新的个体是，则交叉后的两个新的个体是A=011010和和B=100101。即即 A： 0 0 1 1 0 1 B： 1 1 0 0 1 0 T： 0 1 0 0 1 1 A：0 1 1 1 1 0 B：1 0 0 0 0 1基本遗传操作(8/11)38 实值交叉实值交叉 实值交叉是在实数编码情况下所采用的交叉操作

41、，主要包括离散交叉和算实值交叉是在实数编码情况下所采用的交叉操作，主要包括离散交叉和算术交叉，下面主要讨论离散交叉（部分离散交叉和整体离散交叉）术交叉，下面主要讨论离散交叉（部分离散交叉和整体离散交叉） 。 部分离散交叉部分离散交叉是先在两个父代个体的编码向量中随机选择一部分分量，然是先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。后对这部分分量进行交换，生成子代中的两个新的个体。 整体交叉整体交叉则是对两个父代个体的编码向量中的所有分量，都以则是对两个父代个体的编码向量中的所有分量，都以1/2的概率进的概率进行交换，从而生成子代中的两个新的

42、个体。行交换，从而生成子代中的两个新的个体。 以部分离散交叉为例，以部分离散交叉为例，假设两个父代个体的假设两个父代个体的n维实向量分别是维实向量分别是 X=x1x2 xixkxn和和Y=y1y2yiykyn，若随机选择对，若随机选择对第第k个分量个分量以后的所有分量进以后的所有分量进行交换，则生成的两个新的个体向量是：行交换，则生成的两个新的个体向量是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 例例4.11 设有两个父代个体向量设有两个父代个体向量A=20 16 19 32 18 26和和B=36 25 38 12 21 30，若随机选择对若随机选择对

43、第第3个分量个分量以后的所有分量进行交叉，则交叉后两个新的个体向以后的所有分量进行交叉，则交叉后两个新的个体向量是：量是： A= 20 16 19 12 21 30 B= 36 25 38 32 18 26 基本遗传操作(9/11)39 (3) 变异操作变异操作 变异（变异（Mutation）是指对选中个体的染色体中的某些基因进行变动，以形）是指对选中个体的染色体中的某些基因进行变动，以形成新的个体。变异也是生物遗传和自然进化中的一种基本现象，它可增强成新的个体。变异也是生物遗传和自然进化中的一种基本现象，它可增强种群的多样性。遗传算法中的变异操作增加了算法的局部随机搜索能力，种群的多样性。遗

44、传算法中的变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性。根据个体编码方式的不同，变异操作可分为从而可以维持种群的多样性。根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。二进制变异和实值变异两种类型。 二进制变异二进制变异 当个体的染色体采用二进制编码表示时，其变异操作应采用二进制变异方当个体的染色体采用二进制编码表示时，其变异操作应采用二进制变异方法。该变异方法是先随机地产生一个变异位，然后将该变异位置上的基因法。该变异方法是先随机地产生一个变异位，然后将该变异位置上的基因值由值由“0”变为变为“1”，或由，或由“1”变为变为“0”，产生一个新的个体。，产

45、生一个新的个体。 例例4.12 设变异前的个体为设变异前的个体为A=0 0 1 1 0 1，若随机产生的变异，若随机产生的变异位置是位置是2，则，则该个体的第该个体的第2位由位由“0”变为变为“1”。 变异后的新的个体是变异后的新的个体是A= 0 1 1 1 0 1 。基本遗传操作(10/11)40 实值变异实值变异 当个体的染色体采用实数编码表示时，其变异操作应采用实值变异方法。当个体的染色体采用实数编码表示时，其变异操作应采用实值变异方法。该方法是用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，该方法是用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体

46、。最常用的实值变异操作有产生一个新的个体。最常用的实值变异操作有: 基于位置的变异方法基于位置的变异方法 该方法是先随机地产生两个变异位置，然后将第二个变异位置上的基因移该方法是先随机地产生两个变异位置，然后将第二个变异位置上的基因移动到第一个变异位置的前面。动到第一个变异位置的前面。 例例4.13 设选中的个体向量设选中的个体向量C=20 16 19 12 21 30，若随机产生的两个变异位置，若随机产生的两个变异位置分别时分别时2和和4，则变异后的新的个体向量是：，则变异后的新的个体向量是： C= 20 12 16 19 21 30 基于次序的变异基于次序的变异 该方法是先随机地产生两个变

47、异位置，然后交换这两个变异位置上的基因。该方法是先随机地产生两个变异位置，然后交换这两个变异位置上的基因。 例例4.14 设选中的个体向量设选中的个体向量D=20 12 16 19 21 30，若随机产生的两个变异位置，若随机产生的两个变异位置分别时分别时2和和4，则变异后的新的个体向量是：，则变异后的新的个体向量是： D= 20 19 16 12 21 30基本遗传操作(11/11)提纲 动机 遗传算法的定义 生物学基础 遗传算法 案例42 例例4.15 用遗传算法求函数用遗传算法求函数 f(x)=x2的最大值，其中的最大值，其中x为为0，31间的整数。间的整数。 解：解：这个问题本身比较简

48、单，其最大值很显然是在这个问题本身比较简单，其最大值很显然是在x=31处。但作为一个例处。但作为一个例子，它有着较好的示范性和可理解性。子，它有着较好的示范性和可理解性。 按照遗传算法，其求解过程如下：按照遗传算法，其求解过程如下： (1) 编码编码 由于由于x的定义域是区间的定义域是区间0，31上的整数，由上的整数，由5位二进制数即可全部表示。因位二进制数即可全部表示。因此，可采用二进制编码方法，其编码串的长度为此，可采用二进制编码方法，其编码串的长度为5。 例如，用二进制串例如，用二进制串00000来表示来表示x=0,11111来表示来表示x=31等。其中的等。其中的0和和1为基为基因值。

49、因值。 (2) 生成初始种群生成初始种群 若假设给定的种群规模若假设给定的种群规模N=4，则可用，则可用4个随机生成的长度为个随机生成的长度为5的二进制串作的二进制串作为初始种群。再假设随机生成的初始种群（即第为初始种群。再假设随机生成的初始种群（即第0代种群）为：代种群）为： s01=0 1 1 0 1 s02=1 1 0 0 1 s03=0 1 0 0 0 s04=1 0 0 1 0f(x)=x2 求解求解43 (3) 计算适应度计算适应度 要计算个体的适应度，首先应该定义适应度函数。由于本例是求要计算个体的适应度，首先应该定义适应度函数。由于本例是求f(x)的最大的最大值，因此可直接用值

50、，因此可直接用f(x)来作为适应度函数。即：来作为适应度函数。即： f(s)=f(x)其中的二进制串其中的二进制串s对应着变量对应着变量x的值。根据此函数，初始种群中各个个体的适的值。根据此函数，初始种群中各个个体的适应值及其所占比例如表应值及其所占比例如表4-5所示。所示。表表4-5 初始种群情况表初始种群情况表编号编号个体串（染个体串（染色体）色体）x适应值适应值百分比百分比%累计百分比累计百分比%选中次数选中次数S010110101101131316916914.3014.3014.3014.301 1S021100111001252562562552.8852.8867.1867.18