遺傳算法簡(jiǎn)單實(shí)例

遺傳算法(GA)的肇始“活的有機(jī)體是解決問題的專家。它們所表現(xiàn)出來(lái)的各種才能足以使最好的計(jì)算機(jī)程序自慚形穢。這種現(xiàn)象尤其令計(jì)算機(jī)科學(xué)家們感到痛楚。計(jì)算機(jī)科學(xué)家們?yōu)榱四撤N算法可能花費(fèi)數(shù)月乃至數(shù)年的腦力勞動(dòng)，而有機(jī)體那么能通過(guò)進(jìn)化和自然選擇這樣一種顯然并非定向進(jìn)行的機(jī)制獲得這種能力。〞---JohnHolland精選ppt遺傳算法的思想Darwin的進(jìn)化論----“自然選擇、適者生存〞特定環(huán)境的考驗(yàn)種群中個(gè)體的選擇種群中的交叉繁殖種群中個(gè)體的變異上述操作反復(fù)執(zhí)行，個(gè)體逐漸優(yōu)化精選ppt遺傳算法的手工模擬計(jì)算例如為更好地理解遺傳算法的運(yùn)算過(guò)程，下面用手工計(jì)算來(lái)簡(jiǎn)單地模擬遺傳算法的各個(gè)主要執(zhí)行步驟。

例：求下述二元函數(shù)的最大值：maxf(x1,x2)=x12+x22s.t.x1{1,2,3,4,5,6,7}x2{1,2,3,4,5,6,7}(1)個(gè)體編碼遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量x1,x2編碼為一種符號(hào)串。此題中，用無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示。因x1,x2為0~7之間的整數(shù)，所以分別用3位無(wú)符號(hào)二進(jìn)制整數(shù)來(lái)表示，將它們連接在一起所組成的6位無(wú)符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。例如，基因型X＝101110所對(duì)應(yīng)的表現(xiàn)型是：x＝[5，6]。個(gè)體的表現(xiàn)型x和基因型X之間可通過(guò)編碼和解碼程序相互轉(zhuǎn)換。精選ppt(2)初始群體的產(chǎn)生遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。本例中，群體規(guī)模的大小取為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過(guò)隨機(jī)方法產(chǎn)生。如：011101，101011，011100，111001

(3)適應(yīng)度汁算遺傳算法中以個(gè)體適應(yīng)度的大小來(lái)評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳時(shí)機(jī)的大小。本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度。(4)選擇運(yùn)算選擇運(yùn)算(或稱為復(fù)制運(yùn)算)把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)那么或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個(gè)體將有更多的時(shí)機(jī)遺傳到下一代群體中。精選ppt本例中，我們采用與適應(yīng)度成正比的概率來(lái)確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過(guò)程是：

?先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和fi(i=1.2,…,M);?其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小fi/fi

，它即為每個(gè)個(gè)體被遺傳到下一代群體中的概率，?每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1；?最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū)域內(nèi)來(lái)確定各個(gè)個(gè)體被選中的次數(shù)。0124%24%17%35%1#2#3#4#個(gè)體編號(hào)初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001x1x235533471精選ppt(5)交叉運(yùn)算交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過(guò)程，它以某一概率相互交換某兩個(gè)個(gè)體之間的局部染色體。本例采用單點(diǎn)交叉的方法，其具體操作過(guò)程是：?先對(duì)群體進(jìn)行隨機(jī)配對(duì)；?其次隨機(jī)設(shè)置交叉點(diǎn)位置；?最后再相互交換配對(duì)染色體之間的局部基因。選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置個(gè)體編號(hào)12341-23-41-2：23-4：4交叉結(jié)果011001111101101001111011可以看出，其中新產(chǎn)生的個(gè)體“111101〞、“111011〞的適應(yīng)度較原來(lái)兩個(gè)個(gè)體的適應(yīng)度都要高。精選ppt(6)變異運(yùn)算變異運(yùn)算是對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。本例中，我們采用根本位變異的方法來(lái)進(jìn)行變異運(yùn)算，其具體操作過(guò)程是：?首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置，其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處；?然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。個(gè)體編號(hào)1234交叉結(jié)果011001111101101001111011變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)011101111111111001111010精選ppt從上表中可以看出，群體經(jīng)過(guò)一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最正確個(gè)體“111111〞。[注意]需要說(shuō)明的是，表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)生的。這里為了更好地說(shuō)明問題，我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果，而在實(shí)際運(yùn)算過(guò)程中有可能需要一定的循環(huán)次數(shù)才能到達(dá)這個(gè)最優(yōu)結(jié)果。個(gè)體編號(hào)子群體p(1)適值占總數(shù)的百分比總和1234011101111111111001111010349850530.140.420.210.232351x1x235777172精選ppt個(gè)體編號(hào)初始群體p(0)適值fi(x1,x2)占總數(shù)的百分比f(wàn)i/

f1234011101101011011100111001343425500.240.240.170.35x1x235533471fi=143fmax=50f=35.75選擇結(jié)果011101111001101011111001配對(duì)情況交叉點(diǎn)位置1-23-41-2：23-4：4交叉結(jié)果011001111101101001111011選擇次數(shù)1102變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)適值fi(x1,x2)占總數(shù)的百分比f(wàn)i/

f011101111111111001111010349850530.140.420.210.23x1x235777172fi=253fmax=98f=58.75精選ppt遺傳算法的一個(gè)實(shí)例求解方程：將方程求解問題轉(zhuǎn)化為生存問題：解一定在[0,10]之間，將區(qū)間[0,10]劃分成假設(shè)干個(gè)小區(qū)間，設(shè)想每個(gè)小區(qū)間為一個(gè)生物個(gè)體，使以下表達(dá)式最小的個(gè)體有最好的生存能力，該個(gè)體即為解。精選ppt遺傳算法的一個(gè)實(shí)例如何找到這個(gè)最優(yōu)個(gè)體？可通過(guò)Darwin的進(jìn)化論由初始個(gè)體經(jīng)過(guò)代代演化，逐漸進(jìn)化出來(lái)。如何將生物進(jìn)化的操作轉(zhuǎn)化為計(jì)算機(jī)可以執(zhí)行的操作？通過(guò)編碼表征生物個(gè)體，那么生物之間的演化轉(zhuǎn)化為編碼的變化。精選ppt步驟一：初始化個(gè)體編碼：(假定要求小數(shù)點(diǎn)后兩位)將[0,10]劃分為1024個(gè)小區(qū)間個(gè)體10000000000個(gè)體20000000001個(gè)體30000000010……個(gè)體10241111111111種群初始化：隨機(jī)生成m個(gè)10位二進(jìn)制串010精選ppt定義適應(yīng)度函數(shù)：選擇〔適應(yīng)度較大的個(gè)體〕

步驟二：選擇為何取倒數(shù)？0.10.30.20.40.10.10.30.40.20.60.41.0ABCD隨機(jī)產(chǎn)生[0,1]之間的數(shù)RN，選擇個(gè)體RN個(gè)體ABCD精選ppt選中的優(yōu)勢(shì)個(gè)體進(jìn)行交叉-----由父?jìng)€(gè)體生成子個(gè)體步驟三：交叉相同的兩個(gè)父?jìng)€(gè)體生成相同的兩個(gè)子個(gè)體精選ppt變異操作在個(gè)體中隨機(jī)選擇一位，改變?cè)撐坏闹挡襟E四：變異交叉和變異操作均以一定概率進(jìn)行精選ppt反復(fù)執(zhí)行步驟二、三、四并記錄最優(yōu)個(gè)體〔適應(yīng)度最大的個(gè)體〕程序結(jié)束時(shí)，最優(yōu)個(gè)體即為所求解程序結(jié)束的判定根據(jù)循環(huán)次數(shù)根據(jù)最大適應(yīng)度根據(jù)種群中相同個(gè)體數(shù)與總個(gè)體數(shù)的比值步驟五精選ppt遺傳算法各步驟的評(píng)價(jià)選擇---優(yōu)勝劣汰選擇操作為種群提供了演進(jìn)的方向交叉---優(yōu)優(yōu)組合交叉操作的作用在于聚集散布于不同個(gè)體間的局部?jī)?yōu)勢(shì)模式變異---尋找新模式變異操作是種群向外擴(kuò)展的觸角(隨機(jī))好的變異將保存，壞的淘汰精選ppt遺傳算法的總體評(píng)價(jià)優(yōu)點(diǎn)解決問題的方法具有普適性全局收斂性〔依概率收斂〕能解決的問題范圍很廣缺乏求得的解為近似的數(shù)值解對(duì)于經(jīng)典數(shù)學(xué)可以解決的問題，效率較低精選ppt遺傳算法的適應(yīng)度函數(shù)求函數(shù)的全局極小值取的初始區(qū)間，例如：[-10,10]將此區(qū)間分為1024個(gè)小區(qū)間，然后編碼假設(shè)求全局極大值(且為正)，可直接取函數(shù)值為其適應(yīng)度值，據(jù)此作概率選擇；假設(shè)求全局極小值(且為正)，可取函數(shù)值的倒數(shù)為其適應(yīng)度值，據(jù)此作概率選擇。假設(shè)不全為負(fù)，可統(tǒng)一加上一個(gè)正數(shù)，使為正。精選pptTSP問題的遺傳算法求解步驟一：個(gè)體編碼及種群初始化步驟二：適應(yīng)度選擇步驟三：交叉操作步驟四：變異操作步驟五：重復(fù)二、三、四步，直至結(jié)束

令城市(點(diǎn))數(shù)目為N精選ppt個(gè)體編碼取長(zhǎng)度為N的數(shù)字串，串中數(shù)字互不重復(fù)，取值范圍為[1,N]之間的整數(shù)。那么每一個(gè)數(shù)字串代表一個(gè)個(gè)體，個(gè)體中數(shù)字出現(xiàn)的位置表征路徑中城市出現(xiàn)的順序。初始種群令種群中有M個(gè)個(gè)體，可隨機(jī)產(chǎn)生M個(gè)數(shù)字串構(gòu)成初始種群。例如：將數(shù)字串1234…N上的數(shù)字進(jìn)行隨機(jī)的交換步驟一：初始化精選ppt適應(yīng)度的計(jì)算步驟二：適應(yīng)度選擇12345對(duì)于個(gè)體，適應(yīng)度為：被選中作為父?jìng)€(gè)體的概率：選擇M次重新生成種群精選pptTSP中交叉算子的特點(diǎn)

要保證生成的解為有效解從一個(gè)父?jìng)€(gè)體中隨機(jī)選取一段子串A，在另一個(gè)父?jìng)€(gè)體中將A中出現(xiàn)的數(shù)字去掉形成串B，AB為一個(gè)子串步驟三：交叉操作此外還有多種交叉算子精選ppt常用的變異操作：隨機(jī)選取兩個(gè)相鄰位置的數(shù)字，交換其順序。

51243(5)51234(5)步驟四：變異操作1234512345交換3,4此外還有多種變異算子精選ppt反復(fù)執(zhí)行步驟二、三、四結(jié)束判定循環(huán)執(zhí)行G次(例如G=500)后當(dāng)最優(yōu)個(gè)體的總路徑長(zhǎng)度小于預(yù)期時(shí)步驟五：精選ppt中國(guó)各省會(huì)城市的運(yùn)行結(jié)果精選ppt12345缺陷：相同父?jìng)€(gè)體生成不同的子個(gè)體以下是相同個(gè)體：12345(1)54321(5)反射操作12345(1)34512(3)旋轉(zhuǎn)操作交叉算子的進(jìn)一步研究用群論描述所有路徑的集合形成一個(gè)二面體群A等價(jià)解構(gòu)成一個(gè)正規(guī)子群BA中陪集的數(shù)目為2N精選ppt12345(1)32154(3)相同父?jìng)€(gè)體交叉34215(3)15234(1)不同子個(gè)體，且和父?jìng)€(gè)體不同123451234512345精選ppt4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例產(chǎn)生初始種群計(jì)算適應(yīng)度4.1.4遺傳算法的根本操作0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011〔8〕〔5〕〔2〕〔10〕〔7〕〔12〕〔5〕〔19〕〔10〕〔14〕精選ppt4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇4.1.4遺傳算法的根本操作個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174精選ppt4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇4.1.4遺傳算法的根本操作個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000精選ppt4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(shù)：4.1.4遺傳算法的根本操作個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！精選ppt00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例交叉4.1.4遺傳算法的根本操作00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011精選ppt4.1遺傳算法簡(jiǎn)介

智能優(yōu)化計(jì)算簡(jiǎn)單實(shí)例變異4.1.4遺傳算法的根本操作0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011精選ppt4.2根本遺傳算法智能優(yōu)化計(jì)算問題的提出

一元函數(shù)求最大值：4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

精選ppt4.2根本遺傳算法智能優(yōu)化計(jì)算問題的提出

用微分法求取f(x)的最大值：解有無(wú)窮多個(gè)：4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

精選ppt4.2根本遺傳算法智能優(yōu)化計(jì)算問題的提出

當(dāng)i為奇數(shù)時(shí)xi對(duì)應(yīng)局部極大值點(diǎn)，i為偶數(shù)時(shí)xi對(duì)應(yīng)局部極小值。x19即為區(qū)間[-1,2]內(nèi)的最大值點(diǎn)：此時(shí)，函數(shù)最大值f(x19)比f(wàn)(1.85)=3.85稍大。4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

精選ppt4.2根本遺傳算法智能優(yōu)化計(jì)算編碼表現(xiàn)型：x基因型：二進(jìn)制編碼〔串長(zhǎng)取決于求解精度〕串長(zhǎng)與精度之間的關(guān)系：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。4.2.1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

精選ppt4.2根本遺傳算法智能優(yōu)化計(jì)算產(chǎn)生初始種群產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大小〔規(guī)?！?，如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000