遺傳算法為群體優化算法，也就是從多個初始解開始進行優化，每個解稱為一個染色體，各染色體之間通過競爭、合作、單獨變異，不斷進化。
優化時先要將實際問題轉換到遺傳空間，就是把實際問題的解用染色體表示，稱為編碼，反過程為解碼，因為優化后要進行評價，所以要返回問題空間，故要進行解碼。SGA采用二進制編碼，染色體就是二進制位串，每一位可稱為一個基因；解碼時應注意將染色體解碼到問題可行域內。
遺傳算法模擬“適者生存，優勝劣汰”的進化機制，染色體適應生存環境的能力用適應度函數衡量。對于優化問題，適應度函數由目標函數變換而來。一般遺傳算法求解最大值問題，如果是最小值問題，則通過取倒數或者加負號處理。SGA要求適應度函數>0，對于<0的問題，要通過加一個足夠大的正數來解決。這樣，適應度函數值大的染色體生存能力強。
遺傳算法有三個進化算子：選擇（復制）、交叉和變異。
SGA中，選擇采用輪盤賭方法，也就是將染色體分布在一個圓盤上，每個染色體占據一定的扇形區域，扇形區域的面積大小和染色體的適應度大小成正比。如果輪盤中心裝一個可以轉動的指針的話，旋轉指針，指針停下來時會指向某一個區域，則該區域對應的染色體被選中。顯然適應度高的染色體由于所占的扇形區域大，因此被選中的幾率高，可能被選中多次，而適應度低的可能一次也選不中，從而被淘汰。算法實現時采用隨機數方法，先將每個染色體的適應度除以所有染色體適應度的和，再累加，使他們根據適應度的大小分布于0-1之間，適應度大的占的區域大，然后隨機生成一個0-1之間的隨機數，隨機數落到哪個區域，對應的染色體就被選中。重復操作，選出群體規模規定數目的染色體。這個操作就是“優勝劣汰，適者生存”，但沒有產生新個體。
交叉模擬有性繁殖，由兩個染色體共同作用產生后代，SGA采用單點交叉。由于SGA為二進制編碼，所以染色體為二進制位串，隨機生成一個小于位串長度的隨機整數，交換兩個染色體該點后的那部分位串。參與交叉的染色體是輪盤賭選出來的個體，并且還要根據選擇概率來確定是否進行交叉（生成0-1之間隨機數，看隨機數是否小于規定的交叉概率），否則直接進入變異操作。這個操作是產生新個體的主要方法，不過基因都來自父輩個體。
變異采用位點變異，對于二進制位串，0變為1，1變為0就是變異。采用概率確定變異位，對每一位生成一個0-1之間的隨機數，看是否小于規定的變異概率，小于的變異，否則保持原狀。這個操作能夠使個體不同于父輩而具有自己獨立的特征基因，主要用于跳出局部極值。
遺傳算法認為生物由低級到高級進化，后代比前一代強，但實際操作中可能有退化現象，所以采用最佳個體保留法，也就是曾經出現的最好個體，一定要保證生存下來，使后代至少不差于前一代。大致有兩種類型，一種是把出現的最優個體單獨保存，最后輸出，不影響原來的進化過程；一種是將最優個體保存入子群，也進行選擇、交叉、變異，這樣能充分利用模式，但也可能導致過早收斂。
由于是基本遺傳算法，所以優化能力一般，解決簡單問題尚可，高維、復雜問題就需要進行改進了。
下面為代碼。函數最大值為3905.9262，此時兩個參數均為-2.0480，有時會出現局部極值，此時一個參數為-2.0480，一個為2.0480。算法中變異概率pm=0.05，交叉概率pc=0.8。如果不采用最優模式保留，結果會更豐富些，也就是算法最后不一定收斂于極值點，當然局部收斂現象也會有所減少，但最終尋得的解不一定是本次執行中曾找到過的最好解。
標簽：
遺傳算法
上傳時間：
2015-06-04
上傳用戶：芃溱溱123
