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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、個(gè)方案。其中教室被從1,n編號(hào)，課程被從1,m編號(hào)。如果xij=1，表示課程i被安排在教室j；如果xij=0，表示課程i未被安排在教室j；cij表示選擇課程i安排在教室j時(shí)所需消耗的成本。(B)公式(2)表示每一門課程至少被安排在1個(gè)教室，也可以安排在多個(gè)教室；(C)公式(3)表示每一個(gè)教室至多安排2門課程，也可以不安排課程；(D)公式(4)說明xij只能等于0或1。等于1表示課程i被安排在教室j；等于0則表示課程i與課程j沒有關(guān)系；(E)上述說法有不正確的。答案：B解釋：本題考查對(duì)數(shù)學(xué)模型的理解能力；選項(xiàng)（A）的說法沒有問題。公式（2）表示一門課程恰好被安排在一個(gè)教室。而不是（B）選項(xiàng)中的“

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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