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

1、第 9 章 怎樣研究算法 : 遺傳算法例如1、P類問題、NP類問題、NPC類問題是電腦科學(xué)領(lǐng)域關(guān)于可求解性可計算性很重要的概念。關(guān) 于 P、 NP 和 NPC 類問題，答復(fù)以下問題。(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

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

4、項是。(A) P類問題是電腦可以在有限時間內(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) 上述說法都正確；

5、答案：B解釋：此題考核對NP類問題的理解。P類問題 是多項式問題(Polynomial Problem)， NP類問題是非確定性多項式問題 (No n-determi nistic Poly no mial)，NPC問題是完全非確定性多項式問題(NP-Complete)，所以(B)正確。具體內(nèi)容請參考第九章視頻之“可求解與難求解問題以及第九章課件。(5) 以下說法不正確的選項是 。(A) P類問題是總能找到一個多項式時間復(fù)雜性算法進行求解的問題；(B) NP類問題是一定找不到多項式時間復(fù)雜性算法進行求解的問題；(C) NP類問題是不確定能夠找到多項式時間復(fù)雜性算法進行求解的問題；(D) NP類

6、問題雖然是不確定能找到多項式時間復(fù)雜性算法進行求解，但一定能找到多項式時間復(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)。

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

9、能夠找到求NP類問題近似解的多項式時間復(fù)雜性算法, 解；(D) 既然能夠找到求NP類問題近似解的多項式時間復(fù)雜性算法,解;(E) 上述說法都正確;答案：A解釋：此題考核對NP類問題求解的理解。NP類問題指雖然在多項式時間內(nèi)難于求解但不難判斷給定一個解的正確性的問題，即：在 多項式時間內(nèi)可以由一個算法驗證一個解是否正確的非確定性問題，所以NP類問題求精確解，可能找不到多項式時間復(fù)雜性算法，但 NP類問題求近似解，那么一定能夠找到多項式時間復(fù)雜性 算法，(A)正確(B)錯誤；雖然能夠找到求NP類問題近似解的多項式時間復(fù)雜性算法，但所求得的 解不一定是滿意解，(C)(D)錯誤。具體內(nèi)容請參考第九章視

10、頻之“可求解與難求解問題以及第九章課件。2、以下列圖能夠根本反映生物學(xué)遺傳與優(yōu)勝劣汰的過程。 理解該圖，聯(lián)想計算類問題求解，答復(fù)以 下問題。染色休Ad基腔恥7兩個個體FA的架色體:靳個/本的 染色體個休呂的 染色體集色體B的 皓因片段繁忻后的種群個休對環(huán)境的適 應(yīng)性:優(yōu)勝劣汰(1) 以下說法不正確的選項是 。(A) 任何一個生物個體的性狀是由其染色體確定的，染色體是由基因及其有規(guī)律的排列所構(gòu)成的，因此生物個體可由染色體來代表；(B) 生物的繁殖過程是通過將父代染色體的基因復(fù)制到子代染色體中完成的，在復(fù)制過程中會發(fā)生基因重組或基因突變?；蛑亟M是指同源的兩個染色體之間基因的交叉組合，簡稱為“雜交

11、/交配?；蛲蛔兪侵笍?fù)制過程中基因信息的變異，簡稱“突變；(C) 不同染色體會產(chǎn)生不同生物個體的性狀，其適應(yīng)環(huán)境的能力也不同；(D) 自然界表達的是“優(yōu)勝劣汰，適者生存的叢林法那么。不適應(yīng)環(huán)境的生物個體將被淘汰， 自然界生物的生存能力會越來越強；(E) 上述說法有不正確的。答案：E解釋：此題考核對生物遺傳觀點以及所給圖片的理解。關(guān)于生物遺傳進化的根本觀點如下：生物的所有遺傳信息都包含在其染色體中，染色體決定了生物的性狀；(ii) 染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進化過程發(fā)生在染色體上；(iii) 生物的繁殖過程是由其基因的復(fù)制過程來完成的；(iv) 通過同源染色體之間的交叉或染色

12、體的變異會產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(v) 對環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的時機遺傳到下 一代。故A、 B、C、D均正確。于是，E錯誤。具體內(nèi)容請參考課堂視頻 遺傳算法的緣起-生物學(xué)中的遺傳與進化和第九章課件。(2-1)類比計算類問題求解，以下說法不正確的選項是 。(A) 一個染色體即是指問題的一個“可能解。任何“可能解都可以表達為編碼形式，構(gòu)成 編碼的根本單位即是基因；(B) 所謂的復(fù)制、雜交、突變，是指一個可能解或兩個可能解之間發(fā)生的、編碼片段之間的復(fù)制、交叉或變異，它們都是產(chǎn)生新可能解的一種方式；(C) 所謂的環(huán)境適應(yīng)性，可以認為是對一個可能解的一

13、種度量，即能夠度量一個可能解的好與 壞的某一函數(shù)值，被稱為“適應(yīng)度；(D) 基于(A)(B)(C)，遺傳算法就是“通過復(fù)制、交叉或變異，不斷產(chǎn)生新的可能解；計算可能解的適應(yīng)度；淘汰掉適應(yīng)度差的可能解，保存適應(yīng)度好的可能解。(E) 上述說法有不正確的；答案：E 解釋:此題考核對生物學(xué)中的概念與電腦中的概念的映射的理解。染色體映射到電腦中就是編碼解。A正確。復(fù)制是指將一個解從一個解集復(fù)制到另外一 個解集。雜交是指對兩個可能解的編碼通過交換某些編碼位而形成兩個新的可能解的遺傳操作， 是新可能解的一種形成方式。突變是指隨機地改變一個可能解的編碼的某些片段(或基因)而使一個可能解變?yōu)橐恍碌目赡芙獾倪z傳操

14、作，也是新解的一種形成方式。B正確。適應(yīng)度性是指一個可能解接近最優(yōu)解的一個度量。C正確。由ABC，可以得到遺傳算法的根本思 想。D正確。故E錯誤。綜上，E錯誤。具體內(nèi)容請參考課堂視頻“計算學(xué)科的遺傳算法和第九章課件。(2-2)類比計算類問題求解，以下說法不正確的選項是 。(A) 一個染色體即是指問題的一個“可能解，一個基因即是“可能解的一個編碼位或假設(shè) 干編碼位的一個組合；(B) 一個種群即是一個包含問題滿意解的“可能解的集合；(C) 適應(yīng)度，即是對“可能解的一個度量，它可以衡量“可能解接近最優(yōu)解或精確解的程 度；(D) 復(fù)制、交叉、變異等都是產(chǎn)生新“可能解的方式；(E) 上述說法有不正確的；

15、答案：B解釋：此題考核對生物學(xué)中的概念與電腦中的概念的映射的理解。染色體映射到電腦中就是編碼解，即一個可能解的基因型。一個基因即是指可能解的某一位 或幾位，A3正確。種群是指假設(shè)干可能解的集合，而不一定包含問題的滿意解，B錯誤。適應(yīng)度性是指一個可能解接近最優(yōu)解的一個度量，C正確。復(fù)制、交叉、變異等都是產(chǎn)生新“可 能解的方式，D正確。因為B錯誤，故E正確。綜上，此題答案為B。具體內(nèi)容請參考課堂視頻“計算學(xué)科的遺傳算法和第九章課件。3、類比生物遺傳與優(yōu)勝劣汰而形成的遺傳算法的求解過程如以下列圖示意。理解該圖，答復(fù)以下問題。和糾Wit陽承if左丄 廠VLMWlli 墀斥比I：HN 0 i44X 搟覆

16、F(X> I3-10X *20 for0 1D1011 01D10l'0Illi1i01和蠟戶群初細q j1左KI qfc?更妙量井零l*曹 x雯埴.j'_ - a o 1ocL Ji|o|d60r1101 2opD1c1 -1C011aioj01l0-1D0100 c<10t：lL11IJAfiII010a o1 D0 1(nfWil* t ' 丫 1融鹽丹原6o'lijooQiDi a10u|o11D1<a#議卜TH卜1*9刊印?!2* Ft：-s.i±2a?37 F<J7j-6ga10Q12_1o'12, F(12

17、) *-6401 : 1M, F(2l)-«2'1A2. F(42iHHQE1oToB.冋冃戶BBi57, F(57)-2IWKTr41lFf4IJ=S22 .(1) 圖中給出了遺傳算法的根本求解過程示意。關(guān)于圖中包含了哪些過程，以下說法正確的選項是(A) 可能解的編碼過程和初始種群的產(chǎn)生過程；(B) 交叉、變異形成候選種群的過程；(C) 可能解的適應(yīng)度計算過程和汰選可能解形成新一代種群的過程;(D) 算法終止及最終解的形成過程；(E) 上述全部過程。答案：E解釋：此題考查學(xué)生對遺傳算法根本求解過程的理解。圖中第一行第一個箭頭即是可能解的編碼過程和初始種群的產(chǎn)生過程。最右的大

18、方框內(nèi)的即是交叉、變異形成候選種群的過程。右下方的方框以及箭頭即是可能解的適應(yīng)度計算過程和汰選可能解形成新一代種群的過程。左下的圖與箭頭即是算法終止及最終解的形成過程。綜上，E正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題以及第九章課件。(2) 依據(jù)圖中例如及求解過程示意，思考并答復(fù)，以下說法不正確的選項是 。(A) 初始種群中的可能解可以隨機產(chǎn)生；(B) 對于哪兩個可能解進行交叉，可以采取隨機方式從種群中選擇出來；(C) 對于兩個可能解進行兩段交叉，其交叉點是固定的，不可以采取隨機方式確定；(D) 對于哪個解進行變異，以及變異位置確實定，可以采取隨機方式選擇和確定；(E) 上

19、述有不正確的說法。答案：C解釋：此題考查學(xué)生對遺傳算法隨機性的理解。在遺傳算法中，所有的解的產(chǎn)生，以及交叉，變異等可以隨機的產(chǎn)生，并不是固定的。所以 C的說法不正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題以及第九章課件。(3) 依據(jù)圖中例如及求解過程示意，思考并答復(fù)，以下說法不正確的選項是 。(A) 種群的規(guī)模，即種群中可能解的個數(shù)是預(yù)先設(shè)定且固定不變的，其大小影響遺傳算法求解 的質(zhì)量和效率；(B) 種群的規(guī)模，雖然是預(yù)先設(shè)定的，但其大小不會影響遺傳算法求解的質(zhì)量和效率；(C) 種群的規(guī)模可以依據(jù)問題的所有可能解的個數(shù)來確定：太大，雖求解效果好但計算量卻很 大；太小，雖計算量

20、很小，但求解效果卻難以保證；(D) 種群規(guī)模不是隨機確定的；(E) 上述有不正確的說法。答案：B解釋：此題考查學(xué)生對遺傳算法種群規(guī)模及其確定方法的理解。在遺傳算法的設(shè)計過程中，應(yīng)該根據(jù)問題的具體情況設(shè)置適宜的種群規(guī)模。如果規(guī)模過大， 雖然求解效果好，但是計算量很大。如果規(guī)模太小，計算量雖然不大了，但是求解效果就難以保 證了。所以，種群規(guī)模的大小一定會影響遺傳算法求解的質(zhì)量和效率。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題以及第九章課件。(4) 依據(jù)圖中例如及求解過程示意，思考并答復(fù)，以下說法不正確的選項是 。(A) 遺傳算法可以一個輪次一個輪次迭代地進行(被稱為“進化)，可以在迭

21、代到一定次數(shù)后 終止；(B) 遺傳算法一定可以求得滿意解或最優(yōu)解，它一定是在得到滿意解或最優(yōu)解時才終止；(C) 遺傳算法必定涉及隨機處理，因為不僅僅是問題可能解的空間很大， 而任何一個子解空間 也都可能很大，窮舉是難以辦到的；(D) 遺傳算法是以交叉操作為產(chǎn)生新可能解的主要操作，而以變異操作作為產(chǎn)生新可能解的輔 助操作；(E) 上述有不正確的說法。答案：B解釋：此題考查學(xué)生對遺傳算法的迭代性和求解質(zhì)量方面的理解。遺傳算法就是通過不斷的迭代來淘汰不好的解，留下好的解，A正確。不是任何問題采用遺傳算法都可以得到滿意解或最優(yōu)解，因為遺傳算法中會有隨機的過程，算法每次執(zhí)行的結(jié)果 都不盡相同，B的說法不

22、正確。CD的說法都沒有問題。故此題的答案為B。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題以及第九章課件。(5) 依據(jù)圖中例如及求解過程示意，思考并答復(fù)，以下說法不正確的選項是 。(A) 適應(yīng)度，主要用于考察一個可能解是否接近最優(yōu)解，以及接近的程度和方向，所以通常選擇極值函數(shù)(如最大值函數(shù)或最小值函數(shù))作為度量函數(shù)；(B) 一般而言，通過將可能解代入一個極值函數(shù) (如最大值函數(shù)或最小值函數(shù))中獲得函數(shù)值， 以該函數(shù)值作為適應(yīng)度的值；(C) 一個問題，假設(shè)要用遺傳算法求解，那么要能夠?qū)⑵溆成錇轭愃朴谇髽O值一樣的函數(shù)，即函數(shù)的極大值(或極小值)對應(yīng)了問題的最優(yōu)解/較優(yōu)解，這是問題數(shù)學(xué)建

23、模的一種方向；(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)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題以及第九章課件。4、關(guān)于遺傳算法為什么可以求解 NPC類問題。理解以下列圖，答復(fù)以下問題。 *0 o

24、° 00 0Q 、0 °° 0 O 0 O0o °0o o Q 0 O °0QCK 0 O0 Q c Cl 0 «0 0 o0 0*0 0 * o 000 oo o cy 0 ocl0 / y 0 0 O 0 Oo o/o O 0 0*000 0 0 0o q/X 4 0 0 0 0 0O Q TK 0 0 o 0 0 o0 0 0*0 0 0 0 o0 0(/00 0 « « *0 0 0 0 °o o tr o Qo O Qo o0 0*0* 0 o 0 O0 0 0 00 0 0 0(蜀丙単雨陽(可

25、寺向iTMl虹徨爲(d)?|n性對(佯)間肛按富卅寧怖有，可戟飼祐測燃砲札點Z問完十沒懺嘆樂闊札藍疋餌母應(yīng)躋怕 .杠歸HL點同歩illfrf?應(yīng)件艮富(1) 遺傳算法是典型的計算求解的方法，它通過“產(chǎn)生任何一個可能解，并驗證可能解的正確性 的方法求解一個復(fù)雜問題。關(guān)于計算求解，以下說法正確的選項是 。(A) 可以從所有可能解的集合中產(chǎn)生每一個可能解，并驗證可能解的正確性。利用這種策略的算法，電腦一定能夠在有限時間內(nèi)找到精確解；(B) 可以從所有可能解的集合中隨機產(chǎn)生一些可能解，并驗證可能解的正確性。利用這種策略 的算法，電腦一定能夠在有限時間內(nèi)找到精確解；(C) 可以從所有可能解的集合中隨機產(chǎn)

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

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

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

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

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

31、是 。(A) 當對某問題求解，找不到更好的多項式時間復(fù)雜性算法的時候；(B) 當問題的可能解能夠被表達，并能夠確定問題的解空間的時候；(C) 當能夠找到可能解的適應(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)容請參考課堂視頻“遺傳算法為什么可以

32、求解NPC'可題以及第九章課件。6、關(guān)于遺傳算法相關(guān)應(yīng)用問題的抽象，答復(fù)以下問題。(1)為什么說會議室租用問題、測試用例選擇問題和航班機組成員問題是同一個問題，以下說法不正確的選項是。(A) 對這三個問題進行抽象，會議室、測試用例和機組成員都可被看作是“資源 ，而講座、 軟件功能測試和航班都可被看作是“任務(wù)，那么這三個問題都可被看作是：選取最少量的資源以滿 足其能夠完成給定的所有任務(wù)；(B) 對這三個問題進行抽象，每個資源都能夠完成一些任務(wù)，即覆蓋一個任務(wù)集合。不同資源， 具有不同的使用本錢。上述問題都是選擇具有最小本錢的一些資源，使這些資源所覆蓋任務(wù)集合 的并集能夠包含所有需要完成的

33、任務(wù)；(C) 觀察問題相同與否，可將問題語義剝離，形成數(shù)學(xué)模型。如果數(shù)學(xué)模型是相同的，那么其是 相同的問題，否那么便不是相同的問題。上述三個問題抽象后都可以形成以下數(shù)學(xué)模型：nmin z(x)cjxj (1)j 1ns.t.ajXj1, i 1,2,., m (2)j 1Xj0,1, j 1,2,., n (3)所以上述三個問題是同一個問題；(D) 前述說法(A)(B)(C)有不正確的;答案：D解釋：此題考查問題抽象能力；三個問題都是同一個問題：一維的集覆蓋問題。他們數(shù)學(xué)模型均(C)選項所述，每一行都被選出的列覆蓋，被哪一列或幾列覆蓋不重要，要滿足約束矩陣。故此題的正確答案為：D。具體內(nèi)容請參

34、考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2以及第九章課件。(2)集覆蓋問題可以抽象為以下模型，請對以下模型進行理解。關(guān)于該模型，以下說法不正確的選項是。nmin z(x) q% (1)j 1ns.t. aXj 1, i 1,2,., m (2)j 1Xj 0,1, j 1,2,., n (3)(A) 公式(1)是計算所選擇資源的總本錢，目標是求具有最小總本錢的資源集合。其中資源被從1,n編號。如果Xj=1，表示資源j被選擇；如果xj=0,表示資源j未被選擇；Cj表示選擇資源 j時所需消耗的本錢。(B) 公式(2)表示每一個任務(wù)i都被某一個已選擇的資源j(xj>0)能完成的任務(wù)集所覆蓋

35、；(C) 當aij=1，且xj=1時，那么aijXj=1,即任務(wù)i可以被資源j完成，且資源j已被選擇；(D) aijxj 1表示任務(wù)i至少能被一個已選擇出的資源所完成，換句話說，一個任務(wù)可能由多 個資源來完成，在這些資源中只要有一個被選擇即可；(E) 上述說法有不正確的。答案：E解釋：此題考查對數(shù)學(xué)模型的理解能力；該模型為一維集覆蓋問題，需要選出這樣的一維向量<x1,x2,xn> ,使得每一行都被選出的列覆蓋，被哪一列或幾列覆蓋不重要，要滿足約束矩陣。A BCD的說法均正確。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2以及第九章課件。(3) 參閱教材，理解課程表優(yōu)化安

36、排問題。關(guān)于該問題，以下說法正確的選項是 。(A) 該問題，與會議室租用問題、測試用例選擇問題和航班機組成員問題，是同一個問題;(B) 該問題，是一個一維的集合覆蓋問題，仍舊可用以下數(shù)學(xué)模型來表達；nmin z(x) qXj (1)j ins.t.aijxj 1, i 1,2,., m (2)j iXj0,1, j 1,2,., n (3)(C) 該問題，不同于(B)的數(shù)學(xué)模型。它是一個二維的集合覆蓋問題，(B)中數(shù)學(xué)模型的可能解 是<X1,X2，,%, Xn>,而本問題的可能解是 <X11,X12,Xij,Xnn>(D) 上述說法全不正確。答案：C解釋：此題考查對數(shù)學(xué)

37、模型的理解能力；課程表優(yōu)化問題是一個二維集覆蓋問題。其可能解為二維矩陣。其模型為:8min f (x)iJ6CijXij1 j 1(1)s.t.6aij Xij1,j 1for every i, i1,.,8(2)s.t.8a x.2,ij iji 1for every j,j 1,.,6(3)Xij0,1；i 1,.,8;j 1,.,6(4)C正確。故此題的答案為C。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2以及第九章課件。(4) 會議室租用問題、測試用例選擇問題和航班機組成員問題，這三個問題的遺傳算法求解過程, 與下述過程相同還是不同呢，說法正確的選項是 。bl1Q111&

38、#176;10即出;種筑材時帑的慢童玄噴卅* il,. .JM4'4fc|p：tiiiK!ilKr<I 冬他悴 養(yǎng)理息虬縣B.B _*+>)« M 1=可o'o'ioojg|網(wǎng)WB 匚剛;tl匝 Q1遼0 1 01i a 1oa 0 a 1-0 0 D%oilel卞 nw尿斗 % .i'.Min FJt) x3-1«x *20 T0r x«i. .mZMHMi0叩心惻t優(yōu)it 用mm ie m，樸r* iOOloOl噸nl.Jh.削1曲卜顯 r flit FJBH解想亀卜代抻1% FIWJhii：戈蛙FcKj命TIT P

39、 _ 桿汩FM Xiiuo|iidi|pq|i旌解4H和適 眉件rm12, Fi2f 6442. F(421=I4O5 fl fll B F|e|=-flBi g|Q|1 S 齢徘=MJ i! c 比-I如 “R-011JI1011111©10 U U Jb u 亠-亠O'foil' 37. F(37«8鶯衛(wèi)片群倔比解壩ZI.F(21E «!0 辛 57, Ft5T|221Bfia l| 41. S：T22HH：赫M：工ig .蟹K為舌十 H?L豐心扃r耽F 即屮C101V00 0111oo0I1'170-31(A) 求解過程是相同的，只是

40、適應(yīng)度函數(shù)不同，其他如可能解的編碼、初始解的獲得、交叉與 變異規(guī)那么、汰選可能解形成新一代種群的規(guī)那么、算法終止條件等都可以相同；(B) 求解過程是相同的，可能解的編碼、初始解的獲得、交叉與變異規(guī)那么、汰選可能解形成新 一代種群的規(guī)那么、算法終止條件等都可以是相同的，但適應(yīng)度函數(shù)是不同的，此外，這三個問題 需要判斷一個可能解是否是可行解-即產(chǎn)生的可能解需要滿足約束條件(2)，而圖中例如沒有這一 過程；(C) 求解過程是不同的，除適應(yīng)度函數(shù)不同外，其他如可能解的編碼、初始解的獲得、交叉與 變異規(guī)那么、汰選可能解形成新一代種群的規(guī)那么、算法終止條件等都是不同的；(D) 前述說法都正確。答案：B解釋

41、：此題考查對數(shù)學(xué)模型的理解能力；采用遺傳算法解決問題的根本框架都是一樣的，因此求解過程是相同的，可能解的編碼、初 始解的獲得、交叉與變異規(guī)那么、汰選可能解形成新一代種群的規(guī)那么、算法終止條件等都可以是相 同的，而題目中提到的三個問題的適應(yīng)度函數(shù)均為模型中的條件1,而圖示的問題的適應(yīng)度函數(shù)為F(x)，兩者是不一樣的。另外，圖示的問題中，所有的可能解都是可行解，但三個問題的可能 解救不一定是可行解，必須得驗證。這點也是不一樣的。綜上，此題的答案為B。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2以及第九章課件。(5) 參閱教材，理解課程表優(yōu)化安排問題的數(shù)學(xué)模型如下：s.t.s.t.8

42、6min f(x)e xj iji 1 j 16aij 筍1, for every i, i 1,.,8j 1(1)a x ij iji 12, for every j, j 1,.,6Xij 0,1 ; i 1,.,8; j 1,.,6關(guān)于該模型，以下說法不正確的選項是 。(A) 公式(1)是計算某一種方案-該方案給出了哪一門課程安排在哪個教室的一種安排，計算該方案的總本錢，目標是求具有最小總本錢的那個方案。其中教室被從1,n編號，課程被從1,m編號。如果xij=1，表示課程i被安排在教室j;如果xij=0,表示課程i未被安排在教室j; cij表示選擇課程i安排在教室j時所需消耗的本錢。(B

43、) 公式(2)表示每一門課程至少被安排在1個教室，也可以安排在多個教室；(C) 公式(3)表示每一個教室至多安排2門課程，也可以不安排課程；(D) 公式說明Xij只能等于0或1。等于1表示課程i被安排在教室j;等于0那么表示課程i 與課程j沒有關(guān)系；(E) 上述說法有不正確的。答案：B解釋：此題考查對數(shù)學(xué)模型的理解能力；選項A的說法沒有問題。公式2表示一門課程恰好被安排在一個教室。而不是 B 選項中的“每一門課程至少被安排在 1個教室，也可以安排在多個教室。B的說法正確。C D的說法也沒有問題。綜上，此題的答案為B。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題2以及第九章課件。(1

44、)以下說法正確的選項是 。(A) 可行解集合近似解集合(B) 可能解集合可行解集合(C) 可能解集合可行解集合(D) 最優(yōu)解集合滿意解集合7、對類似于遺傳算法的理解，需要理解關(guān)于各種解的名詞之間的細微差異?？赡芙饧蠞M意解集合最優(yōu)解集合; 滿意解集合近似解集合最優(yōu)解集合; 近似解集合滿意解集合最優(yōu)解集合; 近似解集合可行解集合可能解集合;答案：C解釋：此題考查對關(guān)于“解的一些名詞的理解；可能解中包含可行解?？尚薪庵邪平狻＝平庵邪瑵M意解。滿意解中包含最優(yōu)解。 C選項的說法是正確的。綜上，此題的答案為C。具體內(nèi)容請第九章參考課堂視頻與第九章課件。(2-1)設(shè)一個問題的解的形式為x,以下說

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

46、被稱為可能解；(B) 滿足問題約束的可能解被稱為可行解；(C) 在任何一組可行解中求出的最優(yōu)解被稱為是滿意解；(D) 所有可行解中的最優(yōu)解是問題的最優(yōu)解；(E) 上述說法有不正確的；答案：C 解釋:此題考查對關(guān)于“解的一些名詞的理解；由x的取值空間給定的任何一個x值為可能解。該x的值能滿足問題的要求，該x才被稱為 一個可行解。A B的說法正確。由一個算法在任何一組可行解中求出的最優(yōu)解被稱為是近 似解,符合用戶期望的近似解被稱為是滿意解,(C)的說法不正確。D的說法正確。綜上，此題 的答案為C。具體內(nèi)容請第九章參考課堂視頻與第九章課件。8 68、對于類似于課程表優(yōu)化安排問題的二維集覆蓋問題：mi

47、n f(x)CjXj，利用遺傳算i 1 j 1法計算求解，答復(fù)以下問題。(1) 關(guān)于其可能解的編碼，說法正確的選項是 。(A) 僅可以按行優(yōu)先編碼；(B) 僅可以按列優(yōu)先編碼；(C) 既可以按行優(yōu)先編碼，又可以按列優(yōu)先編碼，但其對算法中交叉、變異操作規(guī)那么設(shè)計是沒 有影響的；(D) 既可以按行優(yōu)先編碼，又可以按列優(yōu)先編碼，還可以有其他編碼方式，不同的編碼設(shè)計， 可以有不同的交叉、變異操作規(guī)那么；答案：D 解釋:此題考查對問題解的編碼的多樣性；二維集覆蓋問題的可能解的都是二維矩陣。對于二維矩陣的編碼可以有多種形式。每一種編 碼方式，都可以有自己的交叉、變異操作規(guī)那么。 D的說法是正確的。A B

48、C的說法 都不正確。綜上，此題的答案為D。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題2與第九章課件。(2) 關(guān)于交叉規(guī)那么的設(shè)計，以下說法不正確的選項是 。(A) 既可以采取兩段交叉，也可以采取多段交叉；(B) 兩段交叉中，交叉點的選擇可以隨機確定：即隨機確定一個交叉點，從中將解編碼分為兩 段，將兩個可能解的兩段編碼交換形成兩個新的可能解；(C) 多段交叉既可采取等距離分段交叉， 亦可采取可變距離分段交叉，交叉點和段間距離都可 以隨機確實定；(D) 交叉規(guī)那么僅有以上(A)(B)(C)幾種情況；(E) 對不同的問題，還可能有不同的交叉規(guī)那么設(shè)計；答案：D解釋：此題考查對交叉

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

50、么十分的豐富。A B C均為交叉規(guī)那么。但交叉規(guī)那么不僅僅限于此。還可以 采用交叉與隨機的交叉規(guī)那么，如：兩個染色體的各段的x位如都相同，那么不交換，否那么以概率 p進行交換。具體問題具體分析。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題5與第九章課件。9、遺傳算法的設(shè)計在很多方面都需要引入概率， 在哪些方面引入概率呢？以下說法不正確的選項(A) 初始種群確實定可以引入概率。結(jié)合問題可能解的分布選擇概率模型，將此概率模型引入 初始解的隨機選擇過程中，那么選擇出的初始可能解有助于遺傳算法快速地獲得滿意解；(B) 交叉規(guī)那么設(shè)計可以引入概率。從待交叉兩個可能解確實定，到交叉點確實

51、定，甚至到段間 距離確實定等都可以引入概率，恰當?shù)母怕誓Ｐ瓦x擇有助于遺傳算法快速地獲得滿意解；(C) 遺傳算法處處表達著概率的應(yīng)用和隨機處理。當可能的方案比擬多，且窮舉計算量很大時，便可采用概率方式進行隨機化處理。 例如兩個可能解“00001000 10001100 “00111000 1011 1100， 如果做兩段交叉，那么分段交叉點可以有16個，如果16個交叉點都選擇，那么可能該子解空間仍舊很大，此時可依概率選擇1號位置交叉至16號位置交叉，選擇幾個那么依概率模型確定，選擇1個至16個中的某些個；(D) 雖然遺傳算法處處可以引入概率，但其概率模型卻是相同的；(E) 上述說法有不正確的。答

52、案：D 解釋:此題考查對遺傳算法引入概率的認識；遺傳算法處處都可以引入概率。A B C都是在在遺傳算法中參加概率的例子。在A B C描述的例子中，都引入了概率。常見的概率模型有：古典概型，幾何概型，連續(xù)變量，離散變量，正態(tài)模型，泊松模型，指數(shù)模型等?？梢愿鶕?jù)不同的情況選擇不同的模型。所以D的說法是不正確的。綜上，此題的答案為：D。具體內(nèi)容請第九章參考課堂視頻“怎樣用遺傳算法解決具體的應(yīng)用問題5與第九章課件。10、遺傳算法設(shè)計需要引入變異操作。變異操作是對種群中的某些可能解 (個體)的某些編碼位進 行突變處理，例如二進制編碼的解 01110011,其第3位(自左而右)當前為1那么將其變?yōu)?，稱為

53、 變異操作。關(guān)于變異操作，答復(fù)以下問題。(*1)關(guān)于如何應(yīng)用變異操作，以下說法不正確的選項是 。(A) 對種群中所有可能解(個體)以事先設(shè)定的變異概率確定是否進行變異；(B) 對進行變異的可能解(個體)隨機選擇變異位置進行相應(yīng)位置的“位變異；(C) 對進行變異的可能解(個體)隨機選擇變異位置進行相應(yīng)位置的“位組合變異；(D) 變異概率應(yīng)選取較大值，即：使變異頻繁發(fā)生，這樣有助于快速收斂到滿意解；(E) 上述說法有不正確的。答案：D解釋：此題考查對遺傳算法中關(guān)于變異的認識。選項(D)中，變異概率：控制算法中變異操作的使用頻率， 實際情況下變異發(fā)生的頻率并非越 頻繁越好，當變異概率無限增大的時候，遺傳算法就變?yōu)榧冸S機搜索了，因此變異概率并不是可 以無限擴大的，即在一定條件下使變異概率盡量大有助于快速收斂到滿意解。具體內(nèi)容請參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問題(IV) 和第九章課件。通過變異操作，使遺傳算法具有局部的隨機搜索能力。為什么？以下說法不正確的