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

1、第 9 章 怎樣研究算法 : 遺傳算法例如1、P類問(wèn)題、NP類問(wèn)題、NPC類問(wèn)題是電腦科學(xué)領(lǐng)域關(guān)于可求解性可計(jì)算性很重要的概念。關(guān) 于 P、 NP 和 NPC 類問(wèn)題，答復(fù)以下問(wèn)題。(1) 以下說(shuō)法不正確的選項(xiàng)是 。(A) P類問(wèn)題是電腦可以在有限時(shí)間內(nèi)能夠求解的問(wèn)題；(B) NP 類問(wèn)題是電腦可以在有限時(shí)間內(nèi)能夠驗(yàn)證“解的正確性的問(wèn)題；(C) NPC 類問(wèn)題是對(duì)問(wèn)題的每一個(gè)可能解，電腦都可以在有限時(shí)間內(nèi)驗(yàn)證“解的正確性的 問(wèn)題，被稱為 NP 完全問(wèn)題；(D) 上述說(shuō)法有不正確的；答案：D 解釋：此題考核P類問(wèn)題、NP類問(wèn)題、NPC類問(wèn)題的概念。P類問(wèn)題指電腦可以在有限時(shí)間內(nèi)求解的問(wèn)題，(A)

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

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

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

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

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

7、不確定性， 如“任意組合一個(gè)解，、“隨機(jī)組合一個(gè)解，等；(B) 它能夠找到一個(gè)算法、甚至是多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解，但算法是通過(guò)“猜想方 式求出問(wèn)題的解；(C) 它能夠通過(guò)“產(chǎn)生任何一個(gè)解，并驗(yàn)證解的正確性的方法進(jìn)行求解；(D) 它一定是能夠找到多項(xiàng)式時(shí)間復(fù)雜性算法以驗(yàn)證給定“解的正確性的問(wèn)題；(E) 上述說(shuō)法有不正確的；答案：E解釋：此題考核對(duì)NP類問(wèn)題概念的理解。NP類問(wèn)題：非確定性多項(xiàng)式問(wèn)題(Non-deterministic Polynomial)。有些問(wèn)題，其答案是無(wú)法直 接計(jì)算得到的，只能通過(guò)間接的猜算或試算來(lái)得到結(jié)果，這就是非確定性問(wèn)題(Non-deterministic)。

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

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

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

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

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

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

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

15、答案：B解釋：此題考核對(duì)生物學(xué)中的概念與電腦中的概念的映射的理解。染色體映射到電腦中就是編碼解，即一個(gè)可能解的基因型。一個(gè)基因即是指可能解的某一位 或幾位，A3正確。種群是指假設(shè)干可能解的集合，而不一定包含問(wèn)題的滿意解，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)勝劣汰而形成的遺傳算法的求解過(guò)程如以下列圖示意。理解該圖，答復(fù)以下問(wèn)題。和糾Wit陽(yáng)承if左丄 廠VLMWlli 墀斥比I：HN 0 i44X 搟覆

16、F(X> I3-10X *20 for0 1D1011 01D10l'0Illi1i01和蠟戶群初細(xì)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ò)程示意。關(guān)于圖中包含了哪些過(guò)程，以下說(shuō)法正確的選項(xiàng)是(A) 可能解的編碼過(guò)程和初始種群的產(chǎn)生過(guò)程；(B) 交叉、變異形成候選種群的過(guò)程；(C) 可能解的適應(yīng)度計(jì)算過(guò)程和汰選可能解形成新一代種群的過(guò)程;(D) 算法終止及最終解的形成過(guò)程；(E) 上述全部過(guò)程。答案：E解釋：此題考查學(xué)生對(duì)遺傳算法根本求解過(guò)程的理解。圖中第一行第一個(gè)箭頭即是可能解的編碼過(guò)程和初始種群的產(chǎn)生過(guò)程。最右的大

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

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

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

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

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

23、模的一種方向；(D) 適應(yīng)度函數(shù)可以任取一個(gè)極值函數(shù)，它與求解問(wèn)題本身可以沒(méi)有什么關(guān)系；(E) 上述有不正確的說(shuō)法。答案：D解釋：此題考查學(xué)生對(duì)遺傳算法的適應(yīng)度函數(shù)的理解。遺傳算法的適應(yīng)度函數(shù)用來(lái)考察解與最優(yōu)解的關(guān)系接近程度、方向等。而極值函數(shù)可以 簡(jiǎn)單、清晰地表現(xiàn)該關(guān)系。所以，極值函數(shù)經(jīng)常被選為遺傳算法的適應(yīng)度函數(shù)，A B C正確。適應(yīng)度函數(shù)不能隨意選擇，一定是問(wèn)題映射形成的函數(shù)，否那么該適應(yīng)度函數(shù)沒(méi)有意義，D 錯(cuò)誤。故此題的答案為：D具體內(nèi)容請(qǐng)參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問(wèn)題以及第九章課件。4、關(guān)于遺傳算法為什么可以求解 NPC類問(wèn)題。理解以下列圖，答復(fù)以下問(wèn)題。 *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(蜀丙単雨陽(yáng)(可

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

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

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

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

29、的答案為D。具體內(nèi)容請(qǐng)參考課堂視頻“遺傳算法為什么可以求解 NPC問(wèn)題以及第九章課件。(3) 遺傳算法是典型的計(jì)算求解的方法，它通過(guò)“產(chǎn)生任何一個(gè)可能解，并驗(yàn)證可能解的正確性 的方法求解一個(gè)復(fù)雜問(wèn)題。關(guān)于計(jì)算求解，以下說(shuō)法不正確的選項(xiàng)是 。(A) 在獲得滿意解的概率方面，如果初始可能解被恰中選擇的話，導(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)生新可能

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

31、是 。(A) 當(dāng)對(duì)某問(wèn)題求解，找不到更好的多項(xiàng)式時(shí)間復(fù)雜性算法的時(shí)候；(B) 當(dāng)問(wèn)題的可能解能夠被表達(dá)，并能夠確定問(wèn)題的解空間的時(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)參考課堂視頻“遺傳算法為什么可以

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

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

34、考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問(wèn)題2以及第九章課件。(2)集覆蓋問(wèn)題可以抽象為以下模型，請(qǐng)對(duì)以下模型進(jìn)行理解。關(guān)于該模型，以下說(shuō)法不正確的選項(xiàng)是。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)是計(jì)算所選擇資源的總本錢，目標(biāo)是求具有最小總本錢的資源集合。其中資源被從1,n編號(hào)。如果Xj=1，表示資源j被選擇；如果xj=0,表示資源j未被選擇；Cj表示選擇資源 j時(shí)所需消耗的本錢。(B) 公式(2)表示每一個(gè)任務(wù)i都被某一個(gè)已選擇的資源j(xj>0)能完成的任務(wù)集所覆蓋

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

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

37、模型的理解能力；課程表優(yōu)化問(wèn)題是一個(gè)二維集覆蓋問(wèn)題。其可能解為二維矩陣。其模型為: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)容請(qǐng)參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問(wèn)題2以及第九章課件。(4) 會(huì)議室租用問(wèn)題、測(cè)試用例選擇問(wèn)題和航班機(jī)組成員問(wèn)題，這三個(gè)問(wèn)題的遺傳算法求解過(guò)程, 與下述過(guò)程相同還是不同呢，說(shuō)法正確的選項(xiàng)是 。bl1Q111&

38、#176;10即出;種筑材時(shí)帑的慢童玄噴卅* 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) 求解過(guò)程是相同的，只是

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

41、：此題考查對(duì)數(shù)學(xué)模型的理解能力；采用遺傳算法解決問(wèn)題的根本框架都是一樣的，因此求解過(guò)程是相同的，可能解的編碼、初 始解的獲得、交叉與變異規(guī)那么、汰選可能解形成新一代種群的規(guī)那么、算法終止條件等都可以是相 同的，而題目中提到的三個(gè)問(wèn)題的適應(yīng)度函數(shù)均為模型中的條件1,而圖示的問(wèn)題的適應(yīng)度函數(shù)為F(x)，兩者是不一樣的。另外，圖示的問(wèn)題中，所有的可能解都是可行解，但三個(gè)問(wèn)題的可能 解救不一定是可行解，必須得驗(yàn)證。這點(diǎn)也是不一樣的。綜上，此題的答案為B。具體內(nèi)容請(qǐng)參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問(wèn)題2以及第九章課件。(5) 參閱教材，理解課程表優(yōu)化安排問(wèn)題的數(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)于該模型，以下說(shuō)法不正確的選項(xiàng)是 。(A) 公式(1)是計(jì)算某一種方案-該方案給出了哪一門課程安排在哪個(gè)教室的一種安排，計(jì)算該方案的總本錢，目標(biāo)是求具有最小總本錢的那個(gè)方案。其中教室被從1,n編號(hào)，課程被從1,m編號(hào)。如果xij=1，表示課程i被安排在教室j;如果xij=0,表示課程i未被安排在教室j; cij表示選擇課程i安排在教室j時(shí)所需消耗的本錢。(B

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

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

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

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

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

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

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

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

51、定，甚至到段間 距離確實(shí)定等都可以引入概率，恰當(dāng)?shù)母怕誓Ｐ瓦x擇有助于遺傳算法快速地獲得滿意解；(C) 遺傳算法處處表達(dá)著概率的應(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) 雖然遺傳算法處處可以引入概率，但其概率模型卻是相同的；(E) 上述說(shuō)法有不正確的。答

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

53、 變異操作。關(guān)于變異操作，答復(fù)以下問(wèn)題。(*1)關(guān)于如何應(yīng)用變異操作，以下說(shuō)法不正確的選項(xià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) 上述說(shuō)法有不正確的。答案：D解釋：此題考查對(duì)遺傳算法中關(guān)于變異的認(rèn)識(shí)。選項(xiàng)(D)中，變異概率：控制算法中變異操作的使用頻率， 實(shí)際情況下變異發(fā)生的頻率并非越 頻繁越好，當(dāng)變異概率無(wú)限增大的時(shí)候，遺傳算法就變?yōu)榧冸S機(jī)搜索了，因此變異概率并不是可 以無(wú)限擴(kuò)大的，即在一定條件下使變異概率盡量大有助于快速收斂到滿意解。具體內(nèi)容請(qǐng)參考課堂視頻“怎樣用遺傳算法求解具體的應(yīng)用問(wèn)題(IV) 和第九章課件。通過(guò)變異操作，使遺傳算法具有局部的隨機(jī)搜索能力。為什么？以下說(shuō)法不正確的