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