遺傳算法簡(jiǎn)述ppt課件-文庫(kù)吧資料
2025-05-13 02:31本頁(yè)面
【正文】 1。 —— 遺傳算法對(duì)應(yīng)給定問題 ， 可產(chǎn)生許多潛在解 ， 并可由使用者來(lái)確定最終解 。 —— 遺傳算法的適應(yīng)性強(qiáng) , 除需知適應(yīng)度函數(shù)外 , 幾乎不需要其他的先驗(yàn)知識(shí) 。 —— 遺傳算法的搜索過程是從空間的一個(gè)點(diǎn)集 (種群 )到另一個(gè)點(diǎn)集 (種群 )的搜索 ,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。 —— 遺傳算法是一種隨機(jī)搜索算法 ， 搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集 ， 避免使得算法總是陷入到相同的局部極小點(diǎn) （ 局部最優(yōu)值 ） 。 * 該方法雖然保證不了能夠獲得問題的最優(yōu)解 ， 但若適當(dāng)?shù)乩靡恍﹩l(fā)式規(guī)則 ， 就可以在近似解的質(zhì)量和效率上達(dá)到一種較好的平衡 。 * 該方法的求解效率比較高 ， 但對(duì)每一個(gè)需求解的問題必須找出其特有的啟發(fā)式規(guī)則 ，這個(gè)啟發(fā)式規(guī)則一般無(wú)通用性 ， 不適合于其他問題 。 枚舉空間比較大時(shí) ， 方法求解效率較低 ，甚至無(wú)法求解 。 遺傳算法 遺傳算法特點(diǎn) 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法的收斂性分析 遺傳算法改進(jìn) 遺傳算法的融合 遺傳算法的特點(diǎn)與優(yōu)勢(shì) ◆ 傳統(tǒng)優(yōu)化算法 枚舉法 ：枚舉出可行解集合內(nèi)的所有可行解 ， 以求出精確最優(yōu)解 。 事實(shí)上，人們針對(duì) TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如 順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎ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’’都 是非法的城市序列。 例如，對(duì)于 5個(gè)城市的 TSP，我們用符號(hào) A、B、 C、 D、 E代表相應(yīng)的城市，用這 5個(gè)符號(hào)的序列表示可能解即染色體。但對(duì)于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑椤? （ 1）定義適應(yīng)度函數(shù) 我們將一個(gè)合法的城市序列 s=（ c1, c2, …, , +1）(+1就是 c1)作為一個(gè)個(gè)體。 于是 ， 我們就可以直接在解空間 （ 所有合法的城市序列 ） 中搜索最佳解 。 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。 然后，將染色體 “ 11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解： 31。 于是，得第四代種群 S4： s1=11111（ 31） , s2=11100（ 28） s3=11000（ 24） , s4=10000（ 16） 顯然 ， 在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體 s1=11111。 于是，得到第二代種群 S2： s1=11001（ 25） , s2=01100（ 12） s3=11011（ 27） , s4=10000（ 16） 第二代種群 S2中各染色體的情況 染色體 適應(yīng)度 選擇概率 積累概率 估計(jì)的 選中次數(shù) s1=11001 625 1 s2=01100 144 0 s3=11011 729 2 s4=10000 256 1 假設(shè)這一輪選擇 復(fù)制操作中，種群 S2中的 4個(gè)染色體都被選中 ，則得到群體： s1’=11001（ 25） , s2’= 01100（ 12） s3’=11011（ 27） , s4’= 10000（ 16） 做交叉運(yùn)算，讓 s1’與 s2’， s3’與 s4’ 分別交換后三位基因，得 s1’’ =11100（ 28） , s2’’ = 01001（ 9） s3’’ =11000（ 24） , s4’’ = 10011（ 19） 這一輪仍然不會(huì)發(fā)生變異。 這樣 ， 群體 S1中共有 5 4 = 位基因可以變異 。 設(shè) s1’與 s2’配對(duì) ， s3’與 s4’配對(duì) 。 ③ 若 qk1r≤qk(2≤k≤N), 則染色體 xk被選中 。 ??? NjjiixfxfxP1)()()(選擇概率的計(jì)算公式為 由此可求得 P(s1) = P(13) = P(s2) = P(24) = P(s3) = P(8) = P(s4) = P(19) = 賭輪選擇示意 s4 s2 s1 ● 賭輪選擇法 在算法中賭輪選擇法可用下面的子過程來(lái)模擬 : ① 在 ［ 0,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1