大学计算机-计算思维练习题集
选项(A)(B)(C)(D)均为正确选项。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
(3)通过变异操作，使遗传算法可维持群体多样性。为什么？下列说法不正确的是_____。
(A)由于初始解设置或经多次迭代后，很可能使一代种群中的各个可能解具有相似的结构，此时无论怎样交叉产生的新可能解，都将在与该结构相近的可能解空间搜索--这种现象被称为过早收敛；
(B)为避免过早收敛，有必要保持种群个体的多样性，即使种群中的可能解具有不同的结构，怎样保持不同的结构，即通过变异，打破原有相似的结构，进入到另外的空间中搜索；
(C)当进化到某一代时，种群的解可能具有相类似的结构，可能始终在这个类似结构的解集合中进行循环，为避免这种情况， 通过对一些解应用变异操作，打破种群的解的相类似结构，有助于跳出循环，在更大空间中进行搜索；
(D)当产生的可行解接近最优解的邻域时，应谨慎使用变异，以免偏向最优解的结构被破坏；而当产生的可行解并未接近最优解的邻域时，可以选择较大的变异概率以保证种群解的多样性；
(E)上述说法有不正确的。
答案：E 解释：
本题考查对遗传算法中关于变异的认识。 选项(A)(B)(C)(D)均为正确选项。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
11、遗传算法是迭代计算求解的方法。如何终止遗传算法，下列说法正确的是_____。
(A)当适应度已经达到饱和，继续进化不会产生适应度更好的近似解时，可终止遗传算法； (B)当某一个可行解已经满足满意解的条件，即满意解已经找到，可终止遗传算法；
(C)当进化到指定的代数(进化次数限制)或者当达到一定的资源占用量(计算耗费的资源限制，如计算时间、计算占用的内存等)时可终止算法，如当产生超过一定数量的不重复可行解后即可终止；
(D)仅有上述(A)(B)(C)几种终止遗传算法的情况；
答案：D 解释：
本题考查遗传算法如何终止的问题。
选项(A)终止后可以得到相对接近最优解的结果，理论上不存在更接近最优解的其他结果；选项(B)终止后可以得到满意解，但理论存在更符合条件的结果；选项(C)无法得到全部可行解，但可满足题意得到结果；但单独选择(A)(B)(C)均不全面，因此选择(D)。
大学计算机-计算思维练习题集
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
12、遗传算法是一种算法设计策略。不同的问题甚至相同的问题都可以设计不同的遗传算法进行求解，不同的遗传算法如可能解编码的不同、交叉与变异规则的不同、概率模型的选择不同等。 (1)如何衡量遗传算法的性能好坏，下列说法正确的是_____。
(A)对一些已知最优解的问题类别，可以通过精确算法获得最优解，然后使用“近似率”来衡量解的质量。所谓近似率是指算法求得的解与问题最优解的近似程度。则有：近似率越高的遗传算法，性能越好；
(B)对理论最优解不知道的问题类别，可以通过不同遗传算法在相同问题实例集上测试结果的横向比较来进行评价，即有：在执行相同次数的迭代后，获得满意解越好的遗传算法，性能越好； (C)对于具有迭代特征的近似算法，在迭代多少次后能够使得结果稳定(通俗来讲，即结果不再随进一步迭代而发生变化或发生极小的可以被忽略的变化)—这被称为收敛速度，它从一定程度反映了算法求解的“快慢”。在达到期望的满意解的前提下，迭代次数越少越好。 (D)遗传算法不一定能够得到满意解。因此，当不同算法均应用多次后，求得满意解次数越多的算法越好！ (E)除上述衡量性能的指标外，还有其他的指标来衡量性能。
答案：E 解释：
本题考查如何衡量遗传算法的性能。
选择(E)，(A)(B)(C)(D)均不全面，其他指标，诸如获得满意解所花费的平均时间以及占用的系统资源都可以列为衡量算法性能的指标。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
(2)如何衡量遗传算法的性能好坏，下列说法不正确的是_____。
(A)近似率越高的算法，性能越好；
(B)在执行相同次数的迭代后，获得满意解越好的算法，性能越好； (C)在达到期望满意解的前提下，迭代次数越多的算法，性能越好； (D)当不同算法均应用多次后，求得满意解次数越多的算法，性能越好！
答案：C 解释：
本题考查如何衡量遗传算法的性能。 (A)(B)(D)正确，(C)迭代次数多性能差。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
大学计算机-计算思维练习题集
(3)如何衡量遗传算法的性能好坏，下列说法不正确的是_____。
(A)近似率越低的算法，性能越好；
(B)在执行相同次数的迭代后，获得满意解越好的算法，性能越好； (C)在达到期望满意解的前提下，迭代次数越少的算法，性能越好； (D)当不同算法均应用多次后，求得满意解次数越多的算法，性能越好！
答案：A 解释：
本题考查如何衡量遗传算法的性能。 (B)(C)(D)正确，(A)近似率低性能差。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
13、八皇后问题的遗传算法求解。八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。下图给出了八皇后问题的一个解。回答下列问题。
(1-1)八皇后问题的建模。将棋盘抽象为n×n的矩阵(此时n=8，但抽象不限于n=8，可以是n皇后问题)，Aij=1表示放置皇后，Aij=0表示未放置皇后，其目标函数为
??Ai?1j?1nnij?n。因此八皇后
问题求解的关键是设计约束条件，即满足什么条件的可能解才是可行解，而任何一个可行解都为满意解。有四个公式，表达了某种约束条件(注意，不能确定给出的公式一定是正确的)，下列说法不正确的是_____。
大学计算机-计算思维练习题集
n(式1)
?Ai?1ij?1foranyj?1,...,n
(式2)
?Aj?1nnij?1foranyi?1,...,n
(式3)
?Ai?1i,i?k??1foranyk??(n?2),...,n?2且Ai,h?0foranyh?norh?1
(式4)
?Ai?1nn?1?i?k,i??1foranyk??(n?2),...,n?2且Ah,i?0foranyh?norh?1
(A)式1表达了任何一列中的皇后个数只能有一个；式2表达了任何一行中的皇后个数只能有一个；
(B)式3表达了一条斜线上的皇后个数不能多于1个； (C)式3和式4必须同时具备才能表达任何一条斜线上的皇后个数不能多于1个； (D)式3和式4中关于h的相关内容是没有必要的；
答案：D 解释：
本题考查遗传算法的实际应用。
选项(D)错误，关于h的相关内容是有必要的。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(I)-(IV)”和第九章课件。
(*1-2)八皇后问题的建模。将棋盘抽象为n×n的矩阵(此时n=8，但抽象不限于n=8，可以是n皇后问题)，Ai,j=1表示放置皇后，Ai,j=0表示未放置皇后，其目标函数为
??Ai?1j?1nni,j?n。因此八
皇后问题求解的关键是设计约束条件，即满足什么条件的可能解才是可行解，而任何一个可行解都为满意解。有三个公式，表达了某种约束条件(注意，不能确定给出的公式一定是正确的)，下列说法不正确的是_____。 (式1)
?Ai?1ni,j?1，对任何j?1,...,n
(式2)
?Aj?1ni,j?1，对任何i?1,...,n
大学计算机-计算思维练习题集
(式3)
z?y?1 ，对任何两个位置其值为1的点Ax,y，As,z s?x
(A)式1表达的是任何一列中的皇后个数只能有一个； (B)式2表达的是任何一行中的皇后个数只能有一个；
(C)式3表达的是任何两个皇后不能位于同一条45度或135度斜线上； (D)上述有不正确的；
答案：C 解释：
本题考查遗传算法的实际应用。
选项(C)错误，式3表达的是皇后不能位于（1,1）到（8,8）连接的45度对角线，但可以在其他45度对角线或135度对角线上。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(I)-(IV)”和第九章课件。
(*1-3)八皇后问题的建模。将棋盘抽象为n×n的矩阵(此时n=8，但抽象不限于n=8，可以是n皇后问题)，Aij=1表示放置皇后，Aij=0表示未放置皇后，其目标函数为
??Ai?1j?1nnij?n。下面有若
干个公式，表达了某种约束条件(注意，不能确定给出的公式一定是正确的)。回答下列问题。 (式1)
?Ai?1nij?1foranyj?1,...,n
(式2)
??cj?1i?1nnnijAij??nforanyj?1,...,n;foranyi?1,...,n
(式3)
?Aj?1nij?1foranyi?1,...,n
(式4)
?Ai?1i,i?k??1foranyk??(n?2),...,n?2且Ai,h?0foranyh?norh?1
(式5)
?Ai?1nn?1?i?k,i??1foranyk??(n?2),...,n?2且Ah,i?0foranyh?norh?1