Algoritmos metaheurísticos trayectoriales para optimizar problemas combinatorios

Trajectory metaheuristic algorithms to optimize problems combinatorics

Natalia Alancay, Silvia Villagra, Norma Andrea Villagra

Código

ICT-UNPA-148-2016

Resumen


La aplicación de los algoritmos metaheurísticos a problemas de optimización ha sido muy importante durante las últimas décadas. La principal ventaja de estas técnicas es su flexibilidad y robustez, lo que permite aplicarlas a un amplio conjunto de problemas. En este trabajo nos concentramos en metaheurísticas basadas en trayectoria Simulated Annealing, Tabu Search y Variable Neighborhood Search cuya principal característica es que parten de un punto y mediante la exploración del vecindario varían la solución actual, formando una trayectoria. Mediante las instancias de los problemas combinatorios seleccionados, se realiza una experimentación computacional que ilustra el comportamiento de los métodos algorítmicos para resolver los mismos. El objetivo principal de este trabajo es realizar el estudio y comparación de los resultados obtenidos para las metaheurísticas trayectoriales seleccionadas en su aplicación para la resolución de un conjunto de problemas académicos de optimización combinatoria.

Palabras clave


Metaheurísticas de trayectoria; Simulated Annealing; Tabu Search y Variable Neighborhood Search; Problemas de Optimización Combinatoria


Abstract


The application of metaheuristic algorithms to optimization problems has been very important during the last decades. The main advantage of these techniques is their flexibility and robustness, which allows them to be applied to a wide range of problems. In this work we concentrate on metaheuristics based on Simulated Annealing, Tabu Search and Variable Neighborhood Search trajectory whose main characteristic is that they start from a point and through the exploration of the neighborhood vary the current solution, forming a trajectory. By means of the instances of the selected combinatorial problems, a computational experimentation is carried out that illustrates the behavior of the algorithmic methods to solve them. The main objective of this work is to perform the study and comparison of the results obtained for the selected trajectories metaheuristics in its application for the resolution of a set of academic problems of combinatorial optimization.


Keywords


Trajectory Metaheuristics; Simulated Annealing; Tabu Search; Variable Neighborhood Search; Combinatorial Optimization Problems


Área


Ingeniería y Tecnología

Resolución


0829/16-R-UNPA

Fecha de Aprobación


2016-08-30

Texto completo:

PDF

Referencias


ALBA E. y Troya J. M, 2000. Cellular evolutionary algorithms: Evaluating the influence of ratio. In Parallel Problem Solving from Nature PPSN VI, pages 29–38. Springer. https://doi.org/10.1007/3-540-45356-3_3

ALONSO-Ayuso, A., Escudero, L. F., Martín-Campo, F. J., & Mladenović, N. (2015). A VNS metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes. Journal of Global Optimization, 63(3), 583-596. https://doi.org/10.1007/s10898-014-0144-8

CENTRE Ch. B. R. y Stinson D. R, 1985. An introduction to the Design and Analysis of Algorithms. Charles Babbage Research Centre.

DROSTE S., Jansen T. y Wegener I, 2000. A natural and simple function which is hard for all evolutionary algorithms, volume 4. IEEE. https://doi.org/10.1109/IECON.2000.972425

GAREY M. y Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York, 1979.

GLOVER F. y Kochenberger G, 2003. Handbook of Metaheuristics , Kluwer Academic Publishers. https://doi.org/10.1007/b101874

GLOVER, F. y Laguna M. 1997. Tabu Search, Kluwer Academic Publishers. https://doi.org/10.1007/978-1-4615-6089-0

GLOVER, F. 1986 “Future Paths for Integer Programming and Links to Artificial Intelligence”, Computers and Operations Research. 5. 533-549. https://doi.org/10.1016/0305-0548(86)90048-1

GOLDBERG D. E., Deb K., y Horn J., “Massively multimodality, deception and genetic algorithms,” in Proceedings of the Parallel Problem Solving from Nature, PPSN II, R.

MÄNNER and B. Manderick, Eds. 1992, pp. 37–46, North-Holland.

HANSEN, P. y Mladenovic, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research. 130 (3), 449–467 (2001). https://doi.org/10.1016/S0377-2217(00)00100-4

KENNETH A De J., Mitchell A P. y Spears W. M, 1997. Using problem generators to explore the effects of epistasis. In ICGA, pages 338–345. Citeseer.

KHURI S., Bäck T. y Heitkötter J, 1994. An evolutionary approach to combinatorial optimization problems. In ACM Conference on Computer Science, pages 66–73.Citeseer. https://doi.org/10.1145/197530.197558

KIRKPATRICK S., Gelatt C.D. y Vecchi M.P, 1983. Optimization by Simulated Annealing, Science 220, pp. 671. https://doi.org/10.1126/science.220.4598.671

MACWILLIAMS F. J. y Sloane NJ N. J. A, 1977. The Theory of Error-correcting Codes: Part 2, volume 16. Elsevier.

MARTÍ R. Algoritmos heurísticos en optimización combinatoria. Departamento de Estadística e Investigación Operativa, Facultad de Ciencias Matemáticas. Universidad de Valencia, España 2003.

MELIÁN B. y Glover F. 2003. Búsqueda Tabú. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial 19: 29-48.

MISEVIČIUS, A. (2015). Using iterated tabu search for the traveling salesman problem. Information technology and control, 32(3).

SCHAFFER D. J. y Eshelman L. J, 1991. On crossover as an evolutionarily viable strategy. In ICGA, volume 91, pages 61–68.

SEN, G., Krishnamoorthy, M., Rangaraj, N., & Narayanan, V. (2016). Mathematical models and empirical analysis of a simulated annealing approach for two variants of the static data segment allocation problem. Networks. https://doi.org/10.1002/net.21675

SICILIA, J. A., Quemada, C., Royo, B., & Escuín, D. (2016). An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics. Journal of Computational and Applied Mathematics, 291, 468-477. https://doi.org/10.1016/j.cam.2015.03.050

TSUTSUI S., Ghosh A., Corne D. y Fujimoto Y, 1997. A real coded genetic algorithm with an explorer and an exploiter populations. In ICGA, pages 238–245, 1997.

WANG, S., Zuo, X., Liu, X., Zhao, X., & Li, J. (2015). Solving dynamic double row layout problem via combining simulated annealing and mathematical programming. Applied Soft Computing, 37, 303-310. https://doi.org/10.1016/j.asoc.2015.08.023




DOI: http://dx.doi.org/10.22305/ict-unpa.v8i3.222

Enlaces refback

  • No hay ningún enlace refback.




_______________________________________________________________________________

Revista de Informes Científicos y Técnicos de la Universidad Nacional de la Patagonia Austral. © 2009 Todos los Derechos Reservados.
Licencia Creative CommonsEsta obra está bajo una Licencia Creative Commons Atribución-NoComercial-SinDerivar 4.0 Internacional.