Auswahlmechanismus für genetischen Algorithmus

Question

Ich habe einen genetischen Algorithmus erstellt, aber ich habe das Gefühl, dass etwas falsch in der Auswahl/Mutation Teil meines Codes ist. Dies ist der Teil des Codes, über den ich spreche:

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

Mein Code scheint meistens in Ordnung zu sein. Was ich nicht herausfinden kann ist, warum es immer schlechter läuft. In den ersten paar Generationen scheint es oft neue, bessere Lösungen zu geben. Nach einigen Generationen hört es auf, neue, beste Lösungen zu finden.

Dies könnte natürlich sein, weil es keine bessere Lösung gibt, aber ich mache auch die Berechnungen in Excel zur gleichen Zeit und eine Person kann oft bessere Fitness nur durch die Erhöhung eines seiner "Chromosomen" um 1, Das wäre normalerweise eine 1-Bit-Änderung, und da ich diesen Code normalerweise mit 10000 Personen führe, würde man sagen, dass das Programm dazu verpflichtet ist, eine Person mit dieser Mutation zu erstellen.

Ich habe meinen Code viele Male mit dem Debugger jetzt durchgegangen, Werte bei jedem Schritt des Weges usw. zeigend, aber ich kann nicht scheinen, herauszufinden, wo es falsch geht, also dachte ich, dass ich posten würde mein Code hier und sehen, ob jemand könnte herausfinden, wo ich vermasseln.

Nur für den Rekord ist der Algorithmus einfach ein Formellöser. So kann ich zum Beispiel a = 1, b = 6, target = 50, a * gen1 + b * gene2 eingeben und es würde (theoretisch) eine höhere Fitness zuweisen, je näher ein Individuum an diesem Ergebnis wäre.

Auch, wenn ich eine Vermutung machen, wo ich verwirrt habe oben, würde ich sagen, es ist in der Mutation Teil des Codes:

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

sage ich einfach, weil dies der Teil I verstehe mich am wenigsten und ich könnte mir sehr gut vorstellen, dass ich dort einen "unsichtbaren" Fehler gemacht habe.

Wie auch immer, jede Hilfe würde sehr geschätzt werden.

Answer 1

Nun, dies ist nur ein Weg, um Ihren Code besser und effizienter zu bekommen. Sie verwenden std::uniform_int_distribution ohne Seeding, und mit fast 5 aufeinander folgenden Anrufe, vielleicht deshalb y our random number is not really random after all.

Ein einfacher Weg to get things better, wäre seeding the random engine with time, so dass auf lange Sicht eine bessere Zufallszahl Schöpfung (10000 Personen, irgendwie groß!).

Hier ist ein link zu einer besseren Erklärung, dass und einem einfachen Code-Schnipsel folgendes zu testen:

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

Hoffnung, dass hilft! Prost,