Ciencias de la Computación (plan 1994) 2012-2

Optativas, Seminario de Inteligencia Artificial II

Computación Evolutiva

Seminario de Inteligencia Artificial II Grupo: 7048

La computación evolutiva constituye un conjunto de técnicas heurísticas utilizadas para resolver problemas de diversos tipos, en los que podemos encontrar comúnmente problemas de búsqueda y optimización. La característica principal de estos problemas es la gran cantidad de variables que pueden estar involucradas junto con un enorme espacio de posibles soluciones, a veces tan grande como el número de átomos que constituyen el universo.

Los mecanismos de estos algoritmos se inspiran en el proceso de la evolución biológica, se retoman conceptos como genotipo y fenotipo, los cuales son los principales componentes de la unidad fundamental “el individuo”, y como motor de variabilidad se identifican procesos genéticos como la reproducción y la mutación, así como la adaptabilidad del individuo en su entorno.

Estas técnicas se han aplicado en distintas disciplinas y ramas del conocimiento desde aplicaciones en inteligencia artificial hasta problemas en ingeniería, debido a que es posible encontrar soluciones relativamente buenas en un periodo corto de tiempo.

Este curso ofrece una introducción a la computación evolutiva, se estudiarán los fundamentos, la teoría y aplicaciones de las principales técnicas evolutivas como son: los algoritmos genéticos, estrategias evolutivas, programación evolutiva y programación genética.

Temario

1 Introducción

1.1 Historia de la computación evolutiva

1.2 Inspiración en Biología

1.3 ¿Por qué computación evolutiva?

1.4 Ejemplos de aplicaciones de la computación evolutiva

2 Qué es un algoritmo evolutivo

2.1 Introducción

2.2 Componentes principales de los algoritmos evolutivos

2.3 Cómo trabaja un algoritmo evolutivo

2.4 Algoritmos evolutivos vs. otras técnicas de optimización global

2.5 Ejemplos: “Problema de las 8 reinas”, “Knapsack Problem”

3 Algoritmos genéticos

3.1 Representación de los individuos

3.2 Selección de los padres

3.3 Recombinación

3.4 Mutación

3.5 Selección de supervivientes

3.6 Teorema del Esquema

3.7 Ejemplos.

4 Estrategias evolutivas

4.1 Introducción

4.2 Representación y auto-adaptación

4.3 Mutación y auto-adaptación

4.4 Recombinación

4.5 Selección de padres

4.6 Selección de supervivientes

5 Programación evolutiva

5.1 Desarrollo histórico

5.2 Representación de los individuos

5.3 Selección de padres y recombinación

5.4 Mutación

5.5 Selección de supervivientes

6 Programación genética

6.1 Representación

6.2 Mutación

6.3 Recombinación

6.4 Selección de padres

6.5 Selección de supervivientes

6.6 Inicialización

6.7 Ejemplos. Hormiga artificial, satisfacibilidad del circuito,

6.8 Comportamiento emergente.

7 Aprendizaje en sistemas clasificadores

7.1 Introducción

7.2 Sistema clasificador genérico

8. Proyecto Final

Bibliografía:

• Eiben A., Smith J., Introduction to Evolutionary Computing, Springer, 2003

• Michalewicz Z., Genetic Algorithms + Data Structures Evolution Programs, Springer, 1996 (Third, Revised, and Extended Edition).

• Goldberg D., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

• Eiben A, Schoenauer, M. Evolutionary computing, Information Processing Letters, 82(1): 1-6, 2002.

• Langdon W., Poli R., Fundations of Genetic Programming, Springer-Verlag 2002.