Home

Introducción a la Computación Evolutiva
Introducción a la Computación Evolutiva

Objetivo:

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. Inicialmente, se harán 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 y comparará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 abordara su inspiración biológica, su motivación, su funcionamiento y algunas de sus aplicaciones. Finalmente, se estudiara a mayor detalle el funcionamiento, fundamentos teóricos, implementación y operación de los algoritmos genéticos, que es actualmente el paradigma evolutivo mas utilizado por los investigadores que trabajan en esta disciplina.

Contenido:

  1. Técnicas heurísticas
    • 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.

  2. Nociones de optimización
    • Optimización Global
    • Optimización Numérica
    • Optimización Combinatoria
    • Espacios de búsqueda convexos y cóncavos
    • Restricciones explicitas e implícitas
    • Restricciones de igualdad y desigualdad
    • Zona factible y no factible

  3. Antecedentes históricos
    • Inspiración biológica
    • Primeros intentos
    • Cronología de descubrimientos importantes

  4. Paradigmas principales
    • Estrategias evolutivas
    • Programación evolutiva
    • Algoritmo genético
    • Comparaciones

  5. La computación evolutiva en el contexto de la Inteligencia Artificial
    • Críticas (IA Clásica vs. Técnicas Heurísticas)
    • ¿Un nuevo paradigma?

  6. Terminología biológica vs. terminología usada en la computación evolutiva: glosario básico y comparaciones.

  7. Algoritmos genéticos.
    • Generalidades: Definición. Componentes básicos. Funcionamiento.
    • Representación: Binaria, códigos de gray real, programación genética, algoritmos genéticos desordenados (Messy GAs), otras propuestas.
    • Selección: Proporcional, torneo, estado uniforme, uso de jerarquías.
    • Cruza: Importancia, un punto, dos puntos, uniforme, casos especiales.
    • Mutación: Importancia, forma básica, no uniforme, casos especiales.
    • Función de aptitud. Definición. Uso de "cajas negras". Manejo de restricciones usando funciones de penalización. Ejemplos
    • Ajuste de parámetros: Estudios empíricos. Auto-adaptación.
    • Implementación: Software propio, software de dominio público, sistemas comerciales.
    • Operadores avanzados: Diploides y dominancia. Inversión. Micro-operadores: segregación, traslocación, duplicación y borrado.
    • Teoría: 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? Limitaciones. Ventajas. Áreas de aplicación.

  8. Áreas abiertas de investigación. Inspiración biológica. Paralelismo. Teoría. Representación. Operadores. Co-evolución.

  9. Algoritmos culturales. Ajuste de parámetros. Auto-adaptación

  10. Otras

  11. Temas avanzados (opcionales) Funciones multimodales. Nichos. Repartición de aptitud. Ejemplos

  12. Funciones con objetivos múltiples. Técnicas básicas

  13. 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, 2003, ISBN 3-540-40184-9 (libro de texto).
  • David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.
  • David Corne, Marco Dorigo&Fred Glover (editores), New Ideas in Optimization, McGraw- Hill, London, 1999.
  • Sadiq M. Sait & Habib Youssef, Iterative Computer Algorithms with Applications in Engineering, IEEE Computer Society, Los Alamitos, California, 1999.
  • Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, Massachusetts, 1996.
  • Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Second Edition, 1992.
  • John H. Holland, Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press, Cambridge, Massachusetts, Second Edition, 1992.
  • David B. Fogel, Evolutionary Computation. Toward a New Philosophy of Machine Intelligence, The Institute of Electrical and Electronic Engineers, New York, 1995.
  • Thomas Bšack, Evolutionary Algorithms in Theory and Practice, Oxford University Press, New York, 1996.
  • David B. Fogel, Evolutionary Computation: The Fossil Record, The Institute of Electrical and Electronic Engineers, New York, 1998.
  • John R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, Massachusetts, 1992.
  • Colin B. Reeves (editor), Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Great Britain, 1993.
  • Zbigniew Michalewicz & David B. Fogel, How to Solve It: Modern Heuristics, Springer, Berlin, 2000.

  • share