Keywords
tabu search
combinatorial optimization
discretization
escalamiento multidimensional métrico
análisis de proximidades
búsqueda tabú
optimización combinatoria
discretización
How to Cite
Abstract
We apply tabu search (TS) in metric multidimensional scaling, obtaining good results comparable to those obtained with simulated annealing. A state in TS is a configuration of n points in a p dimensional space, and a neighbour is defined by the translation of length h of one or more coordinates of a point.
References
Bouroche, J.-M. et al. (1977) Analyse des Données en Marketing. Masson, Paris.
Cox, T.; Cox, M. (1995) Multidimensional Scaling. Chapman & Hall, Londres.de Leeuw, J. (1988) “Convergence of the majorization method for multidimensional scaling” Journal of Classification 5:163–180.
Glover, F. (1989) “Tabu search - Part I”, ORSA J. Comput. 1: 190–206.
Glover, F. (1990) “Tabu search - Part II”, ORSA J. Comput. 2: 4–32.
Groenen, P.J.F. (1993) “A comparison of two methods for global optimization in multidimensionalscaling”, in O. Opitz, B. Lausen & R. Klar (Eds.) Information and Classification. Springer-Verlag, Berlin: 145–155
Groenen, P.J.F.; Mathar, R.; Trejos, J. (2000) “Global optimization methods for multidimensional scaling applied to mobile communications”, in W. Gaul, O. Opitz, M. Schader (Eds.) Data Analysis. Scientific Modeling and Practical Application. Springer-Verlag, Berlin: 459–469.
Kruskal, J. (1964a) “Multidimensional scaling by optimizing goodness of fit to a non metric hypothesis” Psychometrika 29: 1–27.
Kruskal, J. (1964b) “Non-metric multidimensional scaling: a numerical method” Psychometrika 29: 115–129.
Kruskal, J. (1976) “More factors than subjects, test and treatments: an indeterminacy theorem for canonical decomposition and individual differences”, Psychometrika 41: 281–293.
Mathar, R. (1995) “A genetic algorithm for multidimensional scaling”. Internal Report, RWTH, Aachen.
Mathar, R.(1997) “A hybrid global optimization algorithm for multidimensional scaling”, Preprint, Institut für Statistik, RWTH Aachen.
Murillo, A.; Piza, E.; Trejos, J. (2000) “Combinatorial optimization heuristics in partitioning with non euclidean distances”, Preprint, CIMPA, San José.
Ngouenet, R.F. (1995) Analyse Géométrique des Données de Dissimilarité par la Multidimension-al Scaling: une Approche Parallèle Basée sur les Algorithmes Génétiques. Application aux Séquences Biologiques. Thèse de Doctorat, Université de Rennes I, Rennes.
Torgerson, W. S. (1958) Theory and Methods of Scaling. John Wiley & Sons, New York.
Trejos, J.; Murillo, A.; Piza, E. (1998) “Global stochastic optimization for partitioning”, in A. Rizziet al. (Eds.) Advances in Data Science and Classification, Springer–Verlag, Berlin: 185–190.
Trejos, J.; Villalobos, M. (1998) “Análisis de proximidades usando sobrecalentamiento simulado” in W. Castillo & J. Trejos (Eds.) XI Simposio Internacional de Métodos Matemáticos Aplicados a las Ciencias, UCR–ITCR, Costa Rica.
Trejos, J.; Villalobos, M. (1999) “Use of simulated annealing in metric multidimensional scaling”, in: M. Greenacre & J. Blasius (Eds.) Large Scale Data Analysis Conference, Cologne, May 1999.
Trejos, J.; Castillo, W.; González, J.; Villalobos, M. (2000) “Application of simulated annealing in some multidimensional scaling problems”, in: H.A.L. Kiers, J.-P. Rasson, P.J.F. Groenen & M. Schader (Eds.) Data Analysis, Classification, and Related Methods, Springer-Verlag, Berlin: 297–302.
Trejos, J. & Castillo, W. (2000) “Simulated annealing optimization for two-mode partitioning”, in: W. Gaul & R. Decker (Eds.) Classification and Information Processing at the Turn of the Millennium, Springer-Verlag, Berlin: 135–142.
Villalobos, M. (1998) Optimización Estocástica para el Análisis de Proximidades. Tesis de Maestría, Universidad de Costa Rica, San José.