Algoritmo Genético C#

Iniciado por Andr0z, Abril 05, 2020, 02:06:23 PM

Tema anterior - Siguiente tema

0 Miembros y 1 Visitante están viendo este tema.

Abril 05, 2020, 02:06:23 PM Ultima modificación: Abril 05, 2020, 02:10:27 PM por Andr0z
Ejemplo básico de un algoritmo genético en C#

Nota: puedes experimentar variando la cantidad de individuos y tasa de mutación y ver como esta afecta a la convergencia y tiempo de solución

Código: csharp

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Al_genetico
{
    class Program
    {
        /*Idea original DanielShiffman, The nature of code*/
        public static string objetivo;
     
        static void Main(string[] args)
        {
            objetivo = "Hola Mundo :D";
            int numero_ind = 100; //Se puede experimentar con la variacion de numero de individuos y tasa de mutacion
            float tasa_mutacion = 0.02f;
            Poblacion poblacion = new Poblacion(tasa_mutacion,numero_ind,objetivo);
            while (true)
            {

                Console.WriteLine(" Generacion: " + poblacion.generacion + " | Mejor Individuo= " + poblacion.Mejor_individuo() + " | Promedio de aptitud por generación= " + poblacion.Promedio());
                poblacion.Seleccion();
                poblacion.Generacion();
                if (poblacion.Mejor_individuo() == objetivo) break;
                poblacion.Calcular_aptitud();

            }
            Console.ReadKey();

        }

        //Generador de numeros aleatorios enteros entre n1 y n2-1
        public static int random_entero(int n1,int n2)
        {
            Guid guid = Guid.NewGuid();
            string justNumbers = new String(guid.ToString().Where(Char.IsDigit).ToArray());
            int seed = int.Parse(justNumbers.Substring(0, 4));
            Random random= new Random(seed);
            return random.Next(n1, n2);   
        }

        //Generador de numeros aleatorios decimales entre  0 y 1
        public static double random_decimal()
        {
            Guid guid = Guid.NewGuid();
            string justNumbers = new String(guid.ToString().Where(Char.IsDigit).ToArray());
            int seed = int.Parse(justNumbers.Substring(0, 4));
            Random random = new Random(seed);
            return random.NextDouble();
        }
    }
}



Clase ADN.cs

Código: csharp

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Al_genetico
{
    class ADN
    {
        public char[] genes;
        public float aptitud;

        //Constructor clase ADN
        public ADN(int num)
        {
            genes = new char[num];
            for (int i = 0; i < genes.Length; i++) genes[i] = Convert.ToChar(Program.random_entero(32, 129));
        }

        //Convertimos nuestra cadena de caracteres a string
        public string ConseguirADN()
        {
            return new string(genes);
        }

        //Calculamos la aptitud comparando elemento a elemento el string del ADN con el objetivo
        public float Aptitud(string objetivo)
        {
            int puntos = 0;
            for (int i = 0; i < genes.Length; i++) if (genes[i] == objetivo[i]) puntos++;
            aptitud = (float)puntos / (float)objetivo.Length;
            return aptitud;
        }

        //Se mezcla la la informacion entre dos ADN  para crear un hijo
        public ADN Reproduccion(ADN padre)
        {
            int punto_cruce = Program.random_entero(0, genes.Length);
            ADN hijo = new ADN(genes.Length);
            for (int i=0;i<genes.Length;i++)
            {
                if (i < punto_cruce) hijo.genes[i] = genes[i];
                else hijo.genes[i] = padre.genes[i];
            }
            return hijo;
        }

        //Se muta(modifica) el elemento del ADN si el numero obtenido aleatoriamente es menor que la tasa de mutacion
        public void Mutacion(float tasa_mutacion)
        {
            for (int i = 0;i< genes.Length; i++) if (Program.random_decimal() < tasa_mutacion) genes[i] = Convert.ToChar(Program.random_entero(32,129));
        }

    }
}


Clase Poblacion.cs

Código: csharp

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Al_genetico
{
    class Poblacion
    {
        public int generacion=1;
        public ADN[] poblacion;
        List<ADN> contenedor;
        float tasa_mutacion;
        string objetivo;

        //Constructor de la población
        public Poblacion(float tm, int num,string objetivo)
        {
            this.objetivo = objetivo;
            tasa_mutacion = tm;
            poblacion = new ADN[num];
            for (int i = 0; i < poblacion.Length; i++)  poblacion[i] = new ADN(objetivo.Length);
            contenedor = new List<ADN>();
            Calcular_aptitud();
        }

        //Se calcula la aptitud de cada uno de los individuos de la poblacion. La mayor aptitud es de 1
        public void Calcular_aptitud()
        {
            for (int i = 0; i < poblacion.Length; i++) poblacion[i].Aptitud(objetivo);
        }

        //Se le asigna al contenedor cuantas veces sea un individuo en proporcion a su aptitud. Mayor aptitud, mayor veces estara ese individuo en nuestro contenedor
        public void Seleccion()
        {
            float val_Max = 0;
            contenedor.Clear();
            for (int i = 0; i < poblacion.Length; i++) if (poblacion[i].aptitud > val_Max)  val_Max = poblacion[i].aptitud;
            for (int i = 0; i < poblacion.Length; i++)
            {
                float map_aptitud = Map(poblacion[i].aptitud, 0, val_Max, 0, 1);
                int numero = (int)(map_aptitud)*100;
                for (int j = 0; j < numero; j++) contenedor.Add(poblacion[i]);
            }     
        }

        /*Se selecciona al azar individuos de nuestro contenedor para realizar su cruza, obtener el hijo
        y remplazar la antigua generacion con los nuevos hijos*/

        public void Generacion()
        {
            for(int i=0;i<poblacion.Length;i++)
            {
                int A = Program.random_entero(0, contenedor.Count - 1);
                int B = Program.random_entero(0, contenedor.Count - 1);
                ADN madre = contenedor[A];
                ADN padre = contenedor[B];
                ADN hijo = madre.Reproduccion(padre);
                hijo.Mutacion(tasa_mutacion);
                poblacion[i] = hijo;
            }
            generacion++;
        }

        //Se selecciona el mejor individuo de la generacion para retornar su string
        public string Mejor_individuo()
        {
            float val_Max = 0;
            int indice = 0;
            for (int i = 0; i < poblacion.Length; i++)
            {
                if (poblacion[i].aptitud > val_Max)
                {
                    val_Max = poblacion[i].aptitud;
                    indice = i;
                }
            }
            return new string(poblacion[indice].genes);
        }

        // Se calcula el promedio de aptitud por generacion
        public float Promedio()
        {
            float promedio = 0;
            for (int i = 0; i < poblacion.Length; i++)  promedio += poblacion[i].aptitud;
            return (float)promedio / (poblacion.Length);
        }

        //Método de mapeo
        float Map(float val, float x1, float x2, float y1, float y2)
        {
            return ((val - x1) / (x2 - x1)) * (y2 - y1) + y1;
        }
    }
}





Gracias por el aporte !

Podrias comentar un poco mas sobre este tipo de algoritmos ? Para que se usa, cual es su finalidad.




Con la fuerza del mar, con la paz del rio


Hola Bartz!!, por nada hermano.
La información vendrá en la edición próxima a salir, es complementario a la revista  ;)

Excelente !




Con la fuerza del mar, con la paz del rio