算法合集之《遺傳算法的特點及其應用》-文庫吧
2024-10-03 18:37 本頁面
【正文】 出了交換操作。即：在匹配集中任選兩個染色體，隨機選擇一點或多點交換點位置，交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數(shù)字串。 變 異 變異運算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小概率隨機地改變遺傳基因的值。在染色體以二進制編碼的系統(tǒng)中，它隨機地將染色體的某一個基因由 1變成0，或由 0變成 1。通過變異操作，可以使搜索能在盡可能大的空間中進行，獲得質(zhì)量較高的優(yōu)化解答。 遺傳算法應用舉例 ?子集和問題 ? TSP(旅行商 )問題 子集和問題 GA在子集和問題上的應用 ? 子集和問題 SUBSET_SUM：給定正整數(shù)集合 S和一個整數(shù) t， 判定是否存在 S的一個子集使得 S’ 中整數(shù)的和為 t。 ? 我們已知道該問題是一個 NP完全問題 。在實際應用中 ， 我們常遇到的是最優(yōu)化子集和問題 。 在這種情況下 ， 我們要找出 S的一個子集 S’ ， 使得其和不超過 t，但又盡可能接近于 t。 子集和問題 ? 下面用遺傳算法來解決： ? 我們可以用 n位二進制數(shù)來表示每個染色體 。 每一位 ，用 0、 1表示是否屬于子集 。 我們將染色體所表示的子集的元素和與所給 t的差異記為適應度 ， 即令染色體 x的每一位為 xi， 所表示元素的值為 Si則 但是經(jīng)過實踐后發(fā)現(xiàn)由于適應度相對差異較小 ， 使得適應度非常接近 ， 難以區(qū)分染色體的優(yōu)劣 ， 使得遺傳進化變得非常緩慢 ， 且 f(x)可能為負值 ， 因此還需對適應度函數(shù)做一下變換 ， 才可以適合本題的要求 。 令 f(k)為當前群體中所有染色體適應度的最大值 f’ (x)=|f(k)f(x)| 所以適應度為 f ’ (x)。 tSxfixi ?? ?? 0)(子集和問題 ? 選擇時可以用前面所介紹的適應度比例法 ， 但可能會因為偶然情況使得優(yōu)秀的染色體沒有子孫 。 因此 ，我在這里采用確定性選擇法 ，
教學課件相關推薦
鄂ICP備17016276號-1