TITLE:
A Heuristic Search Approach to Multidimensional Scaling
AUTHORS:
Patrick R. McMullen
KEYWORDS:
Optimization, Search, Heuristic
JOURNAL NAME:
American Journal of Operations Research,
Vol.12 No.5,
September
15,
2022
ABSTRACT: This
research effort presents an approach to accomplish Multidimensional Scaling
(MDS) via the heuristic approach of Simulated Annealing. Multidimensional
scaling is an approach used to convert matrix-based similarity (or
dissimilarity data) into spatial form, usually via two or three dimensions.
Performing MDS has several important applications—Geographic Information Systems, DNA
Sequencing, and Marketing Research are just a few. Traditionally, classical MDS
decomposes the similarity or dissimilarity matrix into its eigensystem and uses
the eigensystem to calculate spatial coordinates. Here, a heuristic
search-based approach is used to find coordinates from a dissimilarity matrix
that minimizes a cost function. The proposed methodology is used over a variety
of problems. Experimentation shows that the presented methodology consistently
outperforms solutions obtained via the classical MDS approach, and this
approach can be used for other important applications.