算法合集之遺傳算法的特點(diǎn)及其應(yīng)用(編輯修改稿)
2024-11-14 18:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 先計(jì)算群體中每個(gè)串的生存概率 ， 1=j=n， 然后計(jì)算期望復(fù)制數(shù) ei=Ps*n， 式中： n為群體中染色體的數(shù)目 。根據(jù) ei的值給每個(gè)染色體串分配一個(gè)復(fù)制數(shù) 。 ? 交換運(yùn)算與前述相同 ， 不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大 ， 使得遺傳變得不穩(wěn)定 ， 優(yōu)秀的染色體不能遺傳到下一代 。因此可以采用 多點(diǎn)交換 。 ? 變異運(yùn)算時(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之間的距離 ， Dij=Dji， 現(xiàn)在要求一條遍歷所有 N個(gè)城市 ， 且不走重復(fù)路的最短路徑 （ 最短哈密爾頓圈 ） 。 ? 這是一個(gè)典型 NP完全問題 。 傳統(tǒng)解法對(duì)此都并不太奏效下面我們?cè)囍眠z傳算法來(lái)解決這道題目 。 TSP(旅行商)問題 ? 我們先采用十進(jìn)制編碼 ， 每個(gè)染色體由按一定順序排列的 N個(gè)城市的序號(hào)組成 ， 表示一條可能的旅行路徑 。 適應(yīng)度為一條旅行路徑對(duì)應(yīng)的距離 ， 路徑越短的染色體適應(yīng)度越高 。 例如 ， 取 N=10， 城市代號(hào)為 1至 10。 例如種群中的染色體： 2 8 4 10 5 1 7 3 6 9 表示一條旅行路徑 2?8?4?10?5?1?7?3?6?9?2 其總路徑長(zhǎng) 我們可以采用非負(fù)變換 ， 把最小化優(yōu)化目標(biāo)函數(shù)變換為以最大值為目標(biāo)的適應(yīng)度函數(shù) ， 可以如下定義： 其中 cmax為可以取為進(jìn)化過程中路徑長(zhǎng)度的最大值 ， 或者為了保證 f(x)為正而預(yù)先設(shè)定為一個(gè)與種群無(wú)關(guān)的常數(shù) 。 9269367317511054108428 DDDDDD
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1