Analysis of the Results of Applying the Bee Colony Method in the Problem of Coloring General Graphs

Purpose of research. We have discovered a wide range of problems that are important in practice and which can be reduced in polynomial time to discrete combinatorial optimization problems, many of which can be solved using graph theory. One of these tasks is finding the chromatic number of a graph and its corresponding coloring. Taking into account the fact that the combinatorial problem of finding the chromatic number of a graph belongs to the complexity class and does not allow obtaining an optimal solution in a rational time for problems of practically important dimension, the search for a suitable heuristic method that allows obtaining high-quality solutions with low costs required for computation is demanded and relevant. The aim of the study is to analyze the results of using the bee colony method in the task at hand. The tasks of this research are: description of algorithmic techniques in a formalized form, which make it possible to apply the bee colony method in the problem to be solved, making modifications to the bee colony method that increase the efficiency of the method, namely the quality of the resulting final colorings, as well as the determination of factors affecting the quality and the time spent in finding solutions.
Methods. To conduct research in the selected area, computational experiments were organized based on the use of heuristic methods in the problem under consideration. Meta-optimization of the tuning parameters of the methods and determination of their convergence rate was carried out, as well as a comparison of the quality and time of obtaining solutions.
Results. As a result of the study, the convergence rate of the method was found to be higher than that of the random walk method; the dependence of the quality of the resulting final colorings on the graph size N and density d was found. It was found that the chosen method is faster than the method of weighted random enumeration with the variation of vertices according to the minimum of admissible colors on »67% , which currently generates solutions with the lowest chromatic number, while losing quality to it on »7% . A higher rate of convergence was noticed when compared with the method of random walks, the principle of which is the same as that of foraging bees.
Conclusion. It was found that the bee colony method finds colorings with the same average chromatic number in fewer iterations than the random walk method, i.e. it has a higher convergence rate, while remaining significantly fast relative to the method of random search with a variation of vertices to reduce the allowed colors.

1. Zakrevsky A.D., Pottosin Yu.V. Dekompozitsiya parallel'nykh algoritmov logicheskogo upravleniya po zadannomu razbieniyu mnozhestva predlozhenii [Decomposition of parallel logic control algorithms by a given partition of the set of sentences]. A i VT = A and VT, 1985, no. 4, pp. 65-72 (In Russ.).

2. Chaitin Gregory J., Auslander Mark A., Chandra Ashok K., Cocke John, Hopkins Martin E., Peter W. Markstein. Register allocation via coloring. Computer Languages, 1981, pp. 47-57. https://doi.org/10.1016/0096-0551(81)90048-5.

3. Keedwell A.D., Dénes J. Latin Squares and their Applications. Elsevier, 2015, 438 p. https://doi.org/10.1016/C2014-0-03412-0.

4. Filonenko I.N., Chebotarev M.V. [Graph coloring algorithm and its application in the field of computer networks]. Tekhnika i tekhnologii, politika i ehkonomika: problemy i perspektivy [Engineering and technology, politics and economics: problems and prospects]. Kolomna, 2018, pp. 162-68 (In Russ.). https://www.elibrary.ru/item.asp?id=35587418.

5. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Bioinspirirovannyi algoritm komponovki blokov EVA na osnove modifitsirovannoi raskraski grafa [Bioinspired layout algorithm for EVA blocks based on modified graph coloring]. Izvestiya Yuzhnogo federal'nogo universiteta = Proceedings of the Southern Federal University, 2015, no. 4 (165), pp. 6-14 (In Russ.). https://www.elibrary.ru/item.asp?id=23693391.

6. Murzakov D.E., Zenkov M.A., Zhukov A.D., Tishin V.V. Primenenie algoritma posledovatel'noi raskraski grafa v sotovoi seti [Application of a sequential graph coloring algorithm in a cellular network]. Estestvennye i matematicheskie nauki v sovremennom mire = Natural and Mathematical Sciences in the Modern World, 2015, no. 31, pp. 22-32 (In Russ.). https://www.elibrary.ru/item.asp?id=23570102.

7. Kalyuka V.I., Ostapenko S.A., Kobak V.G., Zubakin V.V., Morozov I.V. Reshenie zadachi raskraski vzveshennogo grafa dlya myagkogo raspredeleniya resursa propusknoi sposobnosti v setyakh besprovodnogo abonentskogo dostupa [Solving the problem of coloring a weighted graph for soft distribution of the bandwidth resource in wireless subscriber access networks]. Izvestiya vysshikh uchebnykh zavedenii. Severokavkazskii region. Tekhnicheskie nauki = Proceedings of Higher Educational Institutions. North Caucasian Region. Technical Science, 2015, no. 4 (185), pp. 3-8 (In Russ.). https://doi.org/10.17213/0321-2653-2015-4-3-8.

8. Makoshenko D.V. Naznachenie peremennykh na registry s pomoshch'yu drevovidnogo parametricheskogo algoritma raskraski grafa [Assigning Variables to Registers Using a Tree-like Parametric Graph Coloring Algorithm]. Informatsionnye tekhnologii = Information Technology, 2010, no. 6, pp. 41-46 (In Russ.). https://www.elibrary.ru/item.asp?id=14998776.

9. Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs, Second Edition. Chapman & Hall/CRC, 2006, 1016 p. http://en.bookfi.net/book/643841.

10. Garey M., Johnson D. Vychislitelnyye mashiny i trudnoreshayemyye zadachi [Computers and Intractability]. Moscow, 1982. 416 p. (In Russ.). https://b-ok.cc/book/437794/d9ea2f.

11. Duffy, K., O'Connell, N., Sapozhnikov, A. Complexity analysis of a decentralised graph colouring algorithm. Information Processing Letters, July 2008, vol. 107, is. 2, pp. 60- 63. https://doi.org/10.1016/j.ipl.2008.01.002.

12. Karaboga D.D. An Idea Based On Honey Bee Swarm for Numerical Optimization. Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005. https://abc.erciyes.edu.tr/pub/tr06_2005.pdf.

13. Pham D.T., Ghanbarzadeh А., Кос E., Otri S., Rahim S., Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, 2005. https://doi.org/10.1016/B978-008045157-2/50081-X.

14. Vatutin E.I., Titov V.S., Yemel'yanov S.G. Osnovy diskretnoi kombinatornoi optimizatsii [Basics of discrete combinatorial optimization]. Moscow, Argamak-Media Publ., 2016, 270 p. (In Russ.). https://www.elibrary.ru/item.asp?id=25770934.

15. Yang X.S. Nature-inspired Metaheuristic Algorithms. Luniver Press, 2010, pp. 81- 95. https://www.academia.edu/457296/Nature-inspired_metaheuristic_algorithms.

16. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi [Modern search engine optimization algorithms. Algorithms inspired by nature]. Moscow, MGTU them. N.E. Bauman Publ., 2014. 446 p. (In Russ.). https://www.elibrary.ru/item.asp?id=25070137.

17. Hamming R.W. Error detecting and error correcting codes. Bell System Technical Journal, 1950, vol. 29, pp. 147-160. https://doi.org/10.1002/j.1538-7305.1950.tb00463.x.

18. Levenshteyn V.I. Dvoichnye kody s ispravleniem vypadenii, vstavok i zameshchenii simvolov [Binary Codes for Correcting Dropouts, Inserts, and Symbol Substitutions]. Doklady akademii nauk SSSR = Reports of the USSR Academy of Sciences, 1965, vol. 163, no. 4, pp. 845-848 (In Russ.). http://mi.mathnet.ru/dan31411.

19. Vatutin. E.I., Titov V.S. Osobennosti metaoptimizatsii algoritma pchelinoi kolonii v zadache poiska kratchaishego puti v grafe pri nalichii ogranichenii na plotnost' grafa [Features of meta-optimization of the bee colony algorithm in the task of finding the shortest path in a graph in the presence of restrictions on the graph density]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University, 2016, no. 2 (19), pp. 52-65 (In Russ.). https://www.elibrary.ru/item.asp?id=26396211.

20. Pshenichnykh A.O., Gvozdeva S.N., Vatutin E.I. O vliyanii poryadka rassmotreniya vershin pri poiske raskrasok grafov obshchego vida s ispol'zovaniem zhadnogo algoritma [On the influence of the order of consideration of vertices in the search for colorings of graphs of a general form using a greedy algorithm]. Vysokoproizvoditel'nye vychislitel'nye sistemy i tekhnologii = High Performance Computing Systems and Technologies, 2019, vol. 3, no. 1, pp. 101-106 (In Russ.). https://www.elibrary.ru/item.asp?id=39242603.