遺傳算法復習資料

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