第9章怎樣研究算法遺傳算法示例練習(xí)題答案解析

1、大學(xué)計算機-計算思維練習(xí)題集第9章 怎樣研究算法:遺傳算法示例1、P類問題、NP類問題、NPC類問題是計算機科學(xué)領(lǐng)域關(guān)于可求解性可計算性很重要的概念。關(guān)于P、NP和NPC類問題，回答下列問題。(1)下列說法不正確的是_。(A) P類問題是計算機可以在有限時間內(nèi)能夠求解的問題；(B) NP類問題是計算機可以在有限時間內(nèi)能夠驗證“解”的正確性的問題；(C) NPC類問題是對問題的每一個可能解，計算機都可以在有限時間內(nèi)驗證“解”的正確性的問題，被稱為NP完全問題；(D)上述說法有不正確的；答案：D解釋：本題考核P類問題、NP類問題、NPC類問題的概念。P類問題指計算機可以在有限時間內(nèi)求解的問題，(A

2、)正確；NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性問題，(B)正確；NPC問題指NP問題的所有可能答案都可以在多項式時間內(nèi)進行正確與否的驗算，稱為NP-Complete問題，(C)正確；(A)(B)(C)都正確，所以(D)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(2)可解性問題是指能夠找到多項式時間復(fù)雜性算法進行求解的問題，難解性問題是指找不到多項式時間復(fù)雜性算法進行求解的問題。下列說法不正確的是_。(A) P類問題是可解性問題，NP類問題是難解性問題。(B) NP類問題不一定是難解性問題，因為P類問題也一定是NP類問題；(C) NP類問題

3、不確定是否是P類問題，但NPC類問題一定是難解性問題；(D)上述說法有不正確的；答案：A解釋：本題考核對可解性問題和難解性問題概念的理解。P類問題指計算機可以在有限時間內(nèi)求解的問題，所以是可解性問題；NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性問題，但P類問題是NP類問題的一個子集，所以NP類問題不一定是難解性問題；NPC問題指NP問題的所有可能答案都可以在多項式時間內(nèi)進行正確與否的驗算，稱為NP-Complete問題，是難解性問題，綜上，(A)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(3)下列說法正確的是_。(A) P類問題是計算機可以在有

4、限時間內(nèi)能夠求解的問題；(B) NP類問題是計算機可以在有限時間內(nèi)能夠求解的問題；(C) NPC類問題是計算機可以在有限時間內(nèi)能夠求解的問題；(D)上述說法都正確；答案：A解釋：本題考核P類問題、NP類問題、NPC類問題的概念。只有P類問題是計算機可以在有限時間內(nèi)能夠求解的問題，所以(A)正確。具體內(nèi)容請參考第九講視頻之“可求解與難求解問題”以及第九章課件。(4)P類問題是多項式問題(Polynomial Problem)，NP類問題是_。(A) 非多項式問題；(B) 非確定性多項式問題；(C) 非P類問題；(D) 確定性非多項式問題；(E) 上述說法都正確；答案：B解釋：本題考核對NP類問題

5、的理解。P類問題是多項式問題(Polynomial Problem)，NP類問題是非確定性多項式問題(Non-deterministic Polynomial)，NPC問題是完全非確定性多項式問題(NP-Complete)，所以(B)正確。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(5)下列說法不正確的是_。(A) P類問題是總能找到一個多項式時間復(fù)雜性算法進行求解的問題；(B) NP類問題是一定找不到多項式時間復(fù)雜性算法進行求解的問題；(C) NP類問題是不確定能夠找到多項式時間復(fù)雜性算法進行求解的問題；(D) NP類問題雖然是不確定能找到多項式時間復(fù)雜性算法進行求解，

6、但一定能找到多項式時間復(fù)雜性算法進行“解”的正確性驗證的問題；(E) 上述說法有不正確的；答案：B解釋：本題考核對P類問題、NP類問題概念的理解。P類問題是總能找到一個多項式時間復(fù)雜性算法進行求解的問題，NP類問題雖然是不確定能找到多項式時間復(fù)雜性算法進行求解，但一定能找到多項式時間復(fù)雜性算法進行“解”的正確性驗證的問題，所以(B)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。(*6)非確定性多項式問題是指這樣的問題，下列說法不正確的是_。(A)它能夠找到一個算法、甚至是多項式時間復(fù)雜性算法進行求解，但算法中包含“不確定性”，如“任意組合一個解，”、“隨機組合一個解，”

7、等；(B)它能夠找到一個算法、甚至是多項式時間復(fù)雜性算法進行求解，但算法是通過“猜測”方式求出問題的解；(C)它能夠通過“產(chǎn)生任何一個解，并驗證解的正確性”的方法進行求解；(D)它一定是能夠找到多項式時間復(fù)雜性算法以驗證給定“解”的正確性的問題；(E)上述說法有不正確的；答案：E解釋：本題考核對NP類問題概念的理解。NP類問題：非確定性多項式問題(Non-deterministic Polynomial)。有些問題，其答案是無法直接計算得到的，只能通過間接的猜算或試算來得到結(jié)果，這就是非確定性問題(Non-deterministic)。雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性的問

8、題，即：在多項式時間內(nèi)可以由一個算法驗證一個解是否正確的非確定性問題，所以(A)(B)(C)(D)都是正確的，(E)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。 (7)、關(guān)于NP類問題求解，下列說法正確的是_。(A)NP類問題求精確解，可能找不到多項式時間復(fù)雜性算法；但NP類問題求近似解，則一定能夠找到多項式時間復(fù)雜性算法；(B)NP類問題求精確解，可能找不到多項式時間復(fù)雜性算法；但NP類問題求近似解，則也可能找不到多項式時間復(fù)雜性算法；(C)雖然能夠找到求NP類問題近似解的多項式時間復(fù)雜性算法，但所求得的解一定不是滿意解；(D)既然能夠找到求NP類問題近似解的多項式

9、時間復(fù)雜性算法，則所求得的解就一定是滿意解；(E)上述說法都正確；答案：A解釋：本題考核對NP類問題求解的理解。NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性的問題，即：在多項式時間內(nèi)可以由一個算法驗證一個解是否正確的非確定性問題，所以NP類問題求精確解，可能找不到多項式時間復(fù)雜性算法，但NP類問題求近似解，則一定能夠找到多項式時間復(fù)雜性算法，(A)正確(B)錯誤；雖然能夠找到求NP類問題近似解的多項式時間復(fù)雜性算法，但所求得的解不一定是滿意解，(C)(D)錯誤。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題”以及第九章課件。2、下圖能夠基本反映生物學(xué)遺傳與優(yōu)勝劣汰的過程。

10、理解該圖，聯(lián)想計算類問題求解，回答下列問題。(1)下列說法不正確的是_。(A)任何一個生物個體的性狀是由其染色體確定的，染色體是由基因及其有規(guī)律的排列所構(gòu)成的，因此生物個體可由染色體來代表；(B)生物的繁殖過程是通過將父代染色體的基因復(fù)制到子代染色體中完成的，在復(fù)制過程中會發(fā)生基因重組或基因突變。基因重組是指同源的兩個染色體之間基因的交叉組合，簡稱為“雜交/交配”?；蛲蛔兪侵笍?fù)制過程中基因信息的變異，簡稱“突變”； (C)不同染色體會產(chǎn)生不同生物個體的性狀，其適應(yīng)環(huán)境的能力也不同；(D)自然界體現(xiàn)的是“優(yōu)勝劣汰，適者生存”的叢林法則。不適應(yīng)環(huán)境的生物個體將被淘汰，自然界生物的生存能力會越來越

11、強；(E)上述說法有不正確的。答案：E解釋：本題考核對生物遺傳觀點以及所給圖片的理解。關(guān)于生物遺傳進化的基本觀點如下：生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀；(ii) 染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進化過程發(fā)生在染色體上；(iii) 生物的繁殖過程是由其基因的復(fù)制過程來完成的；(iv) 通過同源染色體之間的交叉或染色體的變異會產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(v) 對環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機會遺傳到下一代。 故（A）、（B）、（C）、（D）均正確。于是，（E）錯誤。具體內(nèi)容請參考課堂視頻“遺傳算法的緣起-生物學(xué)中的

12、遺傳與進化”和第九章課件。(2-1)類比計算類問題求解，下列說法不正確的是_。(A)一個染色體即是指問題的一個“可能解”。任何“可能解”都可以表達為編碼形式，構(gòu)成編碼的基本單位即是基因； (B)所謂的復(fù)制、雜交、突變，是指一個可能解或兩個可能解之間發(fā)生的、編碼片段之間的復(fù)制、交叉或變異，它們都是產(chǎn)生新可能解的一種方式；(C)所謂的環(huán)境適應(yīng)性，可以認(rèn)為是對一個可能解的一種度量，即能夠度量一個可能解的好與壞的某一函數(shù)值，被稱為“適應(yīng)度”；(D)基于(A)(B)(C)，遺傳算法就是“通過復(fù)制、交叉或變異，不斷產(chǎn)生新的可能解；計算可能解的適應(yīng)度；淘汰掉適應(yīng)度差的可能解，保留適應(yīng)度好的可能解?！?E)上

13、述說法有不正確的；答案：E解釋：本題考核對生物學(xué)中的概念與計算機中的概念的映射的理解。染色體映射到計算機中就是編碼解。（A）正確。復(fù)制是指將一個解從一個解集復(fù)制到另外一個解集。雜交是指對兩個可能解的編碼通過交換某些編碼位而形成兩個新的可能解的遺傳操作，是新可能解的一種形成方式。突變是指隨機地改變一個可能解的編碼的某些片段(或基因)而使一個可能解變?yōu)橐恍碌目赡芙獾倪z傳操作 ，也是新解的一種形成方式。（B）正確。適應(yīng)度性是指一個可能解接近最優(yōu)解的一個度量。（C）正確。由（A）（B）（C），可以得到遺傳算法的基本思想。（D）正確。故（E）錯誤。綜上，（E）錯誤。具體內(nèi)容請參考課堂視頻“計算學(xué)科的遺傳

14、算法”和第九章課件。(2-2)類比計算類問題求解，下列說法不正確的是_。(A)一個染色體即是指問題的一個“可能解”，一個基因即是“可能解”的一個編碼位或若干編碼位的一個組合； (B)一個種群即是一個包含問題滿意解的“可能解”的集合；(C)適應(yīng)度，即是對“可能解”的一個度量，它可以衡量“可能解”接近最優(yōu)解或精確解的程度；(D)復(fù)制、交叉、變異等都是產(chǎn)生新“可能解”的方式；(E)上述說法有不正確的；答案：B解釋：本題考核對生物學(xué)中的概念與計算機中的概念的映射的理解。染色體映射到計算機中就是編碼解，即一個可能解的基因型。一個基因即是指可能解的某一位或幾位，（A）正確。種群是指若干可能解的集合，而不一

15、定包含問題的滿意解，（B）錯誤。適應(yīng)度性是指一個可能解接近最優(yōu)解的一個度量，（C）正確。復(fù)制、交叉、變異等都是產(chǎn)生新“可能解”的方式，（D）正確。因為（B）錯誤，故（E）正確。綜上，本題答案為（B）。具體內(nèi)容請參考課堂視頻“計算學(xué)科的遺傳算法”和第九章課件。3、類比生物遺傳與優(yōu)勝劣汰而形成的遺傳算法的求解過程如下圖示意。理解該圖，回答下列問題。(1)圖中給出了遺傳算法的基本求解過程示意。關(guān)于圖中包含了哪些過程，下列說法正確的是_。(A)可能解的編碼過程和初始種群的產(chǎn)生過程；(B)交叉、變異形成候選種群的過程；(C)可能解的適應(yīng)度計算過程和汰選可能解形成新一代種群的過程； (D)算法終止及最終解

16、的形成過程； (E)上述全部過程。答案：E解釋：本題考查學(xué)生對遺傳算法基本求解過程的理解。圖中第一行第一個箭頭即是可能解的編碼過程和初始種群的產(chǎn)生過程。最右的大方框內(nèi)的即是交叉、變異形成候選種群的過程。右下方的方框以及箭頭即是可能解的適應(yīng)度計算過程和汰選可能解形成新一代種群的過程。左下的圖與箭頭即是算法終止及最終解的形成過程。綜上，（E）正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題”以及第九章課件。(2)依據(jù)圖中示例及求解過程示意，思考并回答，下列說法不正確的是_。(A)初始種群中的可能解可以隨機產(chǎn)生； (B)對于哪兩個可能解進行交叉，可以采取隨機方式從種群中選擇出來； (C

17、)對于兩個可能解進行兩段交叉，其交叉點是固定的，不可以采取隨機方式確定；(D)對于哪個解進行變異，以及變異位置的確定，可以采取隨機方式選擇和確定；(E)上述有不正確的說法。答案：C解釋：本題考查學(xué)生對遺傳算法隨機性的理解。在遺傳算法中，所有的解的產(chǎn)生，以及交叉，變異等可以隨機的產(chǎn)生，并不是固定的。所以（C）的說法不正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題”以及第九章課件。(3)依據(jù)圖中示例及求解過程示意，思考并回答，下列說法不正確的是_。(A)種群的規(guī)模，即種群中可能解的個數(shù)是預(yù)先設(shè)定且固定不變的，其大小影響遺傳算法求解的質(zhì)量和效率； (B)種群的規(guī)模，雖然是預(yù)先設(shè)定的，

18、但其大小不會影響遺傳算法求解的質(zhì)量和效率； (C)種群的規(guī)?？梢砸罁?jù)問題的所有可能解的個數(shù)來確定：太大，雖求解效果好但計算量卻很大；太小，雖計算量很小，但求解效果卻難以保證；(D)種群規(guī)模不是隨機確定的；(E)上述有不正確的說法。答案：B解釋：本題考查學(xué)生對遺傳算法種群規(guī)模及其確定方法的理解。在遺傳算法的設(shè)計過程中，應(yīng)該根據(jù)問題的具體情況設(shè)置合適的種群規(guī)模。如果規(guī)模過大，雖然求解效果好，但是計算量很大。如果規(guī)模太小，計算量雖然不大了，但是求解效果就難以保證了。所以，種群規(guī)模的大小一定會影響遺傳算法求解的質(zhì)量和效率。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題”以及第九章課件。(4)

19、依據(jù)圖中示例及求解過程示意，思考并回答，下列說法不正確的是_。(A)遺傳算法可以一個輪次一個輪次迭代地進行(被稱為“進化”)，可以在迭代到一定次數(shù)后終止；(B)遺傳算法一定可以求得滿意解或最優(yōu)解，它一定是在得到滿意解或最優(yōu)解時才終止； (C)遺傳算法必定涉及隨機處理，因為不僅僅是問題可能解的空間很大，而任何一個子解空間也都可能很大，窮舉是難以辦到的； (D)遺傳算法是以交叉操作為產(chǎn)生新可能解的主要操作，而以變異操作作為產(chǎn)生新可能解的輔助操作； (E)上述有不正確的說法。答案：B解釋：本題考查學(xué)生對遺傳算法的迭代性和求解質(zhì)量方面的理解。遺傳算法就是通過不斷的迭代來淘汰不好的解，留下好的解，（A）

20、正確。不是任何問題采用遺傳算法都可以得到滿意解或最優(yōu)解，因為遺傳算法中會有隨機的過程，算法每次執(zhí)行的結(jié)果都不盡相同，（B）的說法不正確。（C）（D）的說法都沒有問題。故此題的答案為（B）。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題”以及第九章課件。(5)依據(jù)圖中示例及求解過程示意，思考并回答，下列說法不正確的是_。(A)適應(yīng)度，主要用于考察一個可能解是否接近最優(yōu)解，以及接近的程度和方向，所以通常選擇極值函數(shù)(如最大值函數(shù)或最小值函數(shù))作為度量函數(shù)；(B)一般而言，通過將可能解代入一個極值函數(shù)(如最大值函數(shù)或最小值函數(shù))中獲得函數(shù)值，以該函數(shù)值作為適應(yīng)度的值；(C)一個問題，若要用

21、遺傳算法求解，則要能夠?qū)⑵溆成錇轭愃朴谇髽O值一樣的函數(shù)，即函數(shù)的極大值(或極小值)對應(yīng)了問題的最優(yōu)解/較優(yōu)解，這是問題數(shù)學(xué)建模的一種方向；(D)適應(yīng)度函數(shù)可以任取一個極值函數(shù)，它與求解問題本身可以沒有什么關(guān)系；(E)上述有不正確的說法。答案：D解釋：本題考查學(xué)生對遺傳算法的適應(yīng)度函數(shù)的理解。遺傳算法的適應(yīng)度函數(shù)用來考察解與最優(yōu)解的關(guān)系（接近程度、方向等）。而極值函數(shù)可以簡單、清晰地表現(xiàn)該關(guān)系。所以，極值函數(shù)經(jīng)常被選為遺傳算法的適應(yīng)度函數(shù)，（A）（B）（C）正確。適應(yīng)度函數(shù)不能隨意選擇，一定是問題映射形成的函數(shù)，否則該適應(yīng)度函數(shù)沒有意義，（D）錯誤。故此題的答案為：（D）具體內(nèi)容請參考課堂視頻“

22、怎樣用遺傳算法求解具體的應(yīng)用問題”以及第九章課件。4、關(guān)于遺傳算法為什么可以求解NPC類問題。理解下圖，回答下列問題。(1)遺傳算法是典型的計算求解的方法，它通過“產(chǎn)生任何一個可能解，并驗證可能解的正確性”的方法求解一個復(fù)雜問題。關(guān)于計算求解，下列說法正確的是_。(A)可以從所有可能解的集合中產(chǎn)生每一個可能解，并驗證可能解的正確性。利用這種策略的算法，計算機一定能夠在有限時間內(nèi)找到精確解；(B)可以從所有可能解的集合中隨機產(chǎn)生一些可能解，并驗證可能解的正確性。利用這種策略的算法，計算機一定能夠在有限時間內(nèi)找到精確解；(C)可以從所有可能解的集合中隨機產(chǎn)生一些可能解，并驗證可能解的正確性。利用這

23、種策略的算法，計算機一定能夠在有限時間內(nèi)找到滿意解；(D)可以從所有可能解的集合中隨機產(chǎn)生一些可能解，并驗證可能解的正確性。利用這種策略的算法，如果隨機產(chǎn)生的可能解越多，則計算機找到滿意解的概率也越大，但耗費時間也越長；(E)上述說法都正確；答案：D解釋：本題考查遍歷搜索與隨機搜索的共性與差別；從可能解中產(chǎn)生的集合，也許這個集合里并沒有精確解，那么計算機不可能在該集合中找到精確解。（A）（B）（C）說法不正確。但是，產(chǎn)生的隨機解越多，找到滿意解的概率越大，（D）正確。綜上，此題的答案為（D）。具體內(nèi)容請參考課堂視頻“遺傳算法為什么可以求解NPC問題”以及第九章課件。(2)遺傳算法是典型的計算求

24、解的方法，它通過“產(chǎn)生任何一個可能解，并驗證可能解的正確性”的方法求解一個復(fù)雜問題。關(guān)于計算求解，下列說法正確的是_。(A)可以從所有可能解的集合中隨機產(chǎn)生一些可能解，并驗證可能解的正確性。利用這種策略的算法可被稱為隨機搜索算法。則，利用隨機搜索算法，計算機在有限時間內(nèi)一定能夠找到滿意解；(B)為改進隨機搜索算法的求解質(zhì)量，在隨機產(chǎn)生可能解的過程中，使后一個可能解的產(chǎn)生與前一個可能解相關(guān)聯(lián)，即在前一個可能解的基礎(chǔ)上隨機產(chǎn)生后一個可能解，例如一個可能解編碼為“110011001100”，可以通過改變該解編碼的某些位產(chǎn)生下一個可能解(即相關(guān))，而改變哪些位則可隨機處理。利用這種策略的算法-可被稱為

25、導(dǎo)向性隨機搜索。則，利用導(dǎo)向性隨機搜索，計算機在有限時間內(nèi)一定能夠找到滿意解；(C)和隨機搜索相比，利用導(dǎo)向性隨機搜索，計算機在有限時間內(nèi)找到滿意解的概率更大一些； (D)和隨機搜索相比，利用導(dǎo)向性隨機搜索，初始的可能解對計算機在有限時間內(nèi)找到滿意解的概率的影響更大一些；(E)上述說法都正確；答案：D解釋：本題考查遍歷搜索與隨機搜索的共性與差別；既然是隨機的產(chǎn)生解，那么一定能產(chǎn)生滿意解釋不可能的。只能說改進算法會讓產(chǎn)生滿意解的概率變大而已。（A）（B）不正確。導(dǎo)向性隨機搜索只是能提高搜索效率，并不能提高找到滿意解的概率，（C）錯誤。（D）的說法沒有問題。因此，此題的答案為（D）。具體內(nèi)容請參考

26、課堂視頻“遺傳算法為什么可以求解NPC問題”以及第九章課件。(3)遺傳算法是典型的計算求解的方法，它通過“產(chǎn)生任何一個可能解，并驗證可能解的正確性”的方法求解一個復(fù)雜問題。關(guān)于計算求解，下列說法不正確的是_。(A)在獲得滿意解的概率方面，如果初始可能解被恰當(dāng)選擇的話，導(dǎo)向性隨機搜索一定比隨機搜索更好一些；(B)在獲得滿意解的概率方面，群導(dǎo)向性隨機搜索一定比導(dǎo)向性隨機搜索更好一些：相比導(dǎo)向性隨機搜索，群導(dǎo)向性隨機搜索采取了多條導(dǎo)向搜索路徑；(C)遺傳算法是一種群導(dǎo)向性隨機搜索：其有一定規(guī)模的種群，即可被認(rèn)為是設(shè)置了多個初始的可能解；其交叉、變異產(chǎn)生新可能解的方法，即可被認(rèn)為是新可能解與原可能解相

27、關(guān)聯(lián)； (D)利用遺傳算法，計算機在有限時間內(nèi)一定能夠找到滿意解；(E)上述說法有不正確的；答案：D解釋：本題考查遍歷搜索與隨機搜索的共性與差別；導(dǎo)向性隨機搜索是根據(jù)初始解進行導(dǎo)向搜索的，如果初始解選擇恰當(dāng)，則能更快的找到滿意解，（A）正確。群導(dǎo)向搜索由于是搜索了多條路徑，相比于導(dǎo)向性搜索更容易找到滿意解，（B）正確。（C）的說法沒有問題。遺傳算法中包含隨機過程，不能保證一定能找到滿意解，（D）的說法不正確。因此，此題的答案為（D）。具體內(nèi)容請參考課堂視頻“遺傳算法為什么可以求解NPC問題”以及第九章課件。5、關(guān)于什么情況下應(yīng)用遺傳算法，下列說法正確的是_。(A)當(dāng)對某問題求解，找不到更好的多

28、項式時間復(fù)雜性算法的時候；(B)當(dāng)問題的可能解能夠被表達，并能夠確定問題的解空間的時候；(C)當(dāng)能夠找到可能解的適應(yīng)度計算方法，即能夠判斷一個可能解接近精確解的程度或方向的時候；(D)前述(A)(B)(C)至少有一個滿足的時候；(E)前述(A)(B)(C)同時滿足的時候；答案：E解釋：本題考查什么情況下可以應(yīng)用遺傳算法；遺傳算法的使用條件：(1)已知“解空間”，即可能解的表現(xiàn)型和基因型(2)關(guān)于可能解的“適應(yīng)度”函數(shù)的計算方法(適應(yīng)度用于判斷一個可能解接近精確解的程度或方向)。故，本題的正確答案為（E）。具體內(nèi)容請參考課堂視頻“遺傳算法為什么可以求解NPC問題”以及第九章課件。6、關(guān)于遺傳算法

29、相關(guān)應(yīng)用問題的抽象，回答下列問題。(1)為什么說會議室租用問題、測試用例選擇問題和航班機組成員問題是同一個問題，下列說法不正確的是_。(A)對這三個問題進行抽象，會議室、測試用例和機組成員都可被看作是“資源”，而講座、軟件功能測試和航班都可被看作是“任務(wù)”，則這三個問題都可被看作是：選取最少量的資源以滿足其能夠完成給定的所有任務(wù)；(B)對這三個問題進行抽象，每個資源都能夠完成一些任務(wù)，即覆蓋一個任務(wù)集合。不同資源，具有不同的使用成本。上述問題都是選擇具有最小成本的一些資源，使這些資源所覆蓋任務(wù)集合的并集能夠包含所有需要完成的任務(wù)；(C)觀察問題相同與否，可將問題語義剝離，形成數(shù)學(xué)模型。如果數(shù)學(xué)

30、模型是相同的，則其是相同的問題，否則便不是相同的問題。上述三個問題抽象后都可以形成下列數(shù)學(xué)模型：min(1)s.t.(2)(3)所以上述三個問題是同一個問題；(D)前述說法(A)(B)(C)有不正確的；答案：D解釋：本題考查問題抽象能力；三個問題都是同一個問題：一維的集覆蓋問題。他們數(shù)學(xué)模型均(C)選項所述，每一行都被選出的列覆蓋，被哪一列或幾列覆蓋不重要，要滿足約束矩陣。故本題的正確答案為：（D）。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2”以及第九章課件。(2)集覆蓋問題可以抽象為下列模型，請對下列模型進行理解。關(guān)于該模型，下列說法不正確的是_。min(1)s.t.(2)(

31、3)(A)公式(1)是計算所選擇資源的總成本，目標(biāo)是求具有最小總成本的資源集合。其中資源被從1,n編號。如果xj=1，表示資源j被選擇；如果xj=0，表示資源j未被選擇；cj表示選擇資源j時所需消耗的成本。(B)公式(2)表示每一個任務(wù)i都被某一個已選擇的資源j(xj0)能完成的任務(wù)集所覆蓋；(C)當(dāng)aij=1，且xj=1時，則aijxj=1，即任務(wù)i可以被資源j完成，且資源j已被選擇；(D)aijxj1 表示任務(wù)i至少能被一個已選擇出的資源所完成，換句話說，一個任務(wù)可能由多個資源來完成，在這些資源中只要有一個被選擇即可；(E)上述說法有不正確的。答案：E解釋：本題考查對數(shù)學(xué)模型的理解能力；該

32、模型為一維集覆蓋問題，需要選出這樣的一維向量，使得每一行都被選出的列覆蓋，被哪一列或幾列覆蓋不重要，要滿足約束矩陣。（A）（B）（C）（D）的說法均正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2”以及第九章課件。(3)參閱教材，理解課程表優(yōu)化安排問題。關(guān)于該問題，下列說法正確的是_。(A)該問題，與會議室租用問題、測試用例選擇問題和航班機組成員問題，是同一個問題；(B)該問題，是一個一維的集合覆蓋問題，仍舊可用下列數(shù)學(xué)模型來表達；min(1)s.t.(2)(3)(C)該問題，不同于(B)的數(shù)學(xué)模型。它是一個二維的集合覆蓋問題，(B)中數(shù)學(xué)模型的可能解是，而本問題的可能解是(D

33、)上述說法全不正確。答案：C解釋：本題考查對數(shù)學(xué)模型的理解能力；課程表優(yōu)化問題是一個二維集覆蓋問題。其可能解為二維矩陣。其模型為：(1)s.t. (2)s.t. (3) (4)（C）正確。故本題的答案為（C）。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2”以及第九章課件。(4)會議室租用問題、測試用例選擇問題和航班機組成員問題，這三個問題的遺傳算法求解過程，與下述過程相同還是不同呢，說法正確的是_。(A)求解過程是相同的，只是適應(yīng)度函數(shù)不同，其他如可能解的編碼、初始解的獲得、交叉與變異規(guī)則、汰選可能解形成新一代種群的規(guī)則、算法終止條件等都可以相同； (B)求解過程是相同的，可能解

34、的編碼、初始解的獲得、交叉與變異規(guī)則、汰選可能解形成新一代種群的規(guī)則、算法終止條件等都可以是相同的，但適應(yīng)度函數(shù)是不同的，此外，這三個問題需要判斷一個可能解是否是可行解-即產(chǎn)生的可能解需要滿足約束條件(2)，而圖中示例沒有這一過程；(C)求解過程是不同的，除適應(yīng)度函數(shù)不同外，其他如可能解的編碼、初始解的獲得、交叉與變異規(guī)則、汰選可能解形成新一代種群的規(guī)則、算法終止條件等都是不同的；(D)前述說法都正確。答案：B解釋：本題考查對數(shù)學(xué)模型的理解能力；采用遺傳算法解決問題的基本框架都是一樣的，因此求解過程是相同的，可能解的編碼、初始解的獲得、交叉與變異規(guī)則、汰選可能解形成新一代種群的規(guī)則、算法終止條

35、件等都可以是相同的，而題目中提到的三個問題的適應(yīng)度函數(shù)均為模型中的條件1，而圖示的問題的適應(yīng)度函數(shù)為F(x)，兩者是不一樣的。另外，圖示的問題中，所有的可能解都是可行解，但三個問題的可能解救不一定是可行解，必須得驗證。這點也是不一樣的。綜上，本題的答案為（B）。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2”以及第九章課件。(5)參閱教材，理解課程表優(yōu)化安排問題的數(shù)學(xué)模型如下：(1)s.t. (2)s.t. (3) (4)關(guān)于該模型，下列說法不正確的是_。(A)公式(1)是計算某一種方案-該方案給出了哪一門課程安排在哪個教室的一種安排，計算該方案的總成本，目標(biāo)是求具有最小總成本的那

36、個方案。其中教室被從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沒有關(guān)系；(E)上述說法有不正確的。答案：B解釋：本題考查對數(shù)學(xué)模型的理解能力；選項（A）的說法沒有問題。公式（2）表示一門課程恰好被安排在一個教室。而不是（B）選項中的“

37、每一門課程至少被安排在1個教室，也可以安排在多個教室”。（B）的說法正確。（C）（D）的說法也沒有問題。綜上，本題的答案為（B）。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2”以及第九章課件。7、對類似于遺傳算法的理解，需要理解關(guān)于各種解的名詞之間的細(xì)微差別。(1)下列說法正確的是_。(A)可行解集合近似解集合可能解集合滿意解集合最優(yōu)解集合；(B)可能解集合可行解集合滿意解集合近似解集合最優(yōu)解集合；(C)可能解集合可行解集合近似解集合滿意解集合最優(yōu)解集合；(D)最優(yōu)解集合滿意解集合近似解集合可行解集合可能解集合； 答案：C解釋：本題考查對關(guān)于“解”的一些名詞的理解；可能解中包含可

38、行解。可行解中包含近似解。近似解中包含滿意解。滿意解中包含最優(yōu)解。（C）選項的說法是正確的。綜上，本題的答案為（C）。具體內(nèi)容請第九章參考課堂視頻與第九章課件。(2-1)設(shè)一個問題的解的形式為x，下列說法不正確的是_。(A)由x的取值空間給定的任何一個x值被稱為可行解；(B)由一個算法在任何一組可行解中求出的最優(yōu)解被稱為是近似解；(C)符合用戶期望的近似解被稱為是滿意解；(D)所有可行解中的最優(yōu)解是問題的最優(yōu)解；(E)上述說法有不正確的；答案：A解釋：本題考查對關(guān)于“解”的一些名詞的理解；由x的取值空間給定的任何一個x值為可能解。該x的值能滿足問題的要求，該x才被稱為一個可行解。（A）的說法不

39、正確。（B）（C）（D）的說法都是正確的。綜上，此題的答案為（A）。具體內(nèi)容請第九章參考課堂視頻與第九章課件。(2-2)設(shè)一個問題的解的形式為x，下列說法不正確的是_。(A)由x的取值空間給定的任何一個x值被稱為可能解；(B)滿足問題約束的可能解被稱為可行解；(C)在任何一組可行解中求出的最優(yōu)解被稱為是滿意解；(D)所有可行解中的最優(yōu)解是問題的最優(yōu)解；(E)上述說法有不正確的；答案：C解釋：本題考查對關(guān)于“解”的一些名詞的理解；由x的取值空間給定的任何一個x值為可能解。該x的值能滿足問題的要求，該x才被稱為一個可行解。（A）（B）的說法正確。由一個算法在任何一組可行解中求出的最優(yōu)解被稱為是近似

40、解,符合用戶期望的近似解被稱為是滿意解,(C)的說法不正確。（D）的說法正確。綜上，此題的答案為（C）。具體內(nèi)容請第九章參考課堂視頻與第九章課件。8、對于類似于課程表優(yōu)化安排問題的二維集覆蓋問題：，利用遺傳算法計算求解，回答下列問題。(1)關(guān)于其可能解的編碼，說法正確的是_。(A)僅可以按行優(yōu)先編碼；(B)僅可以按列優(yōu)先編碼；(C)既可以按行優(yōu)先編碼，又可以按列優(yōu)先編碼，但其對算法中交叉、變異操作規(guī)則設(shè)計是沒有影響的；(D)既可以按行優(yōu)先編碼，又可以按列優(yōu)先編碼，還可以有其他編碼方式，不同的編碼設(shè)計，可以有不同的交叉、變異操作規(guī)則；答案：D解釋：本題考查對問題解的編碼的多樣性；二維集覆蓋問題的

41、可能解的都是二維矩陣。對于二維矩陣的編碼可以有多種形式。每一種編碼方式，都可以有自己的交叉、變異操作規(guī)則。（D）的說法是正確的。（A）（B）（C）的說法都不正確。綜上，本題的答案為（D）。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題2”與第九章課件。(2)關(guān)于交叉規(guī)則的設(shè)計，下列說法不正確的是_。(A)既可以采取兩段交叉，也可以采取多段交叉；(B)兩段交叉中，交叉點的選擇可以隨機確定：即隨機確定一個交叉點，從中將解編碼分為兩段，將兩個可能解的兩段編碼交換形成兩個新的可能解；(C)多段交叉既可采取等距離分段交叉，亦可采取可變距離分段交叉，交叉點和段間距離都可以隨機的確定；(D)

42、交叉規(guī)則僅有以上(A)(B)(C)幾種情況； (E)對不同的問題，還可能有不同的交叉規(guī)則設(shè)計；答案：D解釋：本題考查對交叉規(guī)則設(shè)計多樣性的認(rèn)識；交叉規(guī)則具有多樣性。不僅可以采用兩段交叉、多段交叉，根據(jù)不同的問題，還可以采用點交叉、行交叉、列交叉、塊交叉等。所以（D）的說法是不正確的。因此，此題的答案為（D）。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題5”與第九章課件。(3)關(guān)于交叉規(guī)則的設(shè)計，下列說法不正確的是_。(A)可以采取基本的兩段交叉或多段交叉；(B)可以采取點交叉、行交叉或列交叉；(C)可以不以“位”為單位進行交叉，而以若干位的一個組合為單位進行交叉；(D)交叉規(guī)

43、則僅有以上(A)(B)(C)幾種情況；答案：D解釋：本題考查對結(jié)合問題特征進行交叉規(guī)則設(shè)計的認(rèn)識；交叉規(guī)則十分的豐富。（A）（B）（C）均為交叉規(guī)則。但交叉規(guī)則不僅僅限于此。還可以采用交叉與隨機的交叉規(guī)則，如：兩個染色體的各段的x位如都相同，則不交換，否則以概率p進行交換。具體問題具體分析。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題5”與第九章課件。9、遺傳算法的設(shè)計在很多方面都需要引入概率，在哪些方面引入概率呢？下列說法不正確的是_。(A)初始種群的確定可以引入概率。結(jié)合問題可能解的分布選擇概率模型，將此概率模型引入初始解的隨機選擇過程中，則選擇出的初始可能解有助于遺傳算

44、法快速地獲得滿意解；(B)交叉規(guī)則設(shè)計可以引入概率。從待交叉兩個可能解的確定，到交叉點的確定，甚至到段間距離的確定等都可以引入概率，恰當(dāng)?shù)母怕誓Ｐ瓦x擇有助于遺傳算法快速地獲得滿意解；(C)遺傳算法處處體現(xiàn)著概率的應(yīng)用和隨機處理。當(dāng)可能的方案比較多，且窮舉計算量很大時，便可采用概率方式進行隨機化處理。例如兩個可能解“00001000 10001100”“00111000 1011 1100”，如果做兩段交叉，則分段交叉點可以有16個，如果16個交叉點都選擇，則可能該子解空間仍舊很大，此時可依概率選擇1號位置交叉至16號位置交叉，選擇幾個則依概率模型確定，選擇1個至16個中的某些個；(D)雖然遺傳

45、算法處處可以引入概率，但其概率模型卻是相同的；(E)上述說法有不正確的。 答案：D解釋：本題考查對遺傳算法引入概率的認(rèn)識；遺傳算法處處都可以引入概率。（A）（B）（C）都是在在遺傳算法中加入概率的例子。在（A）（B）（C）描述的例子中，都引入了概率。常見的概率模型有：古典概型 ，幾何概型，連續(xù)變量，離散變量，正態(tài)模型，泊松模型，指數(shù)模型等。可以根據(jù)不同的情況選擇不同的模型。所以（D）的說法是不正確的。綜上，此題的答案為：（D）。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題5”與第九章課件。10、遺傳算法設(shè)計需要引入變異操作。變異操作是對種群中的某些可能解(個體)的某些編碼位進

46、行突變處理，例如二進制編碼的解01110011，其第3位(自左而右)當(dāng)前為1則將其變?yōu)?，稱為變異操作。關(guān)于變異操作，回答下列問題。(*1)關(guān)于如何應(yīng)用變異操作，下列說法不正確的是_。(A)對種群中所有可能解(個體)以事先設(shè)定的變異概率確定是否進行變異；(B)對進行變異的可能解(個體)隨機選擇變異位置進行相應(yīng)位置的“位”變異；(C)對進行變異的可能解(個體)隨機選擇變異位置進行相應(yīng)位置的“位組合”變異；(D)變異概率應(yīng)選取較大值，即：使變異頻繁發(fā)生，這樣有助于快速收斂到滿意解；(E)上述說法有不正確的。答案：D解釋：本題考查對遺傳算法中關(guān)于變異的認(rèn)識。選項(D)中，變異概率：控制算法中變異操作

47、的使用頻率，實際情況下變異發(fā)生的頻率并非越頻繁越好，當(dāng)變異概率無限增大的時候，遺傳算法就變?yōu)榧冸S機搜索了，因此變異概率并不是可以無限擴大的，即在一定條件下使變異概率盡量大有助于快速收斂到滿意解。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。(2)通過變異操作，使遺傳算法具有局部的隨機搜索能力。為什么？下列說法不正確的是_。(A)當(dāng)產(chǎn)生一個可行解時，可以在該解的鄰近解的集合中進行搜索，被稱為局部搜索；該解的鄰近解的集合是變化的，例如與該解有一位不同的鄰近解、與該解有兩位不同的鄰近解，或者與該解有一個“位組合”不同的鄰近解等；(B)當(dāng)產(chǎn)生一個可行解時，由于與該解的

48、鄰近解的集合可能很大，并不能窮舉每一個鄰近解，所以需要隨機選擇鄰近解； (C)當(dāng)產(chǎn)生一個可行解時，通過某一位或幾位的變異，便可產(chǎn)生該解相鄰近的解。即相當(dāng)于，以該解為中心，在與該解的鄰近解的集合中隨機選擇出某個解； (D)當(dāng)產(chǎn)生的可行解接近最優(yōu)解的鄰域時，通過某一位或幾位的變異，便可產(chǎn)生該解相鄰近的解，此有助于使算法加速向最優(yōu)解收斂；(E)上述說法有不正確的。答案：E解釋：本題考查對遺傳算法中關(guān)于變異的認(rèn)識。選項(A)(B)(C)(D)均為正確選項。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。(3)通過變異操作，使遺傳算法可維持群體多樣性。為什么？下列說法不正

49、確的是_。(A)由于初始解設(shè)置或經(jīng)多次迭代后，很可能使一代種群中的各個可能解具有相似的結(jié)構(gòu)，此時無論怎樣交叉產(chǎn)生的新可能解，都將在與該結(jié)構(gòu)相近的可能解空間搜索-這種現(xiàn)象被稱為過早收斂； (B)為避免過早收斂，有必要保持種群個體的多樣性，即使種群中的可能解具有不同的結(jié)構(gòu)，怎樣保持不同的結(jié)構(gòu)，即通過變異，打破原有相似的結(jié)構(gòu)，進入到另外的空間中搜索；(C)當(dāng)進化到某一代時，種群的解可能具有相類似的結(jié)構(gòu)，可能始終在這個類似結(jié)構(gòu)的解集合中進行循環(huán)，為避免這種情況， 通過對一些解應(yīng)用變異操作，打破種群的解的相類似結(jié)構(gòu)，有助于跳出循環(huán)，在更大空間中進行搜索；(D)當(dāng)產(chǎn)生的可行解接近最優(yōu)解的鄰域時，應(yīng)謹(jǐn)慎使用

50、變異，以免偏向最優(yōu)解的結(jié)構(gòu)被破壞；而當(dāng)產(chǎn)生的可行解并未接近最優(yōu)解的鄰域時，可以選擇較大的變異概率以保證種群解的多樣性；(E)上述說法有不正確的。答案：E解釋：本題考查對遺傳算法中關(guān)于變異的認(rèn)識。選項(A)(B)(C)(D)均為正確選項。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。11、遺傳算法是迭代計算求解的方法。如何終止遺傳算法，下列說法正確的是_。(A)當(dāng)適應(yīng)度已經(jīng)達到飽和，繼續(xù)進化不會產(chǎn)生適應(yīng)度更好的近似解時，可終止遺傳算法；(B)當(dāng)某一個可行解已經(jīng)滿足滿意解的條件，即滿意解已經(jīng)找到，可終止遺傳算法；(C)當(dāng)進化到指定的代數(shù)(進化次數(shù)限制)或者當(dāng)達到一

51、定的資源占用量(計算耗費的資源限制，如計算時間、計算占用的內(nèi)存等)時可終止算法，如當(dāng)產(chǎn)生超過一定數(shù)量的不重復(fù)可行解后即可終止； (D)僅有上述(A)(B)(C)幾種終止遺傳算法的情況； 答案：D解釋：本題考查遺傳算法如何終止的問題。選項(A)終止后可以得到相對接近最優(yōu)解的結(jié)果，理論上不存在更接近最優(yōu)解的其他結(jié)果；選項(B)終止后可以得到滿意解，但理論存在更符合條件的結(jié)果；選項(C)無法得到全部可行解，但可滿足題意得到結(jié)果；但單獨選擇(A)(B)(C)均不全面，因此選擇(D)。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。12、遺傳算法是一種算法設(shè)計策略。不同的

52、問題甚至相同的問題都可以設(shè)計不同的遺傳算法進行求解，不同的遺傳算法如可能解編碼的不同、交叉與變異規(guī)則的不同、概率模型的選擇不同等。(1)如何衡量遺傳算法的性能好壞，下列說法正確的是_。(A)對一些已知最優(yōu)解的問題類別，可以通過精確算法獲得最優(yōu)解，然后使用“近似率”來衡量解的質(zhì)量。所謂近似率是指算法求得的解與問題最優(yōu)解的近似程度。則有：近似率越高的遺傳算法，性能越好；(B)對理論最優(yōu)解不知道的問題類別，可以通過不同遺傳算法在相同問題實例集上測試結(jié)果的橫向比較來進行評價，即有：在執(zhí)行相同次數(shù)的迭代后，獲得滿意解越好的遺傳算法，性能越好；(C)對于具有迭代特征的近似算法，在迭代多少次后能夠使得結(jié)果穩(wěn)

53、定(通俗來講，即結(jié)果不再隨進一步迭代而發(fā)生變化或發(fā)生極小的可以被忽略的變化)這被稱為收斂速度，它從一定程度反映了算法求解的“快慢”。在達到期望的滿意解的前提下，迭代次數(shù)越少越好。(D)遺傳算法不一定能夠得到滿意解。因此，當(dāng)不同算法均應(yīng)用多次后，求得滿意解次數(shù)越多的算法越好！(E)除上述衡量性能的指標(biāo)外，還有其他的指標(biāo)來衡量性能。答案：E解釋：本題考查如何衡量遺傳算法的性能。選擇(E)，(A)(B)(C)(D)均不全面，其他指標(biāo)，諸如獲得滿意解所花費的平均時間以及占用的系統(tǒng)資源都可以列為衡量算法性能的指標(biāo)。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。(2)如何

54、衡量遺傳算法的性能好壞，下列說法不正確的是_。(A)近似率越高的算法，性能越好；(B)在執(zhí)行相同次數(shù)的迭代后，獲得滿意解越好的算法，性能越好；(C)在達到期望滿意解的前提下，迭代次數(shù)越多的算法，性能越好；(D)當(dāng)不同算法均應(yīng)用多次后，求得滿意解次數(shù)越多的算法，性能越好！答案：C解釋：本題考查如何衡量遺傳算法的性能。(A)(B)(D)正確，(C)迭代次數(shù)多性能差。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV)”和第九章課件。(3)如何衡量遺傳算法的性能好壞，下列說法不正確的是_。(A)近似率越低的算法，性能越好；(B)在執(zhí)行相同次數(shù)的迭代后，獲得滿意解越好的算法，性能越好；(C)在達到期望滿意解的前提下，迭代次數(shù)越少的算法，性能越好；(D)當(dāng)不同算法均應(yīng)用多次后，求得滿意解次數(shù)越多的算法，性能越好！答案：A解釋：本題考查如何衡量遺傳算法的性