Algoritmos Geneticos

ALGORITMOS GENÉTICOS
Autor: Miguel Ángel Muñoz Pérez.
Primera versión: Noviembre, 1997.
Última modificación: Abril, 2005.

ADVERTENCIA
Si ya sabes lo que es un algoritmo genético y esperas hallar algo novedoso en esta
página, me temo que aquí no lo vas a encontrar. Este documento no es de investigación,
sino de divulgación y es “free”. En este caso acepto gustoso todas tus críticas ysugerencias.
Si no te interesan las matemáticas, no creo que sea de interés lo que aquí se cuenta.
Entonces, ¿a quién le puede interesar? Si no has oído hablar de un algoritmo genético,
pero te gustan los números o si ya sabes que existen pero no conoces cómo funcionan,
te invito a que sigas leyendo.
No es preciso que seas un mago con los números. Basta con que sepas el concepto de
función ypoco más. Si conoces la representación de números en forma binaria, pues
mejor, y si no, yo te la explico.

FUNCIONAMIENTO DE UN ALGORITMO GENETICO
Vamos a partir de una función f(x) muy sencilla:
f(x) =x2
(es decir, x al cuadrado).
Imagina que deseas encontrar el valor de x que hace que la función f(x)
alcance su valor máximo, pero restringiendo a la variable x a tomar valores
comprendidosentre 0 y 31. Aún más, a x sólo le vamos a permitir tomar valores
enteros, es decir: 0,1, 2, 3,..., 30, 31. Obviamente el máximo se tiene para x =
31, donde f vale 961. No necesitamos saber algoritmos genéticos para resolver
este problema, pero su sencillez hace que el algoritmo sea más fácil de
comprender.
Lo primero que debemos hacer es encontrar una manera de codificar las
posiblessoluciones (posible valores de x). Una manera de hacerlo es con la
codificación binaria. Con esta codificación un posible valor de x es

(0, 1, 0, 1, 1).

¿Cómo se interpreta esto? Muy sencillo: multiplica la última componente (un 1)
por 1, la penúltima (un 1) por 2, la anterior (un 0) por 4, la segunda (un 1) por 8
y la primera (un 0) por 16 y a continuación haz la suma: 11. Observa que (0, 0,0, 0, 0) equivale a x = 0 y que (1, 1, 1, 1, 1) equivale a x = 31.
A cada posible valor de la variable x en representación binaria le vamos a
llamar individuo. Una colección de individuos constituye lo que se denomina
población y el número de individuos que la componen es el tamaño de la
población.
Una vez que tenemos codificada la solución, debemos escoger un tamaño de
población. Paraeste ejemplo ilustrativo vamos a escoger 6 individuos.
Debemos partir de una población inicial. Una manera de generarla es
aleatoriamente: coge una moneda y lánzala al aire; si sale cara, la primera
componente del primer individuo es un 0 y en caso contrario un 1. Repite el
lanzamiento de la moneda y tendremos la segunda componente del primer
individuo (un 0 si sale cara y un 1 si sale cruz).Así hasta 5 veces y obtendrás
el primer individuo. Repite ahora la secuencia anterior para generar los
individuos de la población restantes. En total tienes que lanzar 5 * 6 = 30 veces
la moneda.
Nuestro siguiente paso es hacer competir a los individuos entre sí. Este
proceso se conoce como selección. La tabla 1 resume el proceso.

Tabla 1.- SELECCION
(1)
(2)
(3) (4)
1
(0,1,1,0,0) 12 1442
(1,0,0,1,0) 18 324
3
(0,1,1,1,1) 15 225
4
(1,1,0,0,0) 24 576
5
(1,1,0,1,0) 26 676
6
(0,0,0,0,1) 1
1

(5)
6
3
2
5
4
1

Cada fila en la tabla 1 está asociada a un individuo de la población inicial. El
significado de cada columna de la tabla es el siguiente:
(1) = Número que le asignamos al individuo.
(2) = Individuo en codificación binaria.
(3) = Valor de x.

(4) =Valor de f(x).

Observa que el mejor individuo es el 5 con f = 676. Calcula la media de f y
obtendrás fmed =324.3.
En cuanto a la columna (5) ahora te lo explico. Una manera de realizar el
proceso de selección es mediante un torneo entre dos. A cada individuo de la
población se le asigna una pareja y entre ellos se establece un torneo: el mejor
genera dos copias y el peor se desecha. La...