算法合集之遺傳算法的特點(diǎn)及其應(yīng)用-文庫吧資料
2024-10-24 18:37本頁面
【正文】 (旅行商)問題 ? 關(guān)于選擇運(yùn)算 ， 可以考慮前面介紹的確定性選擇法 。 例如 ， 取 N=10， 城市代號為 1至 10。 TSP(旅行商)問題 ? 我們先采用十進(jìn)制編碼 ， 每個(gè)染色體由按一定順序排列的 N個(gè)城市的序號組成 ， 表示一條可能的旅行路徑 。 ? 這是一個(gè)典型 NP完全問題 。 ? 變異運(yùn)算時(shí) ， 只需注意變異概率的取值 ， 至于具體算法如前面所述 。 ? 交換運(yùn)算與前述相同 ， 不過若進(jìn)行單點(diǎn)交換有可能使得兩個(gè)染色體在交換時(shí)產(chǎn)生的差異過大 ， 使得遺傳變得不穩(wěn)定 ， 優(yōu)秀的染色體不能遺傳到下一代 。 因此 ，我在這里采用確定性選擇法 ， 先計(jì)算群體中每個(gè)串的生存概率 ， 1=j=n， 然后計(jì)算期望復(fù)制數(shù) ei=Ps*n， 式中： n為群體中染色體的數(shù)目 。 令 f(k)為當(dāng)前群體中所有染色體適應(yīng)度的最大值 f’ (x)=|f(k)f(x)| 所以適應(yīng)度為 f ’ (x)。 每一位 ，用 0、 1表示是否屬于子集 。 在這種情況下 ， 我們要找出 S的一個(gè)子集 S’ ， 使得其和不超過 t，但又盡可能接近于 t。 ? 我們已知道該問題是一個(gè) NP完全問題 。通過變異操作，可以使搜索能在盡可能大的空間中進(jìn)行，獲得質(zhì)量較高的優(yōu)化解答。 變 異 變異運(yùn)算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小概率隨機(jī)地改變遺傳基因的值。 ?? )(/)( icc xfxfP? )( ixf交 換 復(fù)制操作雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交換操作。某一染色體被選中的概率為 式中 xi為種群中第 i個(gè)染色體對應(yīng)的數(shù)字串 ，f(xi)是第 i個(gè)染色體的適應(yīng)度值 ， 是種群中所有染色體的適應(yīng)度值之和 。其實(shí)就是將適應(yīng)度值視為其權(quán)值 ， 權(quán)值大的被選中的概率也大 。上述 GA的工作過程可用 圖 1簡要描述。 ? 由于新群體的成員是上一代群體的優(yōu)秀者，因而在總體上優(yōu)于上一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1