K-Means Genetic Algorithms with Greedy Genetic Operators
Joint Authors
Kazakovtsev, Lev
Rozhnov, Ivan
Shkaberina, Guzel
Orlov, Viktor
Source
Mathematical Problems in Engineering
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-16, 16 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-11-30
Country of Publication
Egypt
No. of Pages
16
Main Subjects
Abstract EN
The k-means problem is one of the most popular models of cluster analysis.
The problem is NP-hard, and modern literature offers many competing heuristic approaches.
Sometimes practical problems require obtaining such a result (albeit notExact), within the framework of the k-means model, which would be difficult to improve by known methods without a significant increase in the computation time or computational resources.
In such cases, genetic algorithms with greedy agglomerative heuristic crossover operator might be a good choice.
However, their computational complexity makes it difficult to use them for large-scale problems.
The crossover operator which includes the k-means procedure, taking the absolute majority of the computation time, is essential for such algorithms, and other genetic operators such as mutation are usually eliminated or simplified.
The importance of maintaining the population diversity, in particular, with the use of a mutation operator, is more significant with an increase in the data volume and available computing resources such as graphical processing units (GPUs).
In this article, we propose a new greedy heuristic mutation operator for such algorithms and investigate the influence of new and well-known mutation operators on the objective function value achieved by the genetic algorithms for large-scale k-means problems.
Our computational experiments demonstrate the ability of the new mutation operator, as well as the mechanism for organizing subpopulations, to improve the result of the algorithm.
American Psychological Association (APA)
Kazakovtsev, Lev& Rozhnov, Ivan& Shkaberina, Guzel& Orlov, Viktor. 2020. K-Means Genetic Algorithms with Greedy Genetic Operators. Mathematical Problems in Engineering،Vol. 2020, no. 2020, pp.1-16.
https://search.emarefa.net/detail/BIM-1201677
Modern Language Association (MLA)
Kazakovtsev, Lev…[et al.]. K-Means Genetic Algorithms with Greedy Genetic Operators. Mathematical Problems in Engineering No. 2020 (2020), pp.1-16.
https://search.emarefa.net/detail/BIM-1201677
American Medical Association (AMA)
Kazakovtsev, Lev& Rozhnov, Ivan& Shkaberina, Guzel& Orlov, Viktor. K-Means Genetic Algorithms with Greedy Genetic Operators. Mathematical Problems in Engineering. 2020. Vol. 2020, no. 2020, pp.1-16.
https://search.emarefa.net/detail/BIM-1201677
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1201677