算法合集之遺傳算法的特點(diǎn)及其應(yīng)用-文庫(kù)吧在線文庫(kù)
【正文】 行兩點(diǎn)交換即可 ，其實(shí)兩點(diǎn)交換與單點(diǎn)交換是類似的 。 ? 算法的主要部分已經(jīng)討論完了 ， 但是還有一點(diǎn)值得提出的 ， 由于遺傳算法是一種不斷優(yōu)化的搜索算法 ， 因此 ， 我們可以用貪心算法構(gòu)造初始群 。 例如 ， 取 N=10， 城市代號(hào)為 1至 10。 ? 交換運(yùn)算與前述相同 ， 不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大 ， 使得遺傳變得不穩(wěn)定 ， 優(yōu)秀的染色體不能遺傳到下一代 。 在這種情況下 ， 我們要找出 S的一個(gè)子集 S’ ， 使得其和不超過 t，但又盡可能接近于 t。 ?? )(/)( icc xfxfP? )( ixf交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交換操作。 ? 由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一代。 對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的復(fù)雜問題，特別是優(yōu)化問題， GA提供了一個(gè)行之有效的新途徑。 選 擇 選擇運(yùn)算使用比較普遍的一種是適應(yīng)度比例法 。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由 1變成0，或由 0變成 1。 我們將染色體所表示的子集的元素和與所給 t的差異記為適應(yīng)度 ， 即令染色體 x的每一位為 xi， 所表示元素的值為 Si則 但是經(jīng)過實(shí)踐后發(fā)現(xiàn)由于適應(yīng)度相對(duì)差異較小 ， 使得適應(yīng)度非常接近 ， 難以區(qū)分染色體的優(yōu)劣 ， 使得遺傳進(jìn)化變得非常緩慢 ， 且 f(x)可能為負(fù)值 ， 因此還需對(duì)適應(yīng)度函數(shù)做一下變換 ， 才可以適合本題的要求 。 ?? jis ffP /子集和問題 ? 在本題中的一些數(shù)值不妨取值如下： ? 種群長(zhǎng)度 （ 染色體個(gè)數(shù) ） ： 20 ? 選擇概率： ? 變異概率： ? 結(jié)束條件：當(dāng)前最優(yōu)解在 100代遺傳后仍未改變 ， 或已取到最優(yōu)解 TSP(旅行商)問題 GA在 TSP（ 旅行商 ） 問題求解中的應(yīng)用 ? 設(shè)存在 N個(gè)城市 ， Dij表示城 i與城 j之間的距
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1