Aplicacion algoritmos geneticos

TALLER “EJEMPLO APLICACIÓN ALGORITMOS GENETICOS”

AUTOR:
MARCELO HERNANDO TAPASCO PULGARIN
COD. 10142196

UNIVERSIDAD TECNOLOGICA DE PEREIRA
FACULTAD DE CIENCIAS BASICAS
INGENIERIA DE SISTEMAS Y COMPUTACION
PEREIRA
2010
ALGORITMO GENETICO PARA HALLAR EL MINIMO DE f(x)=x2

Primero hay que encontrar el valor de x que hace que la función f(x) alcance su valor máximo, perorestringiendo a la variable x a tomar valores comprendidos entre 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 unamanera de codificar las posibles soluciones(posibles 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.Para este 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 sí sale cara y un 1 sí salecruz). 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) | (5) |
1 |(0,1,1,0,0) | 12 | 144 | 6 |
2 | (1,0,0,1,0) | 18 | 324 | 3 |
3 | (0,1,1,1,1) | 15 | 225 | 2 |
4 | (1,1,0,0,0) | 24 | 576 | 5 |
5 | (1,1,0,1,0) | 26 | 676 | 4 |
6 | (0,0,0,0,1) | 1 | 1 | 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 mejorgenera dos copias y el peor se desecha. La columna (5) indica la pareja asignada a cada individuo, lo cual se ha realizado aleatoriamente. Existen muchas variantes de este proceso de selección, aunque este método nos vale para ilustrar el ejemplo.
Después de realizar el proceso de selección, la población que tenemos es la mostrada en la columna (2) de la tabla 2. Observa, por ejemplo, que en eltorneo entre el individuo 1 y el 6 de la población inicial, el primero de ellos ha recibido dos copias, mientras que el segundo cae en el olvido.
Tabla 2.- CRUCE
(1) | (2) | (3) | (4) |
1 | (0,1,1,0,0) | 5 | 1 |
2 | (0,1,1,0,0) | 3 | 3 |
3 | (1,0,0,1,0) | 2 | 3 |
4 | (1,0,0,1,0) | 6 | 1 |
5 | (1,1,0,1,0) | 1 | 1 |
6 | (1,1,0,1,0) | 4 | 1 |

Tras realizar la selección, se realiza...