遺傳演算法的操作步驟是什麼

A. 遺傳演算法選中次數怎麼算

遺傳演算法選中次數演算法如下：

1、在搜索空間U上定義一個適應度函數f(x)，給定種群規模N，交叉率Pc和變異率Pm，代數T。

2、隨機產生U中的N個個體s1, s2, sN，組成初始種群S={s1, s2, sN}，置代數計數器t=1。

3、計算S中每個個體的適應度f() 。

4、若終止條件滿足，則取S中適應度最大的個體作為所求結果，演算法結束。

5、按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體並將其染色體復制，共做N次，然後將復制所得的N個染色體組成群體S1。

6、按交叉率Pc所決定的參加交叉的染色體數c，從S1中隨機確定c個染色體，配對進行交叉操作，並用產生的新染色體代替原染色體，得群體S2。

7、按變異率Pm所決定的變異次數m，從S2中隨機確定m個染色體，分別進行變異操作，並用產生的新染色體代替原染色體，得群體S3。

8、將群體S3作為新一代種群，即用S3代替S，t=t+1，轉步3。

相關基本概念：

1、個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

2、種群就是模擬生物種群而由若干個體組成的群體, 它一般是整個搜索空間的一個很小的子集。

3、適應度(fitness)就是借鑒生物個體對環境的 適應程度,而對問題中的個體對象所設計的 表徵其優劣的一種測度。

4、適應度函數(fitness function)就是問題中的 全體個體與其適應度之間的一個對應關系。 它一般是一個實值函數。該函數就是遺傳算 法中指導搜索的評價函數。

B. 遺傳演算法理解

遺傳演算法是一種進化演算法，進化是什麼哪？就是種群逐漸適應生存環境，種群中個體不斷得到改良的過程。

遺傳演算法是一種對生物遺傳的模擬、在演算法中，初始化一個種群，種群中的每個染色體個體都是一種解決方案，我們通過適應性fitness來衡量這個解決方案的好壞。並對它們進行選擇、變異、交叉的操作，找到最優的解決方案。

總結一下遺傳演算法的基本的步驟：

1.初始化一個種群，並評估每條染色體所對應個體的適應度。

2.選擇、交叉、變異，產生新的種群

3.再評估每個個體的適應值，如果適應值達到要求或者達到最大循環次數，否則重復2，不斷產生新種群。

知道了GA的大致流程之後、來具體分析一下細節，怎麼實現吧

我們知道遺傳演算法起源於生物遺傳，因此在種群中每個個體就是一個染色體，那如何對染色體進行編碼，讓它表示我們的解決方案那（就是把現實要優化的參數用編碼表示成一個染色體）。這里就遇到了一個編碼、解碼的問題，我們將需要優化的目標編碼成染色體，然後再解碼為我們可以用來計算fitness的解；

一般在進行參數優化時，一般有兩種方式：實數編碼、二進制編碼

實數編碼：基因直接用實數進行表示，這樣的表示方法比較簡單，不用特意解碼了，但是在交叉和變異時，容易過早收斂，陷入局部最優。

二進制編碼：將基因用二進制的形式表示，將參數的值轉化為二進制形式，這樣交叉、變異時更好操作，多樣性好，但是佔用的存儲空間大，需要解碼。

染色體就稱為個體。對於一次實驗，個體就是需要優化參數的一種解、許多這樣的個體就構成了種群。

在面對群體中那麼多個體時，如何判斷個體的好壞呢，就是通過適應值函數了，將解帶入適應值函數，適應值越大、解越好。

在遺傳演算法中，我們怎麼使得裡面的個體變得越來越優秀呢？

核心思想就是：選擇優秀的、淘汰不好的，並且為了生成更好的解，我們要嘗試交叉、變異，帶來新的解。

選擇就是從當前的種群中選擇出比較好的個體、淘汰不好的個體

常見的選擇方法有：輪盤賭選擇、錦標賽選擇、最佳保留選擇等等

輪盤賭選擇就是根據每個個體fitness和種群所有fitness之和比較，確定每個個體被選中的概率，然後進行n次選擇，選擇n個個體構成新種群，是一種放回抽樣的方式。

錦標賽就是每次從種群中選擇m個個體，選擇最優的，放入新種群，重復選擇，直到新種群中個體數目達到n。

最佳保留選擇就是在輪盤賭的基礎上，將fitness個體先加進新種群，因為輪盤賭是一種概率模型，可能存在最優個體沒有進入新種群的情況。

在選擇之後，就要考慮產生新的、更優秀的解，為種群帶來新的血液。遺傳演算法的思路是交叉兩個優秀的解，往往get好的解。

交叉通過在經過選擇的種群中，隨機選擇一對父母，將它們的染色體進行交叉，生成新的個體，替代原來的解。

常用的交叉方法有：單點交叉、多點交叉等等。

交叉就像生物裡面，染色體交換基因一樣的～但是並不是種群中所有個體都進行交叉的，實現時可以，設置一個交叉率和交叉概率，隨機選擇種群中兩個體、隨機一個數，小於交叉率就進行交叉操作，並根據交叉概率判斷交叉的程度，從而生成新個體，反之就保留這兩個體。

變異也是一種產生新個體的方式，通過改變個體上基因，期望產生更好的解。比如在以二進制編碼的個體上，將裡面的0、1進行等位變化啥的，就是0變1、1變0這樣。同樣也要考慮變異率、變異產生的新解是不可控的，可能很好，也可能很壞，不能像交叉一樣，確保一定的效果，所以往往變異率設置的比較小。

C. 遺傳演算法的主要步驟

為了使用遺傳演算法來解決優化問題，准備工作分為以下四步^{［56，57，61］}。

7.4.1 確定問題的潛在解的遺傳表示方案

在基本的遺傳演算法中，表示方案是把問題的搜索空間中每個可能的點表示為確定長度的特徵串（通常是二進制串）。表示方案的確定需要選擇串長l和字母表規模k。在染色體串和問題的搜索空間中的點之間選擇映射有時容易實現，有時又非常困難。選擇一個便於遺傳演算法求解問題的表示方案經常需要對問題有深入的了解。

7.4.2 確定適應值的度量

適應值度量為群體中每個可能的確定長度的特徵串指定一個適應值，它經常是問題本身所具有的。適應值度量必須有能力計算搜索空間中每個確定長度的特徵串的適應值。

7.4.3 確定控制該演算法的參數和變數

控制遺傳演算法的主要參數有群體規模Pop-Size、演算法執行的最大代數N-Gen、交叉概率P_c、變異概率P_m和選擇策略R等參數。

（1）群體規模Pop-Size。群體規模影響到遺傳演算法的最終性能和效率。當規模太小時，由於群體對大部分超平面只給出了不充分的樣本量，所以得到的結果一般不佳。大的群體更有希望包含出自大量超平面的代表，從而可以阻止過早收斂到局部最優解；然而群體越大，每一代需要的計算量也就越多，這有可能導致一個無法接受的慢收斂率。

（2）交叉率P_c。交叉率控制交叉運算元應用的頻率，在每代新的群體中，有P_c·Pop-Size個串實行交叉。交叉率越高，群體中串的更新就越快。如果交叉率過高，相對選擇能夠產生的改進而言，高性能的串被破壞得更快。如果交叉率過低，搜索會由於太小的探查率而可能停滯不前。

（3）變異率P_m。變異是增加群體多樣性的搜索運算元，每次選擇之後，新的群體中的每個串的每一位以相等的變異率進行隨機改變。對於M進制串，就是相應的位從1變為0或0變為1。從而每代大約發生P_m·Pop-Size·L次變異，其中L為串長。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂到單一的值。高水平的變異率產生的實質是隨機搜索。

比起選擇和交叉，變異在遺傳演算法中是次要的，它在恢復群體中失去的多樣性方面具有潛在的作用。例如，在遺傳演算法執行的開始階段，串中一個特定位上的值1可能與好的性能緊密聯系，也就是說從搜索空間中某些初始隨機點開始，在那個位上的值1可能一致地產生適應性度量好的值。因為越好的適應值與串中那個位上的值1相聯系，復製作用就越會使群體的遺傳多樣性損失。當達到一定程度時，值0會從整個群體中的那個位上消失，然而全局最優解可能在串中那個位上是0。一旦搜索范圍縮小到實際包含全局最優解的那部分搜索空間，在那個位上的值0就可能正好是達到全局最優解所需的。這僅僅是一種說明搜索空間是非線性的方式，這種情形不是假定的，因為實際上所有我們感興趣的問題都是非線性的。變異作用提供了一個恢復遺傳多樣性的損失的方法。

（4）選擇策略R。有兩種選擇策略。一是利用純選擇，即當前群體中每個點復制的次數比與點的性能值成比例。二是利用最優選擇，即首先執行純選擇，且具有最好性能的點總是保留到下一代。在缺少最優選擇的情況下，由於采樣誤差、交叉和變異，最好性能的點可能會丟失。

通過指定各個參數Pop-Size、P_c、P_m和R的值，可以表示一個特定的遺傳演算法。

7.4.4 確定指定結果的方法和停止運行的准則

當遺傳的代數達到最大允許代數時，就可以停止演算法的執行，並指定執行中得到的最好結果作為演算法的結果。

基本的遺傳演算法

1）隨機產生一個由固定長度字元串組成的初始群體。

2）對於字元串群體，迭代地執行下述步驟，直到選擇標准被滿足為止。

①計算群體中的每個個體字元串的適應值；

②實施下列三種操作（至少前兩種）來產生新的群體，操作對象的選取基於與適應度成比例的概率。

選擇：把現有的個體串按適應值復制到新的群體中。

交叉：通過遺傳重組隨機選擇兩個現有的子串進行遺傳重組，產生兩個新的串。

變異：將現有串中某一位的字元隨機變異產生一個新串。

3）把在後代中出現的最好適應值的個體串指定為遺傳演算法運行的結果。這一結果可以是問題的解（或近似解）。

基本的遺傳演算法流程圖如圖7-1所示。

D. 遺傳演算法第一次提出來是在什麼文獻中

《搜索、優化和機器學習中的遺傳演算法》。

遺傳演算法（Genetic Algorithm，GA）最早是由美國的 John holland於20世紀70年代提出,該演算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。

遺傳演算法的基本運算過程如下：

（1）初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。

（2）個體評價：計算群體P(t)中各個個體的適應度。

（3）選擇運算：將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

（4）交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。

（5）變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。

（6）終止條件判斷：若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。