Ir al contenido

Documat


New results with scatter search applied to multiobjective combinatorial and nonlinear optimization problems

  • Beausoleil, Ricardo P. [1]
    1. [1] Instituto de Cibernética Matemática y Física

      Instituto de Cibernética Matemática y Física

      Cuba

  • Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 13, Nº. 2, 2006, págs. 151-174
  • Idioma: inglés
  • DOI: 10.15517/rmta.v13i2.274
  • Enlaces
  • Resumen
    • español

      Este art´?culo introduce dos variantes de b´usqueda dispersa multiobjetivo para problemascontinuos y combinatorios, aplicando un enfoque de b´usqueda tab´u como unm´etodo generador de diversificaci´on. Una memoria de frecuencia y otros mecanismosde escape para diversificar la b´usqueda son utilizados. La relaci´on Pareto es aplicadapara designar un subconjunto de las mejores soluciones como conjunto de solucionesde referencia. Una funci´on de selecci´on llamada selecci´on de Kramer es usada paradividir las soluciones de referencia en dos subconjuntos. Las distancias Euclidianas yHamming son utilizadas como medida de desemejanza para hallar soluciones diversas como complemento de las soluciones actualmente Pareto a ser combinadas. Combinacioneslineales y reencadenamiento de trayectorias son usadas como m´etodos decombinaciones. El desempe˜no de estos enfoques es evaluado sobre varios problemasde prueba tomados de la literatura.Palabras clave: Objetivos m´ultiples, metaheur´?sticas, b´usqueda tab´u, b´usqueda dispersa,optimizaci´on no lineal.

    • English

      This paper introduces two variants of a multiple criteria scatter search to deal withnonlinear continuous and combinatorial problems, applying a tabu search approach asa diversification generator method. Frequency memory and another escape mechanismare used to diversify the search. A Pareto relation is applied in order to designatea subset of the best generated solutions to be reference solutions. A choice functioncalled Kramer Choice is used to divide the reference solution in two subsets. Euclideanand Hamming distances are used as measures of dissimilarity in order to find diversesolutions to complement the subsets of high quality current Pareto solutions to becombined. Linear combination and path relinking are used as a combination methods.The performance of these approaches are evaluated on several test problems taken fromthe literature.Keywords: Multiple objectives, metaheuristics, tabu search, scatter search, nonlinearoptimization.

  • Referencias bibliográficas
    • 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...
    • Beausoleil, R. (2004) “Bounded Variables Nonlinear Multiple Criteria Optimization using Scatter Search”, Revista de Matemática: Teoŕıa y...
    • Coello, C.A.; Toscano P.G. (2001) “A micro-genetic algorithm for multiobjective optimization”, In: E. Zitzler, K. Deb, L. Thiele, C.A. Coello...
    • Deb, K.; Agrawal, S.; Pratab, A.; Mayariban, T. (2000) “A fast elitist non-sorting genetic algorithms for multi-objective optimization”, NSGA-II,...
    • Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E. (2001) “Scalable test problems for evolutionary multi-objective optimization”, TIK-Tecnical...
    • Laarhoven P.J.; Aarts E.H.; Lenstra J.K. (1998) “Job shop scheduling by simulated anneling”, Report OS, Centre for Mathématiques, Ecole Polytechnique...
    • Glover, F. (1998) “A template for scatter search and path relinking in artificial evolution”, Lecture Notes in Computer Science (1363): 13–54....
    • Glover, F. (1994) “Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)”, Discrete Applied Mathematics...
    • 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...
    • 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...
    • Knowles, J.; Corne, D. (1999) The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multiobjective Optimization. University...
    • Schott, J.R. (1995) Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master’s thesis, Departament of Aeronautics,...
    • Schaffer, J.D. (1985) “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms”, In: Genetic Algorithms and their Applications,...
    • Van, V.; Lamont, G.B. (1998) “Evolutionary computation and convergence to a Pareto front”, In: J.R. Koza (Ed.), Late Breaking Papers at the...
    • Zitzler, E.; Kalyanmoy, D.; Thiele, L. TIK-Report, No.70, December 22, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute...
    • Zitzler, E.; Laumanns, M.; Thiele, L. (2001) “SPEA2: Improving the strength Pareto evolutionary algorithm”, Technical Report 103, Computer...

Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno