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

.

(連載之八)

.

紮自<遊戲程式設計中的人工智能技術>第三章

 清華大學出版社

 3.4.3 參數值的選取

（Choosing the Parameter Value ）

。。你可能想了解我是如何知道需要采用這些變量初值？這可是價值百萬美元的問題，因至今尚未有快速有效的規則能确定這些值，有的隻是一些原則性的指導。而且，我已把程式用到的所有參數存放在檔案defines.h 中了。這些參數中大多數将是一目了然的，但有其中幾個我想說明一下，即  
       
       #define CROSSOVER_RATE 0.7   
       #define MUTATION_RATE  0.001   
       #define POP_SIZE       140   
       #define CHROMO_LENGTH  70   
       
。   選擇這些值最終還得歸結為每個人對遺傳算法所得到的“感覺”，你隻能通過自己的程式設計實踐、用各種不同的參數值進行調試、看結果會發生什麼，并從中選取适合的值。不同的問題需要不同的值，但是通常來說，如果你在使用二進制編碼的染色體，則把雜交率設定為O.7，變異率設為0.001，将是很好的初始預設值。而确定群體大小的一條有用規則是将基因組的數目取為染色體長度的２倍。   
	
。。因 70表示 Bob 的 35步的最大可能移動數目，是以這裡選擇70作為染色體的長度，它比 Bob 為穿越地圖到達出口所需的步數還要多一些。當你學習了以後幾章的方法後可以使遺傳算法變得更為有效，到時你就能将這個長度減少下來。 
        
曆史的注釋 
。。遺傳算法是 John Holland大腦的産物，早在上個世紀60年代，他已提出這種想法。但不可思議的是，他沒有感到需要在計算機上實際試驗出結果，而甯願利用筆和紙來作修修補補的工作！ 直到後來他的一名學生編寫出程式并在一台個人計算機上運作後，才使人們終于看到在軟體中利用他的思想能夠得到什麼。 
 
  
3.4.4 算子函數（The Operator Functions）
  
。。我們現在從頭到尾來考察一遍遺傳算法的各種操作(或稱算子)函數－選擇、雜交、變異－的代碼。盡管很簡單，但與你一起通讀一遍源碼能給你重溫一次這些函數的機會。這可使你在了解遺傳算法的知識時對它們具有更确切的認識。   


3.4.4.1重溫輪盤賭選擇
       (Roulette Whell Selection Revisited )
   
    讓我們從輪盤賭選擇算法開始。請記住，這一個函數的功能是從群體中選擇一個基因組，選中的幾率正比于基因組的适應性分數。   

 SGenome& CgaBob::RouletteWheelSelection()   
 {   
   double fSlice = RandFloat()*m_dTotalFitnessScore;   

。。我們從零到整個适應分範圍内随機選取了一實數fSlice 。我喜歡把此數看作整個适應性分數餅圖中的一塊，如早先在圖3.4中所示。 ［但并不是其中一塊，譯注］   

   double cfTotal = O;   
   int SelectedGenome = 0;   
   for (int i=O; i<m_iPopSize; ++i)   
     {   
      cfTotal += m_vecGenomes[i].dFitness;   
      if (cfTotal > fSlice)   
       {   
         SelectedGenome = i;   
         break;   
       }   
     }   
     return m_vecGenomes[SelectedGenome];   
  }   
。。現在，程式通過循環來考察各基因組，把它們相應的适應性分數一個一個累加起來，直到這一 部分累加和 大于 fSlice 值時，就傳回該基因組。就是這樣簡單。 

        
  3.4.4.2 重溫雜交操作（Crossover Revisited）

。。這一函數要求２個染色體在同一随機位置上斷裂開，然後将它們在斷開點以後的部分進行互換，以形成 2 個新的染色體 ( 子代 ) 。   

   void CgaBob::Crossover ( const vector<int>  	&mum,   
		   	const vector<int>  	&dad,   
   		   	vector<int> 		&baby1,   
  		   	vector<int> 		&baby2)   
    {   
       這一函數共傳入 4 個參數，參數傳遞均采用引用（ reference ）方式，其中前2 個傳入父輩parent 的染色體（别忘記 , 染色體隻是一個整數型的矢量std::vector ），後 2 個則是用來copy 子代染色體的空矢量。   
     if ( (RandFloat() > m_dCrossoverRate) || (mum == dad) )   
       {   
         baby1 = mum;   
         baby2 = dad;   
         return;   
       }   
   
。。這裡，首先是進行檢測，看 mum 和 dad 兩個上輩是否需要進行雜交。雜交發生的機率是由參數 m_dCrossoverRate 确定。如果不發生雜交，則２個上輩染色體不作任何改變地就直接複制為子代，函數立即傳回。   

   int cp = RandInt(0, m_iChromoLength - 1) ； 
        
。。沿染色體的長度随機選擇一個點來裂開染色體。        

  for (int i=0; i<cp; i++)   
     {   
       baby1.push_back(mum[i]);   
       baby2.push_back(dad[i]);   
     }   
       for (i=cp; i<mum.size(); i++)   
       {   
        baby1.push_back(dad[i]);   
        baby2.push_back(mum[i]); 

    這兩個小循環把 2 個 parent 染色體在雜交點（ CP,crossover point ）以後的所有位進行了互換，并把新的染色體賦給了 2 個子代 : baby1 和 baby2 。   

3.4.4.3 重溫變異操作（Mutation Revisited）  

。。這一函數所做的工作，不過就是沿着一個染色體的長度，一bit一bit地進行考察，并按m_dMutationRate給定的幾率，将其中某些bit實行翻轉。   

void CgaBob::Mutate(vector<int> &vecBits)   
 {   
   for (int curBit=0; curBit<vecBits.size(); curBit++)   
   {   
    //是否要翻轉此bit?   
    If (RandFloat() < m_dMutationRate)   
     (   
       //是，就翻轉此bit   
       vecBits[curBit] = !vecBits[curBit];   
     }   
   }//移到下一個bit   
 }   

。。就是這些了。你的第一遺傳算法程式也就這樣完成了！下面讓我花一些時間來說明一下，當你在運作 Pathfinder 程式時，你能看到些什麼？  
 
 
   
 
 
  －連載８完－