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

Algorítmica (a extinguir)

Curso 2012/2013


Curso: 4º, Primer Cuatrimestre

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

PROGRAMA DE TEORÍA
Parte I. Introducción a las Metaheurísticas

o Tema 1. Metaheurísticas: Introducción y Clasificación
+ Resolución de problemas mediante algoritmos de búsqueda
+ Algoritmos aproximados
+ Metaheurísticas: definición y clasificación
+ Paralelización de metaheurísticas

Parte II. Métodos Basados en Trayectorias y Entornos

o Tema 2. Algoritmos de Búsqueda Local Básicos
+ Introducción
+ Búsqueda Aleatoria versus Búsqueda Local
+ Métodos de Búsqueda Local Básicos
+ Un Método de Búsqueda Local Avanzado: VND
o Tema 3. Algoritmos de Enfriamiento Simulado
+ Fundamentos
+ Algoritmo básico de ES
+ Parámetros y componentes
+ Aplicaciones
o Tema 4. Algoritmos de Búsqueda Tabú
+ Introducción
+ La estructura de la búsqueda tabú
+ Ejemplo ilustrativo
+ Aplicaciones
o Tema 5. Métodos Basados en Trayectorias Múltiples I: Métodos Multiarranque Básicos y GRASP
+ Introducción a la Búsqueda Multiarranque
+ Algoritmos Multiarranque Básicos
+ Modelos Multiarranque
+ Algoritmo GRASP
+ Aplicación de GRASP
o Tema 6. Métodos Basados en Trayectorias Múltiples II: ILS y VNS
+ Introducción
+ Algoritmos de búsqueda local reiterativos basados en óptimos: ILS
+ Búsqueda de entorno variable: VNS
+ Aplicaciones

Parte III. Métodos Basados en Poblaciones

o Tema 7. Algoritmos Genéticos
+ Introducción
+ ¿Cómo se construye?
+ Sobre su utilización
+ Algunas cuestiones: diversidad, exploración vs. explotación
+ Modelos: generacional vs. estacionario
+ Dominios de aplicación
+ Ejemplo: viajante de comercio
+ Aplicaciones

Parte IV. Intensificación y Diversificación

o Tema 8. Estudio del Equilibrio entre Intensificación y Diversificación
+ Introducción - uso básico
+ Aspectos avanzados intensificación vs diversificación

Parte V. Metaheurísticas Híbridas: Poblaciones y Trayectorias

o Tema 9. Algoritmos Meméticos
+ Introducción
+ Algoritmos meméticos
+ Algunos ejemplos
o Tema 10. Scatter Search
+ Búsqueda dispersa
+ Aplicaciones

Parte VI. Paralelización de Metaheurísticas

o Tema 11. Metaheurísticas en Sistemas Descentralizados
+ Introducción
+ Tipos de descentralización
+ Paralelización en metaheurísticas basadas en entornos
+ Paralelización en metaheurísticas basadas en poblaciones

Parte VII. Conclusiones

o Tema 12. Algunas Consideraciones sobre la Adaptación de Metaheurísticas a la Resolución de Problemas
+ Búsquedas basadas en entornos
+ Búsquedas basadas en poblaciones
PROGRAMA DE PRÁCTICAS
* Planteamiento y descripción de distintos problemas:
o Problema MAX-CUT.
o Problema de Asignación Cuadrática (QAP)
o Problema de la Mochila
* Estudio de la resolución de los problemas anteriores mediante las metaheurísticas secuenciales y paralelas estudiadas en teoría
* Implementación de dichas técnicas para la resolución de uno de los problemas, a escoger por el alumno

La explicación de los distintos problemas, que comprende las dos primeras sesiones de prácticas (dos horas), se impartirá en pizarra. El resto del programa de prácticas se impartirá en el aula de ordenadores.
BIBLIOGRAFÍA
* D. Corne, M. Dorigo, F. Glover (Eds.). New Ideas in Optimization. McGraw-Hill, 1999.
* A. Díaz y otros. Optimización Heurística y Redes Neuronales. Paraninfo, 1996.
* A.E. Eiben, J.E. Smith. Introduction to Evolutionary Computing. Springer, 2003.
* F. Glover, G.A. Kochenberger (Eds.). Handbook of Metaheuristics. Kluwer Academic Press, 2003.
* H.H. Hoos, T. Stützle. Stochastic Local Search. Morgan Kaufmann, 2004.
* M. Laguna, R. Martí. Scatter Search. Springer, 2003.
* Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.
* J.M. Moreno Vega, J.A. Moreno Pérez. Heurísticas en Optimización. Consejería de Educación, Cultura y Deportes. Gobierno de Canarias, 1999.
* P.M. Pardalos, M.G.C. Resende. HandBook of Applied Optimization. Oxford University Press, 2002.
* C.R. Reeves. Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Pub., 1993.

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% de la nota final. Si en alguna de las dos partes se obtiene menos de 1 punto se suspenderá la asignatura. En otro caso, la calificación final será la suma de las calificaciones de ambas partes.