Тип публикации: статья из журнала
Год издания: 2021
Ключевые слова: clustering, cuda, genetic algorithm, mutation operator, p-median problem
Аннотация: The continuous p-median problem is a classical unconstrained global optimization model of unsupervised machine learning and location theory where the aim is to find p points (medians) so that the sum of distances from known demand points to the closest of the p sought points reaches its minimum. The problem is NP-hard, and the reseПоказать полностьюarchers focus on the development of heuristic algorithms. A greedy agglomerative procedure starts its search from a solution with an excessive number of medians K>pand combines the elimination of the medians with local search procedures. Genetic algorithms with the crossover operator based on greedy agglomerative procedures are capable of obtaining rather precise results. However, they are computationally expensive, which limits their scope for mediumscale problems. In the case of running such algorithms on massive parallel processing systems with large-scale problems, the population degeneration plays more important role. We propose hybrid genetic algorithms with both crossover and mutation operators involving the greedy agglomerative procedures and partially isolated subpopulations (islands) for the p-median problem. Computational experiments show the comparative efficiency of new algorithmic combinations and demonstrate that with an increase in the input data volume, the instruments for maintaining the population diversity improve the obtained results. © 2021 International Journal of Artificial Intelligence.
Журнал: International Journal of Artificial Intelligence
Выпуск журнала: Vol. 19, Is. 2
Номера страниц: 152-194
ISSN журнала: 09740635
Издатель: Centre for Environment and Socio-Economic Research Publications