Использование генетического алгоритма в задаче кластеризации для взвешенного ориентированного графа
(Стр. 93-101)

Оптимизация – очень важная концепция в любой сфере бизнеса, будь то розничная торговля, финансы, автомобилестроение или здравоохранение. Цель оптимизации – найти точку или набор точек в пространстве поиска, минимизируя/максимизируя функцию потерь/затрат, которая дает оптимальное решение для поставленной задачи. В данном случае особую значимость приобретают методы кластеризации, методы интеллектуального анализа данных и алгоритмы оптимизации кластеризации. В данном контексте особую популярность и значимость приобретают метаэвристические алгоритмы, к числу которых относится генетический алгоритм. Таким образом, цель статьи заключается в рассмотрении возможностей использования генетического алгоритма в задаче кластеризации для взвешенного ориентированного графа. Задачи: 1) рассмотреть особенности использования ГА в задачах оптимизации; 2) предложить вариант решения задачи разбиения некоторого множества пользователей провайдера интернет-услуг на группы в соответствии с определенным набором характеристик с использованием ГА; 3) оценить эффективность предложенного ГА по сравнению с алгоритмом предельного перебора. Методы исследования: методы системного анализа, прикладной и вычислительной математики; экспериментальные исследования; компьютерное и имитационное моделирование. В результате исследования в статье предложен подход для решения задачи кластеризации пользователей сети Интернет с использованием генетического алгоритма. Для учета специфики задачи и повышения эффективности работы генетического алгоритма были применены неоднородные хромосомы и внесены модификации в ход классических процедур скрещивания и мутации. Выводы. Разработанный алгоритм был исследован на быстродействие по сравнению с алгоритмом предельного перебора и показано значительное его преимущество по этому показателю. Для учета специфики задачи и повышения эффективности работы ГА были применены неоднородные хромосомы. Для этого были внесены существенные модификации в ход классических процедур скрещивания и мутации. Разработанный алгоритм был исследован на быстродействие по сравнению с алгоритмом предельного перебора и показано значительное его преимущество по этому показателю. Полученные результаты сравнения позволяют утверждать, что уже для 150 единиц исходного множества решение задачи с помощью метода предельного перебора требует несоизмеримо больших временных затрат. В то время как предложенный ГА дает решение при значительно большей размерности задачи за вполне приемлемое время.

ОБРАЗЕЦ ЦИТИРОВАНИЯ: Куликов А.А. Использование генетического алгоритма в задаче кластеризации для взвешенного ориентированного графа // Computational Nanotechnology. 2024. Т. 11. № 2. С. 93-101. DOI: 10.33693/2313-223X-2024-11-2-93-101. EDN: MULJLE

Ling Li, Xiangbing Zhou. An improved genetic algorithm with Lagrange and density method for clustering // Concurrency and Computation: Practice and Experience. 2020. No. 32.
Акопов А.С., Бекларян Г.Л. Многоагентный генетический алгоритм на основе нечеткой кластеризации при решении многокритериальных задач // Искусственные общества. 2020. № 2. С. 10–17.
Степанян И.В. Молекулярно-генетические алгоритмы кластеризации данных // Научно-техническая информация. Серия 2: Информационные процессы и системы. 2021. № 1. С. 1–8.
Heidari E., Movaghar A. A novel approach for clustering and routing in WSN using genetic algorithm and equilibrium optimizer // International Journal of Communication Systems. 2020. No. 35. Pp. 112–119.
Германчук М.С., Лемтюжникова Д.В., Лукьяненко В.А. Метаэвристические алгоритмы для многоагентных задач маршрутизации // Проблемы управления. 2020. № 6. С. 3–13.
Петров Т.И., Сафин А.Р., Низамиев М.Ф. Применение генетического алгоритма при разработке программного обеспечения для перебора материалов при оптимизации синхронных двигателей // Вестник Казанского государственного энергетического университета. 2022. № 2. С. 96–105.
Gola K.K., Singh B.M. Multi-objective hybrid capuchin search with genetic algorithm based hierarchical resource allocation scheme with clustering model in cloud computing environment // Concurrency and Computation: Practice and Experience. 2023. No. 35. Pp. 67–73.
Houshmand-Nanehkaran F., Lajevardi S.M. Optimization of fuzzy similarity by genetic algorithm in user-based collaborative filtering recommender systems // Expert Systems. 2022. No. 39. Pp. 39–45.
Аралбаев Р.А., Тарасов А.А. Задачи оптимизации и применение алгоритмов генетический алгоритм на практике // Инновации. Наука. Образование. 2021. № 48. С. 1645–1653.
Еремин Е.Л., Шеленок Е.А. Генетический алгоритм в задаче параметрической оптимизации гиперустойчивых систем управления // Вестник Тихоокеанского государственного университета. 2023. № 1. С. 29–38.
Üstün O., Bekiroğlu E. Design of highly effective multilayer feedforward neural network by using genetic algorithm // Expert Systems. 2020. No. 37. Pp. 135–142.
Cao Jianli, Chen Zhikui. Parallel genetic algorithm for N-Queens problem based on message passing interface-compute unified device architecture // Computational Intelligence. 2020. No. 36. Pp. 56–59.
Chanu Y.J., Singh Kh.M. A new hybrid image segmentation approach using clustering and black hole algorithm // Computational Intelligence. 2020. No. 39. Pp. 145–152.
Минитаева А.М., Векшин Р.Д., Шатилов А.А. Анализ различных видов генетических алгоритмов в задачах оптимизации // Технологии инженерных и информационных систем. 2022. № 1. С. 21–34.
Безгачев Ф.В., Галушин П.В., Рудакова Е.Н. Эффективная реализация инициализации и мутации в генетическом алгоритме псевдо-булевой оптимизации // E-Scio. 2020. № 4 (43). С. 224–231.
Бизянов Е.Е., Козлова И.С. Оптимизация процессов управления расписанием движения автотранспорта с использованием нечеткого генетического алгоритма // Экономический вестник Донбасского государственного технического университета. 2020. № 4. С. 49–55.
Baodan Sun, Yun Zhou. Bayesian network structure learning with improved genetic algorithm // International Journal of Intelligent Systems. 2022. No. 37. Pp. 123–129.
Chebouba B.N., Mellal M.A. Fuzzy multiobjective system reliability optimization by genetic algorithms and clustering analysis // Quality and Reliability Engineering International. 2020. No. 37. Pp. 178–183.
Денисов М.А., Сопов Е.А. Генетический алгоритм условной оптимизации для проектирования информативных признаков в задачах классификации // Сибирский аэрокосмический журнал. 2021. № 22. С. 18–31.
Белоусов А.О., Гордеева В.О. Сравнение генетического алгоритма и эволюционных стратегий при оптимизации полосковых модальных фильтров // Радиотехника и электроника. 2023. № 11. С. 1079–1089.

генетический алгоритм, кластеризация, оптимизация, пользователи, интернет, популяция, хромосомы.