Orthogonal Quantum Immune Clone Algorithm For The SAT Problem

The study of SAT problem is of great significance in both theory and application. Researching on the methods for solving the SAT problem divided into below categories: complete algorithm and incomplete algorithm. Because of this problem is a NP complete problem, so its computational complexity is exponential. This is the reason why its solution efficiency cannot meet the requirements. Although incomplete algorithms can not always find the solution, but it have highly solution efficiency and it can be able to meet the demand. Hence, the incomplete algorithm gradually becomes a hot research topic for solving the SAT problem.This paper aims to study the incomplete algorithm for solving the SAT problem. The basic concepts of common incomplete algorithm (Quantum immune clone algorithm, quantum evolutionary algorithm and orthogonality of algorithm) and their extended algorithm were reviewed. The advantages of the aforementioned algorithms were analyzed and new ideas for solving SAT problems are proposed based on orthogonal simplification and attribute determination.Based on the researching of quantum immune clone algorithm and the orthogonality of the SAT problem, a new SAT problem solving algorithm is explored in the third chapter. This algorithm combines quantum immune clone algorithm with orthogonality of orthogonal quantum immune algorithm. Firstly, equivalent transformation of SAT problem is obtained by orthogonalization process. The overlapping information between clauses is eliminated; besides, the attributes of SAT problem is also determined. If the SAT problem is a satistiability problem, then the satisfied solution is obtained by quantum algorithms based on orthogonal clause group. Finally, this study obtain that the optimal solution for OQICA convergence with probability one. The experimental results show that this method has higher success rate than the genetic algorithm and the quantum immune clone algorithm.