如何在遺傳算法中爲未分類的種羣組織輪盤選擇？

Question

我的問題與此鏈接： Roulette-wheel selection in Genetic algorithm. Population needs to be sorted first? 如果我們不對人口進行排序，組織輪盤選擇的方式是什麼？ 當然，我們現在必須以線性方式進行搜索。在這種情況下，你有C++或Java中的任何代碼片段嗎？

Answer 1

人口根本不需要分類 - 輪盤選擇的關鍵在於選擇一個給定的個體進行繁殖的概率與其適應度成正比。

假設你有一個未排序的人口，適應度如下：

[12, 45, 76, 32, 54, 21] 

要執行輪盤賭選擇，你只需要挑選在0〜240（佔總人口的健身之和）範圍內的隨機數。然後，從列表中的第一個元素開始，減去每個個體的適應度，直到隨機數小於或等於零。因此，在上述情況下，如果我們隨機挑選112，我們執行以下操作：

Step 1: 112 - 12 = 100. This is > 0, so continue. 
Step 2: 100 - 45 = 55. This is > 0, so continue. 
Step 3: 55 - 76 = -21. This is <= 0, so stop. 

因此，我們選擇單個＃3的再現。請注意，這並不需要羣體進行排序。

所以，在僞代碼，把它歸結爲：

let s = sum of population fitness 
let r = random number in range [0, s]. 
let i = 0. 
while r > 0 do: 
    r = r - fitness of individual #i 
    increment i 
select individual #i - 1 for reproduction. 

注意，在最後一行的- 1是來抵消這就是循環的最後一次迭代中完成的（因爲即使我們的increment i找到我們想要的個人，無論增加）。