Academic Journals Database
Disseminating quality controlled scientific knowledge

A Clonal Selection Algorithm Based Tabu Search for Satisfiability Problems

Author(s): Abdesslem Layeb

Journal: Journal of Advances in Information Technology
ISSN 1798-2340

Volume: 3;
Issue: 2;
Start page: 138;
Date: 2012;
Original page

Keywords: Maximum Satisfiabilty problem | Artificial Immune System | Clonal Selection | Tabu Search

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.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions