|
|
 |
| |
|
|
|
A Hybrid Quantum Genetic Algorithm and Local Search based DPLL for Max 3-SAT Problems |
|
|
|
PP: 77-87 |
|
|
|
Author(s) |
|
|
|
Abdesslem Layeb,
Djamel-Eddine Saidouni,
|
|
|
|
Abstract |
|
|
| In this paper, we present a new framework for combining complete and incomplete methods in order 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 (non-deterministic polynomial-time hard) if the number
of variables per clause is greater than 3. The proposed approach is based on quantum inspired genetic principles and the well known
exact algorithm DPLL. The underlying idea is to harness the optimization capabilities of quantum genetic algorithm to achieve good
quality solutions for Max SAT problem. A new local search based on DPLL algorithm has been embodied in the quantum genetic
algorithm leading to an efficient hybrid framework which achieves better balance between diversification and intensification search.
The obtained results are very encouraging and show the feasibility and effectiveness of the proposed hybrid approach. |
|
|
|
|
|
|
|
