Multimodal Evolutionary Algorithm for Multidimensional Scaling with City-Block Distances

摘要

?iame straipsnyje nagrin?jamos daugiamat?s skal?s su miesto kvartalo atstumais. ?iam metodui realizuoti reikalingas tikslo funkcijos su daug lokali?j? minimum? ta?k? ir galimu nediferencijuoja-mumu minimumo ta?kuose optimizavimas. Tyrimo tikslas yra sukurti greit? ir efektyv? globaliojo optimizavimo algoritm?, per?velgiant? vis? paie?kos srit? ir randant? gerus sprendinius. Siekiant i?vengti stagnacijos bloguose lokaliuosiuose minimuose, daugiamodalinis evoliucinis algoritmas yra naudojamas globaliajam optimizavimui. Dalimis kvadratin? ma?iausi?j? kvadrat? tikslo funkcijos su miesto kvartalo atstumais struktūra yra i?naudojama lokaliajam pagerinimui. Pasiūlytas algoritmas yra palygintas su literatūroje apra?ytais algoritmais. Nuodugniu skai?iuojamuoju tyrimu parodyta, kad pasiūlyto algoritmo rezultatai yra geriausi. Algoritmas su priderintomis parametr? reik?m?mis randa global?j? minimum? su didele tikimybe.%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.