BACHILLER


Algoritmos Genéticos
Inteligencia Artificial





Ingeniería Cibernética y en Sistemas Computacionales
8° Semestre

Hernández Reyes Lidy
López Suárez Ricardo
Mendiola Illescas Rosa María
Valdez Moreno Israel




12 de Mayo de 2011



Índice
Índice 2
Objetivos 3
Definiciones y conceptos básicos del tema 3
Estructura 5
Tipos de Representación 5
Tamaño de la población5
Población Inicial 5
Función Objetivo 5
Operador de Selección 5
Operador de Cruce 6
Operador de Mutación 6
Ventajas 6
Desventajas 6
¿Cuándo usar algoritmos genéticos? 7
Antecedentes y desarrollo históricos. 7
Fundamentos biológicos. 7
Estado del arte 8
Áreas de aplicación y clases 8
Desarrollos actuales en el mundo y en México. 9
Caso Práctico 10
Bibliografía consultada 12Cuestionario 13


Objetivos

Explicar el concepto de Algoritmo Genético, así como todos los aspectos que lo rodean.
Mostrar un ejemplo práctico para mejor comprensión del tema.

Definiciones y conceptos básicos del tema

El Algoritmo Genético (AG) es un modelo de aprendizaje que debe su comportamiento a una metáfora de algunos de los mecanismos de la evolución que se observan en lanaturaleza (como la reproducción sexual y el principio de la supervivencia del más apto), son métodos adaptativos, generalmente usados en problemas de búsqueda y optimización de parámetros.
Siguiendo la definición dada por Goldberg en 1989:

“Los Algoritmos Genéticos son algoritmos de búsqueda basados en la mecánica de la selección natural y de la genética natural. Combinan la supervivencia del másapto entre estructuras de secuencias con intercambio de información estructurado, aunque aleatorizado, para constituir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas”.

A grandes rasgos, un algoritmo genético consiste en una población de soluciones codificadas de forma similar a cromosomas. Cada uno de estos cromosomas tendrá asociado un ajuste o valor debondad que cuantifica su validez como solución del problema. En función de este valor se le darán más o menos oportunidades de reproducción. Además, con cierta probabilidad se realizarán mutaciones de estos cromosomas.
El poder de los AG proviene del hecho de que se trata de una técnica robusta, y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendoaquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el AG encuentre la solución óptima del problema, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de algoritmos de optimización combinatoria.
Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen serdifíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente. Estos algoritmos se relacionan frecuentemente con problemas NP.
En el caso de que existan técnicas especializadas para resolver un determinado problema, lomás probable es que superen al AG, tanto en rapidez como en eficacia. El gran campo de aplicación de los AG se relaciona con aquellos problemas para los cuales no existen técnicas especializadas. Incluso en el caso en que dichas técnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridándolas con los AG.

Cuando el AG es implementado, se hace de forma que involucre elsiguiente ciclo:

1. Generación de una población inicial de manera aleatoria.
2. Evaluar el desempeño de todos los individuos de la población, tomando en cuenta alguna función objetivo.
3. Crear una nueva población mediante la ejecución de operaciones como el crossover y mutación sobre individuos cuyo desempeño haya sido evaluado.
4. Descartar la población vieja e iterar usando la nueva,...