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 :angel2:)

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.

[Reinhard Kern]

Zitat:

Zitat von rawsoul

Hi zusammen,

ich möchte mich in die generischen Optimierungsverfahren einarbeiten, ...

Hallo,

nein, nicht wirklich - drum heisst dein Algorithmus ja auch "genetisch".

Das ist sehr irreführend, ich habe den Post nur gelesen, weil ich wissen wollte, was zum Teufel eine generischer Algorithmus sein soll. Bitte MOD oder Poster: Titel ändern.

Gruss Reinhard

[ULIK]

Hallo,

ich hab deinen Code zwar nicht am Laufen gehabt, aber nur so vom Durchsehen ein paar Ideen:

• In deinem Crossover kann es passieren, daß das komplette Genom eines Partners durch den des anderen ersetzt wird. Ich würde hier ehe mal mit etwas arbeiten das sicherstellt, daß immer von beiden Eltern Anteile vorhanden sind.
• Du sorgst ja für das Bevorzugen von fitteren Nachkommen dadurch, daß Du in NaturalSelection von fitteren Teilen der Population mehr Nachkommen für die neue Selektion erzeugst, also die Wahrscheinlichkeit höher ist, daß in die neue Population mehr fittere Nachkommen aufgenommen werden. Schau doch mal, ob denn das auch wirklich in einem signifikanten Maße der Fall ist!

Grüße,
Uli