Abstract— We present in this paper a new memetic algorithm to deal with the Max Sat problem. The objective is to find the best assignment for a set of Boolean variables, which gives the maximum of verified clauses in a Boolean formula. Unfortunately, this problem has been shown to be NP-hard if the number of variables per clause is greater than 3. The proposed approach is based on clonal selection principles and local search method. In order to increase the performance of clonal selection to deal with Max Sat problem, an adaptive fitness function based on weighted clauses has been used. The underlying idea is to harness the optimization capabilities of clonal selection algorithm to achieve good quality solutions for Max SAT problem. A local search based on Tabu Search has been embodied in the clonal selection algorithm leading to an efficient hybrid framework which achieves better balance between exploration and exploitation capabilities of the search process. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed hybrid approach.

Index Terms—Maximum Satisfiabilty problem, Artificial Immune System, Clonal Selection, Tabu Search.

Cite: Abdesslem Layeb, "A Clonal Selection Algorithm Based Tabu Search for Satisfiability Problems," Journal of Advances in Information Technology, Vol. 3, No. 2, pp. 138-146, May, 2012.doi:10.4304/jait.3.2.138-146