Algoritmos geneticos

Trabajo Final Algoritmos II
“Algoritmos Genéticos”
Resolución del problema de la mochila y del problema del viajante

Alumno: Vázquez, Hernán Ceferino Fecha de Entrega: 12/12/09 Cursada: 2007
1

ALGORITMOS GENETICOS

Introducción
Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el procesogenético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza, los mecanismos que conducen esta evolución no son totalmente conocidos, pero sí algunas de sus características, que son ampliamente aceptadas: -La evolución es un proceso que opera sobre los cromosomas más que sobre las estructuras de la vida que están codificadas en ellos. -La selecciónnatural es el enlace entre los cromosomas y la actuación de sus estructuras decodificadas. -El proceso de reproducción es el punto en el cual la evolución toma parte, actúa. -La evolución biológica no tiene memoria. (“Darwin C. (1859)”) Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones haciavalores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Los principios básicos de los Algoritmos Genéticos fueron establecidos por Holland (1975), y se encuentran bien descritos en varios textos { Goldberg (1989), Davis (1991), Michalewicz (1992),Reeves (1993) } . En la naturaleza los individuos de una población compiten entre si en la búsqueda de recursostales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero. Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de losindividuos mejor adaptados se propagaran en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes ancestros, puede a veces producir descendientes “súper individuos”, cuya adaptación es mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando unas características cada vez mejoradaptadas al entorno en el que viven. Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de unorganismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este 2

cruce producirá nuevos individuos {descendientes de los anteriores { los cuales comparten algunas de las características desus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones. De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayorproporción de buenas características en comparación con la población anterior. Así a lo largo de las generaciones las buenas características se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda. Si el Algoritmo genético ha sido bien diseñado, la población convergerá hacia una solución...