Using Genetic Algorithm in Clustering Problem for Weighted Oriented Graph

Optimization is a very important concept in any field of business, be it retail, finance, automotive or healthcare. The goal of optimization is to find a point or set of points in the search space by minimizing/maximizing the loss/cost function that gives the optimal solution for the problem at hand. In this case, clustering methods, data mining techniques and clustering optimization algorithms are of particular importance. In this context, metaheuristic algorithms, which include the genetic algorithm, become particularly popular and important. Thus, the aim of the paper is to examine the possibilities of using genetic algorithm in the clustering problem for weighted directed graph. Objectives: 1) to consider the peculiarities of using GA in optimization problems; 2) to propose a variant of solving the problem of partitioning some set of ISP users into groups according to a certain set of characteristics using GA; 3) to evaluate the efficiency of the proposed GA in comparison with the algorithm of limit enumeration. Research methods: methods of system analysis, applied and computational mathematics; experimental research; computer and simulation modeling. As a result of the research, the paper proposes an approach for solving the problem of clustering Internet users using a genetic algorithm. To take into account the specificity of the problem and to improve the efficiency of the genetic algorithm, heterogeneous chromosomes were used and modifications were made in the course of classical procedures of crossing and mutation. Conclusions. The developed algorithm was tested for performance in comparison with the limit search algorithm and its significant advantage in this indicator was shown. To take into account the specifics of the task and increase the efficiency of the GA, heterogeneous chromosomes were used. To achieve this, significant modifications were made to the classical procedures of crossing and mutation. The developed algorithm was tested for performance in comparison with the limit search algorithm and its significant advantage in this indicator was shown. The obtained comparison results allow us to assert that already for 150 units of the original set, solving the problem using the limit search method requires a disproportionately large amount of time. While the proposed GA provides a solution for a significantly larger problem dimension in a quite acceptable time.