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

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

Конференция: Springer Science and Business Media Deutschland GmbH; 6 July 2020 through 10 July 2020; 6 July 2020 through 10 July 2020

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

Идентификатор DOI: 10.1007/978-3-030-58657-7_28

Ключевые слова: clustering, genetic algorithm, greedy agglomerative procedure, k-means

Аннотация: Progress in the development of automatic grouping (clustering) methods, based on solving the p-median and similar problems, is mainly aimed at increasing the computational efficiency of the algorithms, their applicability to larger problems, accuracy, and stability of their results. The researchers’ efforts are focused on the development of compromise heuristic algorithms that provide a fairly quick solution with minimal error. The Genetic Algorithms (GAs) with greedy agglomerative crossover procedure and other special GAs for the considered problems demonstrate the best values of the objective function (sum of squared distances) for many practically important problems. Usually, such algorithms do not use any mutation operator, which is common for other GAs. We propose new GAs for the k-means problem, which use the same procedures as both the crossover and mutation operators. We compared a simple GA for the k-means problem with one-point crossover and its modifications with the uniform random mutation and our new crossover-like mutation. In addition, we compared the GAs with greedy heuristic crossover procedures to their modifications which include the crossover-like mutation. The comparison results show that the idea of our new mutation operator is able to improve significantly the results of the simplest GA as well as the genetic algorithms with greedy agglomerative crossover operator. © 2020, Springer Nature Switzerland AG.

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

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

Номера страниц: 350-362

ISSN журнала: 18650929

• Kazakovtsev L. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation, Siberian Federal University, prosp. Svobodny 79, Krasnoyarsk, 660041, Russian Federation)
• Shkaberina G. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation)
• Rozhnov I. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation, Siberian Federal University, prosp. Svobodny 79, Krasnoyarsk, 660041, Russian Federation)
• Li R. (Reshetnev Siberian State University of Science and Technology, prosp. Krasnoyarskiy Rabochiy 31, Krasnoyarsk, 660031, Russian Federation)
• Kazakovtsev V. (ITMO University, Kronverksky pr. 49, St. Petersburg, 197101, Russian Federation)

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