遺傳算法的一些實例第1頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的思想Darwin的進化論----“自然選擇、適者生存”特定環(huán)境的考驗種群中個體的選擇種群中的交叉繁殖種群中個體的變異

上述操作反復(fù)執(zhí)行，個體逐漸優(yōu)化第2頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的手工模擬計算示例為更好地理解遺傳算法的運算過程，下面用手工計算來簡單地模擬遺傳算法的各個主要執(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)個體編碼遺傳算法的運算對象是表示個體的符號串，所以必須把變量x1,x2編碼為一種符號串。本題中，用無符號二進制整數(shù)來表示。因x1,x2為0~7之間的整數(shù)，所以分別用3位無符號二進制整數(shù)來表示，將它們連接在一起所組成的6位無符號二進制數(shù)就形成了個體的基因型，表示一個可行解。

例如，基因型X＝101110所對應(yīng)的表現(xiàn)型是：x＝[5，6]。個體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。第3頁，課件共44頁，創(chuàng)作于2023年2月

(2)初始群體的產(chǎn)生遺傳算法是對群體進行的進化操作，需要給其淮備一些表示起始搜索點的初始群體數(shù)據(jù)。本例中，群體規(guī)模的大小取為4，即群體由4個個體組成，每個個體可通過隨機方法產(chǎn)生。如：011101，101011，011100，111001

(3)適應(yīng)度汁算遺傳算法中以個體適應(yīng)度的大小來評定各個個體的優(yōu)劣程度，從而決定其遺傳機會的大小。本例中，目標函數(shù)總?cè)》秦撝?，并且是以求函?shù)最大值為優(yōu)化目標，故可直接利用目標函數(shù)值作為個體的適應(yīng)度。

(4)選擇運算選擇運算(或稱為復(fù)制運算)把當前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個體將有更多的機會遺傳到下一代群體中。第4頁，課件共44頁，創(chuàng)作于2023年2月本例中，我們采用與適應(yīng)度成正比的概率來確定各個個體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是：

?先計算出群體中所有個體的適應(yīng)度的總和fi

(i=1.2,…,M);

?其次計算出每個個體的相對適應(yīng)度的大小fi/fi

，它即為每個個體被遺傳到下一代群體中的概率，

?每個概率值組成一個區(qū)域，全部概率值之和為1；

?最后再產(chǎn)生一個0到1之間的隨機數(shù)，依據(jù)該隨機數(shù)出現(xiàn)在上述哪一個概率區(qū)域內(nèi)來確定各個個體被選中的次數(shù)。0124%24%17%35%1#2#3#4#個體編號初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001x1x235533471第5頁，課件共44頁，創(chuàng)作于2023年2月(5)交叉運算交叉運算是遺傳算法中產(chǎn)生新個體的主要操作過程，它以某一概率相互交換某兩個個體之間的部分染色體。本例采用單點交叉的方法，其具體操作過程是：

?先對群體進行隨機配對；

?其次隨機設(shè)置交叉點位置；

?最后再相互交換配對染色體之間的部分基因。選擇結(jié)果011101111001101011111001配對情況交叉點位置個體編號12341-23-41-2：23-4：4交叉結(jié)果011001111101101001111011可以看出，其中新產(chǎn)生的個體“111101”、“111011”的適應(yīng)度較原來兩個個體的適應(yīng)度都要高。第6頁，課件共44頁，創(chuàng)作于2023年2月(6)變異運算變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進行改變，它也是產(chǎn)生新個體的一種操作方法。本例中，我們采用基本位變異的方法來進行變異運算，其具體操作過程是：

?首先確定出各個個體的基因變異位置，下表所示為隨機產(chǎn)生的變異點位置，其中的數(shù)字表示變異點設(shè)置在該基因座處；?然后依照某一概率將變異點的原有基因值取反。對群體P(t)進行一輪選擇、交叉、變異運算之后可得到新一代的群體p(t+1)。個體編號1234交叉結(jié)果011001111101101001111011變異結(jié)果變異點4526011101111111111001111010子代群體p(1)011101111111111001111010第7頁，課件共44頁，創(chuàng)作于2023年2月從上表中可以看出，群體經(jīng)過一代進化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進。事實上，這里已經(jīng)找到了最佳個體“111111”。

[注意]

需要說明的是，表中有些欄的數(shù)據(jù)是隨機產(chǎn)生的。這里為了更好地說明問題，我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果，而在實際運算過程中有可能需要一定的循環(huán)次數(shù)才能達到這個最優(yōu)結(jié)果。個體編號子群體p(1)適值占總數(shù)的百分比總和1234011101111111111001111010349850530.140.420.210.232351x1x235777172第8頁，課件共44頁，創(chuàng)作于2023年2月個體編號初始群體p(0)適值fi(x1,x2)占總數(shù)的百分比fi/f1234011101101011011100111001343425500.240.240.170.35x1x235533471fi=143fmax=50f=35.75選擇結(jié)果011101111001101011111001配對情況交叉點位置1-23-41-2：23-4：4交叉結(jié)果011001111101101001111011選擇次數(shù)1102變異結(jié)果變異點4526011101111111111001111010子代群體p(1)適值fi(x1,x2)占總數(shù)的百分比fi/f011101111111111001111010349850530.140.420.210.23x1x235777172fi=253fmax=98f=58.75第9頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的一個實例求解方程：將方程求解問題轉(zhuǎn)化為生存問題：解一定在[0,10]之間，將區(qū)間[0,10]劃分成若干個小區(qū)間，設(shè)想每個小區(qū)間為一個生物個體，使下列表達式最小的個體有最好的生存能力，該個體即為解。第10頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的一個實例如何找到這個最優(yōu)個體？可通過Darwin的進化論由初始個體經(jīng)過代代演化，逐漸進化出來。如何將生物進化的操作轉(zhuǎn)化為計算機可以執(zhí)行的操作？通過編碼表征生物個體，則生物之間的演化轉(zhuǎn)化為編碼的變化。第11頁，課件共44頁，創(chuàng)作于2023年2月步驟一：初始化個體編碼：(假定要求小數(shù)點后兩位)將[0,10]劃分為1024個小區(qū)間個體10000000000個體20000000001個體30000000010……個體10241111111111種群初始化：隨機生成m個10位二進制串010第12頁，課件共44頁，創(chuàng)作于2023年2月定義適應(yīng)度函數(shù)：選擇（適應(yīng)度較大的個體）

步驟二：選擇為何取倒數(shù)？0.10.30.20.40.10.10.30.40.20.60.41.0ABCD隨機產(chǎn)生[0,1]之間的數(shù)RN，選擇個體RN個體ABCD第13頁，課件共44頁，創(chuàng)作于2023年2月選中的優(yōu)勢個體進行交叉-----由父個體生成子個體步驟三：交叉相同的兩個父個體生成相同的兩個子個體第14頁，課件共44頁，創(chuàng)作于2023年2月變異操作在個體中隨機選擇一位，改變該位的值步驟四：變異交叉和變異操作均以一定概率進行第15頁，課件共44頁，創(chuàng)作于2023年2月反復(fù)執(zhí)行步驟二、三、四并記錄最優(yōu)個體（適應(yīng)度最大的個體）程序結(jié)束時，最優(yōu)個體即為所求解程序結(jié)束的判定根據(jù)循環(huán)次數(shù)根據(jù)最大適應(yīng)度根據(jù)種群中相同個體數(shù)與總個體數(shù)的比值步驟五第16頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法各步驟的評價選擇---優(yōu)勝劣汰

選擇操作為種群提供了演進的方向交叉---優(yōu)優(yōu)組合

交叉操作的作用在于匯集散布于不同個體間的局部優(yōu)勢模式變異---尋找新模式

變異操作是種群向外擴展的觸角(隨機)好的變異將保留，壞的淘汰第17頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的總體評價優(yōu)點解決問題的方法具有普適性全局收斂性（依概率收斂）能解決的問題范圍很廣不足求得的解為近似的數(shù)值解對于經(jīng)典數(shù)學(xué)可以解決的問題，效率較低第18頁，課件共44頁，創(chuàng)作于2023年2月遺傳算法的適應(yīng)度函數(shù)求函數(shù)的全局極小值取的初始區(qū)間，例如：[-10,10]將此區(qū)間分為1024個小區(qū)間，然后編碼若求全局極大值(且為正)，可直接取函數(shù)值為其適應(yīng)度值，據(jù)此作概率選擇；若求全局極小值(且為正)，可取函數(shù)值的倒數(shù)為其適應(yīng)度值，據(jù)此作概率選擇。若不全為負，可統(tǒng)一加上一個正數(shù)，使為正。第19頁，課件共44頁，創(chuàng)作于2023年2月TSP問題的遺傳算法求解步驟一：個體編碼及種群初始化步驟二：適應(yīng)度選擇步驟三：交叉操作步驟四：變異操作步驟五：重復(fù)二、三、四步，直至結(jié)束

令城市(點)數(shù)目為N第20頁，課件共44頁，創(chuàng)作于2023年2月個體編碼取長度為N的數(shù)字串，串中數(shù)字互不重復(fù)，取值范圍為[1,N]之間的整數(shù)。則每一個數(shù)字串代表一個個體，個體中數(shù)字出現(xiàn)的位置表征路徑中城市出現(xiàn)的順序。初始種群令種群中有M個個體，可隨機產(chǎn)生M個數(shù)字串構(gòu)成初始種群。例如：將數(shù)字串1234…N上的數(shù)字進行隨機的交換步驟一：初始化第21頁，課件共44頁，創(chuàng)作于2023年2月適應(yīng)度的計算步驟二：適應(yīng)度選擇12345對于個體，適應(yīng)度為：被選中作為父個體的概率：選擇M次重新生成種群第22頁，課件共44頁，創(chuàng)作于2023年2月TSP中交叉算子的特點

要保證生成的解為有效解從一個父個體中隨機選取一段子串A，在另一個父個體中將A中出現(xiàn)的數(shù)字去掉形成串B，AB為一個子串步驟三：交叉操作此外還有多種交叉算子第23頁，課件共44頁，創(chuàng)作于2023年2月常用的變異操作：隨機選取兩個相鄰位置的數(shù)字，交換其順序。

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

智能優(yōu)化計算簡單實例產(chǎn)生初始種群計算適應(yīng)度4.1.4遺傳算法的基本操作

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）第29頁，課件共44頁，創(chuàng)作于2023年2月4.1遺傳算法簡介

智能優(yōu)化計算簡單實例選擇4.1.4遺傳算法的基本操作

個體染色體適應(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第30頁，課件共44頁，創(chuàng)作于2023年2月4.1遺傳算法簡介

智能優(yōu)化計算簡單實例選擇4.1.4遺傳算法的基本操作

個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000第31頁，課件共44頁，創(chuàng)作于2023年2月4.1遺傳算法簡介

智能優(yōu)化計算簡單實例選擇在0～1之間產(chǎn)生一個隨機數(shù)：4.1.4遺傳算法的基本操作

個體染色體適應(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淘汰！淘汰！第32頁，課件共44頁，創(chuàng)作于2023年2月00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遺傳算法簡介

智能優(yōu)化計算簡單實例交叉4.1.4遺傳算法的基本操作

00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011第33頁，課件共44頁，創(chuàng)作于2023年2月4.1遺傳算法簡介

智能優(yōu)化計算簡單實例變異4.1.4遺傳算法的基本操作

0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011第34頁，課件共44頁，創(chuàng)作于2023年2月4.2基本遺傳算法

智能優(yōu)化計算問題的提出

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

第35頁，課件共44頁，創(chuàng)作于2023年2月4.2基本遺傳算法

智能優(yōu)化計算問題的提出

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

第36頁，課件共44頁，創(chuàng)作于2023年2月4.2基本遺傳算法

智能優(yōu)化計算問題的提出

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

第37頁，課件共44頁，創(chuàng)作于2023年2月4.2基本遺傳算法

智能優(yōu)化計算編碼

表現(xiàn)型：x基因型：二進制編碼（串長取決于求解精度）

串長與精度之間的關(guān)系：若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進制串長應(yīng)為22位。4.2.1簡單函數(shù)優(yōu)化的實例

第38頁，課件共44頁，創(chuàng)作于2023年2月4.2基本遺傳算法

智能優(yōu)化計算產(chǎn)生初始種群

產(chǎn)生的方式：隨機產(chǎn)生的結(jié)果：長度為22的二進制串產(chǎn)生的數(shù)量：種群的大小（規(guī)模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……4.2.1簡單函數(shù)優(yōu)化的實例