遺傳算法復(fù)習(xí)資料

1輪盤賭選擇是指?jìng)€(gè)體選中并遺傳到下一代群體中的概率，與該個(gè)體的適應(yīng)度大小成正比。其工作過(guò)程是這樣的：設(shè)想群體全體成員的適應(yīng)性分?jǐn)?shù)有一張餅圖來(lái)代表，這張餅圖就和用于賭博的轉(zhuǎn)輪形狀一樣。我們要為群體中每一染色體指定餅圖中一個(gè)小塊。為了選取一個(gè)染色體，你要做的就是旋轉(zhuǎn)這個(gè)輪子并把一個(gè)小球拋入其中，讓小球翻來(lái)翻去地跳動(dòng)，知道輪盤停止時(shí)，看小球停止在哪一塊上，就選中與它對(duì)應(yīng)的那個(gè)染色體。2作業(yè)車間調(diào)度問(wèn)題可以描述為：給定一個(gè)工件的集合和一個(gè)機(jī)器的集合，每個(gè)工件包括了多道工序，每道工序需要在一臺(tái)給定的機(jī)器上非間斷的加工某一段時(shí)間；每臺(tái)機(jī)器一次最多只能加工一道工序；調(diào)度就是把工序分配給機(jī)器上某個(gè)時(shí)間段。問(wèn)題的目標(biāo)是找到最小時(shí)間長(zhǎng)度的調(diào)度。3適應(yīng)度函數(shù)是度量個(gè)體適應(yīng)度的函數(shù)。它來(lái)度量群體中各個(gè)給在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。實(shí)用度較高的個(gè)體遺傳到下一代的概率就較大；而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對(duì)小一些。4小生境小生境是指特定環(huán)境中的一種組織的功能，把有共同特征的組織稱作物種。生物學(xué)中，小生境是指特定環(huán)境下的一種生存環(huán)境。生物在其進(jìn)化過(guò)程中，一般總是與自己相同的物種生活在一起，共同繁衍后臺(tái)；他們也都是在某一特定的地理區(qū)域中生存。例如，熱帶魚不能再叫冷的地帶生存，而北極熊也不能在熱帶生存。更特別的例子，人類有個(gè)別的部落至今還仍存在鮮為人知的某個(gè)閉塞的原始環(huán)境中，他們的智力或進(jìn)化水平也許比不上現(xiàn)代開放環(huán)境中的人，但在這個(gè)部落內(nèi)部，也不失有一些優(yōu)秀分子。5二倍體算子生物學(xué)中，二倍體是指含有兩個(gè)染色體組（同源基因組）的個(gè)體。算法DiploidyGA初始化，并設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器初值：t<-1隨機(jī)產(chǎn)生具有二倍體結(jié)構(gòu)的初始群體P(t)對(duì)初始群體P(t)進(jìn)行顯性操作評(píng)價(jià)初始群體P(t)中各個(gè)個(gè)體的適應(yīng)度交叉操作：P’(t)<-Crossover[P(t)]。由每?jī)蓚€(gè)隨即配對(duì)的二倍體個(gè)體進(jìn)行交叉操作時(shí)，共可產(chǎn)生四個(gè)單倍體個(gè)體變異操作：P’’(t)<-Multation[P’(t)]。在對(duì)群體中的各個(gè)個(gè)體進(jìn)行變異操作時(shí)，需要考慮隱性基因的作用對(duì)群體P’’(t)進(jìn)行顯性操作評(píng)價(jià)群體P’’(t)中各個(gè)個(gè)體的適應(yīng)度個(gè)體選擇、復(fù)制操作：P(t+1)<-Reproduction[P(t)UP’’(t)]終止條件判斷。若不滿足終止條件，則t<-t+1轉(zhuǎn)到第5）步，繼續(xù)進(jìn)行進(jìn)化操作過(guò)程；若滿足終止條件，則輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束。6使用基本遺傳算法進(jìn)行運(yùn)算必須提前設(shè)定幾個(gè)參數(shù)，每個(gè)參數(shù)的取值范圍是多少？選擇操作在遺傳算法中的作用是什么？能舉出2種常用的選擇算法，并能詳細(xì)說(shuō)遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個(gè)體編碼串長(zhǎng)度（使用二進(jìn)制編碼來(lái)表示個(gè)體時(shí)，編碼串長(zhǎng)度的選取與問(wèn)題所要求的求解精度有關(guān)）、群體大小M(20-100)、交叉概率Pm(0.0001-0.1)、終止代數(shù)T(100-1000)、代溝G(常見=1.0)選擇操作就是確定如何從父代群體中按某種方法選擇哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。比如輪盤賭選擇、排序選擇輪盤賭選擇：是一種回放式隨機(jī)采樣的方法。基本思想是各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。1）計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和；2）計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)的的大小，即為各個(gè)個(gè)體被遺傳到下代群體中的概率；3）使用模擬賭盤操作來(lái)確定各個(gè)個(gè)體被選中的次數(shù)。排序選擇基本思想是對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。1）對(duì)群體中的所有個(gè)體按其適應(yīng)度進(jìn)行排序；2）根據(jù)具體求解問(wèn)題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配各個(gè)個(gè)體；3）以各個(gè)個(gè)體所分配到的橫串值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來(lái)產(chǎn)生下一代群體。7常用的作業(yè)車間調(diào)度編碼方法有幾種，分別是什么？2種基于工件、基于工序8變異操作在遺傳算法中的作用是什么？能舉出2種常用的變異方法，并能詳細(xì)說(shuō)名作用（1）改善遺傳算法的局部搜索能力（2）維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。例如基本位變異和均勻變異基本位變異操作是指對(duì)個(gè)體編碼串中以變異概率Pm隨機(jī)指定的某一位或某幾位基因座上的基因值作變異運(yùn)算?；疚蛔儺惒僮鞲淖兊闹皇莻€(gè)體編碼串中的個(gè)別幾個(gè)基因座上的基因值。均勻變異操作是指分別符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。首先依次指定個(gè)體編碼串產(chǎn)生的每個(gè)基因座為變異點(diǎn)。然后，對(duì)每個(gè)變異點(diǎn)以變異概率Pm從對(duì)應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)替代原有基因值。9遺傳模擬退火算法的基本思想是什么？能寫出遺傳模擬退火算法的描述。模擬退火算法是將遺傳算法與模擬退火算法相結(jié)合而構(gòu)成的一種哦你優(yōu)化算法。遺傳算法的局部搜索能力較差，但把握搜索過(guò)程總體的能力較強(qiáng)；而模擬退火算法具有較強(qiáng)的局部搜索能力，并能是搜索過(guò)程避免陷入局部最優(yōu)解，但該算法對(duì)整個(gè)搜索空間的狀況了解不多，不便于是搜索過(guò)程進(jìn)入最有希望的搜索區(qū)域，從而使運(yùn)算效率不高。但兩者相結(jié)合互相取長(zhǎng)補(bǔ)短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法，即遺傳模擬退火算法的基本思想。算法GeneticSimulatedAnnealingGA進(jìn)化代數(shù)計(jì)數(shù)器初值：t<-0隨機(jī)產(chǎn)生初始群體P(t)評(píng)價(jià)初始群體P(t)中的適應(yīng)度交叉操作：P’(t)<-Crossover[P(t)]。變異操作：P’’(t)<-Multation[P’(t)]。個(gè)體模擬退火操作：P’’’(t)<-SimulatedAnnealing[P’’(t)]評(píng)價(jià)群體P’’’(t)的適應(yīng)度個(gè)體選擇、復(fù)制操作：P(t+1)<-Reproduction[P(t)UP’’’(t)]終止條件判斷。若不滿足終止條件，則t<-t+1轉(zhuǎn)到第4）步，繼續(xù)進(jìn)行進(jìn)化操作過(guò)程；若滿足終止條件，則輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束。10遺傳算法的優(yōu)點(diǎn)，并能給出一個(gè)求解某個(gè)具體問(wèn)題的改進(jìn)方案。優(yōu)點(diǎn)：1）遺傳算法的處理對(duì)象不是參數(shù)本身，而是對(duì)參數(shù)集進(jìn)行了編碼的個(gè)體。此編碼操作使得遺傳算法可直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。2）遺傳算法不再是單點(diǎn)搜索，而是對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估。這一特點(diǎn)使得一竄算法具有較好的全局搜索性能，減少了限于局部搜索的風(fēng)險(xiǎn)。3）在標(biāo)準(zhǔn)的遺傳算法中，僅有適應(yīng)度函數(shù)來(lái)評(píng)估個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作而且適應(yīng)度函數(shù)不受連續(xù)可微的約束，其定義域可任意設(shè)定，對(duì)適應(yīng)度函數(shù)的唯一要求是對(duì)于輸入可計(jì)算出加以比較的正確的輸出。4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)它的搜索方向。改進(jìn)方案求TSP、遺傳模擬退火算法TSP：假設(shè)N個(gè)城市，有一個(gè)旅行商人要拜訪這N個(gè)城市。他必須選擇要走的路徑，而路徑的限制是每個(gè)城市只能拜訪一次而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得到的路徑路程為所有路徑之中的最小值，即求最佳路徑。遺傳算法求旅行商問(wèn)題的一般編碼策略主要有二進(jìn)制表示、次序表示、路徑表示、矩陣表示和邊表示等。路徑編碼是最直觀的方式，以城市序號(hào)作為遺傳基因、一維數(shù)組city[]來(lái)表示（假設(shè)有10個(gè)城市），二維數(shù)組r[][]表示各個(gè)城市之間的路徑關(guān)系，PopSize表示種群類DNA個(gè)數(shù)，則初始群體可以自動(dòng)生成。利用評(píng)價(jià)函數(shù)evaluate()計(jì)算出該種群的適應(yīng)性。通過(guò)則有函數(shù)elitist()將該代中的最優(yōu)及最差個(gè)體保存下來(lái)，如果新種群中最有個(gè)體由于父代中最優(yōu)個(gè)體則將其保存。否則，將當(dāng)代中最差個(gè)體替換為父代中最優(yōu)個(gè)體，