ISSN 0718-3291 Versión Impresa

ISSN 0718-3305 Versión en línea

Volumen 16 N° 3, Octubre - Diciembre 2008

pdf Índice

Introducción de elementos de memoria en el método simulated annealing para resolver problemas de programación multiobjetivo de máquinas paralelas

 

Felipe Baesler          Reinaldo Moraga          Oscar Cornejo

 

1 Departamento de Ingeniería Industrial. Universidad del Bío-Bío. Avenida Collao 1202. Concepción, Chile. E-mail: fbaesler@ubiobio.cl
2 Facultad de Ingeniería. Universidad Católica de la Santísima Concepción. Concepción, Chile. E-mail: ocornejo@ucsc.cl
3 Department of Industrial and System Engineering. University of Northern Illinois. Dekalb, USA. E-mail: moraga@ceet.niu.edu



RESUMEN 

El presente artículo introduce una variante de la metaheurística simulated annealing, para la resolución de problemas de optimización multiobjetivo. Este enfoque se demonina MultiObjective Simulated Annealing with Random Trajectory Search, MOSARTS. Esta técnica agrega al algoritmo simulated annealing elementos de memoria de corto y largo plazo para realizar una búsqueda que permita balancear el esfuerzo entre todos los objetivos involucrados en el problema. Los resultados obtenidos se compararon con otras tres metodologías en un problema real de programación de máquinas paralelas, compuesto por 24 trabajos y 2 máquinas idénticas. Este problema corresponde a un caso de estudio real de la industria regional del aserrío. En los experimentos realizados, MOSARTS se comportó de mejor manera que el resto de la herramientas de comparación, encontrando mejores soluciones en términos de dominancia y dispersión. 

Palabras clave: Simulated annealing, multiobjetivo, programación de la producción.


ABSTRACT

This paper introduces a variant of the metaheuristic simulated annealing, oriented to solve multiobjective optimization problems. This technique is called MultiObjective Simulated Annealing with Random Trajectory Search (MOSARTS). This technique incorporates short an long term memory concepts to simulated annealing in order to balance the search effort among all the objectives involved in the problem. The algorithm was tested against three different techniques on a real life parallel machine scheduling problem, composed of 24 jobs and two identical machines. This problem represents a real life case study of the local sawmill industry. The results showed that MOSARTS behaved much better than the other methods utilized, because found better solutions in terms of dominance and frontier dispersion.

Keywords: Simulated annealing, multiobjective, scheduling.

 

AGRADECIMIENTOS

Este trabajo fue financiado por los proyectos 052011 3/R de la Dirección de Investigación de la Universidad del Bío-Bío, Concepción-Chile y DIN 10/2005 de la Dirección de Investigación Universidad Católica de la Santísima Concepción, Concepción-Chile.


REFERENCIAS

[1] M. Ehrgott and X. Gandibleux (editores). "Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys". Kluwer Academic Publishers. Boston. 2002.

[2] K. Deb. "Multi-Objective Optimization using Evolutionary Algorithms". John Wiley & Sons. ISBN 0-471-87339-X. Chichester, United Kingdom. 2001.

[3] C. Coello, D. Van Veldhuizen and G.B. Lamont "Evolutionary Algorithms for Solving Multi-Objective Problems". Kluwer Academic Publishers. New York. Marzo 2002.

[4] J. Schaffer. "Multiple Objective Optimization with Vector Evaluated Genetic Algorithms". Thesis to obtain the degree of doctor. Vanderbilt University. 1984.

[5] D. Goldberg. "Genetic Algorithms in Search, Optimization and Machine Learning". Addison-Wesley Publishing Company. Reading, Massachusetts. 1989.

[6] C.M. Fonseca and P.J. Fleming. "Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization". Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 416-423. Morgan Kauffman Publishers. San Francisco, California. 1993.

[7] N. Srinivas and K. Deb. "Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms". Evolutionary Computation. Vol. 2 Nº 3, pp. 221-248. 1994.

[8] E. Zitzler and L. Thiele. "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach". IEEE Transactions on Evolutionary Computation. Vol. 3 Nº 4, pp. 257-271. 1999.

[9] D. Van Veldhuizen and G. Lamont. "On Measuring Multiobjective Evolutionary Algorithm Performance". 2000 Congress on Evolutionary Computation. Vol. 1, pp. 204-211. Piscataway, New Jersey. IEEE Service Center. 2000.

[10] K. Deb, S. Agrawal, A. Pratab and T. Meyarivan. "A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II". In Marc Schoenauer, Kalyanmoy Deb, Günter Rudolph, Xin Yao, Evelyne Lutton, J. J. Merelo and Hans-Paul Schwefel (editores). Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849-858. Springer. 2000.

[11] J. Zydallis, D. Van Veldhuizen and G. Lamont. "A Statistical Comparison of Multiobjective Evolutionary Algorithms Including the MOMGA-II". In Eckart Zitzler, Kalyanmoy Deb, Lothar Thiele, Carlos A. Coello Coello, and David Corne, editors, First International Conference on Evolutionary Multi-Criterion Optimization, pages 226-240. Springer-Verlag. Lecture Notes in Computer Science Nº 1993. 2001.

[12] E. Zitzler, M. Laumanns and L. Thiele. "SPEA2: Improving the Strength Pareto Evolutionary Algorithm". In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou and T. Fogarty (eds.) EUROGEN 2001, Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pp. 95-100, Athens, Greece. 2002.

[13] E. Zitzler, K. Deb and L. Thiele. "Comparison of Multiobjective Evolutionary Algorithms: Empirical Results". Evolutionary Computation. Vol. 8 Nº 2, pp. 173-195. 2000.

[14] D.A. Van Veldhuizen. "Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations". PhD thesis, Department of Electrical and Computer Engineering. Graduate School of Engineering. Air Force Institute of Technology, Wright-Patterson AFB, Ohio, May 1999.

[15] J.D. Knowles and D.W. Corne. "A Comparison of Diverse Approaches to Memetic Multiobjective Combinatorial Optimization". In Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop Program, pp. 103-108. Las Vegas, Nevada. 2000.

[16] P. Serafini. "Simulated Annealing for Multiple Objective Optimization Problems". In Proceedings of the Tenth International Conference of Multiple Criteria Decision Making, Taipei. Vol. 1, pp. 87-96. Julio 1992.

[17] E. Ulungu, J. Teghem and P. Fortemps. "Heuristics for multi-objective combinatorial optimization by simulated annealing". In J. Gu, G. Chen, Q. Wei, and S. Wang, editors, Multiple Criteria Decision Making: Theory and Applications. Proceedings of the 6th National Conference on Multiple Criteria Decision Making, pp. 228-238. Windsor, United Kingdom. 1995.

[18] E. Ulungu, J. Teghem and P. Fortemps. "MOSA Method: A Tool for Solving Multiobjective Combinatorial Optimization Problems". Journal of Multi-Criteria Decision Analysis. Vol. 8 Nº 4, pp. 221-236. 1999.

[19] D. Nam and C. Park. "Multiobjective Simulated Annealing: A Comparative Study to Evolutionary Algorithms". International Journal of Fuzzy Systems. Vol. 2 Nº 2, pp. 87-97. 2000.

[20] M.P. Hansen. "Generating a Diversity of Good Solutions to a Practical Combinatorial Problem using Vectorized Simulated Annealing". Technical report. Institute of Mathematical Modelling. Technical University of Denmark. Denmark. August 1997.

[21] P. Lucic and D. Teodorovic. "Simulated annealing for the multi-objective aircrew rostering problem". Transportation Research Part A. Vol. 33, pp.19-45. 1999.

[22] P. Czyzak and A. Jaszkiewicz. "Pareto simulated annealing-a metaheuristic technique for multiple-objective combinatorial optimization". Journal of Multi-Criteria Decision Analysis. Vol. 7, pp. 34-47. 1998.

[23] B. Suman and P. Kumar. "A survey of simulated annealing as a tool for single and multiobjective optimization". Journal of the Operational Research Society. Vol. 57 Nº 10, pp. 1143-1160. 2006.

[24] A. Nakib, H. Oulhadj and P. Siarry. "Non-supervised image segmentation based on multiobjective optimization ". Pattern Recognition Letters. Vol. 29 Nº 2, pp. 161-172. 2007.

[25] E. Aggelogiannaki and H. Sarimveis. "Simulated annealing algorithm for prioritized multiobjective optimization-implementation in an adaptive model predictive control configuration". IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics. Vol. 37 Nº 4, pp. 902-915. 2007.

[26] M. Hapke A. Jaszkiewicz and R. Slowinski. "Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization". Journal of Heuristics. Vol. 6 Nº 3, pp. 329-345. 2000. 

[27] G.T. Parks and A. Suppapitnarm. "Multiobjective optimizationof PWR reload core designs using simulated annealing". Mathematics & Computation, Reactor Physics and Environmental Analysis in Nuclear Applications. Vol. 2, pp. 1435-1444. Madrid, Spain. 1999.

[28] A. Suppapitnarm, G.T. Parks, K. Shea & P.J. Clarkson. "Conceptual Design of Bicycle Frames by Multiobjective Shape Annealing". Engineering Optimization. Vol. 36 Nº 2, pp. 165-188. 2004.

[29] G. Rabadi, RJ. Moraga and A. Al-Salem. "Heuristics for the unrelated parallel machine scheduling problem with setup times". Journal of Intelligent Manufacturing. Vol. 17 Nº 1, pp. 85-97. 2006.

 

 



Otros Artículos

# Título Ver
1
Algoritmo genético mejorado para la minimización de la tardanza total en un flowshop flexible con tiempos de preparación dependientes de la secuencia (2015)
Eduardo Salazar Hornig, René A. Sarzuri Guarachi
HTML | PDF
2
Método de aseguramiento de la calidad en una metodología de desarrollo de software: un enfoque práctico (2018)
Dante Carrizo, Andres Alfaro
PDF
3
Clasificación de género utilizando vectores de frecuencia basados en descriptores locales (2016)
Eduardo Aguilar-Torres, Juan Bekios-Calfa
HTML | PDF

Desarrollado por: Cristian Díaz Fonseca - cfonseca@matiasluke.cl