How can bees colour graphs

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.