Генетичний алгоритм розфарбування графу

Розфарбування графа в мінімальну кількість кольорів є комбінаторною задачею , яку відносять до класу NP-складних задач. Ця задача може бути сформульоване як рекурентне завдання розфарбування графа в мінімальну кількість кольорів. Спочатку задається певне число кольорів, (обґрунтоване з точки зору можливості розфарбування, тобто з відповідним хроматичним числом), а пізніше виконується алгоритм з подальшим зменшенням їх кількості.

Проблемами цієї задачі є швидкість знаходження розв’язку, а також точність розв’язання.

Результати тестувань генетичного алгоритму на складних графах (700-1000) вершин показали, що використання Tabu Search (метаевристика – назва для стохастичних алгоритмів які використовують випадковий пошук, або пошук перебором, шлях вирішення цих задач) та певного кодування істотно покращують виконання генитичного алгоритму розфарбування графа.

2.6 Алгоритм мурашиної колонії для розфарбування графів

Цей алгоритм використовується для стійкого розфарбування і є NP-складною задаче комбінаторної оптимізації. Розв’язувати цю задачу краще за допомогою метаевристичних.

Даний алгоритм був запропонований М.Доріго у 1992 році. В ідеї алгоритму лежить здатність колонії мурах знаходити найкоротший шлях між мурашником та їжею. Кожна мураха залишає за собою слід секрету(феромонів) і, рухаючись в навколишньому середовищі, намагається дотримуватися стежок із секрету, що залишили інші мурахи. Чим більше мурах проходить цією дорогою, тим більше секретів залишається, тож імовірність що мураха вибере саме цей шлях значно зростає. Алгоритм уникає локальних мінімумів.

Стежини по яких рухаються мурахи можна представити у вигляді ребра графа, що має назву конструкційного. Кожне ребро має свою вагу – час проходження шляху. Мурахи повинні знайти найкоротший шлях між вершинами (мурашником та їжею). Розробка будь-якого алгоритму мурашиної колонії розпочинається з визначення будови конструкційного графу.

Суть полягає в тому, що вершина в графі буде обрана лише один раз, обхід вершин, забезпечує їх розфарбування, при цьому враховується вага ребер, тобто найкоротший шлях до вершини.

Алгоритм ефективно розв’язує задачі з графами до 50 вершин включно. На більших графах більш відоміші алгоритми показують кращий час виконання та якості. Подальші дослідження алгоритму передбачають оптимізацію знаходження ваги ребер і визначення оптимальних складових переходу мурахи до наступної вершини конструкційного графу.

2.7 Практичне застосування розфарбування графів