Application of simulated annealing in metric multidimensional scaling

In Multidimensional Scaling, we want an Euclidean representation of a set of points described by a dissimilarity table. Since no exact solution is known, there is a large number of methods that give an approximated solution minimizing some criterion. This criterion is usually a least squares one, called Stress, that compares the known dissimilarities to the Euclidean distances calculated in representation. The best known methods are gradient descent-type and lead to local optima of Stress. Some other methods, based in a majorizing function (SMACOF method) or the Tunneling method, also cannot guarantee a global optimum. Finally, there are also implementations of genetic algorithms that are quite slow. We propose a simple implementation of simulated annealing that gives good results. We define a grid of the space of representation of the solution, and we go over this grid according to the Metropolis rule. The grid could be thinner as the control parameter, that plays the role of the temperature, tends to zero. We have compared the peformances of our method, and its results are comparable and sometimes better than those obtained with other methods.