Genetische Programmierung Implementierung

Question

Ich bin vertraut mit den allgemeinen genetischen Programmierung, aber ich frage mich, wo ich etwas finden könnte, die mir Details der Umsetzung genetischer Programmierung zeigt. Ich benutze C# und .NET 3.5, und ich möchte genetische Programmierung für Dinge wie Wegfindung verwenden, und im Allgemeinen will nur sehen, was es tun kann. EDIT: Ich sollte wahrscheinlich klarstellen, wonach ich suche: Ich bin daran interessiert, welche Art von Datenstrukturen verwendet werden würden, um die Syntaxbäume zu speichern, wie eine Zuchtoperation ausgeführt werden könnte, so etwas.

Answer 1

Hier ist eine schnelle Umschreiben eines C++ HelloWorld Beispiele, die mir die genetische Programmierung lernen geholfen:

using ga_vector = List<ga_struct>; 

class ga_struct 
{ 
    public ga_struct(string str, uint fitness) 
    { 
     Str = str; 
     Fitness = fitness; 
    } 

    public string Str { get; set; } 
    public uint Fitness { get; set; } 
} 

class Program 
{ 

    private const int GA_POPSIZE = 2048; 
    private const int GA_MAXITER = 16384; 
    private const float GA_ELITRATE = 0.10f; 
    private const float GA_MUTATIONRATE = 0.25f; 
    private const float GA_MUTATION = 32767 * GA_MUTATIONRATE; 
    private const string GA_TARGET = "Hello world!"; 

    private static readonly Random random = new Random((int)DateTime.Now.Ticks); 

    static void Main(string[] args) 
    { 
     ga_vector popAlpha = new ga_vector(); 
     ga_vector popBeta = new ga_vector(); 

     InitPopulation(ref popAlpha, ref popBeta); 
     ga_vector population = popAlpha; 
     ga_vector buffer = popBeta; 

     for (int i = 0; i < GA_MAXITER; i++) 
     { 
      CalcFitness(ref population); 
      SortByFitness(ref population); 
      PrintBest(ref population); 

      if (population[0].Fitness == 0) break; 

      Mate(ref population, ref buffer); 
      Swap(ref population, ref buffer); 
     } 

     Console.ReadKey(); 
    } 

    static void Swap(ref ga_vector population, ref ga_vector buffer) 
    { 
     var temp = population; 
     population = buffer; 
     buffer = temp; 
    } 

    static void InitPopulation(ref ga_vector population, ref ga_vector buffer) 
    { 
     int tsize = GA_TARGET.Length; 
     for (int i = 0; i < GA_POPSIZE; i++) 
     { 
      var citizen = new ga_struct(string.Empty, 0); 

      for (int j = 0; j < tsize; j++) 
      { 
       citizen.Str += Convert.ToChar(random.Next(90) + 32); 
      } 

      population.Add(citizen); 
      buffer.Add(new ga_struct(string.Empty, 0)); 
     } 
    } 

    static void CalcFitness(ref ga_vector population) 
    { 
     const string target = GA_TARGET; 
     int tsize = target.Length; 

     for (int i = 0; i < GA_POPSIZE; i++) 
     { 
      uint fitness = 0; 
      for (int j = 0; j < tsize; j++) 
      { 
       fitness += (uint) Math.Abs(population[i].Str[j] - target[j]); 
      } 

      population[i].Fitness = fitness; 
     } 
    } 

    static int FitnessSort(ga_struct x, ga_struct y) 
    { 
     return x.Fitness.CompareTo(y.Fitness); 
    } 

    static void SortByFitness(ref ga_vector population) 
    { 
     population.Sort((x, y) => FitnessSort(x, y)); 
    } 

    static void Elitism(ref ga_vector population, ref ga_vector buffer, int esize) 
    { 
     for (int i = 0; i < esize; i++) 
     { 
      buffer[i].Str = population[i].Str; 
      buffer[i].Fitness = population[i].Fitness; 
     } 
    } 

    static void Mutate(ref ga_struct member) 
    { 
     int tsize = GA_TARGET.Length; 
     int ipos = random.Next(tsize); 
     int delta = random.Next(90) + 32; 

     var mutated = member.Str.ToCharArray(); 
     Convert.ToChar((member.Str[ipos] + delta)%123).ToString().CopyTo(0, mutated, ipos, 1); 
     member.Str = mutated.ToString(); 
    } 

    static void Mate(ref ga_vector population, ref ga_vector buffer) 
    { 
     const int esize = (int) (GA_POPSIZE*GA_ELITRATE); 
     int tsize = GA_TARGET.Length, spos, i1, i2; 

     Elitism(ref population, ref buffer, esize); 

     for (int i = esize; i < GA_POPSIZE; i++) 
     { 
      i1 = random.Next(GA_POPSIZE/2); 
      i2 = random.Next(GA_POPSIZE/2); 
      spos = random.Next(tsize); 

      buffer[i].Str = population[i1].Str.Substring(0, spos) + population[i2].Str.Substring(spos, tsize - spos); 

      if (random.Next() < GA_MUTATION) 
      { 
       var mutated = buffer[i]; 
       Mutate(ref mutated); 
       buffer[i] = mutated; 
      } 
     } 
    } 

    static void PrintBest(ref ga_vector gav) 
    { 
     Console.WriteLine("Best: " + gav[0].Str + " (" + gav[0].Fitness + ")"); 
    } 

Es könnte einige kleinere Fehler, aber sonst sieht es aus, es funktioniert ok. Auch könnte es besser im Geiste von C# geschrieben werden, aber das sind nur Details. :)

Answer 2

Sie könnten Survival of the Fittest: Natural Selection with Windows Forms betrachten.

EDIT: Siehe previous SO question, die ich gerade gefunden habe. Es ist so ziemlich ein Duplikat. Entschuldigung, dass Sie den Link nicht verstehen (es ist gut, solche Dinge in der Frage zu erwähnen). Auch die andere Frage ist offen für weitere Antworten/Bearbeitungen, obwohl eine Antwort akzeptiert wurde.

Answer 3

Roger Alsings Mona Lisa Projekt ist ein ziemlich gutes Beispiel. http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

EDIT: Der Grund, warum ich das Beispiel mag, ist, weil es eher klein und einfach zu verstehen ist. Es ist eine schnelle und einfache Möglichkeit, das Konzept der genetischen Programmierung zu verstehen.

Answer 4

Sie können diese C# versuchen, .NET 4.0-Port von Sean Luke des EuGH (Evolutionary Computation in Java):

http://branecloud.codeplex.com

Es ist sehr flexible und leistungsfähige Software! Aber es ist auch relativ einfach, um loszulegen, da es viele Arbeitskonsolen-Samples von Anfang an enthält (und viele hilfreiche Komponententests, die während der Konvertierung entwickelt wurden).

Ben