《遺傳算法》課件

《《遺傳算法》課件》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、遺傳算法博士生：戴維迪一、遺傳算法的描述二、基本遺傳算法的構(gòu)成要素三、基本遺傳算法的一般框架四、遺傳算法的數(shù)學(xué)理論五、遺傳算法的基本實(shí)現(xiàn)技術(shù)六、遺傳算法的特點(diǎn)七、遺傳算法的應(yīng)用一、遺傳算法的描述例子：為四個(gè)連鎖飯店尋找最好的經(jīng)營(yíng)決策，其中一個(gè)經(jīng)營(yíng)飯店的決策包括要做出以下三項(xiàng)決定：（1）價(jià)格漢堡包的價(jià)格應(yīng)該定在50美分還是1美元？（2）飲料和漢堡包一起供應(yīng)的應(yīng)該是酒還是可樂(lè)？（3）服務(wù)速度飯店應(yīng)該提供慢的還是快的服務(wù)？目的：找到這三個(gè)決定的組合以產(chǎn)生最高的利潤(rùn)。上述問(wèn)題的表示方案：串長(zhǎng)(l＝3）＋字母表規(guī)模（k＝2）＋映射共有8種表

2、示方案用遺傳算法解這個(gè)問(wèn)題的第一步就是選取一個(gè)適當(dāng)?shù)谋硎痉桨?。飯店編?hào)價(jià)格飲料速度二進(jìn)制表示1高可樂(lè)快0112高酒快0013低可樂(lè)慢1104高可樂(lè)慢010表1飯店問(wèn)題的表示方案（其中的4個(gè)）群體規(guī)模N＝4第0代i串xi適應(yīng)值f（xi）10113200113110640102總和12最小值1平均值3.00最大值6表2初始群體中經(jīng)營(yíng)決策的適應(yīng)值一個(gè)簡(jiǎn)單的遺傳算法由復(fù)制、雜交、變異三個(gè)算子組成第0代交配池i串xi適應(yīng)值f（xi）f（xi）/?f（xi）串f（xi）101130.250113200110.081106311060.5011

3、06401020.170102總和1217最小值12平均值3.004.25最大值66表3使用復(fù)制算子后產(chǎn)生的交配池1.復(fù)制算子：采用賭盤(pán)選擇2.雜交算子：采用一點(diǎn)雜交作用過(guò)程：a）產(chǎn)生一個(gè)在1到l－1之間的隨機(jī)數(shù)ib）配對(duì)的兩個(gè)串相互對(duì)應(yīng)的交換從i＋1到l的位段例如：從交配池中選擇編號(hào)為1和2的串進(jìn)行配對(duì)，且雜交點(diǎn)選在2（用分隔符

4、表示），雜交算子作用的結(jié)果為：01

5、101011

6、0111對(duì)交配池中指定百分比的個(gè)體應(yīng)用雜交算子，假設(shè)雜交概率pc＝50％，交配池中余下的50％個(gè)體僅進(jìn)行復(fù)制運(yùn)算，即復(fù)制概率pr＝50％。第0代交配池第

7、1代i串xi適應(yīng)值f（xi）f（xi）/?f（xi）串f（xi）雜交點(diǎn)xif（xi）101130.25011320102200110.08110621117311060.501106－1106401020.170102－0102總和121717最小值122平均值3.004.254.25最大值667表4使用復(fù)制和雜交算子的作用結(jié)果遺傳算法利用復(fù)制和雜交算子可以產(chǎn)生具有更高平均適應(yīng)值和更好個(gè)體的群體3.變異算子：以一個(gè)很小的概率pm隨機(jī)改變?nèi)旧w串上的某些位。對(duì)于二進(jìn)制串，就是將相應(yīng)位上的0變?yōu)?或?qū)?變?yōu)?。例如：選交配池中編號(hào)為4

8、的串進(jìn)行變異，且變異點(diǎn)在2，則010000變異算子相對(duì)而言，是次要算子，但在恢復(fù)群體中失去的多樣性方面具有潛在的作用。小結(jié)上述遺傳算法描述了從第0代產(chǎn)生第1代的過(guò)程，然后遺傳算法迭代地執(zhí)行這個(gè)過(guò)程，直到滿(mǎn)足某個(gè)停止準(zhǔn)則。在每一代中，算法首先計(jì)算群體中每個(gè)個(gè)體地適應(yīng)值，然后利用適應(yīng)值信息，遺傳算法分別以概率pc、pr和pm執(zhí)行雜交、復(fù)制和變異操作，從而產(chǎn)生新的群體。應(yīng)用遺傳算法求解問(wèn)題需完成四個(gè)主要步驟：1.確定表示方案2.確定適應(yīng)值度量3.確定控制算法的參數(shù)和變量4.確定指定結(jié)果的方法和停止運(yùn)行的準(zhǔn)則二、基本遺傳算法的構(gòu)成要素1.

9、染色體編碼方法最常用的是二進(jìn)制編碼，對(duì)于離散性變量直接編碼，對(duì)于連續(xù)性變量先離散化后再編碼2.適應(yīng)度函數(shù)評(píng)估函數(shù)——用來(lái)評(píng)估一個(gè)染色體的優(yōu)劣的絕對(duì)值適應(yīng)度函數(shù)——評(píng)估一個(gè)染色體相對(duì)整個(gè)群體的優(yōu)劣的相對(duì)值的大小3.遺傳算子復(fù)制算子、交叉算子、變異算子4.基本遺傳算法運(yùn)行參數(shù)?N：群體大小，即群體中所含個(gè)體的數(shù)量，一般取20～100?T：遺傳算法的終止進(jìn)化代數(shù)，一般取100～500?pc：雜交概率，一般取0.4～0.99?pm：變異概率，一般取0.0001～0.1?pr：復(fù)制概率三、基本遺傳算法的一般框架算法過(guò)程：1.隨機(jī)產(chǎn)生一個(gè)由確

10、定長(zhǎng)度的特征串組成的初始群體2.對(duì)串群體迭代地執(zhí)行下面的步（i）和步（ii），直到滿(mǎn)足停止準(zhǔn)則：（i）計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值（ii）應(yīng)用復(fù)制、雜交和變異算子產(chǎn)生下一代群體3.把在任一代中出現(xiàn)地最好地個(gè)體串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問(wèn)題的一個(gè)解（或近似解）GEN＝0產(chǎn)生初始群體是否滿(mǎn)足停止準(zhǔn)則指定結(jié)果結(jié)束計(jì)算每個(gè)個(gè)體的適應(yīng)值i＝0i＝N？以概率選擇遺傳算子GEN＝GEN＋1選擇一個(gè)個(gè)體選擇兩個(gè)個(gè)體選擇一個(gè)個(gè)體執(zhí)行復(fù)制i＝i＋1執(zhí)行變異復(fù)制到新群體執(zhí)行雜交插入到新群體將兩個(gè)子代串插入到新群體i＝i＋1是否是否prp

11、cpmGEN—當(dāng)前代數(shù)N—群體規(guī)模四、遺傳算法的數(shù)學(xué)理論幾個(gè)相關(guān)的定義：1、模式——是一個(gè)相同的構(gòu)形，它描述的是一個(gè)串的子集，這個(gè)集合中串之間在某些位上相同。例如，添加符號(hào)*表示不確定字母，即0或1，考慮串長(zhǎng)為7的模式H＝*11*0**，則串A＝0