輪盤賭算法詳細批注《遊戲程式設計中人工智能》

注：本文含有大量原著内容。本文目的僅在于對程式進行更詳細的批注或解釋，閱讀過該著作的可直接轉至标題<2>檢視詳細注釋。

    <1>原文介紹：

       輪盤賭選擇是從染色體群體中選擇一些成員的方法，被選中的機率和它們的适應性分數成比例，染色體的适應性分數愈高，被選中的機率也愈多。這不保證适應性分數最高的成員一定能選入下一代，僅僅說明它有最大的機率被選中。其工作過程是這樣的：

    設想群體全體成員的适當性分數由一張餅圖來代表 (見圖3.4)，這一餅圖就和用于賭博的轉輪形狀一樣。我們要為群體中每一染色體指定餅圖中一個小塊。塊的大小與染色體的适應性分數成比例，适應性分數愈高，它在餅圖中對應的小塊所占面積也愈大。為了選取一個染色體，你要做的，就是旋轉這個輪子，并把一個小球抛入其中，讓它翻來翻去地跳動，直到輪盤停止時，看小球停止在哪一塊上，就選中與它對應的那個染色體。

<2>輪盤賭算法詳解（原：指原文。注：本文作者批注。）

    原：讓我們從輪盤賭選擇算法開始。請記住，這一個函數的功能是從群體中選擇一個基因組，選中的幾率正比于基因組的适應性分數。

 SGenome& CgaBob::RouletteWheelSelection()//輪盤賭函數的建構

 { 

     double fSlice = RandFloat()*m_dTotalFitnessScore;//閥值的計算

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

     注：雙整型變量fSlice為某種意義上的閥值，一旦cfTotal大于該閥值(cfTotal > fSlice)，從某種角度可以了解為：作為賭徒玩家的你搖起的輪盤停止了！這時候小球停止在i區域(對應的基因組數組元素為m_vecGenomes[i]或m_vecGenomes[SelectedGenome])

    函數RandFloat()的原型為

    inline double RandFloat()   

    {

        return (rand())/(RAND_MAX+1.0);

    }

    另，源碼中有

        #define RAND_MAX 0x7fff

    這意味着rand()傳回的值将在0到2147483647之間産生，實際就是某個介于0-99.99%之間的百分比。至于m_dTotalFitnessScore,是每個基因組内各個基因适應分（請差別于下述“各個基因組适應分總和”這是兩個不同的概念）疊加的結果（适應分的計算步驟詳見源代碼，本文主要解釋輪盤賭思想，對其他不作過多解釋），可看做是整個輪盤的數值大小（如果你的思維能夠将輪盤數字化的話）。那麼double fSlice = RandFloat()*m_dTotalFitnessScore;這個式子就很好了解了。喜歡鑽牛角尖的童鞋可以根據源代碼實際計算一下，看是不是這樣的。

    我們可以将圓形的輪盤想象為一把長形的遊标卡尺，這把尺子又分為很多段（基因組的适應分區域，适應分越大，該基因組占有的區域越大），箭頭（即随機産生的閥值）在尺子的長度範圍内随機移動，很明顯便有了下述判斷：

    if (cfTotal > fSlice)

    { 

         SelectedGenome = i; 

         break; 

    }

原：

    double cfTotal = O; 

    int SelectedGenome = 0;

    for (int i=O; i<m_iPopSize; ++i)//m_iPopSize為群體大小，或者說基因組的數量

    {

//依次疊加各個基因組的适應分

        cfTotal += m_vecGenomes[i].dFitness;//m_vecGenomes[i]為第i個基因組，m_vecGenomes[i].dFitness為第i個基因組的适應分數。

//上一次未跳出循環說明适應分總和還未達到閥值，如果本次分數總和超過閥值，說明該閥值處于該基因組的區域内，可以形象了解為遊标卡尺的遊動指針滑動到了某個刻度區域塊内

if (cfTotal > fSlice)

        {

            SelectedGenome = i;

            break;

        }

    }

    return m_vecGenomes[SelectedGenome];

} 。。

    原：現在，程式通過循環來考察各基因組，把它們相應的适應性分數一個一個累加起來，直到這一部分累加和大于fSlice值時，就傳回該基因組。就是這樣簡單。

    總結：第一次看這個算法的時候并不是太懂，而且原著的程式怎麼也不符合我腦袋中想象的圓形輪盤跟跳動的小球，直到……我将那個輪盤線性化（就像求圓的面積一樣将圓沿中心向四周剖開再将圓周直線化，拉直）。就是這樣簡單，終于明白了原作者的話，恩，這個算法根據源代碼直譯過來的思想就是醬紫的，你懂了沒？