APPLICATION OF SIMULATED ANNEALING IN METRIC MULTIDIMENSIONAL SCALING

Abstract

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 quiet slow. We propose a simple implementation of simulated annealing that gives good results. We define a grid of the space of representatrion of the solution, and we go over this grid according to the Metropolis
rule. The grid could be thiner as the control parameter, that plays the role of the temperature, tend to zero. We have compared the performances of our method, and its results are comparable and sometimes better than those obtained with other methods