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

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.