遺傳演算法中的選擇

1. 遺傳演算法的基本原理

遺傳演算法的基本原理和方法

一、編碼

編碼：把一個問題的可行解從其解空間轉換到遺傳演算法的搜索空間的轉換方法。

解碼（解碼）：遺傳演算法解空間向問題空間的轉換。

二進制編碼的缺點是漢明懸崖（Hamming Cliff），就是在某些相鄰整數的二進制代碼之間有很大的漢明距離，使得遺傳演算法的交叉和突變都難以跨越。

格雷碼（Gray Code）：在相鄰整數之間漢明距離都為1。

（較好）有意義的積木塊編碼規則：所定編碼應當易於生成與所求問題相關的短距和低階的積木塊；最小字元集編碼規則，所定編碼應採用最小字元集以使問題得到自然的表示或描述。

二進制編碼比十進制編碼搜索能力強，但不能保持群體穩定性。

動態參數編碼（Dynamic Paremeter Coding）：為了得到很高的精度，讓遺傳演算法從很粗糙的精度開始收斂，當遺傳演算法找到一個區域後，就將搜索現在在這個區域，重新編碼，重新啟動，重復這一過程，直到達到要求的精度為止。

編碼方法：

1、 二進制編碼方法

缺點：存在著連續函數離散化時的映射誤差。不能直接反映出所求問題的本身結構特徵，不便於開發針對問題的專門知識的遺傳運算運算元，很難滿足積木塊編碼原則

2、 格雷碼編碼：連續的兩個整數所對應的編碼之間僅僅只有一個碼位是不同的，其餘碼位都相同。

3、 浮點數編碼方法：個體的每個基因值用某一范圍內的某個浮點數來表示，個體的編碼長度等於其決策變數的位數。

4、 各參數級聯編碼：對含有多個變數的個體進行編碼的方法。通常將各個參數分別以某種編碼方法進行編碼，然後再將他們的編碼按照一定順序連接在一起就組成了表示全部參數的個體編碼。

5、 多參數交叉編碼：將各個參數中起主要作用的碼位集中在一起，這樣它們就不易於被遺傳運算元破壞掉。

評估編碼的三個規范：完備性、健全性、非冗餘性。

二、選擇

遺傳演算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取那些個體遺傳到下一代群體中的一種遺傳運算，用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。

常用的選擇運算元：

1、 輪盤賭選擇（Roulette Wheel Selection）：是一種回放式隨機采樣方法。每個個體進入下一代的概率等於它的適應度值與整個種群中個體適應度值和的比例。選擇誤差較大。

2、 隨機競爭選擇（Stochastic Tournament）：每次按輪盤賭選擇一對個體，然後讓這兩個個體進行競爭，適應度高的被選中，如此反復，直到選滿為止。

3、 最佳保留選擇：首先按輪盤賭選擇方法執行遺傳演算法的選擇操作，然後將當前群體中適應度最高的個體結構完整地復制到下一代群體中。

4、 無回放隨機選擇（也叫期望值選擇Excepted Value Selection）：根據每個個體在下一代群體中的生存期望來進行隨機選擇運算。方法如下

（1） 計算群體中每個個體在下一代群體中的生存期望數目N。

（2） 若某一個體被選中參與交叉運算，則它在下一代中的生存期望數目減去0.5，若某一個體未被選中參與交叉運算，則它在下一代中的生存期望數目減去1.0。

（3） 隨著選擇過程的進行，若某一個體的生存期望數目小於0時，則該個體就不再有機會被選中。

5、 確定式選擇：按照一種確定的方式來進行選擇操作。具體操作過程如下：

（1） 計算群體中各個個體在下一代群體中的期望生存數目N。

（2） 用N的整數部分確定各個對應個體在下一代群體中的生存數目。

（3） 用N的小數部分對個體進行降序排列，順序取前M個個體加入到下一代群體中。至此可完全確定出下一代群體中M個個體。

6、無回放余數隨機選擇：可確保適應度比平均適應度大的一些個體能夠被遺傳到下一代群體中，因而選擇誤差比較小。

7、均勻排序：對群體中的所有個體按期適應度大小進行排序，基於這個排序來分配各個個體被選中的概率。

8、最佳保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是用它來代替掉本代群體中經過交叉、變異等操作後所產生的適應度最低的個體。

9、隨機聯賽選擇：每次選取幾個個體中適應度最高的一個個體遺傳到下一代群體中。

10、排擠選擇：新生成的子代將代替或排擠相似的舊父代個體，提高群體的多樣性。

三、交叉

遺傳演算法的交叉操作，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。

適用於二進制編碼個體或浮點數編碼個體的交叉運算元：

1、單點交叉（One－pointCrossover）：指在個體編碼串中只隨機設置一個交叉點，然後再該點相互交換兩個配對個體的部分染色體。

2、兩點交叉與多點交叉：

（1） 兩點交叉（Two－pointCrossover）：在個體編碼串中隨機設置了兩個交叉點，然後再進行部分基因交換。

（2） 多點交叉（Multi－pointCrossover）

3、均勻交叉（也稱一致交叉，UniformCrossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。

4、算術交叉（ArithmeticCrossover）：由兩個個體的線性組合而產生出兩個新的個體。該操作對象一般是由浮點數編碼表示的個體。

四、變異

遺傳演算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換，從而形成以給新的個體。

以下變異運算元適用於二進制編碼和浮點數編碼的個體：

1、基本位變異（SimpleMutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。

2、均勻變異（UniformMutation）：分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在演算法的初級運行階段）

3、邊界變異（BoundaryMutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。

4、非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。

5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2的正態分布的一個隨機數來替換原有的基因值。

2. 遺傳演算法的選擇概率

如果用輪盤賭選擇法,則待選擇的個體選擇概率之和一定是1；
如果是基於排序的選擇,則不需要計算每個個體的選擇概率,也就談不上概率之和是不是1的說法.
我不知道你看的是什麼資料,不同的資料對排序選擇法的說明不同.一般情況下,排序不是根據個體在群體中的位置來確定什麼復制概率的,而是根據每個個體的適應度好壞來排序的.

3. 遺傳演算法，交叉概率，和變異概率，選擇，通常在多少值，合適

這幾個操作的概率是相互獨立的，並不要求和為1。
選擇操作中的概率，以輪賭法為例，概率只反映了個體被選擇到的可能性，與個體的適應度大小有關，一般是適應度越大，對應輪賭法中的概率值越大。
交叉操作中的概率是用於判定兩個個體是否進行交叉操作，一般都會大於0.9。
變異操作的概率是允許少數個體存在變異情況，以避免限入局部最優解，其值一般都在0.1以下。

4. 遺傳演算法中的錦標賽選擇演算法的思想是什麼

我理解的是，在50個人中，隨機選擇兩組人，每組10個人，對於每組的10個人按適應度進行排列，選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉；
然後再從剩下來的48個人中，隨機選擇兩組人，每組10個人，對於每組的10個人按適應度進行排列，選擇兩組中適應度最好的兩個個體作為母代進行兩兩交叉；
依此類推，知道你選出的母代個數滿足你的要求，這里母代個數肯定是少於50的。

5. 遺傳演算法中選擇運算元的問題

首先介紹sort函數用法：
[B,I]=sort(A,.....),I為返回的排序後元素在原數組中的行位置或列位置.B一般為排序後的數組。舉例：
A = 3 4 2
1 5 3
4 7 1
[B,I]=sort(A)
B = 1 4 1
3 5 2
4 7 3
I = 2 1 3
1 2 1
3 3 2
[Oderfi,Indexfi]=sort(fi)，因此這句話中的Oderfi保存了從小到大排列的結果，而Indexfi保存了Oderfi中對應原始數組（fi）的的原始位置。
fi_Size=(Oderfi/fi_sum)*Size 這句話挺難理解的，不過我運行了這個程序後，還是被我發現了
其中Oderf為 適應值 由小到大排列，fi_sum為適應值的總和，Size為總的個數，而fi_sum/size就是平均值，因此。fi_size中所存放的數據是Oderf中數值除以其平均值後的結果。其中必有大於1的，小於1的。我們這里的淘汰規則是淘汰掉 種群中小於平均值的數據，下邊的代碼是對這個規則的具體化
fi_S只包含0和1，其中0是小於平均值的個體，1是大於平均值的個體。
for j=1:1:fi_S(i) %Select and Reproce
TempE(kk,:)=E(Indexfi(i),:);
kk=kk+1; %kk is used to reproce
end
E中保存的是初始種群，我們每一代種群中都會有80個個體（每一行是一個個體，列數決定了個體范圍和精度），當fi_S中某個個體（記為個體A）不是0的時候，就執行了TempE(kk,:)=E(Indexfi(i),:);
這句代碼，Indexfi保存了個體A在E中的行數（也就是fi的列數），我們認定這一行（這個個體A）具有優良基因，因此保存在TempE中，進化到下一代。

好久沒看遺傳演算法了，上邊的有些術語是我自己編的，看懂就好
還有，你的程序不完全，你能把這個完整的遺傳演算法代碼給我嗎，我感覺這個程序寫的很簡潔，非常好。我的郵箱[email protected]
另外你用這個程序算做什麼？一般智能演算法解決解決問題具有隨機性，因此很難對誤差做出評價，這也是應用受到阻礙的主要原因，如果在解決具體問題的時候，還是優先考慮定量演算法的。
希望我的回答對你有所幫助。

6. 遺傳演算法的選擇，交叉和變異概率的和是1嗎

這幾個操作的概率是相互獨立的，並不要求和為1。
選擇操作中的概率，以輪賭法為例，概率只反映了個體被選擇到的可能性，與個體的適應度大小有關，一般是適應度越大，對應輪賭法中的概率值越大。

交叉操作中的概率是用於判定兩個個體是否進行交叉操作，一般都會大於0.9。
變異操作的概率是允許少數個體存在變異情況，以避免限入局部最優解，其值一般都在0.1以下。

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

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

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)就是問題中的 全體個體與其適應度之間的一個對應關系。 它一般是一個實值函數。該函數就是遺傳算 法中指導搜索的評價函數。

8. 遺傳演算法中選擇運算元是怎樣根據選擇次數得到結果的

選擇操作是從初始群體(群體規模為N，即N個個體)或當代進化群體(群體規模為N)中選擇N個個體，根據選擇所採用的方法，劣質個體必然會被丟棄（未選擇到），而為了保證群體規模不變，優質個體就必然會被選到多次。

9. 基本遺傳演算法介紹

遺傳演算法是群智能優化計算中應用最為廣泛、最為成功、最具代表性的智能優化方法。它是以達爾文的生物進化論和孟德爾的遺傳變異理論為基礎，模擬生物進化過程和機制，產生的一種群體導向隨機搜索技術和方法。

遺傳演算法的基本思想：首先根據待求解優化問題的目標函數構造一個適應度函數。然後，按照一定的規則生成經過基因編碼的初始群體，對群體進行評價、遺傳運算（交叉和變異）、選擇等操作。經過多次進化，獲得適應度最高的一個或幾個最優個體作為問題的最優解。

編碼是對問題的可行解的遺傳表示，是影響演算法執行效率的關鍵因素的之一。遺傳演算法中，一個解 稱為個體或染色體（chromosome），染色體由被稱為基因（gene）的離散單元組成，每個基因控制顏色體的一個或多個特性，通常採用固定長度的0-1二進制編碼，每個解對應一個唯一的二進制編碼串編碼空間中的二進制位串稱為基因型（genotype）。而實際所表示問題的解空間的對應點稱為表現型（phenotype）。

種群由個體構成，每個個體的染色體對應優化問題的一個初始解。

適應度函數是評價種群中個體對環境適應能力的唯一確定性指標，體現出「適者生存，優勝劣汰」這一自然選擇原則。

遺傳演算法在每次迭代過程中，在父代種群中採用某種選擇策略選擇出指定數目的哥特體提進行遺傳操作。最常用的選擇策略是正比選擇（proportional selection）策略。

在 交叉運算元中，通常由兩個被稱為父代（parent）的染色體組合，形成新的染色體，稱為子代（offspring）。父代是在種群中根據個體適應度進行選擇，因此適應度較高的染色體的基因更有可能被遺傳到下一代 。通過在迭代過程中不斷地應用交叉運算元，使優良個體的基因得以在種群中頻繁出現，最終使得整個種群收斂到一個最優解。

在染色體交叉之後產生的子代個體，其基因位可能以很小的概率發生轉變，這個過程稱為變異。變異是為了增強種群的多樣性，將搜索跳出局部最優解。

遺傳演算法的停止准則一般採用設定最大迭代次數或適應值函數評估次數，也可以是規定的搜索精度。

已Holland的基本GA為例介紹演算法等具體實現，具體的執行過程描述如下：

Step 1： 初始化 。隨機生成含有 個個體的初始種群 ，每個個體經過編碼對應著待求解優化問題的一個初始解。

Step 2： 計算適應值 。個體 ，由指定的適應度函數評價其適應環境的能力。不同的問題，適應度函數的構造方式也不同。對函數優化問題，通常取目標函數作為適應度函數。

Step 3： 選擇 。根據某種策略從當前種群中選擇出 個個體作為重新繁殖的下一代群體。選擇的依據通常是個體的適應度的高低，適應度高的個體相比適應度低的個體為下一代貢獻一個或多個後代的概率更大。選擇過程提現了達爾文「適者生存」原則。

Step 4： 遺傳操作 。在選出的 個個體中，以事件給定的雜交概率 任意選擇出兩個個體進行 交叉運算 ，產生兩個新的個體，重復此過程直到所有要求雜交的個體雜交完畢。根據預先設定的變異概率 在 個個體中選擇出若干個體，按一定的策略對選出的個體進行 變異運算 。

Step 5： 檢驗演算法等停止條件 。若滿足，則停止演算法的執行，將最優個體的染色體進行解碼得到所需要的最優解，否則轉到 Step 2 繼續進行迭代過程。