遺傳算法簡述ppt課件(編輯修改稿)
2025-06-03 02:31 本頁面
【文章內(nèi)容簡介】 適應(yīng)度 選擇概率 積累概率 估計(jì)的 選中次數(shù) s1=11100 784 2 s2=01001 81 0 s3=11000 576 1 s4=10011 361 1 設(shè)這一輪的選擇 復(fù)制結(jié)果為： s1’=11100（ 28） , s2’=11100（ 28） s3’=11000（ 24） , s4’=10011（ 19） 做交叉運(yùn)算，讓 s1’與 s4’， s2’與 s3’ 分別交換后兩位基因，得 s1’’=11111（ 31） , s2’’=11100（ 28） s3’’=11000（ 24） , s4’’=10000（ 16） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第四代種群 S4： s1=11111（ 31） , s2=11100（ 28） s3=11000（ 24） , s4=10000（ 16） 顯然 ， 在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體 s1=11111。 于是 ， 遺傳操作終止 ，將 染色體 “ 11111”作為最終結(jié)果輸出 。 然后，將染色體 “ 11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解： 31。 將 31代入函數(shù) y=x2中，即得原問題的解，即函數(shù) y=x2的最大值為 961。 Y Y y=x2 8 13 19 24 X 第一代種群及其適應(yīng)度 y=x2 12 16 25 27 X Y 第二代種群及其適應(yīng)度 y=x2 9 19 24 28 X Y 第三代種群及其適應(yīng)度 y=x2 16 24 28 31 X 第四代種群及其適應(yīng)度 例 用遺傳算法求解 TSP。 分析 由于其任一可能解 —— 一個(gè)合法的城市序列 ， 即 n個(gè)城市的一個(gè)排列 ， 都可以事先構(gòu)造出來 。 于是 ， 我們就可以直接在解空間 （ 所有合法的城市序列 ） 中搜索最佳解 。 這正適合用遺傳算法求解 。 （ 1）定義適應(yīng)度函數(shù) 我們將一個(gè)合法的城市序列 s=（ c1, c2, …, , +1）(+1就是 c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體 s的適應(yīng)度，從而適應(yīng)度函數(shù)就是 ????niii ccdsf11 ),(1)( （ 2）對個(gè)體 s=（ c1, c2, …, , +1）進(jìn)行編碼。但對于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑?。因?yàn)?如果編碼不當(dāng)，就會(huì)在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無效解。 例如，對于 5個(gè)城市的 TSP，我們用符號(hào) A、B、 C、 D、 E代表相應(yīng)的城市，用這 5個(gè)符號(hào)的序列表示可能解即染色體。 然后進(jìn)行遺傳操作。設(shè) s1=（ A, C, B, E, D, A）， s2=（ A, E, D, C, B, A） 實(shí)施常規(guī)的交叉或變異操作，如交換后三位，得 s1’=（ A,C,B,C,B,A）， s2’=（ A,E,D,E,D,A） 或者將染色體 s1第二位的 C變?yōu)?E，得 s1’’=（ A, E, B, E, D, A） 可以看出，上面得到的 s1’， s2’和 s1’’都 是非法的城市序列。 為此，對 TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。 事實(shí)上，人們針對 TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如 順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異 等等。從而巧妙地用遺傳算法解決了 TSP。 遺傳算法 遺傳算法特點(diǎn) 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法的收斂性分析 遺傳算法改進(jìn) 遺傳算法的融合 遺傳算法的特點(diǎn)與優(yōu)勢 ◆ 傳統(tǒng)優(yōu)化算法 枚舉法 ：枚舉出可行解集合內(nèi)的所有可行解 ， 以求出精確最優(yōu)解 。 * 對于連續(xù)函數(shù) ， 要求先進(jìn)行離散化處理 。 枚舉空間比較大時(shí) ， 方法求解效率較低 ，甚至無法求解 。 啟發(fā)式算法 ：尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則 ， 已找到一個(gè)最優(yōu)解或近似最優(yōu)解 。 * 該方法的求解效率比較高 ， 但對每一個(gè)需求解的問題必須找出其特有的啟發(fā)式規(guī)則 ，這個(gè)啟發(fā)式規(guī)則一般無通用性 ， 不適合于其他問題 。 搜索算法：尋求一種搜索算法 ， 該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作 ， 已找到問題的最優(yōu)解或近似最優(yōu)解 。 * 該方法雖然保證不了能夠獲得問題的最優(yōu)解 ， 但若適當(dāng)?shù)乩靡恍﹩l(fā)式規(guī)則 ， 就可以在近似解的質(zhì)量和效率上達(dá)到一種較好的平衡 。 ◆ 遺傳算法的主要特點(diǎn) —— 遺傳算法一般是直接在解空間搜索 , 而不像圖搜索那樣一般是在問題空間搜索 , 最后才找到解 ， 因而可以更加直接地應(yīng)用 。 —— 遺傳算法是一種隨機(jī)搜索算法 ， 搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集 ， 避免使得算法總是陷入到相同的局部極小點(diǎn) （ 局部最優(yōu)值 ） 。 —— 遺傳算法采用適應(yīng)度函數(shù)和遺傳操作，從而設(shè)法盡快找到解 , 所以遺傳算法又是一種優(yōu)化搜索算法。 —— 遺傳算法的搜索過程是從空間的一個(gè)點(diǎn)集 (種群 )到另一個(gè)點(diǎn)集 (種群 )的搜索 ,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1