Сибирский федеральный университет

Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций

Конференция: International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021

Год издания: 2021

Идентификатор DOI: 10.1007/978-3-030-86433-0_13

Ключевые слова: agglomerative clustering, cluster analysis, facility location, genetic algorithm, p-median

Аннотация: The continuous p-median problem is a classical global optimization model used both for finding optimal locations of facilities on a plane, and as a clustering model. The problem is to find p points (medians) such that the sum of the distances from known demand points to the nearest median is minimal. Such a clustering model is less sensitive to “outliers” (separately located demand points that are not included in any cluster), compared with k-means models. Many heuristic approaches were proposed for this NP-hard problem. The genetic algorithms with the greedy agglomerative crossover operator are some of the most accurate heuristic methods. However, a parameter of this operator (parameter r) determines the efficiency of the whole genetic algorithm. The optimal value of this parameter is hardly predictable based on numerical parameters of the problem such as the numbers of demand points and medians. We investigate its influence on the result of the algorithm, and also propose the use of an exploratory search procedure for adjusting it. The advantages of the self-adjusting algorithm are shown for problems with a data volume of up to 2,075,259 objects. © 2021, Springer Nature Switzerland AG.

Журнал: Communications in Computer and Information Science

Выпуск журнала: Vol. 1476 CCIS

Номера страниц: 184-200

ISSN журнала: 18650929

Издатель: Springer Science and Business Media Deutschland GmbH

• Kazakovtsev L. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation, Siberian Federal University, 79 Svobodny pr., Krasnoyarsk, 660041, Russian Federation)
• Rozhnov I. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation)
• Nasyrov I. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation)
• Orlov V. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation)

• Scopus
• Ядро РИНЦ (eLIBRARY.RU)