Article

Article title GRAPH COLORING SOLUTION BASED ON BEE COLONY OPTIMIZATION
Authors V.M. Kureichik, A.A. Kazharov
Section SECTION I. EVOLUTIONARY MODELLING, GENETIC AND BIONIC ALGORITHMS
Month, Year 12, 2010 @en
Index UDC 681.3
DOI
Abstract This paper is dedicated to the solving of NP-complete task – graph coloring problem. It is proposed to solve the problem on the approach based on Swarm Intelligence – bee algorithm. The main idea of the algorithm – modeling of natural swarm of bees. A software environment that implements the proposed algorithm, as well as other methods for comparison. Experimental studies have proven the effectiveness of bee algorithm for solving the problem of coloring. An acceptable solution is found for 200-vertexes graph within a few seconds on modern computers.

Download PDF

Keywords Bee Colony Algorithms; swarm intelligence; the problem of graph coloring; NP task; graph problem.
References 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.