Использование генетического алгоритма в задаче кластеризации для взвешенного ориентированного графа

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