Roulette Wheel Selection

輪盤賭選擇： Roulette Wheel Selection

輪盤賭選擇又稱比例選擇運算元。

基本介紹

• 中文名：輪盤賭選擇
• 外文名：Roulette Wheel Selection
• 別名：比例選擇運算元
• 補充：工作過程

基本思想

個體被選中的機率與其適應度函式值成正比。

設群體大小為n，個體i的適應度為Fi，則個體i被選中遺傳到下一代群體的機率為：

工作過程

構想群體全部個體的適當性分數由一張餅圖來代表 (見圖)。

群體中每一染色體指定餅圖中一個小塊。塊的大小與染色體的適應性分數成比例，適應性分數愈高，它在餅圖中對應的小塊所占面積也愈大。為了選取一個染色體，要做的就是旋轉這個輪子，直到輪盤停止時，看指針停止在哪一塊上，就選中與它對應的那個染色體。

舉例：

若產生隨機數為0.81，則6號個體被選中。

理論缺點

如果有1000個個體，每個個體適應度為i，每個個體進入交配池的機率如下圖：

如果有1000個個體，每個個體適應度為（i+1)^3，每個個體進入交配池的機率如下圖：

結論：選擇個體的機率與目標函式的形狀有很大關係，這是需要避免的。

如果有1000個個體，對於前999個體適應度為0.0001i，最後一個個體適應度為1，每個個體進入交配池的機率如下圖：

如果有1000個個體，對於前999個體適應度為1+0.0001i，最後一個個體適應度為2，每個個體進入交配池的機率如下圖：

結論：選擇個體的機率與目標函式的偏移有很大關係，這是需要避免的。

Roulette Wheel Selection缺點，健壯性比較差，有以下兩點：

1. 選擇個體的機率與目標函式的形狀有很大關係，這是需要避免的。

2. 選擇個體的機率與目標函式的偏移有很大關係，這是需要避免的。

代碼實現

int RouletteWheelSelection()

{

//每次選擇一個個體，返回個體在數組中的下標

double fSlice = RandomDouble() * m_dTotalFitnessScore;

double cfTotal = 0.0; //機率統計

int SelectedGenomePos = 0; //被選中的個體下標

int i;

for (i = 0; i < POP_SIZE; ++i)

{

cfTotal += m_vecGenomes[i].dFitness;

if (cfTotal > fSlice)

{

SelectedGenomePos = i;

break;

}

}