Пшеничных Александр Олегович, магистрант кафедры вычислительной техники
ул. 50 лет Октября 94, г. Курск 305040
Pshenichnykh O. Aleksandr, Master Student of Computing Techniques Department
50 Let Oktyabrya str. 94, Kursk 305040
Ватутин Эдуард Игоревич, кандидат технических наук, доцент, доцент кафедры вычислительной техники
ул. 50 лет Октября 94, г. Курск 305040
Researcher ID: C-9412-2017
Vatutin I. Eduard, Cand. of Sci. (Engineering), Associate Professor, Associate Professor of the Computing Techniques Department
50 Let Oktyabrya str. 94, Kursk 305040
Цель исследования. Обнаружен большой спектр задач, которые важны на практике и которые могут быть сведены за полиномиальное время к задачам дискретной комбинаторной оптимизации, многие из которых допускают решение с применением теории графов. Одна из таких задач – отыскание хроматического числа графа и соответствующей ему раскраски. Учитывая факт того, что комбинаторная задача отыскания хроматического числа графа относится к классу сложности NP и не допускает получения оптимального решения за рациональное время для задач практически важной размерности, то поиск подходящего эвристического метода, позволяющего получать решения высокого качества с низкими затратами, необходимыми для вычисления, является востребованным и актуальным. Целью проведённого исследования является анализ результатов использования метода пчелиной колонии в поставленной задаче. Задачами описываемой работы являются: описание алгоритмических приёмов в формализованной форме, которые дают возможность применить метод пчелиной колонии в решаемой задаче, внесение модификаций в метод пчелиной колонии, повышающих эффективность применения метода, а именно качество получаемых итоговых раскрасок, а также определение факторов, влияющих на качество и временные затраты при нахождении решений. Методы. Для проведения исследования в выбранной области были организованы вычислительные эксперименты, базирующиеся на применении эвристических методов в рассматриваемой задаче. Была проведена метаоптимизация настроечных параметров методов и определение их скорости сходимости, а также выполнено сравнение качества и времени получения решений. Результаты. В результате проведённого исследования была выявлена скорость сходимости метода большая, чем у метода случайных блужданий, обнаружена зависимость качества получаемых итоговых раскрасок от размера графа N и плотности d. Было установлено, что выбранный метод является более быстрым относительно метода взвешенного случайного перебора с вариацией вершин по минимуму допустимых цветов на »67%, который на текущий момент формирует решения с самым низким хроматическим числом, при этом проигрывая ему в качестве на »7%. Замечена более высокая скорость сходимости при сравнении с методом случайных блужданий, принцип работы которого совпадает с пчёлами-фуражирами. Заключение. Обнаружено, что метод пчелиной колонии находит раскраски с аналогичным усреднённым хроматическим числом за меньшее число итераций, чем метод случайных блужданий, т.е. обладает более высокой скоростью сходимости, при этом оставаясь значительно быстрым относительно метода случайного перебора с вариацией вершин по уменьшению допустимых цветов.
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.
The authors declare that there are no conflicts of interest present.