Materia
Heurísticos de búsqueda
Datos generales de la materia
- Modalidad
- Presencial
- Idioma
- Inglés
Descripción y contextualización de la asignatura
Combinatorial optimization problems are ubiquitous in these days. They appear in the field of engineering, in finance or in science. These problems are characterized for having a finite or countable infinite search space. Examples of these problems are routing, scheduling or packing problems to name a few. Traditional Operations Research has exactly solved these problems by using branch-and-bound type algorithms. However, this kind of algorithms cannot solve medium-large instances due to the computation time required. In fact, most of these problems belong to a class called NP-complete. All the problems in this category share a property: there is not known polynomial algorithm able to solve all possible instances of the problem. Furthermore, if there would be a polynomial algorithm for one instance, then all the problems could be solved in polynomial time. In this topic, our goal is to present heuristics algorithms. These algorithms are characterized for producing good solutions in affordable computation times. Contrary to branch-and-bound algorithms, these methods are not based on strong mathematical roots, however they obtained competitive results in practice.The relevance of this subject in the context of the master is twofold: on the first hand most of the combinatorial optimization problems that are currently solved in industry or economy make use of this kind of algorithms. Secondly, heuristics are a basic tool for other subjects: for instance most of the models in the field of machine learning or data mining are learnt by the use of heuristics. Similarly, the field of computer vision uses systematically heuristics to carry out, for instance segmentation of images or feature extraction.
Profesorado
Nombre | Institución | Categoría | Doctor/a | Perfil docente | Área | |
---|---|---|---|---|---|---|
CEBERIO URIBE, JOSU | Universidad del País Vasco/Euskal Herriko Unibertsitatea | Profesorado Titular De Universidad | Doctor | Bilingüe | Ciencia de la Computación e Inteligencia Artificial | josu.ceberio@ehu.eus |
HERNANDO RODRIGUEZ, LETICIA | Universidad del País Vasco/Euskal Herriko Unibertsitatea | Profesorado Agregado | Doctora | Bilingüe | Estadística e Investigación Operativa | leticia.hernando@ehu.eus |
Competencias
Denominación | Peso |
---|---|
Aprender los fundamentos matemáticos y analógicos de los principales heurísticos de búsqueda de soluciones en problemas difíciles computacionalmente (NP-completos) | 25.0 % |
Ser capaces de identificar y modelar problemas de optimización susceptibles de ser resueltos de forma eficiente mediante técnicas heurísticas de búsqueda | 25.0 % |
Adquirir la habilidad para diseñar e implementar heurísticos de búsqueda eficientes que permitan solucionar problemas de optimización en diversas áreas de la ciencia y la ingeniería. | 25.0 % |
Adquirir conocimientos que permitan evaluar y presentar de forma razonada la bondad de diversas heurísticas de búsqueda en la resolución de un problema de optimización | 25.0 % |
Tipos de docencia
Tipo | Horas presenciales | Horas no presenciales | Horas totales |
---|---|---|---|
Magistral | 12.5 | 18 | 30.5 |
Seminario | 5 | 8 | 13 |
P. Ordenador | 12.5 | 19 | 31.5 |
Actividades formativas
Denominación | Horas | Porcentaje de presencialidad |
---|---|---|
Actividades propuestas por el equipo docente a través de la plataforma virtual | 0.0 | 0 % |
Clases expositivas | 10.0 | 100 % |
Elaboración de informes y exposiciones | 15.0 | 30 % |
Estudio sistematizado | 20.0 | 0 % |
Horas de contacto virtual a través de la plataforma (participación en foros, consulta de dudas, etc) | 0.0 | 100 % |
Interacción con el docente en entornos virtuales | 0.0 | 30 % |
Lectura y análisis prácticos | 20.0 | 50 % |
Talleres de aplicación | 10.0 | 100 % |
Videoconferencias | 0.0 | 100 % |
Sistemas de evaluación
Denominación | Ponderación mínima | Ponderación máxima |
---|---|---|
Asistencia y Participación | 15.0 % | 25.0 % |
Exposiciones | 30.0 % | 40.0 % |
OTROS | 0.0 % | 10.0 % |
Participación en los foros | 15.0 % | 25.0 % |
Pruebas de evaluación a distancia | 75.0 % | 85.0 % |
Trabajos Prácticos | 30.0 % | 40.0 % |
Convocatoria ordinaria: orientaciones y renuncia
The student has to carry out a practical work that consists in the solution of a academic combinatorial optimization problem by means of several metaheuristic algorithms. In order to do that, the students, will have to mathematically formalize the problem, design appropriate algorithms and codify them in the computer. In addition they will carry out comparison between the different designed and implemented algorithms.In a fixed day at the beginning of the course, the student will provide the instructor with a report of the work done together with the source code. Finally the students will do a presentation of the work carried out.
Temario
Tema 1 INTRODUCCIÓN A LA OPTIMIZACIÓNTema 2 ALGORITMOS DE BÚSQUEDA LOCAL
Tema 3 ALGORITMOS POBLACIONALES E HÍBRIDOS
Tema 4 OPTIMIZACIÓN MULTIOBJETIVO
Tema 5 EVALUACIÓN DE LA OPTIMIZACIÓN
Bibliografía
Bibliografía básica
1. C.R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications,1993.2. A. Díaz (Ed.), Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería.Editorial Paraninfo, 1996.
3. P.J.M. Van Laarhoven & E.H.L. Aarts, Simulated Annealing: Theory and Applications. D. Reidel
Publishing Company, Dordretch, Holland, 1987.
4. D. Goldberg, Genetic Algorithm in search, optimization and machine learning. Addison-Wesley, 1989.
5. T. Back, Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.
6. F. Glover, M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997.
Bibliografía de profundización
7. M. Laguna, R. Mart¿¿ & V. Campos, Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem. Computers and Operations Research 26, pp. 1217-1230, 1999.8. M. Dorigo, V. Maniezzo & A. Colorni, The Ant System: Optimization by a colony of cooperating
agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, pp. 1-13, 1996.
9. M. Laguna and R. Martí, Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, 2003.
10. P. Larrañaga & Jose A. Lozano (Ed.) Estimation of Distribution Algorithms. Kluwer Academic Publishers, 2002.
11. B. Melián, J.A. Moreno Perez, J. Marcos Moreno-Vega, J.(Ed.) Revista Iberoamericana de Inteligencia Artificial 19, 2, 2003.
12. H.H Hoos, T. Stuztle, Stochastic local search. Foundations and applications. Morgan Kaufmann, 2005.
Revistas
* IEEE Trans. on Evolutionary Computation* Evolutionary Computation Journal
* Journal of Heuristics
* European Journal of Operations Research
* Computers and Operations Research
* Swarm and Evolutionary Computation