發(fā)布時間：2016-05-16 06:40

  本文關鍵詞：遺傳算法，由筆耕文化傳播整理發(fā)布。

         

         遺傳算法的有趣應用很多，諸如尋路問題，8數(shù)碼問題，囚犯困境，動作控制，找圓心問題（這是一個國外網友的建議：在一個不規(guī)則的多邊形 中，尋找一個包含在該多邊形內的最大圓圈的圓心。），TSP問題（在以后的章節(jié)里面將做詳細介紹。），生產調度問題，人工生命模擬等。直到最后看到一個非 常有趣的比喻，覺得由此引出的袋鼠跳問題（暫且這么叫它吧），既有趣直觀又直達遺傳算法的本質，確實非常適合作為初學者入門的例子。

               問題的提出與解決方案

           讓我們先來考慮考慮下面這個問題的解決辦法。

            已知一元函數(shù)：

                                                  

                

             現(xiàn)在要求在既定的區(qū)間內找出函數(shù)的最大值  

            

極大值、最大值、局部最優(yōu)解、全局最優(yōu)解

        在解決上面提出的問題之前我們有必要先澄清幾個以后將常常會碰到的概念：極 大值、最大值、局部最優(yōu)解、全局最優(yōu)解。學過高中數(shù)學的人都知道極大值在一個小鄰域里面左邊的函數(shù)值遞增，右邊的函數(shù)值遞減，在圖2.1里面的表現(xiàn)就是一 個“山峰”。當然，在圖上有很多個“山峰”，所以這個函數(shù)有很多個極大值。而對于一個函數(shù)來說，最大值就是在所有極大值當中，最大的那個。所以極大值具有局部性，而最大值則具有全局性。

        因為遺傳算法中每一條染色體，對應著遺傳算法的一個 解決方案，一般我們用適應性函數(shù)（fitness function）來衡量這個解決方案的優(yōu)劣。所以從一個基因組到其解的適應度形成一個映射。所以也可以把遺傳算法的過程看作是一個在多元函數(shù)里面求最優(yōu)解的過程。在這個多維曲面里面也有數(shù)不清的“山峰”，而這些最優(yōu)解所對應的就是局部最優(yōu)解。而其中也會有一個“山峰”的海拔最高的，那么這個就是全局最優(yōu) 解。而遺傳算法的任務就是盡量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遺傳算法不一定要找“最高的山峰”，如果問題的適應度評價越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對應的，遺傳算法所要找的就是“最深的谷底”）如果至今你還不太理解的話，那么你先往下看。本章的示例程序將會 非常形象的表現(xiàn)出這個情景。

        

“袋鼠跳”問題

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

爬山法、模擬退火和遺傳算法

解決尋找最大值問題的幾種常見的算法：

        1. 爬山法（最速上升爬山法）：

         從搜索空間中隨機產生鄰近的點，從中選擇對應解最優(yōu)的個體，替換原來的個體，不斷 重復上述過程。因為只對“鄰近”的點作比較，所以目光比較“短淺”，常常只能收斂到離開初始位置比較近的局部最優(yōu)解上面。對于存在很多局部最優(yōu)點的問題，通過一個簡單的迭代找出全局最優(yōu)解的機會非常渺茫。（在爬山法中，袋鼠最有希望到達最靠近它出發(fā)點的山頂，但不能保證該山頂是珠穆朗瑪峰，或者是一個非常 高的山峰。因為一路上它只顧上坡，沒有下坡。）

       2. 模擬退火：

        這個方法來自金屬熱加工過程的啟發(fā)。在金屬熱加工過程中，當金屬的溫度超過它的熔點（Melting Point）時，原子就會激烈地隨機運動。與所有的其它的物理系統(tǒng)相類似，原子的這種運動趨向于尋找其能量的極小狀態(tài)。在這個能量的變遷過程中，開始時。溫度非常高， 使得原子具有很高的能量。隨著溫度不斷降低，金屬逐漸冷卻，金屬中的原子的能量就越來越小，最后達到所有可能的最低點。利用模擬退火的時候，讓算法從較大的跳躍開始，使到它有足夠的“能量”逃離可能“路過”的局部最優(yōu)解而不至于限制在其中，當它停在全局最優(yōu)解附近的時候，逐漸的減小跳躍量，以便使其“落腳 ”到全局最優(yōu)解上。（在模擬退火中，袋鼠喝醉了，而且隨機地大跳躍了很長時間。運氣好的話，它從一個山峰跳過山谷，到了另外一個更高的山峰上。但最后，它漸漸清醒了并朝著它所在的峰頂跳去。）

       3. 遺傳算法：

        模擬物競天擇的生物進化過程，通過維護一個潛在解的群體執(zhí)行了多方向的搜索，并支持這些方向上的信息構成和交換。以面為單位的搜索，比以點為單位的搜索，更能發(fā)現(xiàn)全局最優(yōu)解。（在遺傳算法中，有很多袋鼠，它們降落到喜瑪拉雅山脈的任意地方。這些袋鼠并不知道它們的任務是尋找珠穆朗瑪峰。但每過幾年，就在一些海拔高度較低的地方射殺一些袋鼠，并希望存活下來的袋鼠是多產的，在它們所處的地方生兒育女。）（后來，一個叫天行健的網游給我想了一個更恰切的故事：從前，有一大群袋鼠，它們被莫名其妙的零散地遺棄于喜馬拉雅山脈。于是只好在那里艱苦的生活。海拔 低的地方彌漫著一種無色無味的毒氣，海拔越高毒氣越稀薄。可是可憐的袋鼠們對此全然不覺，還是習慣于活蹦亂跳。于是，不斷有袋鼠死于海拔較低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有機會生兒育女。就這樣經過許多年，這些袋鼠們竟然都不自覺地聚攏到了一個個的山峰上，可是在所有的袋鼠中，只有聚 攏到珠穆朗瑪峰的袋鼠被帶回了美麗的澳洲。）

        

下面主要介紹介紹遺傳算法實現(xiàn)的過程。

遺傳算法的實現(xiàn)過程

          遺傳算法的實現(xiàn)過程實際上就像自然界的進化過程那樣。首先尋找一種對問題潛在解進行“數(shù)字化”編碼的方案。（建立表現(xiàn)型和基因型的映射關系。）然后用隨機 數(shù)初始化一個種群（那么第一批袋鼠就被隨意地分散在山脈上。），種群里面的個體就是這些數(shù)字化的編碼。接下來，通過適當?shù)慕獯a過程之后，（得到袋鼠的位置 坐標。）用適應性函數(shù)對每一個基因個體作一次適應度評估。（袋鼠爬得越高，越是受我們的喜愛，所以適應度相應越高。）用選擇函數(shù)按照某種規(guī)定擇優(yōu)選 擇。（我們要每隔一段時間，在山上射殺一些所在海拔較低的袋鼠，以保證袋鼠總體數(shù)目持平。）讓個體基因交叉變異。（讓袋鼠隨機地跳一跳）然后產生子 代。（希望存活下來的袋鼠是多產的，并在那里生兒育女。）遺傳算法并不保證你能獲得問題的最優(yōu)解，但是使用遺傳算法的最大優(yōu)點在于你不必去了解和操心如何 去“找”最優(yōu)解。（你不必去指導袋鼠向那邊跳，跳多遠。）而只要簡單的“否定”一些表現(xiàn)不好的個體就行了。（把那些總是愛走下坡路的袋鼠射殺。）以后你會 慢慢理解這句話，這是遺傳算法的精粹！

        

        所以我們總結出遺傳算法的一般步驟：

        開始循環(huán)直至找到滿意的解。

1.評估每條染色體所對應個體的適應度。

2.遵照適應度越高，選擇概率越大的原則，從種群中選擇兩個個體作為父方和母方。

3.抽取父母雙方的染色體，進行交叉，產生子代。

4.對子代的染色體進行變異。

5.重復2，3，4步驟，直到新種群的產生。

結束循環(huán)。

接下來，我們將詳細地剖析遺傳算法過程的每一個細節(jié)。

        

編制袋鼠的染色體----基因的編碼方式

          通過前一章的學習，讀者已經了解到人類染色體的編碼符號集，由4種堿基的兩種配合組成。共有4種情況，相當于2 bit的信息量。這是人類基因的編碼方式，那么我們使用遺傳算法的時候編碼又該如何處理呢？

         受到人類染色體結構的啟發(fā)，我們可以設想一下，假設目前只有“0”，“1”兩種堿基，我們也用一條鏈條把他們有序的串連在一起，因為每一個單位都能表現(xiàn)出 1 bit的信息量，所以一條足夠長的染色體就能為我們勾勒出一個個體的所有特征。這就是二進制編碼法，染色體大致如下：

010010011011011110111110

        上面的編碼方式雖然簡單直觀，但明顯地，當個體特征比較復雜的時候，需要大量的編碼才能精確地描述，相應的解碼過程（類似于生物學中的DNA翻譯過程，就是把基因型映射到表現(xiàn)型的過程。）將過份繁復，為改善遺傳算法的計算復雜性、提高運算效率，提出了浮點數(shù)編碼。染色體大致如下：

1.2 – 3.3 – 2.0 –5.4 – 2.7 – 4.3

        那么我們如何利用這兩種編碼方式來為袋鼠的染色體編碼呢？因為編碼的目的是建立表現(xiàn)型到基因型的映射關系，而表現(xiàn)型一般就被理解為個體的特征。比如人的基因型是46條染色體所描述的（總長度 兩 米的紙條？），卻能解碼成一個個眼，耳，口，鼻等特征各不相同的活生生的人。所以我們要想為“袋鼠”的染色體編碼，我們必須先來考慮“袋鼠”的“個體特征”是什么。也許有的人會說，袋鼠的特征很多，比如性別，身長，體重，也許它喜歡吃什么也能算作其中一個特征。但具體在解決這個問題的情況下，我們應該進 一步思考：無論這只袋鼠是長短，肥瘦，只要它在低海拔就會被射殺，同時也沒有規(guī)定身長的袋鼠能跳得遠一些，身短的袋鼠跳得近一些。當然它愛吃什么就更不相關了。我們由始至終都只關心一件事情：袋鼠在哪里。因為只要我們知道袋鼠在那里，我們就能做兩件必須去做的事情：

（1）通過查閱喜瑪拉雅山脈的地圖來得知袋鼠所在的海拔高度（通過自變量求函數(shù)值。）以判斷我們有沒必要把它射殺。

（2）知道袋鼠跳一跳后去到哪個新位置。

         如 果我們一時無法準確的判斷哪些“個體特征”是必要的，哪些是非必要的，我們常常可以用到這樣一種思維方式：比如你認為袋鼠的愛吃什么東西非常必要，那么你就想一想，有兩只袋鼠，它們其它的個體特征完全同等的情況下，一只愛吃草，另外一只愛吃果。你會馬上發(fā)現(xiàn)，這不會對它們的命運有絲毫的影響，它們應該有同 等的概率被射殺！只因它們處于同一個地方。（值得一提的是，如果你的基因編碼設計中包含了袋鼠愛吃什么的信息，這其實不會影響到袋鼠的進化的過程，而那只攀到珠穆朗瑪峰的袋鼠吃什么也完全是隨機的，但是它所在的位置卻是非常確定的。）

        以上是對遺傳算法編碼過程中經常經歷的思維過程，必須把具體問題抽象成數(shù)學模型，突出主要矛盾，舍棄次要矛盾。只有這樣才能簡潔而有效的解決問題。希望初學者仔細琢磨。

        既然確定了袋鼠的位置作為個體特征，具體來說位置就 是橫坐標。那么接下來，我們就要建立表現(xiàn)型到基因型的映射關系。就是說如何用編碼來表現(xiàn)出袋鼠所在的橫坐標。由于橫坐標是一個實數(shù)，所以說透了我們就是要對這個實數(shù)編碼。回顧我們上面所介紹的兩種編碼方式，讀者最先想到的應該就是，對于二進制編碼方式來說，編碼會比較復雜，而對于浮點數(shù)編碼方式來說，則會 比較簡潔。恩，正如你所想的，用浮點數(shù)編碼，僅僅需要一個浮點數(shù)而已。而下面則介紹如何建立二進制編碼到一個實數(shù)的映射。

        明顯地，一定長度的二進制編碼序列，只能表示一定精度的浮點數(shù)。譬如我們要求解精確到六位小數(shù)，由于區(qū)間長度為2 – (-1) = 3 ,為了保證精度要求，至少把區(qū)間[-1,2]分為3 × 106等份。又因為

       

        所以編碼的二進制串至少需要22位。

        把一個二進制串（b0,b1,....bn)轉化位區(qū)間里面對應的實數(shù)值通過下面兩個步驟。

     （1）將一個二進制串代表的二進制數(shù)轉化為10進制數(shù)：

                

     （2）對應區(qū)間內的實數(shù)：

                         

      

       例如一個二進制串<1000101110110101000111>表示實數(shù)值0.637197。

          

        二進制串<0000000000000000000000>和<1111111111111111111111>則分別表示區(qū)間的兩個端點值-1和2。

        由于往下章節(jié)的示例程序幾乎都只用到浮點數(shù)編碼，所以這個“袋鼠跳”問題的解決方案也是采用浮點數(shù)編碼的。往下的程序示例（包括裝載基因的類，突變函數(shù)）都是針對浮點數(shù)編碼的。（對于二進制編碼這里只作簡單的介紹，不過這個“袋鼠跳”完全可以用二進制編碼來解決的，而且更有效一些。所以讀者可以自己嘗試用 二進制編碼來解決。）

         我們定義一個類作為袋鼠基因的載體。（細心的人會提 出這樣的疑問：為什么我用浮點數(shù)的容器來儲藏袋鼠的基因呢？袋鼠的基因不是只用一個浮點數(shù)來表示就行嗎？恩，沒錯，事實上對于這個實例，我們只需要用上一個浮點數(shù)就行了。我們這里用上容器是為了方便以后利用這些代碼處理那些編碼需要一串浮點數(shù)的問題。）

             

class Genome { public: friend class GenAlg; friend class GenEngine; Genome():fitness(0){} Genome(vector <double> vec, double f): vecGenome(vec), fitness(f){} //類的帶參數(shù)初始化參數(shù)。 private: vector <double> vecGenome; // 裝載基因的容器 double fitness; //適應度 };

       好了，目前為止我們把袋鼠的染色體給研究透了，讓我們繼續(xù)跟進袋鼠的進化旅程。   

物競天擇－－適應性評分與及選擇函數(shù)。

1.物競――適應度函數(shù)（fitness function）

        自然界生物競爭過程往往包含兩個方面：生物相互間的搏斗與及生物與客觀環(huán)境的搏斗過程。但在我們這個實例里面，你可以想象到，袋鼠相互之間是非常友好的，它們并不需要互相搏斗以爭取生存的權利。它們的生死存亡更多是取決于你的判斷。因為你要衡量哪只袋鼠該殺，哪只袋鼠不該殺，所以你必須制定一個衡量的標準。而對于這個問題，這個衡量的標準比較容易制定：袋鼠所在的海拔高度。（因為你單純地希望袋鼠爬得越高越好。）所以我們直接用袋鼠的海拔高度作為它們的適應性評分。即適應度函數(shù)直接返回函數(shù)值就行了。

2.天擇――選擇函數(shù)（selection）

        自然界中，越適應的個體就越有可能繁殖后代。但是也不能說適應度越高的就肯定后代越多，只能是從概率上來說更多。（畢竟有些所處海拔高度較低的袋鼠很幸運，逃過了你的眼睛。）那么我們怎么來建立這種概率關系呢？下面我們介紹一種常用的選擇方法――輪盤賭（Roulette Wheel Selection）選擇法。假設種群數(shù)目,某個個體其適應度為,則其被選中的概率為：

                                   

        比如我們有5條染色體，他們所對應的適應度評分分別為：5，7，10，13，15。

        所以累計總適應度為：

                                 

        所以各個個體被選中的概率分別為：

                  

            呵呵，有人會問為什么我們把它叫成輪盤賭選擇法啊？其實你只要看看圖2-2的輪盤就會明白了。這個輪盤是按照各個個體的適應度比例進行分塊的。你可以想象一下，我們轉動輪盤，輪盤停下來的時候，指針會隨機地指向某一個個體所代表的區(qū)域，那么非常幸運地，這個個體被選中了。（很明顯，適應度評分越高的個體被選中的概率越大。）

              

           那么接下來我們看看如何用代碼去實現(xiàn)輪盤賭。

Genome GenAlg:: GetChromoRoulette() { //產生一個0到人口總適應性評分總和之間的隨機數(shù). //中m_dTotalFitness記錄了整個種群的適應性分數(shù)總和) double Slice = (random()) * totalFitness; //這個基因將承載轉盤所選出來的那個個體. Genome TheChosenOne; //累計適應性分數(shù)的和. double FitnessSoFar = 0; //遍歷總人口里面的每一條染色體。 for (int i=0; i

  本文關鍵詞：遺傳算法，，由筆耕文化傳播整理發(fā)布。

本文編號：45543