遺傳算法的基本原理是什麽？
遺傳算法的基本原理和方法
壹、編碼
編碼：把壹個問題的可行解從其解空間轉換到遺傳算法的搜索空間的轉換方法。
解碼（譯碼）：遺傳算法解空間向問題空間的轉換。
二進制編碼的缺點是漢明懸崖（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－point Crossover）：指在個體編碼串中只隨機設置壹個交叉點，然後再該點相互交換兩個配對個體的部分染色體。
2、兩點交叉與多點交叉：
（1） 兩點交叉（Two－point Crossover）：在個體編碼串中隨機設置了兩個交叉點，然後再進行部分基因交換。
（2） 多點交叉（Multi－point Crossover）
3、均勻交叉（也稱壹致交叉，Uniform Crossover）：兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新個體。
4、算術交叉（Arithmetic Crossover）：由兩個個體的線性組合而產生出兩個新的個體。該操作對象壹般是由浮點數編碼表示的個體。
四、變異
遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替換，從而形成以給新的個體。
以下變異算子適用於二進制編碼和浮點數編碼的個體：
1、基本位變異（Simple Mutation）：對個體編碼串中以變異概率、隨機指定的某壹位或某幾位僅因座上的值做變異運算。
2、均勻變異（Uniform Mutation）：分別用符合某壹範圍內均勻分布的隨機數，以某壹較小的概率來替換個體編碼串中各個基因座上的原有基因值。（特別適用於在算法的初級運行階段）
3、邊界變異（Boundary Mutation）：隨機的取基因座上的兩個對應邊界基因值之壹去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的壹類問題。
4、非均勻變異：對原有的基因值做壹隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了壹次輕微的變動。
5、高斯近似變異：進行變異操作時用符號均值為P的平均值，方差為P2的正態分布的壹個隨機數來替換原有的基因值。