Title: How can bees colour graphs

Authors: Malika Bessedik, Bouakline Toufik, Habiba Drias

Addresses: Laboratoire des Methodes de Conception de Systemes (LMCS), E.S.I ex I.N.I., BP 68M Oued Smar 16309, Alger, Algerie. ' Institut National d'Informatique, E.S.I ex I.N.I., BP 68M Oued Smar 16309, Alger, Algerie. ' Laboratoire de Recherche en Intelligence Artificielle, Dept. d'Informatique, USTHB University, Alger, Algerie

Abstract: Marriage in honey bees optimisation (MBO) is a recent evolutionary metaheuristic inspired by the bees reproduction process. Contrary to most of swarm intelligence algorithms such as ant colony optimisation (ACO), MBO uses self-organisation to mix different heuristics. In this paper, we present an MBO approach for the graph colouring problem (GCP). We propose, as worker, in our algorithm (BeesCol) one of the following methods: local search, taboo search or a proposed-based ant colony system algorithm (IACSCol). The worker intervenes at two levels; it improves initial and crossed solutions. Moreover, in BeesCol, one or several queens are generated randomly or by a specific constructive method, namely, recursive largest first or DSATUR. Experimental results on some well studied Dimacs graphs are reported. A comparison between BeesCol and some best-known algorithms for the GCP (hybrid colouring algorithm HCA, ant system and ant colony system) shows that the use of taboo search as worker in BeesCol reached most of best known results.

Keywords: graph colouring problem; GCP; metaheuristics; marriage in honey bees optimisation; MBO; ant colony optimisation; ACO; tabu search; hybrid colouring algorithm; HCA; DSATUR; RLF; self-organisation; swarm intelligence.

DOI: 10.1504/IJBIC.2011.038705

International Journal of Bio-Inspired Computation, 2011 Vol.3 No.1, pp.67 - 76

Available online: 23 Feb 2011 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article