A simulated annealing heuristic for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices. (English) Zbl 1040.91080

Summary: This paper presents a heuristic for uni- and multidimensional (city-block) scaling of symmetric proximity matrices. The heuristic begins with the partition of each coordinate axis into equally spaced discrete points. A simulated annealing algorithm is used to search the lattice defined by these points with the objective of minimizing either a least-squares or least absolute deviation loss function. The solution obtained by the simulated annealing algorithm is subsequently refined by passing the object permutations for each dimension to a postprocessor that finds a locally optimal set of coordinates. Experimental testing was conducted for uni- and two-dimensional (city-block) scaling using a well-studied proximity matrix. Although the simulated annealing based heuristic is effective in its own right, the results herein suggest that perhaps its greatest utility is the provision of very good starting solutions for combinatorial algorithms designed for uni- and multidimensional scaling.


91C15 One- and multidimensional scaling in the social and behavioral sciences
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
Full Text: DOI