遺傳算法入門到掌握

　　想了很久，應(yīng)該用一個怎么樣的例子帶領(lǐng)大家走進(jìn)遺傳 算法的神奇世界呢？遺傳算法的有趣應(yīng)用很多，諸如尋路問題，8 數(shù)碼問題，囚犯困境，動作控制，找圓心問題（這是一個國外網(wǎng)友的建議：在一個不規(guī)則的多邊形 中，尋找一個包含在該多邊形內(nèi)的最大圓圈的圓心。），TSP 問題（在以后的章節(jié)里面將做詳細(xì)介紹。），生產(chǎn)調(diào)度問題，人工生命模擬等。直到最后看到一個非 常有趣的比喻，覺得由此引出的袋鼠跳問題（暫且這么叫它吧），既有趣直觀又直達(dá)遺傳算法的本質(zhì)，確實非常適合作為初學(xué)者入門的例子。這一章將告訴讀者，我 們怎么讓袋鼠跳到珠穆朗瑪峰上去（如果它沒有過早被凍壞的話）。問題的提出與解決方案讓我們先來考慮考慮下面這個問題的解決辦法。

　　現(xiàn)在要求在既定的區(qū)間內(nèi)找出函數(shù)的最大值。函數(shù)圖像如圖 2-1 所示。極大值、最大值、局部最優(yōu)解、全局最優(yōu)解在解決上面提出的問題之前我們有必要先澄清幾個以后將常常會碰到的概念：極大值、最大值、局部最優(yōu)解、全局最優(yōu)解。學(xué)過高中數(shù)學(xué)的人都知道極大值在一個小鄰域里面左邊的函數(shù)值遞增，右邊的函數(shù)值遞減，在圖 2.1 里面的表現(xiàn)就是一 個“山峰”。當(dāng)然，在圖上有很多個“山峰”，所以這個函數(shù)有很多個極大值。而對于一個函數(shù)來說，最大值就是在所有極大值當(dāng)中，最大的那個。所以極大值具有 局部性，而最大值則具有全局性。因為遺傳算法中每一條染色體，對應(yīng)著遺傳算法的一個 解決方案，一般我們用適應(yīng)性函數(shù)（fitness function）來衡量這個解決方案的優(yōu)劣。所以從一個基因組到其解的適應(yīng)度形成一個映射。所以也可以把遺傳算法的過程看作是一個在多元函數(shù)里面求最優(yōu) 解的過程。在這個多維曲面里面也有數(shù)不清的“山峰”，而這些最優(yōu)解所對應(yīng)的就是局部最優(yōu)解。而其中也會有一個“山峰”的海拔最高的，那么這個就是全局最優(yōu) 解。而遺傳算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遺傳算法不一定要找“最高的山峰”，如果問題的適應(yīng)度評價越小越 好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對應(yīng)的，遺傳算法所要找的就是“最深的谷底”）如果至今你還不太理解的話，那么你先往下看。本章的示例程序?qū)?非常形象的表現(xiàn)出這個情景。

　　“袋鼠跳”問題 既然我們把 函數(shù)曲線理解成一個一個山峰和山谷組成的山脈。那么我們可以設(shè)想所得到的每一個解就是一只袋鼠，我們希望它們不斷的向著更高處跳去，直到跳到最高的山峰 （盡管袋鼠本身不見得愿意那么做）。所以求最大值的過程就轉(zhuǎn)化成一個“袋鼠跳”的過程。下面介紹介紹“袋鼠跳”的幾種方式。