×

A permutation-translation simulated annealing algorithm for \(L_{1}\) and \(L_{2}\) unidimensional scaling. (English) Zbl 1084.62055

Summary: 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.

MSC:

62H99 Multivariate analysis
90C59 Approximation methods and heuristics in mathematical programming
65C60 Computational problems in statistics (MSC2010)
62-04 Software, source code, etc. for problems pertaining to statistics

Software:

pertsaus2
PDFBibTeX XMLCite
Full Text: DOI