陳景偉-遺傳算法基本原理課件

遺傳算法基本原理陳景偉提綱遺傳算法概述實(shí)現(xiàn)遺傳算法的基本步驟遺傳算法的應(yīng)用遺傳算法概述尋優(yōu)算法：求解最優(yōu)值問題的方法遺傳算法粒子群算法模擬退火算法……遺傳算法的概念是在1975年由Michigan大學(xué)的J.Holland提出的，這是一種通過(guò)模擬自然進(jìn)化過(guò)程尋找最優(yōu)解的方法。遺傳算法概述遺傳算法的基本原理：生物進(jìn)化論和遺傳學(xué)遺傳：子代與父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異：子代與父代，以及子代不同個(gè)體之間總有差異，是生命多樣性的根源；生存斗爭(zhēng)與適者生存：具有適應(yīng)性變異的個(gè)體被保留，不具有適應(yīng)性變異的個(gè)體被淘汰。進(jìn)化：生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷改良，這種現(xiàn)象被稱為進(jìn)化。實(shí)現(xiàn)遺傳算法的基本步驟編碼與解碼實(shí)現(xiàn)遺傳算法的第一步就是明確對(duì)求解問題的編碼和解碼方式。對(duì)于函數(shù)優(yōu)化問題，一般有兩種編碼方式：實(shí)數(shù)編碼：直接用實(shí)數(shù)表示基因，容易理解且不需要解碼過(guò)程，但容易過(guò)早收斂，從而陷入局部最優(yōu)。二進(jìn)制編碼：簡(jiǎn)單易行，穩(wěn)定性高，種群多樣性大，但需要的存儲(chǔ)空間大。一串編碼代表一個(gè)染色體。實(shí)現(xiàn)遺傳算法的基本步驟適應(yīng)度函數(shù)進(jìn)化論中的適應(yīng)度，是表示某一個(gè)體對(duì)環(huán)境的適應(yīng)能力，也表示該個(gè)體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評(píng)價(jià)函數(shù)，是用來(lái)判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來(lái)進(jìn)行評(píng)估的。遺傳算法在搜索進(jìn)化過(guò)程中一般不需要其他外部信息，僅用評(píng)估函數(shù)來(lái)評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。由此可見，在不少場(chǎng)合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。實(shí)現(xiàn)遺傳算法的基本步驟遺傳算子遺傳算子是用來(lái)模擬生物基因遺傳的算子，包括選擇、交配和突變?nèi)N算子。選擇選擇操作是從前代種群中選擇多對(duì)較優(yōu)個(gè)體，一對(duì)較優(yōu)個(gè)體稱之為一對(duì)父母，讓父母?jìng)儗⑺鼈兊幕騻鬟f到下一代，直到下一代個(gè)體數(shù)量達(dá)到種群數(shù)量上限；在選擇操作前，將種群中個(gè)體按照適應(yīng)度從小到大進(jìn)行排列，采用一種選擇方法，如輪盤賭方法，各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。輪盤賭選擇方法具有隨機(jī)性，在選擇的過(guò)程中可能會(huì)丟掉較好的個(gè)體，所以可以使用精英機(jī)制，將前代最優(yōu)個(gè)體直接選擇。實(shí)現(xiàn)遺傳算法的基本步驟遺傳算法流程遺傳算法的應(yīng)用函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。組合優(yōu)化主要用于解決組合優(yōu)化中的NP完全問題。自動(dòng)控制如模糊控制器優(yōu)化設(shè)計(jì)、參數(shù)辨識(shí)等。遺傳算法的應(yīng)用函數(shù)優(yōu)化例子：遺傳算法的應(yīng)用評(píng)價(jià)個(gè)體適應(yīng)度遺傳算法的應(yīng)用遺傳算法的應(yīng)用遺傳算法的應(yīng)用種群每條染色體的適應(yīng)度、被復(fù)制概率和累積概率遺傳算法的應(yīng)用遺傳操作：突變遺傳算法的應(yīng)用遺傳算法的應(yīng)用遺傳算法的應(yīng)用至此，已經(jīng)完成了遺傳算法的第一代操作。重復(fù)以上操作，直到最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閾值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，