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