Home

Introducción a la Computación Evolutiva

Introducción a la computación evolutiva

Objetivo

En este curso se estudiaran 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 analizaran y compararan 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 más utilizado por los investigadores que trabajan en esta disciplina.

 

 

Contenido

  1. Técnicas heurísticas

a) Problemas P y NP

b) Técnicas clásicas de búsqueda y optimización

c) Lo que el mundo real demanda

d) ¿Que es una heurística?

e) ¿Realmente necesitamos técnicas heurísticas?

f ) Ejemplos de técnicas heurísticas: Búsqueda tabú, recocido simulado, escalando la colina.

  1. Nociones de optimización

a) Optimización Global

b) Optimización Numérica

c) Optimización Combinatoria

d) Espacios de búsqueda convexos y cóncavos

e) Restricciones explicitas e implícitas

f ) Restricciones de igualdad y desigualdad

g) Zona factible y no factible

  1. Antecedentes históricos

a) Inspiración biológica

b) Primeros intentos

c) Cronología de descubrimientos importantes

  1. Paradigmas principales

a) Estrategias evolutivas

b) Programación evolutiva

c) Algoritmo genético

d) Comparaciones

  1. La computación evolutiva en el contexto de la Inteligencia Artificial

a) Criticas (IA Clásica vs. Técnicas Heurísticas)

b) ¿Un nuevo paradigma?

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

  2. Algoritmos genéticos.

a) Generalidades: Definición. Componentes básicos. Funcionamiento

b) Representación: Binaria, códigos de gray real, programación genética, algoritmos genéticos desordenados (Messy GAs), otras propuestas.

c) Selección: Proporcional, torneo, estado uniforme, uso de jerarquías.

d) Cruza: Importancia, un punto, dos puntos, uniforme, casos especiales.

e) Mutación: Importancia, forma básica, no uniforme, casos especiales

f ) Función de aptitud. Definición. Uso de “cajas negras”. Manejo de restricciones usando funciones de penalización. Ejemplos

g) Ajuste de parámetros: Estudios empíricos. Auto-adaptación

h) Implementación: Software propio, software de dominio público, sistemas comerciales.

i) Operadores avanzados: Diploides y dominancia. Inversión. Micro-operadores: segregación, traslocación, duplicación y borrado.

j) Teoría: Teorema de los esquemas. Modelos exactos. Teoría de convergencia. No Free Lunch Theorems. Criticas. Decepción

k) ¿Cuándo aplicar un algoritmo genético? Limitaciones. Ventajas. Áreas de aplicación

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

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

  3. Otras

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

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

  6. 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

  1. A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, 2003, ISBN 3-540-40184-9 (libro de texto).

  2. David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.

  3. David Corne, Marco Dorigo&Fred Glover (editores), New Ideas in Optimization, McGraw- Hill, London, 1999.

  4. Sadiq M. Sait & Habib Youssef, Iterative Computer Algorithms with Applications in Engineering, IEEE Computer Society, Los Alamitos, California, 1999.

  5. Melanie Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, Massachusetts, 1996.

  6. Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Second Edition, 1992.

  7. 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.

  8. David B. Fogel, Evolutionary Computation. Toward a New Philosophy of Machine Intelligence, The Institute of Electrical and Electronic Engineers, New York, 1995.

  9. Thomas Back, Evolutionary Algorithms in Theory and Practice, Oxford University Press, New York, 1996.

  10. David B. Fogel, Evolutionary Computation: The Fossil Record, The Institute of Electrical and Electronic Engineers, New York, 1998.

  11. John R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, Massachusetts, 1992.

  12. Colin B. Reeves (editor), Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sons, Great Britain, 1993.

  13. Zbigniew Michalewicz & David B. Fogel, How to Solve It: Modern Heuristics, Springer, Berlin, 2000.

 

 

  • share