Bees swarm optimization metaheuristic guided by decomposition for solving MAX-SAT
Auteurs
Y. Djenouri, Z. Habbas, and W. Aggoune-Mtalaa
Référence
in 8th International Conference on Agents and Artificial Intelligence (ICAART 2016), 24-26 February 2016, Rome, Italy, pp. 472-479, 2016
Description
Decomposition methods aim to split a problem into a collection a collection of smaller interconnected sub-problems. Several research works have explored decomposition methods for solving large optimization problems. Due to its theroretical properties, Tree decomposition has been especially the subject of numerous successfull studies in the context of exact optimization solvers. More recently, Tree decomposition has been successfully used to guide the Variable Neighbor Search (VNS) local search method. Our present contribution follows this last direction and proposes two approaches called BSOGD1 and BSOGD2 for guiding the Bees Swarm Optimization (BSO) metaheuristic by using a decomposition method. More pragmatically, this paper deals with the MAX-SAT problem and uses the Kmeans algorithm as a decomposition method. Several experimental results conducted on DIMACS benchmarks and some other hard SAT instances lead to promising results in terms of the quality of the solutions. Moreover, th ese experiments highlight a good stability of the two approaches, more especially, when dealing with hard instances like the Parity8 family from DIMACS. Beyond these first promising results, note that this approach can be easily applied to many other optimization problems such as the Weighted MAX-SAT, the MAX-CSP or the coloring problem and can be used with other decomposition methods as well as other metaheuristics.
