当前位置：文档之家 › 03第三章 遗传算法

03第三章 遗传算法

  • 格式：docx
  • 大小：1.23 MB
  • 文档页数：14

第三章 遗传算法 习题与答案

1. 填空题

（1）遗传算法的缩写是 ，它模拟了自然界中 过程而提出，可以解决 问题。在遗传算法中，主要的步骤是 、 、 。

（2）遗传算法的三个算子是 、 、 。

解释：

本题考查遗传算法的基础知识。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

（1）GA，生物进化，全局优化，编码，计算适应度函数，遗传算子

（2）选择，交叉，变异

2. 对于编码长度为7的二进制编码，判断以下编码的合法性。

（1）[1020110]

（2）[1011001]

（3）[0110010]

（4）[0000000]

（5）[2134576]

解释：

本题考查遗传算法的二进制编码的合法性。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

（1）[1020110] 不合法，不能出现“2” （2）[1011001] 合法

（3）[0110010] 合法

（4）[0000000] 合法

（5）[2134576] 不合法，不能出现0、1以外的数字

3. 下图能够基本反映生物学遗传与优胜劣汰的过程。理解该图，联想计算

类问题求解，回答下列问题。

（1）下列说法正确的是_____。（多选）

A）任何一个生物个体的性状是由其染色体确定的，染色体是由基因及其有规律的排列所构成的，因此生物个体可由染色体来代表。

B）生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突变。基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配”。基因突变是指复制过程中基因信息的变异，简称“突变”。 C）不同染色体会产生不同生物个体的性状，其适应环境的能力也不同。

D）自然界体现的是“优胜劣汰，适者生存”的丛林法则。不适应环境的生物个体将被淘汰，自然界生物的生存能力会越来越强。

解释：

本题考核对生物遗传观点以及所给图片的理解。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：A、B、C、D

关于生物遗传进化的基本观点如下：

（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。

（2）染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。

（3）生物的繁殖过程是由其基因的复制过程来完成的。

（4）通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。

（5）对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。

故A、B、C、D均正确。

（2）类比计算类问题求解，下列说法正确的是_____。（多选）

A）一个染色体即是指问题的一个“可能解”。任何“可能解”都可以表达为编码形式，构成编码的基本单位即是基因。

B）所谓的复制、杂交、突变，是指一个可能解或两个可能解之间发生的、编码片段之间的复制、交叉或变异，它们都是产生新可能解的一种方式。

C）所谓的环境适应性，可以认为是对一个可能解的一种度量，即能够度量一个可能解的好与坏的某一函数值，被称为“适应度”。 D）基于A）、B）、C），遗传算法就是“通过复制、交叉或变异，不断产生新的可能解；计算可能解的适应度；淘汰掉适应度差的可能解，保留适应度好的可能解。

解释：

本题考核对生物学中的概念与计算机中的概念的映射的理解。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：A、B、C、D

染色体映射到计算机中就是编码解。A正确。复制是指将一个解从一个解集复制到另外一个解集。杂交是指对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作，是新可能解的一种形成方式。突变是指随机地改变一个可能解的编码的某些片段（或基因）而使一个可能解变为一新的可能解的遗传操作 ，也是新解的一种形成方式。B正确。适应度性是指一个可能解接近最优解的一个度量。C正确。由A、B、C选项，可以得到遗传算法的基本思想。D正确。

（3）类比计算类问题求解，下列说法不正确的是_____。

A）一个染色体即是指问题的一个“可能解”，一个基因即是“可能解”的一个编码位或若干编码位的一个组合。

B）一个种群即是一个包含问题满意解的“可能解”的集合。

C）适应度，即是对“可能解”的一个度量，它可以衡量“可能解”接近最优解或精确解的程度。

D）复制、交叉、变异等都是产生新“可能解”的方式。

解释：

本题考核对生物学中的概念与计算机中的概念的映射的理解。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：B 染色体映射到计算机中就是编码解，即一个可能解的基因型。一个基因即是指可能解的某一位或几位，A正确。种群是指若干可能解的集合，而不一定包含问题的满意解，B错误。适应度性是指一个可能解接近最优解的一个度量，C正确。复制、交叉、变异等都是产生新“可能解”的方式，D正确。

4. 简述三个遗传算子。

解释：

本题考查遗传算法的核心算子的特点与作用。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

遗传算子是模拟生物进化过程最关键的进化机制，包括选择算子、交叉算子和变异算子，它们是遗传算法的核心和基本算子。

（1）选择算子

选择是为了从当前种群中选出优良的个体，使它们有机会作为父代来繁殖子代。进化过程中是根据各个个体的适应度值，按照一定的规则或方法从上一代种群中选择出一些优良的个体遗传到下一代种群中，遗传算法正是通过选择算子的操作来体现这一思想，而进行选择的原则是适应度值高的个体为下一代贡献一个或多个子代的概率大，这是生物能够保持性状而达到物种稳定的最主要原因。

（2）交叉算子

交叉算子又称为交换算子，它同时对两个染色体的部分基因进行交换，是遗传算法中最主要的遗传操作。它的作用是不断产生新的染色体，避免算法陷入局部最优。

（3）变异算子

遗传算法在选择算子和交叉算子的作用下已经能起到种群进化的作用，但在这个过程中，算法无法保证一些重要的遗传信息不丢失。因此，仅仅依靠这两种遗传操作，算法缺乏搜索整个解空间的能力，并且所获得的解可能是局部最优解。在生物的遗传和进化过程中，生物的某些基因偶尔会发生变异，从而产生出新的个体，虽然其概率比较小，但对新物种的产生也是一个不可忽视的因素。为了模仿生物遗传和进化过程中的这种变异现象，在遗传算法中引入了变异算子来产生新的个体，在迭代过程中较好地扩展了算法的搜索空间，使算法有能力在整个解空间进行鲁棒搜索而不会陷入局部最优。

5. 讨论交叉率的重要性，讨论范围[0, 1]内的不同值的效果。

解释：

本题考查遗传算法交叉率的影响。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

交叉概率控制着交叉算子的应用概率。较大的交叉概率可使各代充分交叉，产生更多的新解，使算法的探索能力增强，但同时种群中的优良模式遭到破坏的可能性也增大，以致产生较大的代沟，从而使搜索走向随机化；若交叉概率太低，就会使得更多的个体直接复制到下一代，遗传搜索可能陷入停滞状态。一般取cP=0.50～0.85。

6. “以高变异率开始进化，随着代数的增加，递减变异率”该策略是否有意

义？为什么？

解释：

本题考查遗传算法变异率的影响。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

变异操作是对遗传算法的改进，对交叉过程中可能丢失的某种遗传基因进行修复和补充，也可防止遗传算法较快收敛到局部最优解。若变异概率取值较大，虽然能够产生较多的个体，增加了种群的多样性，但也有可能破坏掉很多好的模式，使得遗传算法的性能近似于随机搜索的性能；若变异概率较小，虽然种群的稳定性较好，但一旦陷入局部极值就很难跳出来，容易产生早熟收敛。

在进化初期应该保持较高的变异率，从而能够充分的对解空间进行探索，维护种群多样性，避免陷入局部最优；在进化中后期，由于对解空间的探索已经较为充分，应该加强对最优解附近的开发力度，从而保证算法的收敛性。所以“以高变异率开始进化，随着代数的增加，递减变异率”策略具有意义。

7. 在遗传算法中，变量x取0到63之间的整数值，如何对x进行二进制

编码？

解释：

本题考查遗传算法如何进行二进制编码。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

因为x取值是0到63之间的整数，可以使每一个染色体长度均为6的二进制位串，其编码结果为000000至111111的64个染色体。

8. 在利用遗传算法解决旅行商问题时，若对下列一个染色体进行变异操作，

请写出变异结果。（假设变异点基因位置为3位和5位）

A：2 8 4 10 5 1 7 3 6 9

解释：

本题考查遗传算法求解TSP问题时变异操作的施行。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

将3位和5为基因进行互换，得变异结果为'A：2 8 5 10 4 1 7 3 6 9

9. 在利用遗传算法解决旅行商问题时，若采用基于位置的交叉方式对下列

两个染色体进行交叉，请写出交叉结果。

A：2 8 4 10 5 1 7 3 6 9

B：5 6 7 1 10 2 8 3 9 4

解释：

本题考查遗传算法求解TSP问题时交叉操作的施行。 具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

（1）两父代染色体串为：

A：2 8 4 10 5 1 7 3 6 9

B：5 6 7 1 10 2 8 3 9 4

得到3组映射关系：

4

7 5 10 3 3

（2）对于染色体A，依据3组映射关系，三个基因4、5、3应该分别变为7、10、3，同时染色体中原来为7、10、3的基因改成4、5、3，其中基因3与本身交换，即不变。得到A的子代染色体A：

A：2 8 4 10 5 1 7 3 6 9

A：2 8 7 5 10 1 4 3 6 9

（3）对染色体B，依据3组映射关系，三个基因7、10、3应该分别变为4、5、3，同时染色体中原来为4、5、3的基因改成7、10、3，其中基因3与本身交换，即不变。得到B的子代染色体B：

B：5 6 7 1 10 2 8 3 9 4

B：10 6 4 1 5 2 8 3 9 7

交叉操作的结果为：

'A：2 8 7 5 10 1 4 3 6

'B：10 6 4 1 5 2 8 3 9

10. 遗传算法是一种算法设计策略。不同的问题甚至相同的问题都可以设计

不同的遗传算法进行求解，不同的遗传算法可能解编码的不同、交叉与变异规则的不同、概率模型的选择不同等。

（1）如何衡量遗传算法的性能好坏，下列说法正确的是_____。

合集下载

第三章-遗传算法的理论基础

第三章-遗传算法的理论基础

第三章 遗传算法的理论基础

遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。

3.1 模式定理

不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。

定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。

以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。

引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容

定义3.2 模式H中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。

显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。

定义3.3 模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。

第一章 遗传算法概述

第一章 遗传算法概述

1 第一章 遗传算法概述

遗传算法(Genetic Algorithm，简称GA)起源于对生物系统所进行的计算机模拟研究。美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本定理——模式定理(Schema

Theorem)，并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation

in Natural Land Artificial Systems》。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975年，De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989年，Goldberg出版了《Genetic Algorithm in Search，Optimization and Machine Learning》一书，系统地总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用。1991年，Davis出版了《Handbook of Genetic

Algorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic

Programming，简称GP)的概念。遗传算法被众多的使用者证明在控制系统的离线设计方面是有效的策略。例如， Krishnakumar和Goldberg 以及 Bramlette和Cusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell(鲍威尔) 的增音机设计所用的时间要少(功能评估)。Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法怎么能在控制器结构的选择中使用。

第三章 遗传算法的理论基础

第三章 遗传算法的理论基础

31 第三章 遗传算法的理论基础

遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。

3.1 模式定理

不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。

定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。

以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。

引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容

定义3.2 模式H中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。

显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。

定义3.3 模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。

03第三章 遗传算法

03第三章 遗传算法

第三章 遗传算法 习题与答案

1. 填空题

（1）遗传算法的缩写是 ，它模拟了自然界中 过程而提出，可以解决 问题。在遗传算法中，主要的步骤是 、 、 。

（2）遗传算法的三个算子是 、 、 。

解释：

本题考查遗传算法的基础知识。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

（1）GA，生物进化，全局优化，编码，计算适应度函数，遗传算子

（2）选择，交叉，变异

2. 对于编码长度为7的二进制编码，判断以下编码的合法性。

（1）[1020110]

（2）[1011001]

（3）[0110010]

（4）[0000000]

（5）[2134576]

解释：

本题考查遗传算法的二进制编码的合法性。

具体内容请参考课堂视频“第3章遗传算法”及其课件。

答案：

（1）[1020110] 不合法，不能出现“2” （2）[1011001] 合法

（3）[0110010] 合法

（4）[0000000] 合法

（5）[2134576] 不合法，不能出现0、1以外的数字

3. 下图能够基本反映生物学遗传与优胜劣汰的过程。理解该图，联想计算

类问题求解，回答下列问题。

（1）下列说法正确的是_____。（多选）

A）任何一个生物个体的性状是由其染色体确定的，染色体是由基因及其有规律的排列所构成的，因此生物个体可由染色体来代表。

B）生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突变。基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配”。基因突变是指复制过程中基因信息的变异，简称“突变”。 C）不同染色体会产生不同生物个体的性状，其适应环境的能力也不同。