Solving Constraint Satisfaction Problems by Artificial Bee Colony with Greedy Scouts
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 algo- rithm is based on the DisABC algorithm which is proposed to solve binary optimization. In our al- gorithm, two main improvements are adopted: (1) to supplement low local search ability of the ABC, 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 per- formance is varied by difference of the proportion of using partial assignments of the best solution.