專題3關(guān)于遺傳算法.ppt

1,2019年6月29日星期六,專題3 關(guān)于遺傳算法,步驟： 1.編碼 2.計(jì)算適應(yīng)度 3.復(fù)制 4.交換 5.突變,2019年6月29日星期六,2,設(shè)自變量 x 介于031，求其二次函數(shù)的最大值，即： max f(x) = x2, x 0, 31,命題： 極大值問題,當(dāng)然，利用簡單的代數(shù)運(yùn)算，很容易求出該問題的解?，F(xiàn)在改用遺傳算法求解，遺傳算法通常包括下述內(nèi)容：,2019年6月29日星期六,3,（1）編碼 遺傳算法首先要對實(shí)際問題進(jìn)行編碼，用字符串表達(dá)問題。這種字符串相當(dāng)于遺傳學(xué)中的染色體。每一代所產(chǎn)生的字符串個體總和稱為群體。為了計(jì)算機(jī)實(shí)現(xiàn)的方便，通常字符串長度固定，字符選0或1。 本例中，利用5位二進(jìn)制數(shù)表示x值，采用隨機(jī)產(chǎn)生的方法，假設(shè)得出擁有四個個體的初始群體，即：01101，11000，01000，10011。x值相應(yīng)為13，24，8，19。,2019年6月29日星期六,4,（2）計(jì)算適應(yīng)度 衡量字符串（染色體）好壞的指標(biāo)是適應(yīng)度，它也就是遺傳算法的目標(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,2019年6月29日星期六,5,（2）計(jì)算適應(yīng)度 表中第6列的 f(xi)/f 表示每個個體的相對適應(yīng)度，它反映了個體之間的相對優(yōu)劣性。如2號個體的 f(xi)/f 值最高（1.97），為優(yōu)良個體，3號個體最低（0.22），為不良個體。,2019年6月29日星期六,6,（3）復(fù)制 為了將已有的群體變?yōu)橄乱淮后w，遺傳算法仿效進(jìn)化論中“自然選擇、適者生存”的原則，從舊群體中選擇優(yōu)良個體進(jìn)行復(fù)制。選擇的依據(jù)是個體適應(yīng)度的大小，適應(yīng)度大的個體接受復(fù)制，使之繁殖；適應(yīng)度小的個體則刪除掉，使之死亡。,2019年6月29日星期六,7,（3）復(fù)制 在本例中，根據(jù)相對適應(yīng)度的大小對個體進(jìn)行取舍，2號個體性能最優(yōu)，予以復(fù)制繁殖。3號個體性能最差，將它刪除，使之死亡，表中的M表示傳遞給下一代的個體數(shù)目，其中2號個體占2個，3號個體為0，1號、4號個體保持為1個。,這樣，就產(chǎn)生了下一代群體。,2019年6月29日星期六,8,（3）復(fù)制,從表中的第4列可以看出，復(fù)制后產(chǎn)生的新一代群體的平均適應(yīng)度明顯增加，由原來的293增加到421。造成平均適應(yīng)度增加的原因有二： 1）淘汰原來最差的個體。使最小適應(yīng)度由原來的64增加到169。 2）增加了優(yōu)良個體（2號）的個數(shù)，使適應(yīng)度累計(jì)值增加。,2019年6月29日星期六,9,（4）交換,通過復(fù)制產(chǎn)生的新群體，其性能得到改善，然而它不能產(chǎn)生新的個體。為了產(chǎn)生新的個體，遺傳算法仿照生物學(xué)中雜交的方法，對染色體（字符串）的某些部分進(jìn)行交叉換位。被交換的母體都選自經(jīng)過復(fù)制產(chǎn)生的新一代個體（優(yōu)勝者）。,2019年6月29日星期六,10,（4）交換,本例中，利用隨機(jī)配對的方法，決定1號和2號個體、3號和4號個體分別交換，如表中第5列。再利用隨機(jī)定位的方法，確定這兩對母體交叉換位的位置分別從字符長度的第4位及第3位開始。如：3號、4號個體從字符長度第3位開始交換。交換開始的位置稱交換點(diǎn)。,2019年6月29日星期六,11,（4）交換,從表中可以看出，交換后出現(xiàn)優(yōu)異個體3號，其適應(yīng)度高達(dá)729，大大高于交換前的最大值（576）。與此同時(shí)，平均適應(yīng)度也從原來的421提高到439，說明交換后的群體正朝優(yōu)良方向發(fā)展。,2019年6月29日星期六,12,（5）突變,遺傳算法模仿生物學(xué)中基因突變的方法，將個體字符串某位符號進(jìn)行逆變，即由1變?yōu)?或由0變?yōu)?。例如，下式左側(cè)的個體于第3位突變，得到新個體如右側(cè)所示。,上述（2）（5）反復(fù)執(zhí)行，直至得出滿意的最優(yōu)解。,由上可知，遺傳算法參考生物中有關(guān)進(jìn)化與遺傳的過程，利用復(fù)制、交換、突變等操作，不斷循環(huán)執(zhí)行，逐漸逼近全局最優(yōu)解。,遺傳算法中，個體是否進(jìn)行突變以及在哪個部位突變，都由事先給定的概率決定。通常，突變概率很小，約為0.008，本例的第一代中就沒有發(fā)生突變。,2019年6月29日星期六,13,設(shè)某快餐店下設(shè)四個門市部，其經(jīng)營方式可以有下述幾個方案： （1）價(jià)格：每份快餐售價(jià)5元或10元。 （2）飲料：出售酒或可樂。 （3）服務(wù)方式：由侍者服務(wù)或自助服務(wù)。 試問應(yīng)以何種價(jià)格、何種飲料及何種服務(wù)方式進(jìn)行經(jīng)營最佳？,遺傳算法示例,命題： 經(jīng)營決策問題,為了解決這個問題，可以采用遺傳算法做實(shí)驗(yàn)，其過程如下：,2019年6月29日星期六,14,（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，具體含義如下表。,2019年6月29日星期六,15,（2）確定適應(yīng)度 上述四種經(jīng)營策略，分別在四個門市部執(zhí)行。一周后，得出各門市部的贏利值，也就是適應(yīng)度，如表中第3列所示，其中以3號策略贏利最高（6），2號策略贏利最低（1）。,2019年6月29日星期六,16,（3）復(fù)制 由于3號策略效果最佳，宜推廣使用。相反，2號策略效果最差，停止使用。于是，新的經(jīng)營策略經(jīng)復(fù)制后如表中第5列所示，相應(yīng)的適應(yīng)度（贏利）見第6列。 經(jīng)過復(fù)制操作，總贏利值由12升到17，這主要是由于推廣優(yōu)良策略，取消劣等策略的原因。,2019年6月29日星期六,17,（4）交換 為了尋求更好的新策略，采用交換方法。利用隨機(jī)產(chǎn)生的方法，確定1號、2號策略進(jìn)行交換，且交換位置從第2位開始。于是得出新策略111，為表中第9列的2號策略，而1號策略變?yōu)?10，等同于原來的4號策略。將交換后得出的新策略在四個門市部執(zhí)行，其贏利值見表中最后1列，其中2號新策略的效益最佳。,2019年6月29日星期六,18,（5 ）突變 也可以采用突變的方法產(chǎn)生新策略，按某一事