遺傳演算法的二進制編碼

1. 基本遺傳演算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 遺傳演算法理解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. MATLAB中遺傳演算法編程中，二進制編碼如何處理實數變數

假如你想要編碼為x，設x的范圍是【min,max】，二進制編碼長度為10，那二進解碼方式是：x*（max-min)/1023,這個不用開始編碼，開始你可以用rand(n,10)產生n個樣本的隨機數，然後優化即可。
不是能把「數學模型中的目標函數和每一條約束函數分別編程Matlab里的M文件」，是你用遺傳演算法就必須要編進去，電腦怎麼知道往哪個方向優化是好的，要不把你郵箱留下，我給你發個尋求最大值的遺傳演算法。

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

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

一、編碼

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

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

二進制編碼的缺點是漢明懸崖（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的正態分布的一個隨機數來替換原有的基因值。

5. 遺傳演算法二進制編碼問題：二進制編碼的位數是如何確定的

用這個公式試試，這個是解碼用的，至於你說的位數，可以給你舉個例子，比如[0,1],精度千分之1，就是相當於裡面離散化出來1000+1個點，2的10次方是1024,2的9次方是512，這時候你就只要取10位就可以把這1001個點的變化全部包含到二進制裡面了

6. 遺傳演算法的編碼方法有幾種

常用的編碼介紹
1、二進制編碼：
（1）定義：二進制編碼方法是使用二值符號集{0,1}，它所構成的個體基因型是一個二進制編碼符號串。二進制編碼符號串的長度與問題所要求的求解精度有關。
（2）舉例：0≤x≤1023,精度為1,m表示二進制編碼的長度。則有建議性說法：使
2m-1≤1000（跟精度有關）≤2m-1。取m=10
則X:0010101111就可以表示一個個體，它所對應的問題空間的值是x=175。
（3）優缺點
優點：符合最小字元集原則，便於用模式定理分析；
缺點：連續函數離散化時的映射誤差。
2、格雷碼編碼
（1）定義：格雷碼編碼是其連續的兩個整數所對應的編碼之間只有一個碼位是不同的，其餘碼位完全相同。它是二進制編碼方法的一種變形。
十進制數0—15之間的二進制碼和相應的格雷碼分別編碼如下。
二進制編碼為：0000，0001，0010，001
1，0100。0101，0110，0111，
1000，1001，1010，1011，1100，1101，1110，1111；
格雷碼編碼為：0000，0001，0011，0010，0110，0111，0101，0100，
1100，1101，1111，1110，1010，1011，1001，1000。
（2）舉例：對於區間[0。1023]中兩個鄰近的整數X1=175和X2=176，若用長度為10位的二進制編碼，可表示為X11：0010101111和X12
0010110000，而使用同樣長度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000。
（3）優點：增強了遺傳演算法的局部搜索能力，便於連續函數的局部控制項搜索。
3、浮點數(實數)編碼
（1）定義：浮點數編碼是指個體的每個基因值用某一范圍內的一個浮點數來表示，而個體的編碼長度等於其決策變數的個數。因為這種編碼方法使用的決策變數的真實值，也稱之為真值編碼方法。
（2）舉例：
（3）優點：實數編碼是遺傳演算法中在解決連續參數優化問題時普遍使用的一種編碼方式，具有較高的精度，在表示連續漸變問題方面具有優勢。
4、排列編碼
排列編碼也叫序列編碼，是針對一些特殊問題的特定編碼方式。排序編碼使問題簡潔，易於理解。該編碼方式將有限集合內的元素進行排列。若集合內包含m個元素，則存在m!種排列方法，當m不大時，m!也不會太大，窮舉法就可以解決問題。當m比較大時，m!就會變得非常大，窮舉法失效，遺傳演算法在解決這類問題上具有優勢。如解決TSP問題時，用排列編碼自然、合理。
5、其它編碼方式
多參數級聯編碼等

7. 閬椾紶綆楁硶綆鍗曟槗鎳傜殑渚嬪瓙

閬椾紶綆楁硶鐨勪緥瀛愬備笅錛

奼傝В鍑芥暟 f錛坸錛 錛 x 錛 10錛妔in錛5錛妜錛 錛 7錛奵os錛4錛妜錛 鍦ㄥ尯闂達薊0錛9錛界殑鏈澶у箋

閫氳繃涓婅堪鍏寮忥紝鎴戜滑灝卞彲浠ユ垚鍔熷湴灝嗕簩榪涘埗鏌撹壊浣撲覆瑙ｇ爜鎴愶薊0錛9錛藉尯闂翠腑鐨勫嶮榪涘埗瀹炴暟瑙ｃ