C# - Generischer Algorithmus

[rawsoul]

Hi zusammen,

ich möchte mich in die generischen Optimierungsverfahren einarbeiten, das Prinzip ist verstanden, aber mein Code tut nicht, was er soll

Ein Highfitnesskandidat überlebt nicht sehr lange. Maximal 3 bis 4 Generationen, dann war es das. Das optimale Ergebnis, der Zielkandidat also ist bekannt. Der Sinn geht flöten, aber es geht mir hier um das Prinzip des Algorithmus

Hier mal die drei Klassen:

(Gibts denn hier kein Spoilertag? Der Source macht den Post so lang )

Program:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Genetic_Algorithm;

namespace Genetic_Algorithm
{
    class Program
    {
        private void run()
        {
            Population popul = new Population("hello", 0.01f, 100);
            popul.CalculateFitness();
            int generation = 0;
            while (!popul.IsFinished())
            {
                popul.NaturalSelection();
                popul.NewGeneration();
                generation++;
                popul.CalculateFitness();
                if (generation % 100 == 0)
                {
                    Console.WriteLine(popul.GetBest());
                }
            }
            Console.Read();
        }

        static void Main(string[] args)
        {
            new Program().run();
        }
    }
}

Population:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Genetic_Algorithm;

namespace Genetic_Algorithm
{
    class Population
    {
        DNA[] popul;
        float[] fitness;
        String target;
        bool finished;
        List<DNA> selection;
        float mutationRate;
        System.Random rnd = new System.Random((int)System.DateTime.Now.Ticks);

        public Population(String phrase, float mutationRate, int maxPopulation)
        {
            popul = new DNA[maxPopulation];
            for (int i = 0; i < popul.Length; i++)
            {
                popul[i] = new DNA(phrase.Length);
            }
            target = phrase;
            this.mutationRate = mutationRate;
            selection = new List<DNA>();
            finished = false;
        }

        public bool IsFinished()
        {
            return finished;
        }

        public void CalculateFitness()
        {
            fitness = new float[popul.Length];
            for (int i = 0; i < fitness.Length; i++)
            {
                fitness[i] = popul[i].GetFitness(target );
            }
        }

        private float GetTotalFitness()
        {
            float total = 0f;
            for (int i = 0; i < popul.Length; i++)
            {
                total += fitness[i];
            }
            return total;
        }

        public void NaturalSelection()
        {
            selection.Clear();
            float totalFitness = GetTotalFitness();
            for (int i = 0; i < popul.Length; i++)
            {
                float normalFitness = fitness[i] / totalFitness;
                selection.Add(popul[i]);
                for (int j = 0; j < normalFitness * 10000f + 1; j++)
                {
                    selection.Add(popul[i]);
                }
            }
        }

        public void NewGeneration()
        {
            for (int i = 0; i < popul.Length; i++)
            {
                DNA mom = selection[rnd.Next(selection.Count)];
                DNA dad = selection[rnd.Next(selection.Count)];
                DNA child = mom.Crossover(dad);
                child.Mutate(mutationRate);
                popul[i] = child;
            }
        }

        public String GetBest()
        {
            int index = 0;
            float bestFitness = 0f;
            for (int i = 0; i < popul.Length; i++)
            {
                if (fitness[i] > bestFitness)
                {
                    index = i;
                    bestFitness = fitness[i];
                }
            }
            return popul[index].GetString() + " : " + fitness[index];
        }
    }
}

DNA:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Genetic_Algorithm;

namespace Genetic_Algorithm
{
    class DNA
    {
        char[] dna;
        System.Random rnd = new System.Random((int) System.DateTime.Now.Ticks);

        public DNA(int length)
        {
            dna = new char[length];
            for (int i = 0; i < dna.Length; i++)
            {
                dna[i] = (char)rnd.Next(32, 127);
            }
        }

        public DNA(DNA old)
        {
            dna = (char[])old.dna.Clone();
        }

        public float GetFitness(String target)
        {
            int score = 0;
            for (int i = 0; i < dna.Length; i++)
            {
                if (dna[i] == target[i])
                {
                    score++;
                }
            }
            return (float)score / (float)target.Length;
        }

        public DNA Crossover(DNA partner)
        {
            DNA child = new DNA(dna.Length);
            int mid = rnd.Next(dna.Length);
            for (int i = 0; i < mid; i++)
            {
                child.dna[i] = dna[i];
            }
            for (int i = mid; i < dna.Length; i++)
            {
                child.dna[i] = partner.dna[i];
            }
            return new DNA(child);
        }

        public void Mutate(float mutationRate)
        {
            for (int i = 0; i < dna.Length; i++)
            {
                if ((float)rnd.Next(10000) / 10000f < mutationRate)
                {
                    dna[i] = (char)rnd.Next(32, 127);
                }
            }
        }

        public String GetString()
        {
            return new String(dna);
        }
    }
}

Das variieren der mutationRate hilft da auch nicht weiter, ich vermute, dass der Crossover (Klasse DNA) nicht korrekt funktioniert. Leider habe ich die tatsächliche Ursache nicht gefunden.

Wenn jemand Zeit findet, mal drüberzuschauen und Ideen hierzulassen, würd' ich mich sehr freuen

LG,
Frank.