遺傳算法的實(shí)例第1頁，課件共19頁，創(chuàng)作于2023年2月遺傳算法(GA)的肇始“活的有機(jī)體是解決問題的專家。它們所表現(xiàn)出來的各種才能足以使最好的計(jì)算機(jī)程序自慚形穢。這種現(xiàn)象尤其令計(jì)算機(jī)科學(xué)家們感到痛楚。計(jì)算機(jī)科學(xué)家們?yōu)榱四撤N算法可能花費(fèi)數(shù)月乃至數(shù)年的腦力勞動(dòng)，而有機(jī)體則能通過進(jìn)化和自然選擇這樣一種顯然并非定向進(jìn)行的機(jī)制獲得這種能力。”---JohnHolland第2頁，課件共19頁，創(chuàng)作于2023年2月遺傳算法的思想Darwin的進(jìn)化論

----“自然選擇、適者生存”特定環(huán)境的考驗(yàn)種群中個(gè)體的選擇種群中的交叉繁殖種群中個(gè)體的變異

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

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

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

(3)適應(yīng)度汁算遺傳算法中以個(gè)體適應(yīng)度的大小來評定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)會(huì)的大小。本例中，目標(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è)體將有更多的機(jī)會(huì)遺傳到下一代群體中。第5頁，課件共19頁，創(chuàng)作于2023年2月

本例中，我們采用與適應(yīng)度成正比的概率來確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是：

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

(i=1.2,…,M);

?其次計(jì)算出每個(gè)個(gè)體的相對適應(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)來確定各個(gè)個(gè)體被選中的次數(shù)。0124%24%17%35%1#2#3#4#個(gè)體編號初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001x1x235533471第6頁，課件共19頁，創(chuàng)作于2023年2月(5)交叉運(yùn)算交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過程，它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體。本例采用單點(diǎn)交叉的方法，其具體操作過程是：

?先對群體進(jìn)行隨機(jī)配對；

?其次隨機(jī)設(shè)置交叉點(diǎn)位置；

?最后再相互交換配對染色體之間的部分基因。選擇結(jié)果011101111001101011111001配對情況交叉點(diǎn)位置個(gè)體編號12341-23-41-2：23-4：4交叉結(jié)果011001111101101001111011

可以看出，其中新產(chǎn)生的個(gè)體“111101”、“111011”的適應(yīng)度較原來兩個(gè)個(gè)體的適應(yīng)度都要高。第7頁，課件共19頁，創(chuàng)作于2023年2月(6)變異運(yùn)算變異運(yùn)算是對個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。本例中，我們采用基本位變異的方法來進(jìn)行變異運(yùn)算，其具體操作過程是：

?首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置，其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因座處；

?然后依照某一概率將變異點(diǎn)的原有基因值取反。對群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。個(gè)體編號1234交叉結(jié)果011001111101101001111011變異結(jié)果變異點(diǎn)4526011101111111111001111010子代群體p(1)011101111111111001111010第8頁，課件共19頁，創(chuàng)作于2023年2月

從上表中可以看出，群體經(jīng)過一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最佳個(gè)體“111111”。

[注意]

需要說明的是，表中有些欄的數(shù)據(jù)是隨機(jī)產(chǎn)生的。這里為了更好地說明問題，我們特意選擇了一些較好的數(shù)值以便能夠得到較好的結(jié)果，而在實(shí)際運(yùn)算過程中有可能需要一定的循環(huán)次數(shù)才能達(dá)到這個(gè)最優(yōu)結(jié)果。個(gè)體編號子群體p(1)適值占總數(shù)的百分比總和1234011101111111111001111010349850530.140.420.210.232351x1x235777172第9頁，課件共19頁，創(chuàng)作于2023年2月算法流程圖第10頁，課件共19頁，創(chuàng)作于2023年2月TSP問題的遺傳算法求解步驟一：個(gè)體編碼及種群初始化步驟二：適應(yīng)度選擇步驟三：交叉操作步驟四：變異操作步驟五：重復(fù)二、三、四步，直至結(jié)束

令城市(點(diǎn))數(shù)目為N第11頁，課件共19頁，創(chuàng)作于2023年2月個(gè)體編碼取長度為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ī)的交換步驟一：初始化第12頁，課件共19頁，創(chuàng)作于2023年2月適應(yīng)度的計(jì)算步驟二：適應(yīng)度選擇12345對于個(gè)體，適應(yīng)度為：被選中作為父個(gè)體的概率：第13頁，課件共19頁，創(chuàng)作于2023年2月TSP中交叉算子的特點(diǎn)

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

51243(5)51234(5)步驟四：變異操作1234512345交換3,4此外還有多種變異算子第15頁，課件共19頁，創(chuàng)作于2023年2月反復(fù)執(zhí)行步驟二、三、四結(jié)束判定：

步