A permutation-translation simulated annealing algorithm for L 1 and L 2 unidimensional scaling. Given a set of objects and a symmetric matrix of dissimilarities between them, Unidimensional Scaling is the problem of finding a representation by locating points on a continuum. Approximating dissimilarities by the absolute value of the difference between coordinates on a line constitutes a serious computational problem. This paper presents an algorithm that implements Simulated Annealing in a new way, via a strategy based on a weighted alternating process that uses permutations and point-wise translations to locate the optimal configuration. Explicit implementation details are given for least squares loss functions and for least absolute deviations. The weighted, alternating process is shown to outperform earlier implementations of Simulated Annealing and other optimization strategies for Unidimensional Scaling in run time efficiency, in solution quality, or in both.

References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Palubeckis, Gintaras: An improved exact algorithm for least-squares unidimensional scaling (2013)
  2. Vera, J.Fernando; Macías, Rodrigo; Heiser, Willem J.: Cluster differences unfolding for two-way two-mode preference rating data (2013)
  3. Žilinskas, Julius: Parallel branch and bound for multidimensional scaling with city-block distances (2012)
  4. Schepers, Jan; Van Mechelen, Iven; Ceulemans, Eva: The real-valued model of hierarchical classes (2011)
  5. Brusco, Michael J.; Köhn, Hans-Friedrich: Exemplar-based clustering via simulated annealing (2009)
  6. Vera, J.Fernando; Macías, Rodrigo; Heiser, Willem J.: A latent class multidimensional scaling model for two-way one-mode continuous rating dissimilarity data (2009)
  7. Vera, J.Fernando; Macías, Rodrigo; Heiser, Willem J.: A dual latent class unfolding model for two-way two-mode preference rating data (2009)
  8. Brusco, Michael J.; Köhn, Hans-Friedrich; Stahl, Stephanie: Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis (2008)
  9. Ceulemans, Eva; van Mechelen, Iven: CLASSI: A classification model for the study of sequential processes and individual differences therein (2008)
  10. Žilinskas, Antanas; Žilinskas, Julius: A hybrid method for multidimensional scaling using city-block distances (2008)
  11. Brusco, Michael; Steinley, Douglas: A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices (2007)
  12. Ceulemans, Eva; Van Mechelen, Iven; Leenen, Iwin: The local minima problem in hierarchical classes analysis: an evaluation of a simulated annealing algorithm and various multistart procedures (2007)
  13. Murillo, Alex; Vera, J.Fernando; Heiser, Willem J.: A permutation-translation simulated annealing algorithm for $L_1$ and $L_2$ unidimensional scaling (2005)