Visualization of multidimensional data by means of Multidimensional Scaling (MDS) is a popular technique of exploratory data analysis widely usable, e.g. in analysis of bio-medical data, behavioral science, marketing research, etc. Implementations of MDS methods include a subroutine for an auxiliary global optimization problem. The latter is difficult because of high dimensionality, absence of overall smoothness, and a large number of local minima. In such a situation application of a genetic algorithm (GA) seems reasonable. A favorable assessment of application of GAs in MDS in previous publications is based on heuristic arguments without estimating quantitatively the precision of GA while applied to the solution of corresponding global optimization problems. Indeed, the estimation of precision is difficult because of complexity to find the actual global minimum not only in routine use but also in unique research experiments. Quantitatively the precision of GA was estimated, at least in the experimental problems of modest dimensionality, using global minima found by means of the developed parallel version of explicit enumeration algorithm. To cope with high complexity of the minimization problem a parallel version of GA is developed, and its efficiency for problem of higher dimensionality is investigated.