大学计算机-计算思维练习题集
86minf(x)???cijxiji?1j?1 ……………………………(1)
s.t. s.t.
?axj?16ijij?1,foreveryi,i?1,...,8 ……………………………(2) ……………………………(3)
……………………………(4)
?ai?18ijijx??2,foreveryj,j?1,...,6xij?{0,1};i?1,...,8;j?1,...,6
关于该模型，下列说法不正确的是_____。
(A)公式(1)是计算某一种方案---该方案给出了哪一门课程安排在哪个教室的一种安排，计算该方案的总成本，目标是求具有最小总成本的那个方案。其中教室被从1,…,n编号，课程被从1,…,m编号。如果xij=1，表示课程i被安排在教室j；如果xij=0，表示课程i未被安排在教室j；cij表示选择课程i安排在教室j时所需消耗的成本。
(B)公式(2)表示每一门课程至少被安排在1个教室，也可以安排在多个教室； (C)公式(3)表示每一个教室至多安排2门课程，也可以不安排课程； (D)公式(4)说明xij只能等于0或1。等于1表示课程i被安排在教室j；等于0则表示课程i与课程j没有关系； (E)上述说法有不正确的。
答案：B 解释：
本题考查对数学模型的理解能力；
选项（A）的说法没有问题。公式（2）表示一门课程恰好被安排在一个教室。而不是（B）选项中的“每一门课程至少被安排在1个教室，也可以安排在多个教室”。（B）的说法正确。（C）（D）的说法也没有问题。综上，本题的答案为（B）。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题2”以及第九章课件。
7、对类似于遗传算法的理解，需要理解关于各种解的名词之间的细微差别。 (1)下列说法正确的是_____。 (A)可行解集合?近似解集合?可能解集合?满意解集合?最优解集合；
(B)可能解集合?可行解集合?满意解集合?近似解集合?最优解集合； (C)可能解集合?可行解集合?近似解集合?满意解集合?最优解集合； (D)最优解集合?满意解集合?近似解集合?可行解集合?可能解集合； 答案：C 解释：
大学计算机-计算思维练习题集
本题考查对关于“解”的一些名词的理解；
可能解中包含可行解。可行解中包含近似解。近似解中包含满意解。满意解中包含最优解。（C）选项的说法是正确的。综上，本题的答案为（C）。
具体内容请第九章参考课堂视频与第九章课件。
(2-1)设一个问题的解的形式为x，下列说法不正确的是_____。 (A)由x的取值空间给定的任何一个x值被称为可行解；
(B)由一个算法在任何一组可行解中求出的最优解被称为是近似解； (C)符合用户期望的近似解被称为是满意解； (D)所有可行解中的最优解是问题的最优解； (E)上述说法有不正确的；
答案：A 解释：
本题考查对关于“解”的一些名词的理解； 由x的取值空间给定的任何一个x值为可能解。该x的值能满足问题的要求，该x才被称为一个可行解。（A）的说法不正确。（B）（C）（D）的说法都是正确的。综上，此题的答案为（A）。
具体内容请第九章参考课堂视频与第九章课件。
(2-2)设一个问题的解的形式为x，下列说法不正确的是_____。 (A)由x的取值空间给定的任何一个x值被称为可能解； (B)满足问题约束的可能解被称为可行解；
(C)在任何一组可行解中求出的最优解被称为是满意解； (D)所有可行解中的最优解是问题的最优解； (E)上述说法有不正确的；
答案：C 解释：
本题考查对关于“解”的一些名词的理解； 由x的取值空间给定的任何一个x值为可能解。该x的值能满足问题的要求，该x才被称为一个可行解。（A）（B）的说法正确。由一个算法在任何一组可行解中求出的最优解被称为是近似解,符合用户期望的近似解被称为是满意解,(C)的说法不正确。（D）的说法正确。综上，此题的答案为（C）。
具体内容请第九章参考课堂视频与第九章课件。
大学计算机-计算思维练习题集
868、对于类似于课程表优化安排问题的二维集覆盖问题：minf(x)???ci?1j?1ijijx，利用遗传算
法计算求解，回答下列问题。
(1)关于其可能解的编码，说法正确的是_____。 (A)仅可以按行优先编码；
(B)仅可以按列优先编码；
(C)既可以按行优先编码，又可以按列优先编码，但其对算法中交叉、变异操作规则设计是没有影响的；
(D)既可以按行优先编码，又可以按列优先编码，还可以有其他编码方式，不同的编码设计，可以有不同的交叉、变异操作规则；
答案：D 解释：
本题考查对问题解的编码的多样性；
二维集覆盖问题的可能解的都是二维矩阵。对于二维矩阵的编码可以有多种形式。每一种编码方式，都可以有自己的交叉、变异操作规则。（D）的说法是正确的。（A）（B）（C）的说法都不正确。综上，本题的答案为（D）。
具体内容请第九章参考课堂视频“怎样用遗传算法解决具体的应用问题2”与第九章课件。
(2)关于交叉规则的设计，下列说法不正确的是_____。 (A)既可以采取两段交叉，也可以采取多段交叉；
(B)两段交叉中，交叉点的选择可以随机确定：即随机确定一个交叉点，从中将解编码分为两段，将两个可能解的两段编码交换形成两个新的可能解；
(C)多段交叉既可采取等距离分段交叉，亦可采取可变距离分段交叉，交叉点和段间距离都可以随机的确定；
(D)交叉规则仅有以上(A)(B)(C)几种情况；
(E)对不同的问题，还可能有不同的交叉规则设计；
答案：D 解释：
本题考查对交叉规则设计多样性的认识；
交叉规则具有多样性。不仅可以采用两段交叉、多段交叉，根据不同的问题，还可以采用点交叉、行交叉、列交叉、块交叉等。所以（D）的说法是不正确的。因此，此题的答案为（D）。
具体内容请第九章参考课堂视频“怎样用遗传算法解决具体的应用问题5”与第九章课件。
大学计算机-计算思维练习题集
(3)关于交叉规则的设计，下列说法不正确的是_____。 (A)可以采取基本的两段交叉或多段交叉；
(B)可以采取点交叉、行交叉或列交叉；
(C)可以不以“位”为单位进行交叉，而以若干位的一个组合为单位进行交叉； (D)交叉规则仅有以上(A)(B)(C)几种情况；
答案：D 解释：
本题考查对结合问题特征进行交叉规则设计的认识；
交叉规则十分的丰富。（A）（B）（C）均为交叉规则。但交叉规则不仅仅限于此。还可以采用交叉与随机的交叉规则，如：两个染色体的各段的x位如都相同，则不交换，否则以概率p进行交换。具体问题具体分析。 具体内容请第九章参考课堂视频“怎样用遗传算法解决具体的应用问题5”与第九章课件。
9、遗传算法的设计在很多方面都需要引入概率，在哪些方面引入概率呢？下列说法不正确的是_____。 (A)初始种群的确定可以引入概率。结合问题可能解的分布选择概率模型，将此概率模型引入初始解的随机选择过程中，则选择出的初始可能解有助于遗传算法快速地获得满意解；
(B)交叉规则设计可以引入概率。从待交叉两个可能解的确定，到交叉点的确定，甚至到段间距离的确定等都可以引入概率，恰当的概率模型选择有助于遗传算法快速地获得满意解；
(C)遗传算法处处体现着概率的应用和随机处理。当可能的方案比较多，且穷举计算量很大时，便可采用概率方式进行随机化处理。例如两个可能解“00001000 10001100”“00111000 1011 1100”，如果做两段交叉，则分段交叉点可以有16个，如果16个交叉点都选择，则可能该子解空间仍旧很大，此时可依概率选择1号位置交叉至16号位置交叉，选择几个则依概率模型确定，选择1个至16个中的某些个；
(D)虽然遗传算法处处可以引入概率，但其概率模型却是相同的； (E)上述说法有不正确的。
答案：D 解释：
本题考查对遗传算法引入概率的认识；
遗传算法处处都可以引入概率。（A）（B）（C）都是在在遗传算法中加入概率的例子。在（A）（B）（C）描述的例子中，都引入了概率。常见的概率模型有：古典概型 ，几何概型，连续变量，离散变量，正态模型，泊松模型，指数模型等。可以根据不同的情况选择不同的模型。
大学计算机-计算思维练习题集
所以（D）的说法是不正确的。综上，此题的答案为：（D）。
具体内容请第九章参考课堂视频“怎样用遗传算法解决具体的应用问题5”与第九章课件。
10、遗传算法设计需要引入变异操作。变异操作是对种群中的某些可能解(个体)的某些编码位进行突变处理，例如二进制编码的解01110011，其第3位(自左而右)当前为1则将其变为0，称为变异操作。关于变异操作，回答下列问题。
(*1)关于如何应用变异操作，下列说法不正确的是_____。 (A)对种群中所有可能解(个体)以事先设定的变异概率确定是否进行变异；
(B)对进行变异的可能解(个体)随机选择变异位置进行相应位置的“位”变异； (C)对进行变异的可能解(个体)随机选择变异位置进行相应位置的“位组合”变异； (D)变异概率应选取较大值，即：使变异频繁发生，这样有助于快速收敛到满意解； (E)上述说法有不正确的。
答案：D 解释：
本题考查对遗传算法中关于变异的认识。 选项(D)中，变异概率：控制算法中变异操作的使用频率，实际情况下变异发生的频率并非越频繁越好，当变异概率无限增大的时候，遗传算法就变为纯随机搜索了，因此变异概率并不是可以无限扩大的，即在一定条件下使变异概率尽量大有助于快速收敛到满意解。
具体内容请参考课堂视频“怎样用遗传算法求解具体的应用问题(IV)”和第九章课件。
(2)通过变异操作，使遗传算法具有局部的随机搜索能力。为什么？下列说法不正确的是_____。
(A)当产生一个可行解时，可以在该解的邻近解的集合中进行搜索，被称为局部搜索；该解的邻近解的集合是变化的，例如与该解有一位不同的邻近解、与该解有两位不同的邻近解，或者与该解有一个“位组合”不同的邻近解等；
(B)当产生一个可行解时，由于与该解的邻近解的集合可能很大，并不能穷举每一个邻近解，所以需要随机选择邻近解；
(C)当产生一个可行解时，通过某一位或几位的变异，便可产生该解相邻近的解。即相当于，以该解为中心，在与该解的邻近解的集合中随机选择出某个解；
(D)当产生的可行解接近最优解的邻域时，通过某一位或几位的变异，便可产生该解相邻近的解，此有助于使算法加速向最优解收敛；
(E)上述说法有不正确的。
答案：E 解释：
本题考查对遗传算法中关于变异的认识。