遺傳算法基本原理

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

遺傳算法的應(yīng)用遺傳算法的應(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)用遺傳操作：突變遺傳算法的應(yīng)用遺傳算法的應(yīng)用遺傳算法的應(yīng)用至此，已經(jīng)完成了遺傳算法的第一代操作。重復(fù)以上操作，直到最