Irakasgaiaren azalpena eta testuingurua

Los problemas de optimización combinatoria son omnipresentes hoy en día. Aparecen en el campo de la ingeniería, en las finanzas o en la ciencia. Estos problemas se caracterizan por tener un espacio de búsqueda finito o infinito contable. Ejemplos de estos problemas son problemas de enrutamiento, planificación o asignación, por nombrar algunos. La investigación de operaciones tradicional ha resuelto estos problemas mediante el uso de algoritmos de tipo branch & bound. Sin embargo, este tipo de algoritmos no pueden resolver instancias medianas-grandes debido al tiempo de cálculo requerido. De hecho, la mayoría de estos problemas pertenecen a una clase llamada NP-completo. Todos los problemas de esta categoría comparten una propiedad: no existe ningún algoritmo polinomial conocido capaz de resolver todas las instancias posibles del problema. Además, si hubiera un algoritmo polinomial para una instancia, entonces todos los problemas podrían resolverse en tiempo polinomial. En este tema, nuestro objetivo es presentar algoritmos heurísticos. Estos algoritmos se caracterizan por producir buenas soluciones en tiempos de cálculo asequibles. No obstante, a diferencia de los algoritmos de branch & bound, estos métodos no se basan en fundamentos matemáticas sólidos, y no proporcionan garantías de optimalidad de las soluciones proporcionadas.



La relevancia de esta materia en el contexto del máster es doble: de primera mano, la mayoría de los problemas de optimización combinatoria que se resuelven actualmente en la industria o la economía hacen uso de este tipo de algoritmos. En segundo lugar, las heurísticas son una herramienta básica para otras materias: por ejemplo, la mayoría de los modelos en el campo del aprendizaje automático o la minería de datos se aprenden mediante el uso de heurísticas.

Ohiko deialdia: orientazioak eta uko egitea

El estudiante deberá realizar un trabajo práctico que consiste en la solución de un problema académico de optimización combinatoria mediante varios algoritmos metaheurísticos. Para ello, los estudiantes deberán formalizar matemáticamente el problema, diseñar algoritmos adecuados y codificarlos en el ordenador. Además, realizarán un estudio experimental donde comparar el rendimiento de los diferentes trabajos.



La entrega consistirá en un informe del trabajo realizado en formato paper junto al código fuente, y un breve video explicando el contenido del trabajo (el problema, algoritmos desarrollados, experimentación y conclusiones extraídas).



El trabajo se realizará preferentemente de manera grupal, aunque se permitirán trabajos individuales.

Ezohiko deialdia: orientazioak eta uko egitea

En el caso de que el trabajo entregado no haya superado la nota mínima, los alumnos tendrán opción de entregar una versión mejorada del trabajo (habiendo incorporado el feedback obtenido en la primera convocatoria) en una fecha extraordinaria.

Irakasgai-zerrenda

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

Bibliografia

Nahitaez erabili beharreko materiala

eGela

Oinarrizko bibliografia

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.

Gehiago sakontzeko bibliografia

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.

Aldizkariak

* IEEE Trans. on Evolutionary Computation



* Evolutionary Computation Journal



* Journal of Heuristics



* European Journal of Operations Research



* Computers and Operations Research



* Swarm and Evolutionary Computation

Estekak

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