Materia

Contenido de XSL

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

NombreInstituciónCategoríaDoctor/aPerfil docenteÁreaEmail
LOZANO ALONSO, JOSE ANTONIOUniversidad del País Vasco/Euskal Herriko UnibertsitateaProfesorado Catedratico De UniversidadDoctorNo bilingüeCiencia de la Computación e Inteligencia Artificialja.lozano@ehu.eus

Competencias

DenominaciónPeso
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úsqueda25.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ón25.0 %

Tipos de docencia

TipoHoras presencialesHoras no presencialesHoras totales
Magistral12.51830.5
Seminario5813
P. Ordenador12.51931.5

Actividades formativas

DenominaciónHorasPorcentaje de presencialidad
Actividades propuestas por el equipo docente a través de la plataforma virtual0.00 %
Clases expositivas10.0100 %
Elaboración de informes y exposiciones15.030 %
Estudio sistematizado20.00 %
Horas de contacto virtual a través de la plataforma (participación en foros, consulta de dudas, etc)0.0100 %
Interacción con el docente en entornos virtuales0.030 %
Lectura y análisis prácticos20.050 %
Talleres de aplicación10.0100 %
Videoconferencias0.0100 %

Sistemas de evaluación

DenominaciónPonderación mínimaPonderación máxima
Asistencia y Participación15.0 % 25.0 %
Exposiciones30.0 % 40.0 %
Otros0.0 % 10.0 %
Participación en los foros15.0 % 25.0 %
Pruebas de evaluación a distancia75.0 % 85.0 %
Trabajos Prácticos30.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ÓN

Tema 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

Enlaces

https://en.wikipedia.org/wiki/Metaheuristic

Contenido de XSL

Sugerencias y solicitudes