Implementación de programación genética

Question

Estoy familiarizado con las generalidades de la programación genética, pero me pregunto dónde podría encontrar algo que me muestre detalles sobre la implementación de la programación genética. Utilizo C# y .NET 3.5, y me gustaría utilizar la programación genética para cosas como PathFinding, y generalmente solo quiero ver qué puede hacer. Editar: probablemente debería aclarar lo que estoy buscando: estoy interesado en qué tipo de estructuras de datos se utilizarían para almacenar los árboles de sintaxis, cómo se podría realizar una operación de reproducción, ese tipo de cosas.

Answer 1

Aquí hay una rápida reescritura de uno de C ++ helloworld Ejemplos que me ayudaron a aprender programación genética:

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 + ")");
    }

Puede haber algunos errores menores, pero de lo contrario parece que está funcionando bien. También podría escribirse mejor en el espíritu de C#, pero esos son solo detalles. :)

Answer 2

El proyecto Mona Lisa de Roger Alsing es un buen ejemplo.http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Editar: La razón por la que me gusta el ejemplo es porque es bastante pequeño y fácil de entender. Es una forma rápida y fácil de comprender el concepto de programación genética.

Answer 3

Podrías mirar Supervivencia del más apto: selección natural con formas de ventanas.

Editar: ver esto antes de la pregunta, que acabo de encontrar. Es prácticamente un duplicado. Lo siento, no entiendes el enlace (es bueno mencionar esas cosas en la pregunta). Además, la otra pregunta aún está abierta para más respuestas/ediciones, a pesar de que se ha aceptado una respuesta.

Answer 4

Puede probar este puerto C# .NET 4.0 del ECJ de Sean Luke (Computación evolutiva en Java):

http://branecloud.codeplex.com

¡Es un software muy flexible y potente! Pero también es relativamente fácil comenzar porque incluye muchas muestras de consola de trabajo fuera de la caja (y muchas pruebas unitarias útiles que se desarrollaron durante la conversión).

Ben