專題3關(guān)于遺傳算法課件

1、專題3 關(guān)于遺傳算法步驟：1.編碼2.計(jì)算適應(yīng)度3.復(fù)制4.交換5.突變2022/9/191設(shè)自變量 x 介于031，求其二次函數(shù)的最大值，即： max f(x) = x2, x 0, 31命題： 極大值問題5001000 0 31 xf (x) 當(dāng)然，利用簡單的代數(shù)運(yùn)算，很容易求出該問題的解?，F(xiàn)在改用遺傳算法求解，遺傳算法通常包括下述內(nèi)容：2022/9/192（1）編碼 遺傳算法首先要對(duì)實(shí)際問題進(jìn)行編碼，用字符串表達(dá)問題。這種字符串相當(dāng)于遺傳學(xué)中的染色體。每一代所產(chǎn)生的字符串個(gè)體總和稱為群體。為了計(jì)算機(jī)實(shí)現(xiàn)的方便，通常字符串長度固定，字符選0或1。 本例中，利用5位二進(jìn)制數(shù)表示x值，采用隨機(jī)

2、產(chǎn)生的方法，假設(shè)得出擁有四個(gè)個(gè)體的初始群體，即：01101，11000，01000，10011。x值相應(yīng)為13，24，8，19。個(gè)體編號(hào)初始群體xi適應(yīng)度f(xi)f(xi)/f(xi)f(xi)/fMp12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.2241202022/9/193（2）計(jì)算適應(yīng)度 衡量字符串（染色體）好壞的指標(biāo)是適應(yīng)度，它也就是遺傳算法的

3、目標(biāo)函數(shù)。 本例中適應(yīng)度比較簡單，用x2計(jì)算。 表中還列出了當(dāng)前適應(yīng)度的總和f(xi)及平均值f，即： f(xi) = f(x1) + f(x2) + f(x3) + f(x4) = 1170 f = f(xi) /4 = 293 個(gè)體編號(hào)初始群體xi適應(yīng)度f(xi)f(xi)/f(xi)f(xi)/fMp12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22

4、41202022/9/194（3）復(fù)制 為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效進(jìn)化論中“自然選擇、適者生存”的原則，從舊群體中選擇優(yōu)良個(gè)體進(jìn)行復(fù)制。選擇的依據(jù)是個(gè)體適應(yīng)度的大小，適應(yīng)度大的個(gè)體接受復(fù)制，使之繁殖；適應(yīng)度小的個(gè)體則刪除掉，使之死亡。 2022/9/196（3）復(fù)制 在本例中，根據(jù)相對(duì)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行取舍，2號(hào)個(gè)體性能最優(yōu)，予以復(fù)制繁殖。3號(hào)個(gè)體性能最差，將它刪除，使之死亡，表中的M表示傳遞給下一代的個(gè)體數(shù)目，其中2號(hào)個(gè)體占2個(gè)，3號(hào)個(gè)體為0，1號(hào)、4號(hào)個(gè)體保持為1個(gè)。 這樣，就產(chǎn)生了下一代群體。個(gè)體編號(hào)初始群體xi適應(yīng)度f(xi)f(xi)/f(xi)f(xi)/fM

5、p12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201總計(jì)f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.2241202022/9/197（4）交換 通過復(fù)制產(chǎn)生的新群體，其性能得到改善，然而它不能產(chǎn)生新的個(gè)體。為了產(chǎn)生新的個(gè)體，遺傳算法仿照生物學(xué)中雜交的方法，對(duì)染色體（字符串）的某些部分進(jìn)行交叉換位。被交換的母體都選自經(jīng)過復(fù)制產(chǎn)生的新一代個(gè)體（優(yōu)勝者）。2022/9/199（4）交換 本例中，利用隨機(jī)配對(duì)的方法

6、，決定1號(hào)和2號(hào)個(gè)體、3號(hào)和4號(hào)個(gè)體分別交換，如表中第5列。再利用隨機(jī)定位的方法，確定這兩對(duì)母體交叉換位的位置分別從字符長度的第4位及第3位開始。如：3號(hào)、4號(hào)個(gè)體從字符長度第3位開始交換。交換開始的位置稱交換點(diǎn)。個(gè)體編號(hào)復(fù)制后群體xi復(fù)制后適應(yīng)度f(xi)交換對(duì)象交換位置交換后群體復(fù)制后適應(yīng)度f(xi)12345678123401101110001100010011132424191695765763612號(hào)1號(hào)4號(hào)3號(hào)443301100110011101110000144625729256總計(jì)平均值最大值最小值1682421576361175443972925611000100111101

7、1100002022/9/1910（4）交換 從表中可以看出，交換后出現(xiàn)優(yōu)異個(gè)體3號(hào)，其適應(yīng)度高達(dá)729，大大高于交換前的最大值（576）。與此同時(shí)，平均適應(yīng)度也從原來的421提高到439，說明交換后的群體正朝優(yōu)良方向發(fā)展。個(gè)體編號(hào)復(fù)制后群體xi復(fù)制后適應(yīng)度f(xi)交換對(duì)象交換位置交換后群體復(fù)制后適應(yīng)度f(xi)12345678123401101110001100010011132424191695765763612號(hào)1號(hào)4號(hào)3號(hào)443301100110011101110000144625729256總計(jì)平均值最大值最小值168242157636117544397292562022/9/19

8、11（5）突變 遺傳算法模仿生物學(xué)中基因突變的方法，將個(gè)體字符串某位符號(hào)進(jìn)行逆變，即由1變?yōu)?或由0變?yōu)?。例如，下式左側(cè)的個(gè)體于第3位突變，得到新個(gè)體如右側(cè)所示。 上述（2）（5）反復(fù)執(zhí)行，直至得出滿意的最優(yōu)解。 由上可知，遺傳算法參考生物中有關(guān)進(jìn)化與遺傳的過程，利用復(fù)制、交換、突變等操作，不斷循環(huán)執(zhí)行，逐漸逼近全局最優(yōu)解。 遺傳算法中，個(gè)體是否進(jìn)行突變以及在哪個(gè)部位突變，都由事先給定的概率決定。通常，突變概率很小，約為0.008，本例的第一代中就沒有發(fā)生突變。10000101002022/9/1912 設(shè)某快餐店下設(shè)四個(gè)門市部，其經(jīng)營方式可以有下述幾個(gè)方案： （1）價(jià)格：每份快餐售價(jià)5元或

9、10元。 （2）飲料：出售酒或可樂。 （3）服務(wù)方式：由侍者服務(wù)或自助服務(wù)。 試問應(yīng)以何種價(jià)格、何種飲料及何種服務(wù)方式進(jìn)行經(jīng)營最佳？ 遺傳算法示例命題： 經(jīng)營決策問題 為了解決這個(gè)問題，可以采用遺傳算法做實(shí)驗(yàn)，其過程如下：2022/9/1913（1）編碼 我們用3位數(shù)表示經(jīng)營策略： 第3位數(shù)表示服務(wù)方式：0（侍者）、1（自助） 第2位數(shù)代表飲料種類：0（酒）、1（可樂） 第1位數(shù)表示價(jià)格：0（10元/份）、1（5元/份） 采用隨機(jī)產(chǎn)生的方法，得出第1組經(jīng)營試驗(yàn)的方案為011、001、110及010，具體含義如下表。編號(hào)價(jià)格飲料服務(wù)方式編碼110可樂自助011210酒自助00135可樂侍者110

10、410可樂侍者0102022/9/1914（3）復(fù)制 由于3號(hào)策略效果最佳，宜推廣使用。相反，2號(hào)策略效果最差，停止使用。于是，新的經(jīng)營策略經(jīng)復(fù)制后如表中第5列所示，相應(yīng)的適應(yīng)度（贏利）見第6列。 經(jīng)過復(fù)制操作，總贏利值由12升到17，這主要是由于推廣優(yōu)良策略，取消劣等策略的原因。編號(hào)初始策略復(fù)制后交換后xif(xi)f(xi)/f(xi)xif(xi)交換對(duì)象交換位置xif(xi)12345678910123401100111001031620.250.080.500.1701111011001036622號(hào)1號(hào)220101111100102762總計(jì)平均最大值最小值12361174.2562174.25722022/9/1916（4）交換 為了尋求更好的新策略，采用交換方法。利用隨機(jī)產(chǎn)生的方法，確定1號(hào)、2號(hào)策略進(jìn)行交換，且交換位置從第2位開始。于是得出新策略111，為表中第9列的2號(hào)策略，而1號(hào)策略變?yōu)?10，等同于原來的4號(hào)策略。將交換后得出的新策略在四個(gè)門市部執(zhí)行，其贏利值見表中最后1列，其中2號(hào)新策略的效益最佳。編號(hào)初始策略復(fù)制后交換后