Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization. (English) Zbl 1157.90533

Žilinskas, A.; Žilinskas, J.

Comput. Math. Appl. 52, No. 1-2, 211-224 (2006).

Summary: Multidimensional scaling is a widely used technique for visualization of multidimensional data. For the implementation of a multidimensional scaling technique a difficult global optimization problem should be solved. To attack such problems a hybrid global optimization method is developed combining evolutionary global search with local descent. A parallel version of the proposed method is implemented to enable solution of large scale problems in acceptable time. The results of the experimental investigation of the efficiency of the proposed method are presented.

MSC:

90C30	Nonlinear programming
90C59	Approximation methods and heuristics in mathematical programming
90C90	Applications of mathematical programming

Keywords:

multidimensional scaling; metaheuristics; global optimization; parallel algorithms

References:

[1]	Borg, I.; Groenen, P., Modern. Multidimensional Scaling (1997), Springer: Springer New York · Zbl 0862.62052
[2]	Cox, T.; Cox, M., Multidimensional Scaling (2001), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL · Zbl 1004.91067
[3]	De Leeuw, J.; Heiser, W., Theory of multidimensional scaling, (Krishnaiah, P. R., Handbook of Statistics (1982), North-Holland: North-Holland Amsterdam), 285-316
[4]	Törn, A.; Žilinskas, A., Global Optimization, Lecture Notes in Computer Science 350, ((1989), Springer: Springer Berlin), 1-250
[5]	Groenen, P., The Majorization Approach to Multidimensional Scaling (1993), DSWO: DSWO Amsterdam · Zbl 0898.62080
[6]	Everett, J. E., Algorithms for multidimensional scaling, (Chambers, L., The Practical Handbook of Genetic Algorithms (2001), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL), 203-233
[7]	Groenen, P.; Mathar, R.; Trejos, J., Global optimization methods for MDS applied to mobile communications, (Gaul, W.; Opitz, O.; Schander, M., Data Analysis: Scientific Models and Practical Applications (2000), Springer), 459-475
[8]	Mathar, R., A hybrid global optimization algorithm for multidimensional scaling, (Klar, R.; Opitz, O., Classification and Knowledge Organization (1996), Springer: Springer Berlin), 63-71
[9]	Mathar, R.; Zilinskas, A., On global optimization in two-dimensional scaling, Acta Applicandae Mathematicae, 33, 109-118 (1993) · Zbl 0792.60023
[10]	Press, W., Numerical Recipes in C++ (2002), Cambridge University Press: Cambridge University Press Cambridge
[11]	Kearsley, A.; Tapia, R.; Trosset, M., The solution of the metric STRESS and SSTRESS problems in multidimensional scaling using Newton’s method, Computational Statistics, 13, 369-396 (1998) · Zbl 0926.92002
[12]	Lange, K.; Hunter, D.; Yang, I., Optimization transfer using surrogate objective functions, Journal of Computational and Graphical Statistics, 9, 1, 1-59 (2000), (with discussion)
[13]	De Leeuw, J., Differentiability of Kruskal’s stress at a local minimum, Psychometrika, 149, 111-113 (1984)
[15]	Cantú-Paz, E., Efficient and Accurate Parallel Genetic Algorithms (2000), Kluwer Academic · Zbl 0963.68164
[16]	Message Passing Interface Forum, MPI: A message-passing interface standard (version 1.1), Technical Report (1995)
[17]	Fisher, R. A., The use of multiple measurements in taxonomy problems, Annals of Eugenics, 7, 179-188 (1936)
[18]	Brusco, M. J., A simulated annealing heuristics for unidimensional and multidimensional (city block) scaling of symmetric proximity matrices, Journal of Classification, 18, 3-33 (2001) · Zbl 1040.91080