logo UGR Departamento de Ciencias de la Computación e Inteligencia Artificial
Universidad de Granada
Escuela Técnica Superior de Ingenierías Informática y de Telecomunicación
c/. Daniel Saucedo Aranda, s/n 18071 Granada España
logo decsai

Ingeniería Informática

Bioinformática (a extinguir)

Curso 2013/2014


Curso: 5º, Segundo Cuatrimestre

Créditos de Teoría: 0, Créditos de Prácticas: 0

PROGRAMA DE TEORÍA
PARTE I. INTRODUCCIÓN

Tema 1. Computación Basada en Modelos Naturales

o Computación Natural

o Introducción a los Modelos de Computación Bioinspirados
PARTE II. MODELOS BASADOS EN ADAPTACIÓN SOCIAL (Swarm Intelligence)

Tema 2. Introducción a los Modelos Basados en Adaptación Social

o Resolución de Problemas Mediante Cooperación Social

o Introducción a los Modelos Sociales

o Sistemas Artificiales Basados en Enjambres/Sociedades

Tema 3. Optimización Basada en Colonias de Hormigas

o Las Colonias de Hormigas Naturales

o Algoritmos de Optimización basados en Colonias de Hormigas

o Aplicaciones

Tema 4. Optimización Basada en Nubes de Partículas (Particle Swarm)

o Nubes de Partículas basadas en el Vuelo de las Bandadas de Aves y el Movimiento de los Bancos de Peces.

o Algoritmo de Optimización basado en Nubes de Partículas: PSO

o Aplicaciones
PARTE III. COMPUTACÍON EVOLUTIVA

Tema 5. Introducción a la Computación Evolutiva

o Evolución Natural y Evolución Artificial

o Algoritmos Evolutivos

o Breve Historia de la Computación Evolutiva y Taxonomía

o Problemas abordados: múltiples soluciones y objetivos, restricciones, descomposición de problemas (coevolución), etc.

o Aplicaciones de los Algoritmos Evolutivos

Tema 6. Algoritmos Genéticos I. Conceptos Básicos

o Introducción a los Algoritmos Genéticos.

o Esquema de Funcionamiento. Operadores

o Modelos de Evolución Generacional y Estacionario

o Algoritmos Genéticos con Codificación Real

Tema 7. Algoritmos Genéticos II. Diversidad y Convergencia

o Diversidad y Convergencia en Algoritmos Genéticos

o Modelo: Algoritmo Evolutivo CHC

o Otros Modelos de Equilibrio Diversidad-Convergencia

Tema 8. Algoritmos Genéticos III. Múltiples Soluciones en Problemas Multimodales

o Introducción a los Problemas Multimodales

o Algoritmos Genéticos con Técnicas de Nichos

Tema 9. Estrategias de Evolución y Programación Evolutiva

o Introducción a las Estrategias de Evolución

o Modelo EE(1+1)

o Modelos basados en poblaciones: EE(μ,λ) y EE(μ+λ)

o Introducción a la Programación Evolutiva

o Diferencias entre la Programación Evolutiva y las Estrategias de Evolución

Tema 10. Algoritmos Basados en Evolución Diferencial (Differential Evolution - DE)

o Introducción a los algoritmos de Evolución Diferencial

o Modelos de DE

Tema 11. Modelos de Evolución basados en Estimación de Distribuciones (EDA)

o Introducción a los EDA

o Modelos básicos: PBIL, Compact GA, UMDA

o Modelos con dependencias: MIMIC, TREE; EBNA

o Otros modelos

Tema 12. Algoritmos Evolutivos para Problemas Multiobjetivo

o Introducción a los Problemas Multiobjetivo

o Algoritmos Evolutivos para Problemas Multiobjetivo (MOEAs)

o Elitismo y MOEAs

o Medidas de Calidad de MOEAs

Tema 13. Programación Genética

o Descripción General. Representación y Operadores

o Programación Genética y Algoritmos Genéticos: Modelo GA-P

o Aplicaciones

Tema 14. Modelos Evolutivos de Aprendizaje

o Introducción al Aprendizaje Evolutivo

o Modelos de Aprendizaje Evolutivo de Reglas

o Regresión Simbólica mediante Programación Genética
PARTE IV. OTROS MODELOS DE COMPUTACIÓN BIOINSPIRADOS

Tema 15. Sistemas Inmunológicos Artificiales

o El Sistemas Inmunológico Natural

o Algoritmos Basados en el Sistema Inmunológico Artificial

o Aplicaciones

Tema 16. Otros Modelos de Computación Natural/Bioinspirados

o Computación basada en DNA

o Autómatas Celulares

o Computación basada en Membranas

o Computación Cuántica
PROGRAMA DE PRÁCTICAS
El programa de prácticas se compone de cuatro prácticas independientes, cuya realización será opcional. El alumno podrá realizar las que desee, no existiendo restricciones:

* Práctica 1. Optimización Basada en Colonias de Hormigas
o Planteamiento y descripción de dos problemas de optimización combinatoria: el viajante de comercio y la asignación cuadrática.
o Estudio de la resolución de ambos problemas mediante los algoritmos de Optimización basados en Colonias de Hormigas estudiados en teoría.
o Implementación de dichas técnicas para la resolución de distintos casos de ambos problemas y estudio comparativo de su rendimiento.
* Práctica 2. Algoritmos Evolutivos con Codificación Real
o Planteamiento y descripción de problemas de optimización numérica (minimización de funciones).
o Estudio de la resolución de estos problemas mediante algoritmos evolutivos con codificación real: algoritmos genéticos con codificación real, CHC con codificación real, estrategias de evolución y programación evolutiva, algoritmos basados en nichos, DE, EDAs, ...
o Implementación de dichas técnicas para la resolución de dichos problemas y estudio comparativo de su rendimiento.
* Práctica 3. Algoritmos Genéticos Multiobjetivo
o Planteamiento y descripción de problemas multiobjetivo: problemas de optimización numérica (minimización de funciones matemáticas) y problema de la mochila.
o Estudio de la resolución de estos problemas mediante algoritmos evolutivos multiobjetivo: MOGA, NSGA-II, SPEA2 y MOGLS.
o Implementación de estos algoritmos evolutivos multiobjetivo para la resolución de dichos problemas y estudio comparativo de su rendimiento.
BIBLIOGRAFÍA
# M. Amos. Theoretical and Experimental DNA Computing. Springer Verlag, 2005.
# T. Back, Evolutionary Algorithms in Theory and Practice. Oxford, 1996.
# T. Back, D. Fogel, Z. Michalewicz, Handbook of Evolutionary Computation. Institute of Physics Publishing and Oxford University Press, 1997.
# W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone, Genetic Programming. An Introduction. Kaufmann Publishers, 1998.
# P. Bentley, Digital Biology. How Nature is Transforming our Technology. Headline, 2001.
# E. Bonabeau, M. Dorigo, T. Theraulaz. From Natural to Artificial Swarm Intelligence. Oxford University Press, 1999
# M. Chambers (Ed.), Practical Handbook of Genetic Algorithms, Vols. I, II, y III. CRC Press, 1995, 1998.
# D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization. McGraw-Hill, 1999.
# L.N. de Castro, J. Timmis, Artificial Inmune Systems: A New Computational Intelligence Approach. Springer-Verlag, 2002.
# M. Dorigo, T. Stützle, Ant Colony Optimization. The MIT Press, 2004.
# A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing. Springer, 2003.
# D.B. Fogel, Evolutionary Computation. IEEE Press, 1995.
# D.B. Fogel (Ed.), Evolutionary Computation. The Fossil record. IEEE Press, 1998.
# D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989.
# J.H. Holland, Adaptation in Natural and Artificial Systems. MIT Press, 1992.
# J. Kennedy, R.C. Eberhart, Swarm Intelligence. Morgan Kauffmann, 2001.
# J.R. Koza, Genetic Programming. MIT Press, 1992.
# W. B. Langdon, R. Poli. Foundations of Genetic Programming. Springer-Verlag, 2002.
# Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.
# H-P. Schwefel, Evolution and Optimum Seeking. John Wiley, 1995.
# M. Shipper. Machine Nature. The Coming Age of Bio-Inspired Computing. McGraw-Hill, 2002.
MÉTODO DE EVALUACIÓN
Se realizará un examen final de preguntas múltiples y se evaluarán las prácticas entregadas. La calificación de cada parte corresponderá al 50 por ciento de la nota final. Si en alguna de las dos partes se obtiene menos de 1 punto sobre 5 se suspenderá la asignatura. En otro caso, la calificación final será la suma de las calificaciones de ambas partes.