Статья

Название статьи ПРИМЕНЕНИЕ ПЧЕЛИНОГО АЛГОРИТМА ДЛЯ РАСКРАСКИ ГРАФОВ
Автор В.М. Курейчик, А.А. Кажаров
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 12, 2010
Индекс УДК 681.3
DOI
Аннотация Работа посвящена решению NP-трудной графовой задачи о раскраске. Предлагается решить проблему на подходе, основанном на роевом интеллекте – пчелиный алгоритм. Основная идея алгоритма – моделирование естественного роя пчел. Разработана программная среда, реализующая предложенный алгоритм, а также другие методы для сравнений. Экспериментальные исследования доказали эффективность пчелиного алгоритма при решении задачи о раскраске. Приемлемое решение для графов размерностью до 200 вершин находится в течение нескольких секунд на ЭВМ с тактовой частотой 2.5 ГГц.

Скачать в PDF

Ключевые слова Пчелиные алгоритмы; роевой интеллект; задача раскраски; NP-задача; графовая задача.
Библиографический список 1. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Изд-во «Мир», 1978.
2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика: Теория графов. –- Таганрог: Изд-во ТТИ ЮФУ, 2010. – 162 с.
3. Курейчик В.М. Биоинспирированный поиск с использованием сценарного подхода // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – С. 7-12.
4. Кажаров А.А. Решение задачи разбиения графа на основе биоинспирированных алгоритмов // Труды международных научно-технических конференций «Интеллектуальные системы» (AIS’10) и «Интеллектуальные САПР». – М.: ФИЗМАТЛИТ, 2010.
5. Субботин С.А., Олейник Ан.А., Олейник Ал.А. PSO-метод // Интеллектуальные мультиагентные методы (Swarm Intelligence). – 2006. – № 3. – C. 55-70.
6. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчѐл // Известия ЮФУ. Технические науки. – 2009. – 12 (101). – С. 41-46.
7. Cormen T., Leiserson Ch., Rivest R., Stein C. Introductin to algorithms. Second edition. The MIT Press edition, Cambridge, Massachusetts, London, England, 2002.
8. Кирсанов М.Н. Графы в Mapple. Задачи, алгоритмы, программы. – М: ФИЗМАТЛИТ, 2007.
9. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. – Ростов-на-Дону: ООО «Ростиздат», 2004.
10. Holland John H. Adaptation in natural an artificial systems. The MIT Press edition, Massachusetts, London, England, 1992.
11. Курейчик В.М., Курейчик В.В., Родзин С.И. Концепции эволюционных вычислений, инспирированных природными системами // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 16-24.

Comments are closed.