算法合集之遺傳算法的特點(diǎn)及其應(yīng)用-wenkub
2022-11-02 18:37:50 本頁面
【正文】 應(yīng)度應(yīng)為正值 。 選 擇 選擇運(yùn)算使用比較普遍的一種是適應(yīng)度比例法 。 ? 算法開始時(shí)先隨機(jī)地產(chǎn)生一些染色體 ， 計(jì)算其適應(yīng)度 ， 根據(jù)適應(yīng)度對(duì)諸染色體進(jìn)行選擇 、交換 、 變異等遺傳操作 ， 剔除適應(yīng)度低的染色體 ， 留下適應(yīng)度高的染色體 。 對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題，特別是優(yōu)化問題， GA提供了一個(gè)行之有效的新途徑。 簡單的遺傳算法 ? GA把每一個(gè)可能的解編碼為一個(gè)向量 ， 稱為一個(gè)染色體 ， 向量的每一個(gè)元素稱為基因 。 ? 由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。其實(shí)就是將適應(yīng)度值視為其權(quán)值 ， 權(quán)值大的被選中的概率也大 。 ?? )(/)( icc xfxfP? )( ixf交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交換操作。通過變異操作，可以使搜索能在盡可能大的空間中進(jìn)行，獲得質(zhì)量較高的優(yōu)化解答。 在這種情況下 ， 我們要找出 S的一個(gè)子集 S’ ， 使得其和不超過 t，但又盡可能接近于 t。 令 f(k)為當(dāng)前群體中所有染色體適應(yīng)度的最大值 f’ (x)=|f(k)f(x)| 所以適應(yīng)度為 f ’ (x)。 ? 交換運(yùn)算與前述相同 ， 不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大 ， 使得遺傳變得不穩(wěn)定 ， 優(yōu)秀的染色體不能遺傳到下一代 。 ? 這是一個(gè)典型 NP完全問題 。 例如 ， 取 N=10， 城市代號(hào)為 1至 10。 因此須改進(jìn)交換運(yùn)算 。 ? 算法的主要部分已經(jīng)討論完了 ， 但是還有一點(diǎn)值得提出的 ， 由于遺傳算法是一種不斷優(yōu)化的搜索算法 ， 因此 ， 我們可以用貪心算法構(gòu)造初始群 。 結(jié) 束 語 ? 遺傳算法的原理是簡單的 ， 但是如何熟練運(yùn)用遺傳算法卻并不是一個(gè)簡單的問題 ， 理論要切合實(shí)際 ， 對(duì)于不同問題 ， 遺傳算法要稍加變化 ， 就如同畫龍點(diǎn)睛一般 ， 切忌不可生搬硬套 。 圖 一 Y 問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1