Palabras clave
metaheuristics
tabu search
scatter search
nonlinear optimization
Objetivos múltiples
metaheurísticas
búsqueda tabú
búsqueda dispersa
optimización no lineal
Cómo citar
Resumen
Este artículo introduce dos variantes de búsqueda dispersa multiobjetivo para problemas continuos y combinatorios, aplicando un enfoque de búsqueda tabú como un método generador de diversificación. Una memoria de frecuencia y otros mecanismos de escape para diversificar la búsqueda son utilizados. La relación Pareto es aplicada para designar un subconjunto de las mejores soluciones como conjunto de soluciones de referencia. Una función de selección llamada selección de Kramer es usada para dividir las soluciones de referencia en dos subconjuntos. Las distancias Euclidianas y Hamming son utilizadas como medida de desemejanza para hallar soluciones diversas como complemento de las soluciones actualmente Pareto a ser combinadas. Combinaciones lineales y reencadenamiento de trayectorias son usadas como métodos de combinaciones. El desempeño de estos enfoques es evaluado sobre varios problemas de prueba tomados de la literatura.
Citas
Balas, E. “Machine sequencing via disjunctive graphs: an implicit enumeration algorithm”, Ops.Res 17 (6): 927–1136.
Beausoleil, R.P. (2001) “Multiple criteria scatter search”, MIC’2001-4th Metaheuristics International Conference. Porto, Portugal.
Beausoleil, R.P. (2002) “A tabu search approach for weighted tardiness with sequence-dependent setups in one-machine problem”, Revista de Matemática: Teoŕıa y Aplicaciones 9(1): 35–46.
Beausoleil, R. (2004) “Bounded Variables Nonlinear Multiple Criteria Optimization using Scatter Search”, Revista de Matemática: Teoŕıa y Aplicaciones 11 (1): 17–40.
Coello, C.A.; Toscano P.G. (2001) “A micro-genetic algorithm for multiobjective optimization”, In: E. Zitzler, K. Deb, L. Thiele, C.A. Coello & D. Corne (Eds.), First International Conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Sciences No.1993, Springer-Verlag: 216–140
Deb, K.; Agrawal, S.; Pratab, A.; Mayariban, T. (2000) “A fast elitist non-sorting genetic algorithms for multi-objective optimization”, NSGA-II, KanGal, report 200001, Indian Institute of Technology, Kanpur, India.
Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E. (2001) “Scalable test problems for evolutionary multi-objective optimization”, TIK-Tecnical Report (112).
Laarhoven P.J.; Aarts E.H.; Lenstra J.K. (1998) “Job shop scheduling by simulated anneling”, Report OS, Centre for Mathématiques, Ecole Polytechnique Fédérale de Lausanne.
Glover, F. (1998) “A template for scatter search and path relinking in artificial evolution”, Lecture Notes in Computer Science (1363): 13–54. J.-K,Hao, E.Lutton, E.Ronald, M.Schoenauer and D.Snyers (Eds), Springer.
Glover, F. (1994) “Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)”, Discrete Applied Mathematics (40): 231–255.
Glover, F.; Laguna M. (1993) “Modern Heuristic Techniques for Combinatorial Problems”, Halsted Press, John Wiley & Sons, Inc.: 70–147.
Glover, F.; Laguna, M.; Mart́ı, R. “Scatter Search Tutorial for a class of non-linear optimization problem on bounded variables”.
Makarov, I.M.; Vinogradskaia, T.M.; Rubinski, A.A; Sokolov, V.B. (1982) Choice Theory and Decision Making. Nauka, Moscu.
Rubin, P.A.; Ragatz, G.L. (1995) “Scheduling in a sequence dependent setup environment with genetic search”, Computers and Operation Research (22): 85–99.
Pratyush, S.; Jian-Bo, Y. (1998) Multiple criteria decision support in engineering design, Springer-Verlag.
Schaffer, J.D. (1985) “Multiple objective optimization with vector evaluated genetic algorithms”, Unpublished doctoral dissertation, Vanderbilt University.
Knowles, J.; Corne, D. (1999) The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multiobjective Optimization. University of Reading, UK.
Schott, J.R. (1995) Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master’s thesis, Departament of Aeronautics, Massachusetts Institute of Technology, Cambrige, Massachusetts.
Schaffer, J.D. (1985) “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms”, In: Genetic Algorithms and their Applications, Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum, Hillsdale, New Jersey: 93–100
Van, V.; Lamont, G.B. (1998) “Evolutionary computation and convergence to a Pareto front”, In: J.R. Koza (Ed.), Late Breaking Papers at the Genetic Programming 1998 Conference, Stanford University, CA: 221–228
Zitzler, E.; Kalyanmoy, D.; Thiele, L. TIK-Report, No.70, December 22, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland.
Zitzler, E.; Laumanns, M.; Thiele, L. (2001) “SPEA2: Improving the strength Pareto evolutionary algorithm”, Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.