Effects of Different Worker Heuristics in Marriage in Honey Bees Optimization : As Applied to the Graph Coloring Problem

Sammanfattning: Marriage in Honey Bees Optimization (MBO) is an interesting meta-heuristic inspired by the mating process of honey bees, where worker bees are collectively responsible for raising the next generation of the colony. In MBO, worker bees are represented by heuristics that are used to navigate the search space. This thesis investigates the effects of three worker heuristics in different combinations, in an implementation of MBO applied to the Graph Coloring Problem (GCP). GCP was chosen due to its application to real life problems, for instance scheduling. The worker heuristics included were a greedy algorithm, GREEDYRECOLOR, and the two tabu searches PARTIALCOL and TABUCOL. The different combinations were tested on known GCP benchmarks. MBO was found to utilize the strengths of each worker available where needed. Including GREEDYRECOLOR was not useful on average. PARTIALCOL was found to be the best overall worker. However, there were indications that using both PARTIALCOL and TABUCOL might be beneficial.