健身比例「輪盤」選擇的高效實現

我目前正在編寫一個C語言的鍵盤佈局優化算法（例如Peter Klausler設計的算法），我想實現如此處所述的適合度選擇（PDF Link）：健身比例「輪盤」選擇的高效實現

隨着輪盤賭選擇您選擇一個基於 roullete輪模型的人口成員。製作一個餡餅圖表，其中成員切片到整個圓的面積是成員適度與總人口的比率。正如你所看到的，圓圈的圓周上的點是隨機挑選的那些那些具有較高適合度的成員將被挑選的概率較高。這確保自然選擇需要的地方。

問題是，我沒有看到如何有效地實現它。我想到了兩種方法：一種是不可靠的，另一種是緩慢的。

首先，緩慢之一：

對於長度爲N的鍵盤池，創建長度的數組N，其中該陣列的每個元素實際上包含兩個元素，最小和最大值。每個鍵盤都有相應的最小值和最大值，範圍取決於鍵盤的適應性。例如，如果鍵盤零有10健身，鍵盤一個具有20健身，和鍵盤二包含的25健身，它是這樣的：代碼：

array[0][0] = 0; // minimum 
array[0][1] = 9; // maximum 
array[1][0] = 10; 
array[1][1] = 30; 
array[2][0] = 31; 
array[2][1] = 55;

（在這種情況下，因爲它意味着更少的努力是必需的。）

然後生成一個隨機數。無論數字落入哪個範圍，相應的鍵盤都會被「殺死」，並被另一個鍵盤的後代取代。根據需要多次重複此操作。

問題在於它非常緩慢。完成O（N^2）操作。

下一頁快1：

首先弄清楚什麼對鍵盤的最低和最高的適應度是。然後在（最低健身）和（最高健身）之間生成一個隨機數，並殺死所有鍵盤的適應度高於生成的數字。這是有效的，但不能保證只殺死一半的鍵盤。它也有一些與「輪盤」選擇不同的機制，所以它甚至可能不適用。

所以問題是，什麼是有效的實現？

本書第36頁有一些有效的算法（Link），但問題是，只有在輪盤賭選擇只有一次或幾次時纔有效。有沒有什麼有效的方法可以同時做很多輪盤賭選擇？

來源

2009-08-14 Michael Dickens

請將代碼塊重新格式化爲代碼，並修復您的Google圖書鏈接。 – 2009-08-14 06:32:23

一方面，它聽起來就像你正在談論不適宜分數，如果你想「扼殺」您的選擇（這很可能是與高得分鍵盤）。我看到不需要維護兩個數組。我認爲，最簡單的方法是保持分數的單一陣列，然後您可以遍歷做出選擇：

/* These will need to be populated at the outset */ 
int scores[100]; 
int totalScore; 

for (gen = 0; gen < nGenerations; ++gen) { 
    /* Perform a selection and update */ 
    int r = rand() % totalScore;  /* HACK: using % introduces bias */ 
    int t = 0; 
    for (i = 0; i < 100; ++i) { 
     t += scores[i]; 
     if (r < t) { 
      /* Bingo! */ 
      totalScore -= scores[i]; 
      keyboards[i] = generate_new_keyboard_somehow(); 
      scores[i] = score_keyboard(keyboards[i]); 
      totalScore += scores[i]; /* Now totalScore is correct again */ 
     } 
    } 
}

每個選擇/更新需要O（n）的時間n個鍵盤。

來源

2009-08-14 06:50:15

健身比例「輪盤」選擇的高效實現

回答

相關問題