算法合集之《遺傳算法的特點及其應用》-預覽頁
【正文】 tSxfixi ?? ?? 0)(子集和問題 ? 選擇時可以用前面所介紹的適應度比例法 ， 但可能會因為偶然情況使得優(yōu)秀的染色體沒有子孫 。因此可以采用 多點交換 。 傳統(tǒng)解法對此都并不太奏效下面我們試著用遺傳算法來解決這道題目 。 例如種群中的染色體： 2 8 4 10 5 1 7 3 6 9 表示一條旅行路徑 2?8?4?10?5?1?7?3?6?9?2 其總路徑長 我們可以采用非負變換 ， 把最小化優(yōu)化目標函數(shù)變換為以最大值為目標的適應度函數(shù) ， 可以如下定義： 其中 cmax為可以取為進化過程中路徑長度的最大值 ， 或者為了保證 f(x)為正而預先設定為一個與種群無關的常數(shù) 。 我們可以采用 部分匹配交換運算 （ PMX） 。 TSP(旅行商)問題 ? 題目中的一些數(shù)值不妨取值如下： ? 種群長度 （ 染色體個數(shù) ） ： 20 ? 變異概率： ? 結束條件：當前最優(yōu)解在 100代遺傳后仍未改變 。 我認為遺傳算法應當與現(xiàn)有優(yōu)化算法結合 ， 可產(chǎn)生比單獨使用遺傳算法或現(xiàn)有優(yōu)化算法更好 ， 更實用的算法 。 ? 設有兩個父輩染色體 A和 B： A： 10100100101110 B： 01001110110001 設兩個交換點選擇如下： A： 10100|10010|1110 B： 01001|11011|0001 則兩點交換運算就是交換染色體 A和染色體 B， 兩個交換點之間的部分 ， 則交換結果如下： A’ ： 10100110111110 B’ ： 01001100100001 部分匹配交換運算 ? 部分匹配交換運算先在兩父染色體串中各產(chǎn)生兩個交換點 ， 把這兩點之間的區(qū)域定義為匹配區(qū)域 ，再對兩個匹配區(qū)域中的基因通過對應匹配置換 。 作如下置換： A： 2 8 4 10 * 5 1 7 3 * 6 9 A’ ： 1 7 4 5 * 10 2 8 3 * 6 9
教學課件相關推薦
鄂ICP備17016276號-1