Algoritmos Genéticos: un ejemplo simple

Como hay una demanda bastante importante del ejemplo en C de un algoritmo genético he decidido ponerlo aquí a disposición de quien quiera verlo en lugar de enviarlo por correo individualmente. El ejemplo es la resolución de una práctica de la asignatura “Modelos Computacionales” que cursé en la Universidad de Córdoba hace dos o tres años. Como es una práctica, no creo que esté exenta de fallos, pero el funcionamiento es correcto aunque también simple.

Os recomiendo leer el enunciado aunque el código está comentado y es fácil de entender. Se trata de la minimización de la famosa función de Sphere. Sin más dilaciones os dejo el enunciado y el código:

#define POBLACION 11
#define LONG_COD 20
#define LIMITE -5.12
#define PROB_CRUCE 0.3
#define PROB_MUTACION 0.001
#define INTERVALO 10.24/pow(2,LONG_COD/2)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
	int genotipo[LONG_COD];
	double aptitud;
} Individuo;

void decoder (double *, double *, int *);
double fitness (double, double);
int generarBinario (void);
Individuo generarIndividuo (void);
Individuo * generarPoblacion (void);
Individuo * seleccionTorneos(Individuo * pob);
void mutacionHijos (Individuo *);
void cruzarSeleccion (Individuo *);
Individuo elite(Individuo *);
void AG();
void imprimePoblacion (Individuo *);
void imprimeGenotipo(Individuo);
void generarGraficoGeneracional(void);

int main() {

	srand(time(NULL));
	AG();
	return 0;
}

/* PROC decoder (double *x, double *y, int *genotipo)						DEV (double)
 * MODIFICA (double *x double *y)
 * EFECTO recibe un vector de enteros compuesto de 0 y 1 que representa dos numeros
 * 	codificados en binario. se encarga de convertir estos dos numeros binarios a su
 * 	equivalente en decimal con ayuda de la macro PRECISION (incremento del valor entre
 * 	cada binario) y la macro LIMITE que es el valor del limite inferior de la repre-
 * 	sentacion que en el problema es -5.12	*/

void decoder (double * x, double * y, int * genotipo)
{
	int i;
	*x = *y = 0.0;

	// calculo del primer decimal
	for(i=0; i<LONG_COD/2; i++)
		*x += genotipo[i] * pow(2, (LONG_COD/2)-(i+1));
	*x = (*x) * INTERVALO + LIMITE;

	//calculo del segundo decimal
	for(;i<LONG_COD;i++)
		*y += genotipo[i] * pow(2, LONG_COD-(i+1));
	*y = (*y) * INTERVALO + LIMITE;
}

/* PROC fitness (double p1, double p2)					DEV (double)
 * MODIFICA nada
 * EFECTO recibe dos valores que representan los puntos que caracterizan a un individuo
 * 	la funcion sirve para calcular la aptitud o fitness de cierto individuo segun sus
 * 	puntos. este valor de aptitud es el que devuelve la funcion. */

double fitness (double p1, double p2)
{
	return pow(p1,2) + pow(p2,2);
}

/* PROC generarBinario (void)								DEV (void)
 * MODIFICA nada
 * EFECTO se encarga de devolver un valor entero que siempre sera cero o uno. lo vamos a
 * 	utilizar para generar los individuos al principio dado que su genoma es una cadena
 * 	binaria que se genera aleatoriamente	*/

int generarBinario (void) {
	if (1 + (int) (10.0*rand()/(RAND_MAX+1.0)) > 5)
		return 1;
	else
		return 0;
}

/* PROC generarIndividuo (void)							DEV (Individuo)
 * MODIFICA nada
 * EFECTO se encarga de generar un individuo utilizando valores aleatorios. primero crea
 * 	la cadena de bits del genotipo utilizando la funcion generaBinario y luego evalua
 * 	la aptitud del individuo utilizando la funcion decoder para decodificar el genotipo
 * 	y la funcion fitness para obtener la aptitud.	*/

Individuo generarIndividuo (void){
	Individuo ind;
	int i;
	double x, y;

	for (i=0; i<LONG_COD; i++)
		ind.genotipo[i]=generarBinario();

	decoder(&x, &y, ind.genotipo);
	ind.aptitud = fitness(x,y);

	return ind;
}

/* PROC generarPoblacion (void)							DEV (Individuo *)
 * MODIFICA nada
 * EFECTO esta funcion genera una poblacion con la cantidad de individuos dada por la
 * 	macro POBLACION. para generar cada individuo utiliza la funcion generarIndividuo()
 * 	y una vez ha terminado el bucle, devuelve el puntero al primer individuo	*/

Individuo * generarPoblacion(void)
{
	Individuo * poblacion;
	int i;

	poblacion = (Individuo *) malloc(sizeof(Individuo)*POBLACION);
	for(i=0;i<POBLACION;i++)
		poblacion[i] = generarIndividuo();

	return poblacion;
}

/* PROC seleccionTorneos (Individuo *)					DEV (Individuo *)
 * MODIFICA nada
 * EFECTO se crea un nuevo vector de individuos que contendra a los individuos seleccionados
 * 	para el cruce. la seleccion se hace por torneos por tanto cada individuo seleccionado
 * 	sera el que tenga mejor aptitud de dos candidatos. el proceso se repite en POBLACION-1
 * 	iteraciones, que es la cantidad de individuos que se deben seleccionar. la reserva de
 * 	memoria se hace sobre POBLACION individuos dado que, como luego vamos a seleccionar el
 * 	mejor de la poblacion anterior por elitismo, debemos dejar una plaza de la siguiente
 * 	generacion libre. la seleccion es con repeticion */

Individuo * seleccionTorneos (Individuo * poblacion)
{
	Individuo candidato_a, candidato_b;
	int i;

	Individuo * seleccion = (Individuo *) malloc (sizeof(Individuo)*POBLACION);

	for (i=0; i<POBLACION-1; i++)
	{
		candidato_a = poblacion[(int) (((double) POBLACION)*rand()/(RAND_MAX+1.0))];
		candidato_b = poblacion[(int) (((double) POBLACION)*rand()/(RAND_MAX+1.0))];

		if (candidato_a.aptitud < candidato_b.aptitud)
			seleccion[i] = candidato_a;
		else
			seleccion[i] = candidato_b;
	}

	return seleccion;
}

/* PROC mutacionHijos (Individuo *)							DEV (void)
 * MODIFICA (Individuo *)
 * EFECTO esta funcion aplica la mutacion segun la probabilidad dada por PROB_MUTACION.
 * 	recibe un vector de individuos en el que debe ocurrir que los dos primeros sean
 * 	los hijos correspondientes a un cruce. el genotipo de cada uno de los individuos
 * 	se recorre por completo calculando la probabilidad de que el bit mute y cambiando
 * 	si se diera el caso positivo	*/

void mutacionHijos (Individuo * hijos)
{
	int i, j;

	for(i=0; i<2; i++)
		for(j=0; j<LONG_COD; j++)
			if ((double) rand()/(RAND_MAX+1.0) < PROB_MUTACION)
			{
				if(hijos[i].genotipo[j])
					hijos[i].genotipo[j] = 0;
				else hijos[i].genotipo[j] = 1;
			}
}

/* PROC cruzarSeleccion (Individuo *)					DEV (void)
 * MODIFICA (Individuo *)
 * EFECTO esta funcion se encarga de cruzar los individuos seleccionados. la seleccion
 * 	esta ordenada luego cruzamos los individuos seguidos de dos en dos. para cada una
 * 	de las iteraciones se aplica la probabilidad de cruce. en caso de que se crucen
 * 	los individuos se genera un punto de cruce y se intercambian las porciones del
 * 	vector. luego se llama a la funcion de mutacion. en caso de que no haya cruce, los
 * 	padres pasan directamente a la siguiente generacion	*/

void cruzarSeleccion (Individuo * seleccion)
{
	int i, j, punto, aux;
	double x, y;

	for(i=0; i<POBLACION-1; i+=2)
	{
		if((double) rand()/(RAND_MAX+1.0) < PROB_CRUCE)
		{
			punto = (int) (((double) LONG_COD)*rand()/(RAND_MAX+1.0));

			for(j=punto; j<LONG_COD; j++)
			{
				aux=seleccion[i].genotipo[j];
				seleccion[i].genotipo[j]=seleccion[i+1].genotipo[j];
				seleccion[i+1].genotipo[j]=aux;
			}

			mutacionHijos(&seleccion[i]);

			decoder(&x, &y, seleccion[i].genotipo);
			seleccion[i].aptitud = fitness(x,y);

			decoder(&x, &y, seleccion[i+1].genotipo);
			seleccion[i+1].aptitud = fitness(x,y);
		}
	}
}

/* PROC elite (Individuo * poblacion)					DEV (Individuo)
 * MODIFICA nada
 * EFECTO se trata de una funcion que devuelve el mejor individuo de una poblacion
 * 	que se pasa como argumento. utiliza un individuo como comparador y devuelve
 * 	el que para nuestro caso tiene el mejor fitness, es decir, aptitud mas baja */

Individuo elite (Individuo * poblacion)
{
	int i;
	Individuo best = poblacion[0];

	for(i=0; i<POBLACION; i++)
		if(best.aptitud > poblacion[i].aptitud)
			best = poblacion[i];

	return best;
}

/* PROC AG(void)												DEV (void)
 * MODIFICA nada
 * EFECTO se trata de la funcion que ejecuta el algoritmo. el proceso es el siguiente
 * 	1 - Generar la poblacion
 * 	2 - Seleccion de candidatos al cruce
 * 	3 - Cruce de los candidatos (incluye mutacion)
 * 	4 - Incluir al mejor de la generacion anterior en la nueva
 * 	5 - Repetir el proceso	*/

void AG (void)
{
	Individuo * seleccion, * poblacion = generarPoblacion();
	Individuo best;
	int generacion = 0;
	double x, y;

	do
	{
		seleccion = seleccionTorneos(poblacion);
		cruzarSeleccion(seleccion);
		seleccion[POBLACION-1] = elite(poblacion);
		free(poblacion);
		poblacion = seleccion;
		generacion++;
	} while (elite(poblacion).aptitud > pow(10,-2));

	best = elite(poblacion);
	free(poblacion);
	decoder(&x, &y, best.genotipo);

	printf ("*************************************\n");
	printf ("*          FIN DEL ALGORITMO        *\n");
	printf ("*************************************\n");
	printf (" - En el punto (%.5f, %.5f)\n", x, y);
	printf (" - Su fenotipo es %.5f\n", best.aptitud);
	printf (" - Es la generacion numero %i\n", generacion);
	printf ("*************************************\n");
}

/* PROC imprimePoblacion (Individuo * pob)						DEV (void)
 * MODIFICA nada
 * EFECTO 	es una funcion auxiliar que imprime por pantalla toda la informacion
 * 	relativa a una poblacion que se debe pasar como argumento. recorre con un
 * 	bucle for todos los individuos para imprimirlos uno a uno y se ayuda de la
 * 	funcion decoder para sacar la aptitud	*/

void imprimePoblacion (Individuo * pob)
{
	int i;
	double x, y;

	for(i=0;i<POBLACION;i++)
	{
		decoder(&x, &y, pob[i].genotipo);
		printf ("INDIVIDUO NUMERO %i \t", i+1);
		printf ("(%f,", x);
		printf (" %f)", y);
		printf ("\tAptitud = %.20f\n", pob[i].aptitud);
	}
}

/* PROC imprimeGenotipo (Individuo x)							DEV (void)
 * MODIFICA nada
 * EFECTO esta funcion se encarga de imprimir por pantalla el genotipo asociado a
 * 	un individuo que se pasa como argumento. recorre el genotipo por medio de
 * 	un bucle for y no necesita funciones auxiliares	*/

void imprimeGenotipo (Individuo x)
{
	int i;

	for(i=0; i<LONG_COD; i++)
		printf ("%i  ", x.genotipo[i]);
	printf ("\n");
}

/* PROC imprimeGenotipo (Individuo x)							DEV (void)
 * MODIFICA nada
 * EFECTO esta funcion la utilizamos para generar los ficheros de puntos que se
 * 	utilizan en GNUPLOT para dibujar las graficas. se trata de una serie de
 * 	ejecuciones del algoritmo similar a como se hace en la funcion AG(), solo
 * 	que en este caso se imprime en un fichero, anadiendo informacion al final
 * 	con un formato especifico de generacion-aptitud, ademas se utiliza una
 * 	variable media para calcular la aptitud media de cada 10 generaciones	*/

void generarGraficoGeneracional()
{
	FILE *f;
	int generacion, j;
	double media;
	Individuo *seleccion, *poblacion = generarPoblacion();

	f=fopen("Puntos.dat", "at");
	fprintf (f, "\n0 %.40f\n", elite(poblacion).aptitud);
	for(generacion=1; generacion<2000;)
	{
		media = 0;
		for(j=0; j<10; j++, generacion++)
		{
			seleccion = seleccionTorneos(poblacion);
			cruzarSeleccion(seleccion);
			seleccion[POBLACION-1] = elite(poblacion);
			media += elite(poblacion).aptitud;
			free(poblacion);
			poblacion = seleccion;
		}
		media /= j;
		fprintf (f, "%i %.40f\n", generacion, media);
	}

	fprintf (f, "\n\n");
	fclose(f);
}

Saludos !

Anuncios

6 pensamientos en “Algoritmos Genéticos: un ejemplo simple

  1. Pingback: Algoritmos Genéticos (AGs) « just 4 cool !

  2. Hola.. gracias por poner el ejemplo tengo ciertas dudas lo primero estoy programando uno que me maximice una funcion con una sola variable (x), mi problema esta en la representacion de los Cromosomas (Genotipo) ya que tengo que hacerlo en Excel VBA, por fa explicame que es lo que hace la Macro Precisioin y Limite, puesto que tengo q representar numeros en un rango de (-10 – 10) y pues la longitud de la cadena binaria debe ser la misma en todos los casos.

  3. Hola he estado mirando tu blog y me parece excelente quisiera que me ayudaras. estoy haciendo mi tesis de grado de asignaciond e personasl con algoritmos geneticos, estoy un poco confundida no se como programar el algoritmo, estoy manejando etiquetas linguisticas mediante un sitema difuso.
    si tiene salguna idea por fa ayudame….
    escribeme a mi mail enyilin3251@hotmail.com

  4. Hola estuve leyendo tu blog y necesito resolver este ejercicio que te pongo a continuación con un algoritmo genético, si me puedes ayudar preferentemente en java.
    Explorando Marte
    Un explorador en Marte tiene que recoger ejemplos de rocas de 3 lugares
    diferentes en cualquier orden y volver a la nave.
    Asuma que tiene un modulo de navegación que hace que el explorador vaya desde cualquier lugar de interés a cualquier otro lugar de interés, que tiene las acciones primitivas ir-nave, ir-roca1, ir-roca2 e ir-roca3.
    Se conoce el tiempo que demora ir de un lugar a otro entre los 4 lugares de interés.
    Nuestro objetivo es encontrar una secuencia de acciones que realicen esta tarea en el mínimo tiempo posible.

  5. Muy bueno, esto de los algoritmos evolutivos en interesante para la optimizacion de respuestas, el problema es que si se tiene un sistema mas complejo la respuesta va a demorar mas tiempo. En cambio un algoritmo basado en estimación de distribuciones se pueden usar para el procesamiento de respuestas complejas en un tiempo relativamente corto.

  6. Hola, muy buenas tardes! espero que se encuentren bien.. Quisiera saber como implementar en ese mismo código dos ejemplos mas sobre otras posibles mutaciones para generar otros resultados optimizados, quisiera que me ayudaran porque ando un poco perdido sobre este tema de algoritmos geneticos

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s