遺傳算法的選擇機制

Question

我已經構建了一個遺傳算法，但是我覺得我的代碼的選擇/變異部分有些問題。這是我說的代碼的一部分：

#include "stdafx.h" 
#include <iostream> 
#include <vector> 
#include <random> 
#include <string> 
#include <iomanip> 
#include <math.h> 

// The random number generator I am using. 
std::random_device rd; 
std::mt19937 rng(rd()); 

for (int k = 1; k < population_size; k++)      // Loop until new population is filled up. K = 1 because first individual has the best genes from last generation. 
{ 
// Calculate total fitness. 

double totalfitness = 0; 

for (int i = 0; i < population_size; i++) 
{ 
    totalfitness += individuals[i].fitness; 
} 

// Calculate relative fitness. 

for (int i = 0; i < population_size; i++) 
{ 
    individuals[i].probability = individuals[i].fitness/totalfitness; 
} 

std::uniform_real_distribution<double> dist2(0.0, 1.0);  // Initiate random number generator to generate a double between 0 and 1. 

double rndNumber = dist2(rng);        // Generate first double 
double rndNumber2 = dist2(rng);        // Generate second double 
double offset = 0.0;          // Set offset (starting point from which it'll add up probabilities) at 0. 
int father = 0;            // father is the individual that is picked, initialize at 0. 
int mother = 0; 

// Pick first parent. Once picked, set the fitness for that individual at 0 so that it can not be picked again. 

for (int i = 0; i < population_size; i++) 
{ 
    offset += individuals[i].probability; 
    if (rndNumber < offset) 
    { 
     father = i; 
     individuals[i].fitness = 0.0; 
     break; 
    } 
} 

offset = 0.0;  // Reset offset to zero because we'll start again for the second parent. 
totalfitness = 0; // Recalculate total fitness using only the remaining individuals and reset total fitness to 0 

// Here we recalculate total fitness using only the fitness of the individuals remaining. 

for (int i = 0; i < population_size; i++) 
{ 
    totalfitness += individuals[i].fitness; 
} 

// Then we recalculate probability for the individuals based on the new totalfitness. 

for (int i = 0; i < population_size; i++) 
{ 
    individuals[i].probability = individuals[i].fitness/totalfitness; 
} 

// Then we give back the old fitness to the father/mother 

individuals[father].fitness = 1/(individuals[father].evaluation*individuals[father].evaluation); 

// Then pick parent 2. 

for (int i = 0; i < population_size; i++) 
{ 
    offset += individuals[i].probability; 
    if (rndNumber2 < offset) 
    { 
     mother = i; 
     break; 
    } 
} 

// Having picked father and mother, now the idea is to run a random number generator between 0 and 1 for each gene. 
// So if: father {5, 8, 9, 3} 
//   mother {1, 5, 2, 6) 
//   rndnum {0, 0, 1, 1} 
// then  child {5, 8, 2, 6} 

std::uniform_int_distribution<int> gene_selection(0, 1);  // Initiate random number generator to generate an integer between 0 and 1. 

for (int i = 0; i < number_of_variables; i++) 
{ 
    int gene1 = gene_selection(rng); 
    if (gene1 == 0) 
    { 
     new_individuals[k].chromosomes[0].push_back(individuals[father].chromosomes[0].at(i)); 
    } 
    else if (gene1 == 1) 
    { 
     new_individuals[k].chromosomes[0].push_back(individuals[mother].chromosomes[0].at(i)); 
    } 
} 

for (int j = 0; j < number_of_variables; j++) 
{ 
    for (int l = 0; l < 32; l++) 
    { 
     std::uniform_int_distribution<int> mutation(0, 50); 
     int mutation_outcome = mutation(rng); 
     if (mutation_outcome == 1) 
     { 
      new_individuals[k].chromosomes[0].at(j) ^= (1 << l); 
      if (new_individuals[k].chromosomes[0].at(j) == 0) 
      { 
       int new_var = uni(rng); 
       new_individuals[k].chromosomes[0].at(j) = new_var; 
      } 
     } 
    } 
} 
} 

// When all new individuals have values, give individuals values of new_individuals and start next round of evaluation. 

for (int i = 0; i < population_size; i++) 
{ 
individuals[i] = new_individuals[i]; 
} 

我的代碼大多數似乎工作正常。我似乎無法弄清楚的是爲什麼它表現得越來越差。前幾代人似乎經常找到新的更好的解決方案。幾代後，它停止尋找新的最佳解決方案。

這當然可能是因爲沒有更好的解決方案，但我也在同時在Excel中進行計算，並且個體通常可以通過將其「染色體」之一增加1來獲得更好的適應性，這通常是一個1位的變化，因爲我通常運行10000個人的代碼，你會說程序必然會創建一個具有這種變異的人。

我已經通過代碼很多次了調試器現在，顯示值的每一步的方式等，但我似乎無法找出它出錯的地方，所以我想我會發布我的代碼在這裏，看看有沒有人可以發現我搞砸了。

只是爲了記錄，算法只是一個公式求解器。所以我可以例如輸入a = 1，b = 6，target = 50，a * gene1 + b * gene2，它會（理論上）指定一個更高的適應度，一個人越接近這個結果。

另外，如果我不得不做，我已經搞砸了一個猜測，我會說這是在代碼中的突變部分：

for (int j = 0; j < number_of_variables; j++) 
{ 
    for (int l = 0; l < 32; l++) 
    { 
     std::uniform_int_distribution<int> mutation(0, 50); 
     int mutation_outcome = mutation(rng); 
     if (mutation_outcome == 1) 
     { 
      new_individuals[k].chromosomes[0].at(j) ^= (1 << l); 
      if (new_individuals[k].chromosomes[0].at(j) == 0) 
      { 
       int new_var = uni(rng); 
       new_individuals[k].chromosomes[0].at(j) = new_var; 
      } 
     } 
    } 
} 

我說這只是因爲這是我的一部分至少理解我自己，我可以非常想象我在那裏做了一個「隱形」的錯誤。

無論如何，任何幫助將不勝感激。

Answer 1

嗯，這只是讓你的代碼更好更高效的一種方法。您正在使用std::uniform_int_distribution沒有播種，並與幾乎連續5次通話，也許這就是爲什麼y our random number is not really random after all。

一個簡單的方法to get things better，將是seeding the random engine with time，因此從長遠來看允許更好的隨機數創建（10000個人，不知何故大！）。

這裏有一個link到一個更好的解釋和一個簡單的代碼片段，以測試如下：

#include <iostream> 
#include <random> 

std::default_random_engine generator((unsigned int)time(0)); 
int random(int n) { 
    std::uniform_int_distribution<int> distribution(0, n); 
    return distribution(generator); 
} 
int main() { 
     for(int i = 0; i < 15; ++i) 
       std::cout << random(5) << " " << random(5)<< std::endl; 
     return 0; 
} 

希望這將幫助！乾杯，