數(shù)值分析方法 課件 8.4 遺傳算法

數(shù)值分析方法主編

李冬果李林高磊首都醫(yī)科大學(xué)生物醫(yī)學(xué)工程學(xué)院智能醫(yī)學(xué)工程學(xué)學(xué)系面向“四新”人才培養(yǎng)普通高等教育系列教材第八章智能優(yōu)化算法基礎(chǔ)第一節(jié)最優(yōu)化問(wèn)題和隨機(jī)算法第二節(jié)禁忌搜索算法第三節(jié)模擬退火方法第四節(jié)遺傳算法第五節(jié)粒子群算法

目錄/Contents

8.4遺傳算法在自然界中，生命為了適應(yīng)環(huán)境變化，而產(chǎn)生了進(jìn)化機(jī)制。即通過(guò)遺傳和隨機(jī)突變產(chǎn)生下一代，在自然選擇下，適應(yīng)環(huán)境的個(gè)體和它們的遺傳特性得以存活。遺傳算法（Geneticalgorithm,GA）是一種群體算法，它通過(guò)模擬一個(gè)種群在自然選擇作用下的繁衍，突變，和選擇過(guò)程，在可能的解空間中進(jìn)行搜索得到最優(yōu)結(jié)果的一個(gè)過(guò)程。遺傳算法最早于1975年由J.Holland等人提出。8.4.1算法原理遺傳算法模擬了生物進(jìn)化過(guò)程，真核生物的主要遺傳物質(zhì)是脫氧核糖核酸（DNA），在生物細(xì)胞中，DNA與組蛋白組成了染色體，是細(xì)胞中可被觀察到的遺傳信息載體。遺傳信息的基本單位被稱為基因，它是DNA的片段，一條染色體上可以包含很多個(gè)不同的基因，而生物體表現(xiàn)出的形狀則由這些基因的組合決定。在生物進(jìn)化過(guò)程中，染色體的親代與子代之間存在著復(fù)制，交叉，變異和選擇的基本階段。復(fù)制使子代保持了親代的主要信息，是遺傳性狀得到保持的基本機(jī)制。而同源染色體的交叉，即兩個(gè)染色體的某些部分進(jìn)行互換，和染色體上部分基因發(fā)生隨機(jī)的變異，則是子代產(chǎn)生不同于親代性狀的兩種機(jī)制。最后，在自然選擇的作用下，不適應(yīng)環(huán)境的子代被淘汰，而適應(yīng)環(huán)境的子代則被保留下來(lái)。在數(shù)學(xué)家看來(lái)，遺傳過(guò)程就是一個(gè)優(yōu)化過(guò)程。出于簡(jiǎn)化的目的，每個(gè)個(gè)體被視為一條染色體，也就是優(yōu)化問(wèn)題的潛在解，而該解所對(duì)應(yīng)的優(yōu)化目標(biāo)函數(shù)就是對(duì)該個(gè)體適應(yīng)環(huán)境水平的評(píng)價(jià)，算法基于此可以進(jìn)行選擇。而復(fù)制、交叉和變異，是由父代個(gè)體獲得子代個(gè)體的方式，可以分別對(duì)應(yīng)著不同的運(yùn)算過(guò)程。由此，遺傳算法被開(kāi)發(fā)出來(lái)。8.4.2算法設(shè)計(jì)遺傳算法是對(duì)群體遺傳過(guò)程的模擬，生物遺傳過(guò)程中的各階段，都被對(duì)應(yīng)于優(yōu)化算法的不同運(yùn)算程序。主要包括，遺傳編碼，適應(yīng)度函數(shù)，交叉操作，變異操作，個(gè)體選擇等。（1）遺傳編碼遺傳算法使用“染色體”作為運(yùn)算的基礎(chǔ)，因此，需要把實(shí)際優(yōu)化問(wèn)題中的潛在解映射為一條“染色體”，這個(gè)過(guò)程稱為編碼(encoding)，而相反的過(guò)程，則稱為解碼(decoding)。針對(duì)不同的問(wèn)題，遺傳算法可以有不同的編碼方式，如二進(jìn)制編碼，自然數(shù)編碼，實(shí)數(shù)編碼和樹(shù)型編碼等。在實(shí)際應(yīng)用中，二進(jìn)制編碼最最簡(jiǎn)單，也最常用，為方便起見(jiàn)，后續(xù)內(nèi)容均以二進(jìn)制編碼為例。

（3）交叉操作模擬生物遺傳過(guò)程中，兩個(gè)同源染色體交叉交換部分染色體產(chǎn)生新個(gè)體的過(guò)程，遺傳算法定義了交叉操作。在遺傳算法中，一般在親代群體中隨機(jī)匹配兩條染色體，然后進(jìn)行交叉運(yùn)算。交叉過(guò)程，一般是隨機(jī)選定一個(gè)或多個(gè)交叉點(diǎn)，然后再依次交換兩條染色體在交叉點(diǎn)后的部分。

如上例中，如果只有一個(gè)交叉點(diǎn)，稱為單點(diǎn)交叉，而有兩個(gè)或更多交叉點(diǎn)的方法稱為兩點(diǎn)交叉或多點(diǎn)交叉。交叉的意義在于生成與親代不同的子代，在算法中，是否交叉，在何位置交叉以及有幾個(gè)交叉點(diǎn)經(jīng)常都是通過(guò)概率的方式?jīng)Q定的。交叉概率大，則算法能夠產(chǎn)生更多的新解，搜索范圍隨之?dāng)U大，從而保持了群體的多樣性，避免陷入局部最優(yōu)。但相應(yīng)地增加了運(yùn)算量，浪費(fèi)運(yùn)算資源。（4）變異操作在生物遺傳過(guò)程中，基因可能發(fā)生突變，DNA序列上某個(gè)位點(diǎn)可能被替換為不同的堿基。在遺傳算法當(dāng)中，則將變異操作理解為“染色體”某個(gè)位置發(fā)生改變，對(duì)二進(jìn)制編碼而言，意味著在某個(gè)位置發(fā)生0-1的互補(bǔ)運(yùn)算，即字符0被替換為1，或者1被替換為0。一般情況下，是否發(fā)生變異也需要按照一個(gè)給定的變異概率參數(shù)來(lái)決定，通過(guò)(0,1)上的隨機(jī)數(shù)與給定的變異概率相比較，來(lái)決定是否發(fā)生變異。這個(gè)概率參數(shù)如果設(shè)的過(guò)小，則搜索空間被限制，反之如果變異概率過(guò)大，則子代與親代的區(qū)別可能過(guò)大，從而失去了對(duì)親代“優(yōu)良性狀”的繼承。（5）選擇操作親代通過(guò)交叉、變異操作生成的子代合在一起組成了新的候選群落，這個(gè)群落并非每個(gè)個(gè)體都能夠產(chǎn)生子代，需要通過(guò)一個(gè)選擇過(guò)程來(lái)從這個(gè)群落中挑選出環(huán)境適應(yīng)度更高的個(gè)體，使其成為下一次遺傳過(guò)程的親代。為了避免陷入局部最優(yōu)值，選擇操作不會(huì)直接根據(jù)適應(yīng)度函數(shù)值來(lái)進(jìn)行排序篩選，而是需要通過(guò)某種方法引入一個(gè)隨機(jī)狀態(tài)，使適應(yīng)度高的個(gè)體更可能被選擇，但適應(yīng)度低的個(gè)體也有被選中的機(jī)會(huì)。為了達(dá)到這一效果，數(shù)學(xué)家開(kāi)發(fā)了很多算法。

8.4.3算法實(shí)現(xiàn)根據(jù)上述內(nèi)容，遺傳算法的主要步驟如下：步驟1

根據(jù)編碼方法，輸入指定規(guī)模初始群體，定義適應(yīng)度函數(shù)；步驟2

為群體中每個(gè)個(gè)體計(jì)算適應(yīng)度值；步驟3

通過(guò)選擇操作，從群體中選出親代群體；步驟4

在親代群體中隨機(jī)配對(duì)，按概率選定交叉點(diǎn)進(jìn)行交叉操作以產(chǎn)生新個(gè)體；步驟5

對(duì)新個(gè)體進(jìn)行變異操作；步驟6

重復(fù)執(zhí)行步驟2到步驟5，直到算法終止條件得到滿足。在遺傳算法的過(guò)程中，有些細(xì)節(jié)需要加以注意：

（1）精英保留策略。為了保證算法結(jié)果收斂于全局最優(yōu)解，在選擇過(guò)程中還要增加一個(gè)精英保留策略，即每次產(chǎn)生下一代的過(guò)程中，需保留一個(gè)適應(yīng)度最高的個(gè)體，將其直接復(fù)制到下一代中。經(jīng)過(guò)基于馬爾可夫鏈的相關(guān)理論分析，證明如果不在算法中采用精英保留策略，算法將不能收斂到全局最優(yōu)解。

（2）算法的終止條件。遺傳算法的終止條件可以設(shè)為群體趨于穩(wěn)定，即各染色體變化很小，但由于遺傳算法的特性，這個(gè)條件有時(shí)不易達(dá)到