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
(https://i.imgur.com/LnNqhxT.jpg)
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
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
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.
Hola Bartz!!, por nada hermano.
La información vendrá en la edición próxima a salir, es complementario a la revista ;)
Excelente !