Анализ результатов применения метода пчелиной колонии в задаче раскраски графов общего вида

Цель исследования. Обнаружен большой спектр задач, которые важны на практике и которые могут быть сведены за полиномиальное время к задачам дискретной комбинаторной оптимизации, многие из которых допускают решение с применением теории графов. Одна из таких задач – отыскание хроматического числа графа и соответствующей ему раскраски. Учитывая факт того, что комбинаторная задача отыскания хроматического числа графа относится к классу сложности NP и не допускает получения оптимального решения за рациональное время для задач практически важной размерности, то поиск подходящего эвристического метода, позволяющего получать решения высокого качества с низкими затратами, необходимыми для вычисления, является востребованным и актуальным. Целью проведённого исследования является анализ результатов использования метода пчелиной колонии в поставленной задаче. Задачами описываемой работы являются: описание алгоритмических приёмов в формализованной форме, которые дают возможность применить метод пчелиной колонии в решаемой задаче, внесение модификаций в метод пчелиной колонии, повышающих эффективность применения метода, а именно качество получаемых итоговых раскрасок, а также определение факторов, влияющих на качество и временные затраты при нахождении решений.
Методы. Для проведения исследования в выбранной области были организованы вычислительные эксперименты, базирующиеся на применении эвристических методов в рассматриваемой задаче. Была проведена метаоптимизация настроечных параметров методов и определение их скорости сходимости, а также выполнено сравнение качества и времени получения решений.
Результаты. В результате проведённого исследования была выявлена скорость сходимости метода большая, чем у метода случайных блужданий, обнаружена зависимость качества получаемых итоговых раскрасок от размера графа N и плотности d. Было установлено, что выбранный метод является более быстрым относительно метода взвешенного случайного перебора с вариацией вершин по минимуму допустимых цветов на »67%, который на текущий момент формирует решения с самым низким хроматическим числом, при этом проигрывая ему в качестве на »7%. Замечена более высокая скорость сходимости при сравнении с методом случайных блужданий, принцип работы которого совпадает с пчёлами-фуражирами.
Заключение. Обнаружено, что метод пчелиной колонии находит раскраски с аналогичным усреднённым хроматическим числом за меньшее число итераций, чем метод случайных блужданий, т.е. обладает более высокой скоростью сходимости, при этом оставаясь значительно быстрым относительно метода случайного перебора с вариацией вершин по уменьшению допустимых цветов.

1. Закревский А.Д., Поттосин Ю.В. Декомпозиция параллельных алгоритмов логического управления по заданному разбиению множества предложений // А и ВТ. 1985. № 4. С. 65-72.

2. Register allocation via coloring / Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, Peter W. Markstein // Computer Languages. 1981. P. 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. Филоненко И.Н., Чеботарев М.В. Алгоритм раскраски графа и его применение в области компьютерных сетей // Техника и технологии, политика и экономика: проблемы и перспективы. Коломна, 2018. С. 162-168. URL: https://www.elibrary.ru/item.asp?id=35587418.

5. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Биоинспирированный алгоритм компоновки блоков ЭВА на основе модифицированной раскраски графа // Известия Южного федерального университета. 2015. № 4 (165). С. 6-14. URL: https://www.elibrary.ru/item.asp?id=23693391.

6. Применение алгоритма последовательной раскраски графа в сотовой сети / Д.Э. Мурзаков, М.А. Зенков, А.Д. Жуков, В.В. Тишин // Естественные и математические науки в современном мире. 2015. № 31. С. 22-32. URL: https://www.elibrary.ru/item.asp?id=23570102.

7. Решение задачи раскраски взвешенного графа для мягкого распределения ресурса пропускной способности в сетях беспроводного абонентского доступа / В.И. Калюка, С.А. Остапенко, В.Г. Кобак, В.В. Зубакин, И.В. Морозов // Известия высших учебных заведений. Северокавказский регион. Технические науки. 2015. № 4 (185). С. 3-8. https://doi.org/10.17213/0321-2653-2015-4-3-8.

8. Макошенко Д.В. Назначение переменных на регистры с помощью древовидного параметрического алгоритма раскраски графа // Информационные технологии. 2010. № 6. С. 41-46. URL: 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. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982. 416 с. URL: 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. 2008. Vol. 107. Iss. 2. P. 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. URL: https://abc.erciyes.edu.tr/pub/tr06_2005.pdf.

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

14. Ватутин Э.И., Титов В.С., Емельянов С.Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с. URL: https://www.elibrary.ru/item.asp?id=25770934.

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

16. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновлённые природой. М.: МГТУ им. Н.Э. Баумана, 2014. 446 с. URL: 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. P. 147-160. https://doi.org/10.1002/j.1538-7305.1950.tb00463.x.

18. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады академий наук СССР. 1965. Т. 163. Вып. 4. С. 845-848. URL: http://mi.mathnet.ru/dan31411.

19. Ватутин Э.И., Титов В.С. Особенности метаоптимизации алгоритма пчелиной колонии в задаче поиска кратчайшего пути в графе при наличии ограничений на плотность графа // Известия Юго-Западного государственного университета. 2016. № 2 (19). С. 52-65. URL: https://www.elibrary.ru/item.asp?id=26396211.

20. Пшеничных О., Гвоздева С.Н., Ватутин Э.И. О влиянии порядка рассмотрения вершин при поиске раскрасок графов общего вида с использованием жадного алгоритма // Высокопроизводительные вычислительные системы и технологии. 2019. Т. 3. № 1. С. 101-106. URL: https://www.elibrary.ru/item.asp?id=39242603.