遺傳算法入門(連載之七)

(連載之七)

.

紮自<遊戲程式設計中的人工智能技術>第三章 .  清華大學出版社 .

3.4.2 Epoch （時代）

遺傳算法類中最燴靈人口的内容就是 Epoch()方法。這就是我們前面3.3節講過的遺傳算法的那個循環。它是這個類的工作部門（workhorse）。這一方法與所有工作或多或少都有連系。下面就讓我們來更近距離地考察它 ... 
 
 void CgaBob::epoch()  
 {  
   UpdateFitnessScores();  

    在每一個 epoch 循環内所要做的第一件事情，就是測試染色體群中每一個成員的适應性分數。 UpdateFitnessScores() 是用來對每個基因組的二進制染色體編碼進行譯碼的函數，而由它再把譯碼所得到的一系列結果，也就是由代表東、南、西、北四個方向的整數，發送給 CBobsMap::TestRoute 。後者檢查Bob在地圖中遊走了多遠，并根據Bob離開出口的最終距離，傳回一個相應的适應性分數。讓我通過很少幾行源碼來告訴你怎樣計算Bob的适應性分數: 
  
   int DiffX = abs(posX - m_iEndX);  
   int DiffY = abs(posY - m_iEndY); 
      
    這裡，DiffX和DiffY 就是Bob所在格子相對于迷宮出口的水準和垂直偏離值。試考察圖 3.6 的例子。灰色小格代表Bob通過迷宮的路程，上面寫着B的小格是他最終所到達的地方。在這一位置上，Diffx = 3，而 DiffY = 0。      

return 1/(double)(DiffX+DiffY+1); 
    
    上面一行程式就是計算Bob的适應性分數，它把DiffX，DiffY這兩個數字加起來，然後求倒數。DiffX，DiffY的和中還加了一個1，這是為了避免分母出現0的錯誤。如果Bob到達出口，DiffX+DiffY=0.
    UpdateFitnessScores 也保持對每一代适應性分數最高的基因組以及所有與基因組相關的适應性分數的跟蹤。這些數值在執行賭輪選擇要使用。      

圖 3.6 Bob嘗試尋找迷宮出口

      這最後一行式子就是計算 Bob 的适應性分數。它把 DiffX與DiffY 兩個數字加起來然後求倒數。DiffX與DiffY的和數中還加了一個１，這是為了確定除法不會出現一個分母為零的錯誤，如果 Bob到達出口，Diffx + DiffY = 0。

     UpdateFitnessScores 也保持對每一代裡适應分最高的基因組、以及與所有基因組相關的适應性分數的跟蹤。這些數值在執行輪盤賭選擇時需要使用。到此，你已經知道了函數 UpdateFitnessScores() 所做的全部工作，讓我們回到 Epoch 函數的讨論 ...

     由于在每一個Epoch中都需要建立一個新的基因組群，是以，當它們在建立出來時(每次２個基因組)，我們需要尋找一些地方來儲存它們。

   //現在建立一個新的群體

   int NewBabies = 0;   

  //為嬰兒基因組建立存儲器  

   vector<SGenome> vecBabyGenomes;

現在繼續讨論遺傳算法循環中所處理的各種事務。

   while (NewBabies < m_iPopSize)    

   {

    //用輪盤賭法選擇 2 個上輩（parents）

     SGenome mum = RouletteWheelSelection();   

     SGenome dad = RouletteWheelSelection();

    在每次疊代過程中，我們需要選擇 2 個基因組來作為 2 個新生嬰兒的染色體的上輩。我今後常喜歡把這２個上輩分别稱為 dad （父親）和 mum （母親）因為他們将來就是要生孩子的）。你應該回憶得起來，一個基因組的适應性愈強，則由輪盤賭方法選擇作為父母的幾率也愈大。

   //雜交操作    

     SGenome baby1, baby2; 

     Crossover(mum.vecBits ,dad.vecBits, baby1.vecBits, baby2.vecBits);

    以上２行的工作是：建立 2 個空白基因組，這就是２個嬰兒；它們與所選的上輩一起傳遞給雜交函數Crossover() 。這一函數執行了雜交（需要依賴于所設雜交率m_dCrossoverRate來進行），并把新的染色體的２進制位串存放到２個新生嬰兒 baby1和baby2之中。

   // 變異操作  

    Mutate(baby1.vecBits);  

    Mutate(baby2.vecBits);

    以上這 2 步是對嬰兒實行突變！這聽起來可怕，但這對他們是有利的。一個嬰兒的位的突變機率依賴于所選的參數 m_dMutationRate（突變率）。

   // 把２個新生因個嬰兒加入新群體 

    vecBabyGenomes.push_back(baby1); 

    vecBabyGenomes.push_back(baby2); 

    NewBabies += 2; 

  }

    這 2 個新生後代最終要加入到新的群體中，這樣就完成了一次 Loop 的疊代過程。這一過程需要不斷重複，直到建立出來的後代總量和初始群體的大小相同。

   // 把所有嬰兒複制到初始群體 

    m_vecGenomes = vecBabyGenomes; 

   // 代的計數加１ 

   ++m_iGeneration; 

 }

    這裡，原有的那個群體由新生一代所組成的群體來代替，并把代的計數器加１，以跟蹤目前的代。就是這麼一些了！呵呵，不難吧？

    這一 Epoch函數将無止境地重複，直到染色體收斂到了一個解，或到使用者要求停止時為止。下面我将會向你顯示上述各種操作（算子）的代碼，但在此首先讓我們來聊聊，應該如何确定使用的參數值。

－連載７完－