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
  Bibliografía
  - A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, Second Edition, 2015, ISBN 978-3-662-44873-1.
  - 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 15 de mayo de 2023 (PDF).
  - Acetatos de la clase del 16 de mayo de 2023 (PDF).
  - Acetatos de la clase del 24 de mayo de 2023 (PDF).
  - Acetatos de la clase del 31 de mayo de 2023 (PDF).
  - Acetatos de la clase del 7 de junio de 2023 (PDF).
  - Acetatos de la clase del 9 de junio de 2023 (PDF).
  - Acetatos de la clase del 14 de junio de 2023 (PDF).
  - Acetatos de la clase del 16 de junio de 2023 (PDF).
  - Acetatos de la clase del 28 de junio de 2023 (PDF).
  - Acetatos de la clase del 7 de julio de 2023 (PDF).
  - Acetatos de la clase del 12 de julio de 2023 (PDF).
  - Acetatos de la clase del 21 de julio de 2023 (PDF).
  - Acetatos de la clase del 26 de julio de 2023 (PDF).
  - Acetatos de la clase del 28 de julio de 2023 (PDF).
  - Acetatos de la clase del 2 de agosto de 2023 (PDF).
  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: 24 de mayo de 2023)
  - Tarea No. 2 (Fecha de entrega: 31 de mayo de 2023)
  - Tarea No. 3 (Fecha de entrega: 16 de junio de 2023)
  - Tarea No. 4 (Fecha de entrega: 7 de julio de 2023)
    
    Archivos para la tarea no. 4:
  - Tarea No. 5 (Fecha de entrega: 14 de julio de 2023)
  Proyecto Final
  - Los lineamientos para el proyecto final ya están disponibles.
  - Ejemplos de posibles proyectos para 2023.
  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.
  - Acetatos de otro curso de computación evolutiva : Estos acetatos fueron propuestos por los autores del libro de texto usado en nuestro curso para impartir un curso de computación evolutiva.
  - Glosario de computación evolutiva: Un glosario básico, pero bastante completo, de terminología usada en computación evolutiva. Este glosario lo desarrollaron varios investigadores de Alemania hace algunos años.
  Página creada y mantenida por Carlos A. Coello Coello