Abstract: For SAT problem， a discrete artificial bee colony algorithm named ABCSAT algorithm was proposed. The corresponding optimization model was established， and the key issues such as problem encoding and transition， fitness function， bee’s foraging strategy， discrete operation etc. were solved. Different from dealing with continual optimization problem， fitness function was defined as the number of unsatisfied clauses in the ABCSAT algorithm. According the character of SAT problem， series of foraging strategy were designed and discrete operations on candidate solutions were performed by using the heuristic information of constraint relations among each clause and variable. Through experiments on the standard SATLIB benchmarks， the algorithm was tested and compared with related algorithms. The results validated the effectiveness of ABCSAT algorithm on middle/smallscale SAT problems， and showed that the algorithm could be more effectively on solving this problem.

Key words: SAT, artificial bee colony algorithm, genetic algorithm, swarm intelligence, heuristic strategy