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 y poco más. Siconoces 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 comprendidos entre 0 y 31. Aúnmá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 posibles soluciones (posible valoresde 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 = 0y 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. Para este ejemplo ilustrativo vamos aescoger 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 primerindividuo. 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 144 2 (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 columna (5) indica la pareja asignada a cada individuo, lo cual se ha realizado...