遺傳算法基本原理第1頁/共28頁提綱遺傳算法概述實現(xiàn)遺傳算法的基本步驟遺傳算法的應用第2頁/共28頁遺傳算法概述尋優(yōu)算法：求解最優(yōu)值問題的方法遺傳算法粒子群算法模擬退火算法……遺傳算法的概念是在1975年由Michigan大學的J.Holland提出的，這是一種通過模擬自然進化過程尋找最優(yōu)解的方法。第3頁/共28頁遺傳算法概述遺傳算法的基本原理：生物進化論和遺傳學遺傳：子代與父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異：子代與父代，以及子代不同個體之間總有差異，是生命多樣性的根源；生存斗爭與適者生存：具有適應性變異的個體被保留，不具有適應性變異的個體被淘汰。進化：生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得其品質不斷改良，這種現(xiàn)象被稱為進化。第4頁/共28頁實現(xiàn)遺傳算法的基本步驟編碼與解碼實現(xiàn)遺傳算法的第一步就是明確對求解問題的編碼和解碼方式。對于函數(shù)優(yōu)化問題，一般有兩種編碼方式：實數(shù)編碼：直接用實數(shù)表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優(yōu)。二進制編碼：簡單易行，穩(wěn)定性高，種群多樣性大，但需要的存儲空間大。一串編碼代表一個染色體。第5頁/共28頁實現(xiàn)遺傳算法的基本步驟適應度函數(shù)進化論中的適應度，是表示某一個體對環(huán)境的適應能力，也表示該個體繁殖后代的能力。遺傳算法的適應度函數(shù)也叫評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標，它是根據(jù)所求問題的目標函數(shù)來進行評估的。遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應度函數(shù)要比較排序并在此基礎上計算選擇概率，所以適應度函數(shù)的值要取正值。由此可見，在不少場合，將目標函數(shù)映射成求最大值形式且函數(shù)值非負的適應度函數(shù)是必要的。第6頁/共28頁實現(xiàn)遺傳算法的基本步驟遺傳算子遺傳算子是用來模擬生物基因遺傳的算子，包括選擇、交配和突變三種算子。選擇選擇操作是從前代種群中選擇多對較優(yōu)個體，一對較優(yōu)個體稱之為一對父母，讓父母們將它們的基因傳遞到下一代，直到下一代個體數(shù)量達到種群數(shù)量上限；在選擇操作前，將種群中個體按照適應度從小到大進行排列，采用一種選擇方法，如輪盤賭方法，各個個體被選中的概率與其適應度函數(shù)值大小成正比。輪盤賭選擇方法具有隨機性，在選擇的過程中可能會丟掉較好的個體，所以可以使用精英機制，將前代最優(yōu)個體直接選擇。第7頁/共28頁實現(xiàn)遺傳算法的基本步驟交配生物遺傳基因的重組是自然界生物進化過程中的核心。在遺傳算法中與之相對應的是遺傳操作中的交配算子。所謂交配是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交配，遺傳算法的搜索能力得以飛躍提高。交配算子根據(jù)交配率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。最常用的交配算子為單點交配。具體操作是:在個體串中隨機設定一個交配點，實行交配時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體。下面給出了單點交配的一個例子：個體A：1001↑111→1001000新個體個體B：0011↑000→0011111新個體第8頁/共28頁實現(xiàn)遺傳算法的基本步驟突變突變算子是用來模擬生物基因突變的操作。一般來說，突變算子操作的基本步驟如下：a)對群中所有個體以事先設定的變異概率判斷是否進行變異b)對進行變異的個體隨機選擇變異位進行變異。遺傳算法引入突變的目的有兩個:一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交配算子已接近最優(yōu)解鄰域時，利用突變算子的這種局部隨機搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優(yōu)解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應取較大值。第9頁/共28頁實現(xiàn)遺傳算法的基本步驟遺傳算法流程第10頁/共28頁遺傳算法的應用函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是遺傳算法進行性能評價的常用算例。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結果。組合優(yōu)化主要用于解決組合優(yōu)化中的NP完全問題。自動控制如模糊控制器優(yōu)化設計、參數(shù)辨識等。第11頁/共28頁遺傳算法的應用函數(shù)優(yōu)化例子：第12頁/共28頁遺傳算法的應用編碼第13頁/共28頁遺傳算法的應用

第14頁/共28頁遺傳算法的應用第15頁/共28頁遺傳算法的應用評價個體適應度第16頁/共28頁遺傳算法的應用第17頁/共28頁遺傳算法的應用第18頁/共28頁遺傳算法的應用種群每條染色體的適應度、被復制概率和累積概率第19頁/共28頁遺傳算法的應用遺傳操作：選擇第20頁/共28頁遺傳算法的應用遺傳操作：交配第21頁/共28頁遺傳算法的應用第22頁/共28頁遺傳算法的應用遺傳操作：突變第23頁/共28頁遺傳算法的應用第24頁/共28頁遺傳算法的應用第25頁/共28頁遺傳算法的應用至此，已經(jīng)完成了遺傳算法的第一代操作。重復以上操作，直到最優(yōu)個體的適應度達到給定的閾值，或者最優(yōu)個體的適應度和群體適應度不