Parallel genetic algorithm: assessment of performance in multidimensional scaling

ABSTRACT

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.

REFERENCES

• 1: W. Basalaj. Proximity Visualization of Abstract Data. http://www.pavis.org/essay, 2001.
• 2: I. Borg and P.J.F. Groenen. Modern Multidimensional Scaling: Theory and Applications, 2nd ed. Springer, New York, 2005.
• 3: M.J. Brusco. A simulated annealing heuristics for unidimensional and multidimensional (city-block) scaling of symmetric proximity matrices. Journal of Classification, 18(1):3--33, January 2001.
• 4: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 5: J.E. Everett. Algorithms for multidimensional scaling. In L.D. Chambers (ed.) The Practical Handbook of Genetic Algorithms, 2nd ed., pages 203--233. Chapman & Hall/CRC, 2001.
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: P.J.F. Groenen, R. Mathar, and W.J. Heiser. The majorization approach to multidimensional scaling for Minkowski distances. Journal of Classification, 12(1):3--19, March 1995.
• 8: P.J.F. Groenen. The Majorization Approach to Multidimensional Scaling. DSWO Press, Leiden, 1993.
• 9: P. Groenen, R. Mathar, and J. Trejos. Global optimization methods for MDS applied to mobile communications. In W. Gaul, O. Opitz, and M. Schander (eds.) Data Analysis: Scientific Models and Practical Applications, pages 459--475. Springer, 2000.
• 10: P.L. Leung and K. Lau. Estimating the city-block two-dimensional scaling model with simulated annealing. European Journal of Operational Research, 158(2):518--524, October 2004.
• 11: R. Mathar. A hybrid global optimization algorithm for multidimensional scaling. In R. Klar and O. Opitz (eds.) Classification and Knowledge Organization, pages 63--71. Springer, 1997.
• 12: R. Mathar and A. Žilinskas. On global optimization in two-dimensional scaling. Acta Applicandae Mathematicae, 33(1):109--118, October 1993.
• 13: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 14: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 15: L. Tsogo, M.-H. Masson, and A. Bardot. Recovery of the metric structure of a pattern of points using minimal information. IEEE Trans. Systems, Man and Cybernetics, Part A, 31(1):30--42, January 2001.
• 16: A. Varoneckas, A. Žilinskas, and J. Žilinskas. Multidimensional scaling using parallel genetic algorithm. In I.D.L. Bogle and J. Žilinskas (eds.) Computer Aided Methods in Optimal Design and Operations, pages 129--138. World Scientific, 2006.
• 17: A. ilinskas , J. ilinskas, Parallel hybrid algorithm for global optimization of problems occurring in MDS-based visualization, Computers & Mathematics with Applications, v.52 n.1-2, p.211-224, July, 2006 [doi>10.1016/j.camwa.2006.08.016]
• 18: Antanas Žilinskas , Julius Žilinskas, Two level minimization in multidimensional scaling, Journal of Global Optimization, v.38 n.4, p.581-596, August 2007 [doi>10.1007/s10898-006-9097-x]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming; Quadratic programming methods
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Performance

Keywords:
genetic algorithms, multidimensional scaling