Algoritmos geneticos

ÍNDICE

INTRODUCCIÓN 3
JUSTIFICACIÓN 4
DESARROLLO HISTÓRICO 5
ALGORITMOS GENÉTICOS 6
1. DEFINICIÓN 6
2. ¿PORQUÉ UTILIZAR ALGORITMOS GENÉTICOS EN LA OPTIMIZACIÓN? 6
3. ESQUEMAS DE REPRESENTACIÓN 7
4. OPERADORES GENÉTICOS 8
4.1. SELECCIÓN 8
4.1.1. Selección por Ruleta 8
4.1.2. Selección por Torneo 8
4.2. CRUCE 9
4.2.1. Cruce de 1 punto 10
4.2.2. Cruce de 2 puntos 104.2.3. Cruce Uniforme 10
4.3. MUTACIÓN 11
5. FUNCIONAMIENTO DE UN ALGORTIMO GENÉTICO (AG) 11
6. FUNCIÓN DE APTITUD Y EVALUACIÓN 14
6.1. FUNCIÓN DE APTITUD 14
6.2. FUNCIÓN DE EVALUACIÓN 14
Fitness Puro: r(i,t) 14
Fitness Estandarizado: s(i,t) 15
Fitness Ajustado: a(i,t) 15
Fitness Normalizado: n(i,t) 15
7. APLICACIONES DE LOS ALGORITMOS GENÉTICOS 16
CONCLUSIONES 18RECOMENDACIONES 19
ANEXOS 20
BIBLIOGRAFÍA 27

INTRODUCCIÓN

El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad en todo el mundo durante los últimos años. Se presentarán aquí los conceptos básicos que se requieren para abordarla.

En los últimos años, la comunidad científica internacional ha mostrado un crecienteinterés en una nueva técnica de búsqueda basada en la teoría de la evolución y que se conoce como el algoritmo genético.

Esta técnica se basa en los mecanismos de selección que utiliza la naturaleza, de acuerdo a los cuales los individuos más aptos de una población son los que sobreviven, al adaptarse más fácilmente a los cambios que se producen en su entorno. Hoy en día se sabe que estoscambios se efectúan en los genes de un individuo (unidad básica de codificación de cada uno de los atributos de un ser vivo), y que sus atributos más deseables (los que le permiten adaptarse mejor a su entorno) se transmiten a sus descendientes cuando éste se reproduce sexualmente.

Un investigador de la Universidad de Michigan llamado John Holland era consciente de la importancia de la selecciónnatural, y a fines de los 60s desarrolló una técnica que permitió incorporarla a un programa. Su objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica que inventó Holland se le llamó originalmente "planes reproductivos", pero se hizo popular bajo el nombre "algoritmo genético" tras la publicación de su libro en 1975.

Para alcanzar la solución a un problema se parte deun conjunto inicial de individuos, llamado población, generado de manera aleatoria. Cada uno de estos individuos representa una posible solución al problema. Estos individuos evolucionarán tomando como base los esquemas propuestos por Darwin sobre la selección natural, y se adaptarán en mayor medida tras el paso de cada generación a la solución requerida.

JUSTIFICACIÓN

En la naturaleza losindividuos de una población compiten entre sí en la búsqueda de recursos tales 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 dotadosproducirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán 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 "superindividuos", cuya adaptación es mucho mayor que la de cualquiera de sus ancestros.

De estamanera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven.

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 cruce producirá nuevos individuos, descendientes de los...