Multimodal Evolutionary Algorithm for Multidimensional Scaling with City-Block Distances

Article type: Research Article

Authors: Redondo, Juana López | Ortigosa, Pilar Martínez | Žilinskas, Julius

Affiliations: Department of Computer Architecture and Technology, University of Granada, Periodista Daniel Saucedo Aranda, s/n. 18071 Granada, Spain, e-mail: jlredondo@atc.ugr.es | Department of Informatics, University of Almería, Campus de Excelencia Internacional Agroalimentario (ceiA3), Spain, e-mail: ortigosa@ual.es | Vilnius University Institute of Mathematics and Informatics, Akademijos 4, LT-08663 Vilnius, Lithuania, e-mail: julius.zilinskas@mii.vu.lt

Abstract: Multidimensional scaling with city-block distances is considered in this paper. The technique requires optimization of an objective function which has many local minima and can be non-differentiable at minimum points. This study is aimed at developing a fast and effective global optimization algorithm spanning the whole search domain and providing good solutions. A multimodal evolutionary algorithm is used for global optimization to prevent stagnation at bad local optima. Piecewise quadratic structure of the least squares objective function with city-block distances has been exploited for local improvement. The proposed algorithm has been compared with other algorithms described in literature. Through a comprehensive computational study, it is shown that the proposed algorithm provides the best results. The algorithm with fine-tuned parameters finds the global minimum with a high probability.

Keywords: multidimensional scaling, city-block distances, evolutionary algorithms, multimodal algorithms

Journal: Informatica, vol. 23, no. 4, pp. 601-620, 2012