Bounded Variables nonlinear Multiple Criteria Optimization using Scatter search

• Beausoleil, Ricardo P. ^[1]
  1. [1] Centro de Matemática y Física Teórica
• Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 11, Nº. 1, 2004, págs. 17-40
• Idioma: inglés
• DOI: 10.15517/rmta.v11i1.235
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    El artículo presenta una adaptación del algoritmo de Búsqueda Dispersa Multiobjetivo para la solucionar problemas de optimización vectorial no lineales continuos, empleando un enfoque de Búsqueda Tabú como un método generador de soluciones diversas. Memoria de Frequencias y otros mecanismos de escapes son utilizados para diversificar la búsqueda. La relación Pareto es aplicada para designar un subconjunto de las mejores soluciones generadas a ser soluciones de referencias. Una función de selección denominada selección de Kramer se utiliza para dividir al conjunto de referencia en dos subconjuntos. La distancia Euclideana es usada como una medida de disimilaridad a modo de hallar soluciones diversas que complementen los subconjuntos de soluciones potencialmente Pareto de alta calidad a ser combinadas. Como método de conbinación usamos la combinación convexa. El desempeño de este enfoque es evaluado con diferentes problemas de pruebas tomados de la literatura.

  • English

    This paper introduces an adaptation of multiple criteria scatter search to deal with nonlinear continuous vector optimization problems on bounded variables, applying Tabu Search approach as diversification generator method. Frequency memory and another escape mechanism are used to diversify the search. A relation Pareto is apply in order to designate a subset of the best generated solutions to be reference solutions. A choice function called Kramer Selection is used to divide the reference solution in two subsets. The Euclidean distance is used as a measure of dissimilarity in order to find diverse solutions to complement the subsets of high quality current Pareto solutions to be combined. Convex combination is used as a combined method. The performance of this approach is evaluated on several test problems taken from the literature.

• Referencias bibliográficas
  • Battiti, R.; Tecchiolli, G. (1994) “The reactive tabu search”, ORSA Journal on Computing 6(2): 126–140.
  • Battiti, R. (1996) “Reactive search: toward self-tuning heuristics”, in: Modern Heuristic Search Methods, chapter 4, V.J. Rayward-Smith, I.H....
  • Beausoleil, R. (2001) “Multiple criteria scatter search”, Proceedings of 4th Metaheuristics International Conference, Jorge Pinho de Sousa...
  • Binh, T.T.; Korn, U. (1996) “An evolution strategy for the multiobjective optimization”, Institute for Automation, Magdeburg.
  • Coello Coello, C.A. (1999) “A comprensive survey of evolutionary-based multiobjective optimization techniques”, Knowledge and Information...
  • Cvetkovic, D.; Parmee, I.C. (1999) “Use of preference for GA-based multi-objective optimization”, PEDC, University of Plymouth.
  • Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E. (2001) “Scalable test problems for evolutionary multi-objective optimization”, TIK-Tecnical...
  • Glover, F. (1989) “Tabu search”, part I, ORSA Journal of Computing 1(3): 190–206.
  • Glover, F. (1993) “Tabu thresholding: improved search by nonmonotonic trayectories”, ORSA Journal on Computing.
  • Glover, F.; Laguna, M. (1993) “Modern heuristic techniques for combinatorial problems”, John Wiley & Sons, Inc., chapter 3: 70–147.
  • Glover, F. (1994) “Tabu Search for nonlinear and parametric optimization (with links to genetic algorithms)”, Discrete Applied Mathematics...
  • Glover, F. (1998) “A template for scatter search and path relinking”, in: Artificial Evolution, Lecture Notes in Computer Science 1363, J.-K....
  • Glover, F. (1999) “Scatter search and path relinking”, in: New Methods in Optimization, D. Corne, M. Dorigo & F. Glover (Eds.), McGraw-Hill.
  • Glover, F.; Laguna, M.; Martí, R. (s.f.) “Scatter search tutorial for a class of non-linear optimization problem on bounded variables”.
  • Grignon, P.; Fadel, G.M. (1999) “Multiobjective optimization by iterative genetic algorithm”, Proceedings of DETC 99, ASME Design Engineering...
  • Horn, J.; Nafpliotis, N.; Goldberg, D.E. (1994) “A niched Pareto genetic algorithm for multiobjective optimization”, ICEC’94, IEEE: 82–87.
  • Keeney, R.L.; Raiffa H. (1976) Decision with Multiple Objectives: Preference and Value Tradeoffs. Wiley, New York.
  • Knowles, J.; Corne, D. (1999) “The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimization”, University...
  • Makarov, I. M.; Vinogradskaia, T. M; Rubinski, A.A; Sokolov. V. B. (1982) Choice Theory and Decision Making. Nauka, Moscow (in Russian).
  • Molyneaux, A. K.; Leyland, G.B.; Favrat, D. (2001) “A new clustering evolutionary multi-objective optimisation technique”, Proceeding ISAS2001,...
  • Schaffer, J.D. (s.f.) Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. Unpublished doctoral dissertation, Vanderbilt...
  • Sen, P; Yang, J.B. (1998) Multiple Criteria Decision Support in Engineering Design. Springer-Verlag.
  • Vol’ski V. I. (1982) “Application of the Kramer method to identifying part of a Pareto set in multi-criteria optimization”, Automation and...
  • “Genetic algorithms with gender for multi-function optimization”, EPCC-SS92-01.