The non-metric multidimensional scaling (nMDS) is a method for determining metric distances between objects using an appropriate transformation and analyzing the relation among configured objects, when it is difficult to configure objects in a Euclidean space due to non-metric dissimilarities between them. The transformation of non-metric dissimilarities into metric distances can be regarded as an optimization problem in which there are many local optima. Given that the conventional Taguchi-Oono algorithm utilizes the steepest descent method, it has a drawback in that the method can search a local optimum only. To alleviate this problem, in this paper, we applied a continuous simulated annealing based on a Gaussian distribution to the nMDS and proposed a new optimization algorithm which could escape from local optima and search for a global optimum more effectively. We tested the proposed algorithm in terms of benchmarking problems and found, with the analysis of the experimental results, that the proposed algorithm outperformed the Taguchi-Oono algorithm.