遺伝的アルゴリズムの選択メカニズム

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]; 
} 

私のコードはほとんど問題なく動作しているようです。私が理解できないように見えるのは、それがますます悪化する理由です。最初の数世代では、新しい、より良い解決策を見つけることが多いようです。数世代後、新しい最高のソリューションを見つけるのを止めます。

これはもちろん解決策がないからかもしれませんが、私も同時に優れた計算をしています。個人は、その「染色体」の1つを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; 
      } 
     } 
    } 
} 

私は、これは一部Iであるという理由だけでこれを言います少なくとも私自身を理解していて、私はそこに「目に見えない」エラーを作り出したと想像することができました。

とにかく、どんな助けでも大歓迎です。

Answer 1

これはコードをより効率的にする方法です。 std::uniform_int_distributionをシードなしで使用していて、ほぼ5回の連続した呼び出しで、おそらくy our random number is not really random after allの理由があります。

簡単な方法の1つであるto get things betterは、seeding the random engine with timeとなり、長期的にはより良い乱数生成が可能になります。

ここ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; 
} 

役立つことを願っています！乾杯、