第9章怎样研究算法遗传算法示例练习题答案解析

大学计算机-计算思维练习题集

(B)生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突变。基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配”。基因突变是指复制过程中基因信息的变异，简称“突变”；

(C)不同染色体会产生不同生物个体的性状，其适应环境的能力也不同；

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

(E)上述说法有不正确的。 答案：E 解释：

本题考核对生物遗传观点以及所给图片的理解。 关于生物遗传进化的基本观点如下：

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

(ii) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上； (iii) 生物的繁殖过程是由其基因的复制过程来完成的；

(iv) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。 (v) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。

故（A）、（B）、（C）、（D）均正确。于是，（E）错误。

具体内容请参考课堂视频“遗传算法的缘起--生物学中的遗传与进化”和第九章课件。

(2-1)类比计算类问题求解，下列说法不正确的是_____。

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

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

(C)所谓的环境适应性，可以认为是对一个可能解的一种度量，即能够度量一个可能解的好与坏的某一函数值，被称为“适应度”；

大学计算机-计算思维练习题集

(D)基于(A)(B)(C)，遗传算法就是“通过复制、交叉或变异，不断产生新的可能解；计算可能解的适应度；淘汰掉适应度差的可能解，保留适应度好的可能解。”

(E)上述说法有不正确的； 答案：E 解释：

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

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

具体内容请参考课堂视频“计算学科的遗传算法”和第九章课件。

(2-2)类比计算类问题求解，下列说法不正确的是_____。

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

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

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

(D)复制、交叉、变异等都是产生新“可能解”的方式； (E)上述说法有不正确的；

答案：B 解释：

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

染色体映射到计算机中就是编码解，即一个可能解的基因型。一个基因即是指可能解的某一位或几位，（A）正确。种群是指若干可能解的集合，而不一定包含问题的满意解，（B）错误。

大学计算机-计算思维练习题集

适应度性是指一个可能解接近最优解的一个度量，（C）正确。复制、交叉、变异等都是产生新“可能解”的方式，（D）正确。因为（B）错误，故（E）正确。综上，本题答案为（B）。

具体内容请参考课堂视频“计算学科的遗传算法”和第九章课件。

3、类比生物遗传与优胜劣汰而形成的遗传算法的求解过程如下图示意。理解该图，回答下列问题。

(1)图中给出了遗传算法的基本求解过程示意。关于图中包含了哪些过程，下列说法正确的是_____。

(A)可能解的编码过程和初始种群的产生过程； (B)交叉、变异形成候选种群的过程；

(C)可能解的适应度计算过程和汰选可能解形成新一代种群的过程； (D)算法终止及最终解的形成过程； (E)上述全部过程。

答案：E 解释：

本题考查学生对遗传算法基本求解过程的理解。

图中第一行第一个箭头即是可能解的编码过程和初始种群的产生过程。最右的大方框内的即是交叉、变异形成候选种群的过程。右下方的方框以及箭头即是可能解的适应度计算过程和汰选可能解形成新一代种群的过程。左下的图与箭头即是算法终止及最终解的形成过程。综上，（E）正确。

大学计算机-计算思维练习题集

具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。

(2)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_____。

(A)初始种群中的可能解可以随机产生；

(B)对于哪两个可能解进行交叉，可以采取随机方式从种群中选择出来；

(C)对于两个可能解进行两段交叉，其交叉点是固定的，不可以采取随机方式确定； (D)对于哪个解进行变异，以及变异位置的确定，可以采取随机方式选择和确定； (E)上述有不正确的说法。

答案：C 解释：

本题考查学生对遗传算法随机性的理解。

在遗传算法中，所有的解的产生，以及交叉，变异等可以随机的产生，并不是固定的。所以（C）的说法不正确。

具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。

(3)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_____。

(A)种群的规模，即种群中可能解的个数是预先设定且固定不变的，其大小影响遗传算法求解的质量和效率；

(B)种群的规模，虽然是预先设定的，但其大小不会影响遗传算法求解的质量和效率； (C)种群的规模可以依据问题的所有可能解的个数来确定：太大，虽求解效果好但计算量却很大；太小，虽计算量很小，但求解效果却难以保证；

(D)种群规模不是随机确定的； (E)上述有不正确的说法。

答案：B 解释：

本题考查学生对遗传算法种群规模及其确定方法的理解。

在遗传算法的设计过程中，应该根据问题的具体情况设置合适的种群规模。如果规模过大，虽然求解效果好，但是计算量很大。如果规模太小，计算量虽然不大了，但是求解效果就难以保证了。所以，种群规模的大小一定会影响遗传算法求解的质量和效率。

具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题”以及第九章课件。

(4)依据图中示例及求解过程示意，思考并回答，下列说法不正确的是_____。

(A)遗传算法可以一个轮次一个轮次迭代地进行(被称为“进化”)，可以在迭代到一定次数后