Using Genetic Algorithm in Clustering Problem for Weighted Oriented Graph
( Pp. 93-101)

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.

Kulikov A.A. Using Genetic Algorithm in Clustering Problem for Weighted Oriented Graph. Computational Nanotechnology. 2024. Vol. 11. No. 2. Pp. 93–105. (In Rus.). 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.
Akopov A.S., Beklaryan G.L. Multi-agent genetic algorithm based on fuzzy clustering for solving multicriteria problems. Artificial Societies. 2020. No. 2. Pp. 10–17. (In Rus.)
Stepanyan I.V. Molecular genetic algorithms for data clustering. Scientific and Technical Information. Series 2: Information Processes and Systems. 2021. No. 1. Pp. 1–8. (In Rus.)
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.
Germanchuk M.S., Lemtyuzhnikova D.V., Lukyanenko V.A. Metaheuristic algorithms for multi-agent routing problems. Management Problems. 2020. No. 6. Pp. 3–13. (In Rus.)
Petrov T.I., Safin A.R., Nizamiev M.F. Application of a genetic algorithm in the development of software for material selection in the optimization of synchronous motors. Bulletin of the Kazan State Energy University. 2022. No. 2. Pp. 96–105. (In Rus.)
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.
Aralbaev R.A., Tarasov A.A. Optimization problems and application of genetic algorithm algorithms in practice. Innovation. Science. Education. 2021. No. 48. Pp. 1645–1653. (In Rus.)
Eremin E.L., Shelenok E.A. Genetic algorithm in the problem of parametric optimization of hyperstable control systems. Bulletin of the Pacific State University. 2023. No. 1. Pp. 29–38. (In Rus.)
Ü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.
Minitaeva A.M., Vekshin R.D., Shatilov A.A. Analysis of various types of genetic algorithms in optimization problems. Technologies of Engineering and Information Systems. 2022. No. 1. Pp. 21–34. (In Rus.)
Bezgachev F.V., Galushin P.V., Rudakova E.N. Efficient implementation of initialization and mutation in a pseudo-Boolean optimization genetic algorithm. E-Scio. 2020. No. 4 (43). Pp. 224–231. (In Rus.)
Bizyanov E.E., Kozlova I.S. Optimization of vehicle scheduling management processes using a fuzzy genetic algorithm. Economic Bulletin of Donbass State Technical University. 2020. No. 4. Pp. 49–55. (In Rus.)
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.
Denisov M.A., Sopov E.A. Genetic algorithm of conditional optimization for designing informative features in classification problems. Siberian Aerospace Journal. 2021. No. 22. Pp. 18–31. (In Rus.)
Belousov A.O., Gordeeva V.O. Comparison of genetic algorithm and evolutionary strategies in optimizing stripline modal filters. Radio Engineering and Electronics. 2023. No. 11. Pp. 1079–1089. (In Rus.)

genetic algorithm, clustering, optimization, users, Internet, population, chromosomes.