Experimental Evaluation of Artificial Bee Colony with Greedy Scouts for Constraint Satisfaction Problems
Yuko Aratsu, Kazunori Mizuno, Hitoshi Sasaki, Seiichi Nishihara · 2013
In this paper, we propose the artificial bee colony algorithm for solving large-scale and hard constraint satisfaction problems (CSPs). Our algorithm is based on the DisABC algorithm which is particularly designed for binary optimization. In our algorithm, two main improvements are adopted: (1) a hybrid algorithm with greedy local search technique, called GSAT is combined and (2) in the scout bee phase, greedy scout bees are introduced, where bees construct new candidate solutions by using a partial assignment of the best solution probabilistically. We demonstrate that our algorithm can be effective for the hard instance which are concentrated in the phase transition and we also discuss that the search performance is varied by difference of the proportion of using partial assignments of the best solution.