Introducción a la Computación Evolutiva

Introducción a la Computación Evolutiva

En este curso se estudiarán los conceptos básicos de las técnicas más importantes de computación evolutiva, haciendo especial énfasis en los algoritmos genéticos. Comenzaremos con una breve motivación respecto al uso de las heurísticas y con un repaso de sus características. Luego comenzaremos a hablar de la computación evolutiva en particular. Iniciaremos con un recorrido histórico en el que se resumirán los logros más importantes en torno a la simulación de los procesos evolutivos como una herramienta para el aprendizaje y la optimización. Posteriormente se analizarán de manera general los 3 paradigmas principales que se utilizan hoy en día en la computación evolutiva: las estrategias evolutivas, la programación evolutiva y los algoritmos genéticos. En cada caso se abordará su inspiración biológica, su motivación, su funcionamiento y algunas de sus aplicaciones. Finalmente se estudiará a mayor detalle el funcionamiento, fundamentos teóricos, implementación y operación de los algoritmos genéticos, que es actualmente el paradigma evolutivo más utilizado por los investigadores que trabajan en esta disciplina.

Profesor:

Dr. Carlos Artemio Coello Coello
CINVESTAV-IPN

Depto. de Computación
Av. Instituto Politécnico Nacional No. 2508
Col. San Pedro Zacatenco
México, D.F. 07360
ccoello@cs.cinvestav.mx
http://delta.cs.cinvestav.mx/~ccoello

TEMARIO:

Técnicas heurísticas (1.5 hrs)
- Problemas P y NP
- Técnicas clásicas de búsqueda y optimización
- Lo que el mundo real demanda
- ¿Qué es una heurística?
- ¿Realmente necesitamos técnicas heurísticas?
- Ejemplos de técnicas heurísticas
  - Búsqueda tabú
  - Recocido simulado
  - Escalando la colina
Nociones de optimización (1.5 hrs)
- Optimización Global
- Optimización Numérica
- Optimización Combinatoria
- Espacios de búsqueda convexos y cóncavos
- Restricciones explícitas e implícitas
- Restricciones de igualdad y desigualdad
- Zona factible y no factible
Antecedentes históricos (1 hr)
- Inspiración biológica
- Primeros intentos
- Cronología de descubrimientos importantes
Paradigmas principales (1 hr)
- Estrategias evolutivas
- Programación evolutiva
- Algoritmo genético
- Comparaciones
La computación evolutiva en el contexto de la Inteligencia Artificial (1 hr)
- Críticas
- ¿Un nuevo paradigma?
Terminología biológica vs. terminología usada en la computación evolutiva (1 hr)
- Glosario básico
- Comparaciones
Algoritmos genéticos
- Generalidades (1 hr)
  - Definición
  - Componentes básicos
  - Funcionamiento
- Representación (3 hrs)
  - Binaria
  - Códigos de Gray
  - Real
  - Programación genética
  - Algoritmos genéticos desordenados (messy GAs)
  - Otras propuestas
- Selección (2 hrs)
  - Proporcional
  - Torneo
  - Estado Uniforme
  - Uso de jerarquías
- Cruza (3 hrs)
  - Importancia
  - Un punto
  - Dos puntos
  - Uniforme
  - Casos especiales
- Mutación (2 hrs)
  - Importancia
  - Forma básica
  - No uniforme
  - Casos especiales
- Función de aptitud (3 hrs)
  - Definición
  - Uso de "cajas negras"
  - Manejo de restricciones usando funciones de penalización
  - Ejemplos
- Ajuste de parámetros (1 hr)
  - Estudios empíricos
  - Auto-adaptación
- Implementación (3 hrs)
  - Software propio
  - Software de dominio público
  - Sistemas comerciales
- Operadores avanzados (2 hrs)
  - Diploides y dominancia
  - Inversión
  - Micro-operadores
    - Segregación
    - Traslocación
    - Duplicación
    - Borrado
- Teoría (4 hrs)
  - Teorema de los esquemas
  - Modelos exactos
  - Teoría de convergencia
  - No Free Lunch Theorems
  - Críticas
  - Decepción
- ¿Cuándo aplicar un algoritmo genético? (1 hr)
  - Limitaciones
  - Ventajas
  - Areas de aplicación
- Areas abiertas de investigación (1 hr)
  - Inspiración biológica
  - Paralelismo
  - Teoría
  - Representación
  - Operadores
  - Co-evolución
  - Algoritmos culturales
  - Ajuste de parámetros
  - Auto-adaptación
  - Otras
- Temas avanzados (opcionales) (4 hrs)
  - Funciones multimodales
    - Nichos
    - Repartición de aptitud
    - Ejemplos
  - Funciones con objetivos múltiples
    - Técnicas básicas
  - Manejo de restricciones
    - Función de penalización
    - Pena de muerte
    - Separación de objetivos y restricciones
    - Uso de representaciones y operadores especiales
    - Otras propuestas
  Bibliografia
  - A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, 2003, ISBN 3-540-40184-9.
  - Lecturas adicionales
  - Pueden transferir mis notas del curso (en constante actualización) (PDF).
  Material del curso
  - Lineamientos generales del curso (PDF).
  - Acetatos de la clase del 11 de mayo de 2010 (PDF).
  - Acetatos de la clase del 13 de mayo de 2010 (PDF).
  - Acetatos de la clase del 20 de mayo de 2010 (PDF).
  - Acetatos de la clase del 25 de mayo de 2010 (PDF).
  - Acetatos de la clase del 27 de mayo de 2010 (PDF).
  - Acetatos de la clase del 1 de junio de 2010 (PDF).
  - Acetatos de la clase del 3 de junio de 2010 (PDF).
  - Acetatos de la clase del 8 de junio de 2010 (PDF).
  - Acetatos de la clase del 15 de junio de 2010 (PDF).
  - Acetatos de la clase del 17 de junio de 2010 (PDF).
  - Acetatos de la clase del 22 de junio de 2010 (PDF).
  - Acetatos de la clase del 24 de junio de 2010 (PDF).
  - Acetatos de la clase del 29 de junio de 2010 (PDF).
  - Acetatos de la clase del 1 de julio de 2010 (PDF).
  - Acetatos de la clase del 13 de julio de 2010 (PDF).
  - Acetatos de la clase del 15 de julio de 2010 (PDF).
  - Acetatos de la clase del 27 de julio de 2010 (PDF).
  - Acetatos de la clase del 3 de agosto de 2010
    Parte 1 (Power Point 2007).
    Parte 2 (Power Point 2007).
  Lecturas
  - David B. Fogel, An Introduction to Simulated Evolutionary Optimization, IEEE Transactions on Neural Networks, Vol. 5, No. 1, pp. 3--14, January 1994.
  - Coello Coello, Carlos A., La importancia de la representación en los algoritmos Genéticos (Parte I), Soluciones Avanzadas. Tecnologías de Información y Estrategias de Negocios, Año 7, Número 69, pp. 50-56, 15 de mayo de 1999.
  - Coello Coello, Carlos A., La importancia de la representación en los algoritmos Genéticos (Parte II), Soluciones Avanzadas. Tecnologías de Información y Estrategias de Negocios, Año 7, Número 70, pp. 44-48, 15 de junio de 1999.
  - Goldberg, David E. & Deb, Kalyanmoy, A Comparative Analysis of Selection Schemes Used in Genetic Algorithms, in Gregory J. E. Rawlins (Editor), Foundations of Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, California, pp. 69-93, 1991.
  - Peter J.B. Hancock, Selection Methods for Evolutionary Algorithms, en Lance Chambers (editor), Practical Handbook of Genetic Algorithms, Vol. II, CRC Press, Boca Raton, Florida, pp. 67-92, 1995.
  - Spears, William M. Crossover or Mutation?, in L. Darrell Whitley, Foundations of Genetic Algorithms 2, Morgan Kaufmann Publishers, San Mateo, California, pp. 221-237, 1993.
  - Bäck, Thomas, Self-Adaptation in Genetic Algorithms, En F. Varela & P. Bourgine (Editores), Proceedings of the First European Conference on Artificial Life, Paris, France, MIT Press, pp. 263-271, 1992.
  - Schaffer, J. David, Caruana, Richard A., Eshelman, Larry J., & Das, Rajarshi, A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization, en J. David Schaffer (Editor), Proceedings of the Third International Conference on Genetic Algorithms, pp. 51--60, Morgan Kaufmann Publishers, 1989.
  - Ágoston Endre Eiben, Robert Hinterding and Zbigniew Michalewicz. Parameter Control in Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 3, No. 2, pp. 124--141, July 1999.
  - F. Herrera, M. Lozano and J.L. Verdegay. Tackling Real-Coded Genetic Algorithms: Operators and tools for the Behaviour Analysis, Artificial Intelligence Review, Vol. 12, pp. 265--319, 1998.
  - A.M. Sánchez, M. Lozano, P. Villar and F. Herrera, Hybrid Crossover Operators with Multiple Descendents for Real-Coded Genetic Algorithms: Combining Neighborhood-based Crossover Operators, International Journal of Intelligent Systems, Vol. 24, No. 5, pp. 540--567, 2009.
  - C. García-Martínez, M. Lozano, F. Herrera, D. Molina and A.M. Sánchez, Global and Local Real-Coded Genetic Algorithms Based on Parent-Centric Crossover Operators, European Journal of Operational Research, Vol. 185, No. 3, pp. 1088--1113, 2008.
  - Kalyanmoy Deb, Ashish Anand and Dhiraj Joshi, A computationally efficient evolutionary algorithm for real-parameter optimization, {\em Evolutionary Computation}, Vol. 10, No. 4, pp. 371--395, 2002.
  - K. Deb and S. Agrawal, A niched-penalty approach for constraint handling in genetic algorithms, in Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA-99), Springer, pp. 235--243, Portoroz, Slovenia, April 1999.
  - Thomas P. Runarsson and Xin Yao. Stochastic Ranking for Constrained Evolutionary Optimization, IEEE Transactions on Evolutionary Computation, Vol. 4, No. 3, pp. 284--294, September 2000.
  Software
  - Generador de números aleatorios gaussianos con media cero y desviación estándar "sigma" (Código en C)
  - Un algoritmo genético simple (Código en C y el header file correspondiente)
  Tareas
  - Tarea No. 1 (Fecha de entrega: 27 de mayo de 2010)
  - Tarea No. 2 (Fecha de entrega: 3 de junio de 2010)
  - Tarea No. 3 (Fecha de entrega: 22 de junio de 2010)
  - Tarea No. 4 (Fecha de entrega: 1 de julio de 2010)
    
    Archivos para la tarea no. 4:
  - Tarea No. 5 (Fecha de entrega: 13 de julio de 2010)
  Proyecto Final
  - Los lineamientos para el proyecto final ya están disponibles.
  - Ejemplos de posibles proyectos para 2010.
  Ligas útiles
  - The Hitch-Hiker's Guide to Evolutionary Computation : Compilada por Joerg Heitkötter y David Beasley, esta guía es indiscutiblemente uno de los documentos más útiles para los interesados en la computación evolutiva.
  - Zooland : Información sobre vida artificial, algoritmos genéticos, programación evolutiva y estrategias evolutivas. Esta página contiene además artículos técnicos, software de dominio público para demostrar el funcionamiento de diferentes algoritmos evolutivos (por ejemplo: Tierra, Vivarium y WinGA), una lista de estudiantes de doctorado en vida artificial, guías de estudio propuestas para cursos de vida artificial y muchas otras cosas más.
  - Repositorio de artículos sobre computación evolutiva : Esta es una larga lista de artículos técnicos sobre diferentes aspectos de la computación evolutiva. La lista se encuentra ubicada en el Laboratorio de Inteligencia Artificial de la Universidad de Edimburgo, en Escocia.
  - GA List : Una de las listas más completas de sitios alrededor del mundo donde se efectúa investigación con algoritmos genéticos. Este sitio contiene también software de dominio público para implementar algoritmos genéticos y programación genética, así como el GA Digest, una popular publicación electrónica donde se anuncian conferencias, journals, software y demás cuestiones relacionadas con la computación evolutiva.
  - ENCORE : Esta es una red europea con información sobre computación evolutiva, incluyendo software, bibliografías, índices de tesis de maestría y doctorales, etc. ENCORE significa Evolutionary Computation Repository Network.
  Página creada y mantenida por Carlos A. Coello Coello