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